value_set.cc
Go to the documentation of this file.
00001 #include <ruby.h>
00002 #include <set>
00003 #include <algorithm>
00004 
00005 using namespace std;
00006 
00007 static VALUE cValueSet;
00008 static ID id_new;
00009 
00010 typedef std::set<VALUE> ValueSet;
00011 static ValueSet& get_wrapped_set(VALUE self)
00012 {
00013     ValueSet* object = 0;
00014     Data_Get_Struct(self, ValueSet, object);
00015     return *object;
00016 }
00017 
00018 static void value_set_mark(ValueSet const* set) { std::for_each(set->begin(), set->end(), rb_gc_mark); }
00019 static void value_set_free(ValueSet const* set) { delete set; }
00020 static VALUE value_set_alloc(VALUE klass)
00021 {
00022     ValueSet* cxx_set = new ValueSet;
00023     return Data_Wrap_Struct(klass, value_set_mark, value_set_free, cxx_set);
00024 }
00025 /* call-seq:
00026  *  set.empty?                      => true or false
00027  *
00028  * Checks if this set is empty
00029  */
00030 static VALUE value_set_empty_p(VALUE self)
00031 { 
00032     ValueSet& set = get_wrapped_set(self);
00033     return set.empty() ? Qtrue : Qfalse;
00034 }
00035 
00036 /* call-seq:
00037  *  set.size                        => size
00038  *
00039  * Returns this set size
00040  */
00041 static VALUE value_set_size(VALUE self)
00042 { 
00043     ValueSet& set = get_wrapped_set(self);
00044     return INT2NUM(set.size());
00045 }
00046 
00047 
00048 /* call-seq:
00049  *  set.each { |obj| ... }          => set
00050  *
00051  */
00052 static VALUE value_set_each(VALUE self)
00053 {
00054     ValueSet& set = get_wrapped_set(self);
00055     for (ValueSet::iterator it = set.begin(); it != set.end();)
00056     {
00057         // Increment before calling yield() so that 
00058         // the current element can be deleted safely
00059         ValueSet::iterator this_it = it++;
00060         rb_yield(*this_it);
00061     }
00062     return self;
00063 }
00064 
00065 /* call-seq:
00066  *  set.delete_if { |obj| ... }         => set
00067  *
00068  * Deletes all objects for which the block returns true
00069  */
00070 static VALUE value_set_delete_if(VALUE self)
00071 {
00072     ValueSet& set = get_wrapped_set(self);
00073     for (ValueSet::iterator it = set.begin(); it != set.end();)
00074     {
00075         // Increment before calling yield() so that 
00076         // the current element can be deleted safely
00077         ValueSet::iterator this_it = it++;
00078         bool do_delete = RTEST(rb_yield(*this_it));
00079         if (do_delete)
00080             set.erase(this_it);
00081     }
00082     return self;
00083 }
00084 
00085 /* call-seq:
00086  *  set.include?(value)     => true or false
00087  *
00088  * Checks if +value+ is in +set+
00089  */
00090 static VALUE value_set_include_p(VALUE vself, VALUE vother)
00091 {
00092     ValueSet const& self  = get_wrapped_set(vself);
00093     return self.find(vother) == self.end() ? Qfalse : Qtrue;
00094 }
00095 
00096 /* call-seq:
00097  *  set.to_value_set                => set
00098  */
00099 static VALUE value_set_to_value_set(VALUE self) { return self; }
00100 
00101 /* call-seq:
00102  *  set.dup => other_set
00103  *
00104  * Duplicates this set, without duplicating the pointed-to objects
00105  */
00106 static VALUE value_set_dup(VALUE vself, VALUE vother)
00107 {
00108     ValueSet const& self  = get_wrapped_set(vself);
00109     VALUE vresult = rb_funcall2(cValueSet, id_new, 0, NULL);
00110     ValueSet& result = get_wrapped_set(vresult);
00111     for (ValueSet::const_iterator it = self.begin(); it != self.end(); ++it)
00112         result.insert(result.end(), *it);
00113 
00114     return vresult;
00115 }
00116 
00117 /* call-seq:
00118  *  set.include_all?(other)             => true or false
00119  *
00120  * Checks if all elements of +other+ are in +set+
00121  */
00122 static VALUE value_set_include_all_p(VALUE vself, VALUE vother)
00123 {
00124     ValueSet const& self  = get_wrapped_set(vself);
00125     if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
00126         rb_raise(rb_eArgError, "expected a ValueSet");
00127     ValueSet const& other = get_wrapped_set(vother);
00128     return std::includes(self.begin(), self.end(), other.begin(), other.end()) ? Qtrue : Qfalse;
00129 }
00130 
00131 /* call-seq:
00132  *  set.union(other)            => union_set
00133  *  set | other                 => union_set
00134  *
00135  * Computes the union of +set+ and +other+. This operation is O(N + M)
00136  * is +other+ is a ValueSet
00137  */
00138 static VALUE value_set_union(VALUE vself, VALUE vother)
00139 {
00140     ValueSet const& self  = get_wrapped_set(vself);
00141     if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
00142         rb_raise(rb_eArgError, "expected a ValueSet");
00143     ValueSet const& other = get_wrapped_set(vother);
00144     
00145     VALUE vresult = rb_funcall2(cValueSet, id_new, 0, NULL);
00146     ValueSet& result = get_wrapped_set(vresult);
00147     std::set_union(self.begin(), self.end(), other.begin(), other.end(), 
00148             std::inserter(result, result.end()));
00149     return vresult;
00150 }
00151 
00152 /* call-seq:
00153  *  set.merge(other)            => set
00154  *
00155  * Merges the elements of +other+ into +self+. If +other+ is a ValueSet, the operation is O(N + M)
00156  */
00157 static VALUE value_set_merge(VALUE vself, VALUE vother)
00158 {
00159     ValueSet& self  = get_wrapped_set(vself);
00160     if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
00161         rb_raise(rb_eArgError, "expected a ValueSet");
00162     ValueSet const& other = get_wrapped_set(vother);
00163     
00164     self.insert(other.begin(), other.end());
00165     return vself;
00166 }
00167 
00168 /* call-seq:
00169  *   set.intersection!(other)   => set
00170  *
00171  * Computes the intersection of +set+ and +other+, and modifies +self+ to be
00172  * that interesection. This operation is O(N + M) if +other+ is a ValueSet
00173  */
00174 static VALUE value_set_intersection_bang(VALUE vself, VALUE vother)
00175 {
00176     ValueSet& self  = get_wrapped_set(vself);
00177     if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
00178         rb_raise(rb_eArgError, "expected a ValueSet");
00179     ValueSet const& other = get_wrapped_set(vother);
00180     
00181     ValueSet result;
00182     std::set_intersection(self.begin(), self.end(), other.begin(), other.end(), 
00183             std::inserter(result, result.end()));
00184     self.swap(result);
00185     return vself;
00186 }
00187 
00188 /* call-seq:
00189  *   set.intersection(other)    => intersection_set
00190  *   set & other                => intersection_set
00191  *
00192  * Computes the intersection of +set+ and +other+. This operation
00193  * is O(N + M) if +other+ is a ValueSet
00194  */
00195 static VALUE value_set_intersection(VALUE vself, VALUE vother)
00196 {
00197     ValueSet const& self  = get_wrapped_set(vself);
00198     if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
00199         rb_raise(rb_eArgError, "expected a ValueSet");
00200     ValueSet const& other = get_wrapped_set(vother);
00201     
00202     VALUE vresult = rb_funcall2(cValueSet, id_new, 0, NULL);
00203     ValueSet& result = get_wrapped_set(vresult);
00204     std::set_intersection(self.begin(), self.end(), other.begin(), other.end(), 
00205             std::inserter(result, result.end()));
00206     return vresult;
00207 }
00208 
00209 /* call-seq:
00210  *  set.intersects?(other)      => true or false
00211  *
00212  * Returns true if there is elements in +set+ that are also in +other
00213  */
00214 static VALUE value_set_intersects(VALUE vself, VALUE vother)
00215 {
00216     ValueSet const& self  = get_wrapped_set(vself);
00217     if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
00218         rb_raise(rb_eArgError, "expected a ValueSet");
00219     ValueSet const& other = get_wrapped_set(vother);
00220 
00221     ValueSet::const_iterator 
00222         self_it   = self.begin(),
00223         self_end  = self.end(),
00224         other_it  = other.begin(),
00225         other_end = other.end();
00226 
00227     while(self_it != self_end && other_it != other_end)
00228     {
00229         if (*self_it < *other_it)
00230             ++self_it;
00231         else if (*other_it < *self_it)
00232             ++other_it;
00233         else
00234             return Qtrue;
00235     }
00236     return Qfalse;
00237 }
00238 
00239 /* call-seq:
00240  *   set.difference!(other)     => set
00241  *
00242  * Modifies +set+ so that it is the set of all elements of +set+ not in +other+.
00243  * This operation is O(N + M).
00244  */
00245 static VALUE value_set_difference_bang(VALUE vself, VALUE vother)
00246 {
00247     ValueSet& self  = get_wrapped_set(vself);
00248     if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
00249         rb_raise(rb_eArgError, "expected a ValueSet");
00250     ValueSet const& other = get_wrapped_set(vother);
00251     
00252     ValueSet result;
00253     std::set_difference(self.begin(), self.end(), other.begin(), other.end(), 
00254             std::inserter(result, result.end()));
00255     self.swap(result);
00256     return vself;
00257 }
00258 
00259 /* call-seq:
00260  *   set.difference(other)      => difference_set
00261  *   set - other                => difference_set
00262  *
00263  * Computes the set of all elements of +set+ not in +other+. This operation
00264  * is O(N + M).
00265  */
00266 static VALUE value_set_difference(VALUE vself, VALUE vother)
00267 {
00268     ValueSet const& self  = get_wrapped_set(vself);
00269     if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
00270         rb_raise(rb_eArgError, "expected a ValueSet");
00271     ValueSet const& other = get_wrapped_set(vother);
00272     
00273     VALUE vresult = rb_funcall2(cValueSet, id_new, 0, NULL);
00274     ValueSet& result = get_wrapped_set(vresult);
00275     std::set_difference(self.begin(), self.end(), other.begin(), other.end(), 
00276             std::inserter(result, result.end()));
00277     return vresult;
00278 }
00279 
00280 /* call-seq:
00281  *  set.insert(value)           => true or false
00282  * 
00283  * Inserts +value+ into +set+. Returns true if the value did not exist
00284  * in the set yet (it has actually been inserted), and false otherwise.
00285  * This operation is O(log N)
00286  */
00287 static VALUE value_set_insert(VALUE vself, VALUE v)
00288 {
00289     ValueSet& self  = get_wrapped_set(vself);
00290     bool exists = self.insert(v).second;
00291     return exists ? Qtrue : Qfalse;
00292 }
00293 /* call-seq:
00294  *  set.delete(value)           => true or false
00295  * 
00296  * Removes +value+ from +set+. Returns true if the value did exist
00297  * in the set yet (it has actually been removed), and false otherwise.
00298  */
00299 static VALUE value_set_delete(VALUE vself, VALUE v)
00300 {
00301     ValueSet& self  = get_wrapped_set(vself);
00302     size_t count = self.erase(v);
00303     return count > 0 ? Qtrue : Qfalse;
00304 }
00305 
00306 /* call-seq:
00307  *  set == other                => true or false
00308  *
00309  * Equality
00310  */
00311 static VALUE value_set_equal(VALUE vself, VALUE vother)
00312 {
00313     ValueSet const& self  = get_wrapped_set(vself);
00314     if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
00315         return Qfalse;
00316     ValueSet const& other = get_wrapped_set(vother);
00317     return (self == other) ? Qtrue : Qfalse;
00318 }
00319 
00320 /* call-seq:
00321  *  set.clear                   => set
00322  *
00323  * Remove all elements of this set
00324  */
00325 static VALUE value_set_clear(VALUE self)
00326 {
00327     get_wrapped_set(self).clear();
00328     return self;
00329 }
00330 
00331 /* call-seq:
00332  *  set.initialize_copy(other)  => set
00333  *
00334  * Initializes +set+ with the values in +other+. Needed by #dup
00335  */
00336 static VALUE value_set_initialize_copy(VALUE vself, VALUE vother)
00337 {
00338     ValueSet const& other = get_wrapped_set(vother);
00339     set<VALUE> new_set(other.begin(), other.end());
00340     get_wrapped_set(vself).swap(new_set);
00341     return vself;
00342 }
00343 
00344 
00345 
00346 
00347 
00348 
00349 
00350 /* call-seq:
00351  *  to_value_set    => value_set
00352  *
00353  * Converts this array into a ValueSet object
00354  */
00355 static VALUE array_to_value_set(VALUE self)
00356 {
00357     VALUE vresult = rb_funcall2(cValueSet, id_new, 0, NULL);
00358     ValueSet& result = get_wrapped_set(vresult);
00359 
00360     long size  = RARRAY_LEN(self);
00361     for (int i = 0; i < size; ++i)
00362         result.insert(rb_ary_entry(self, i));
00363 
00364     return vresult;
00365 }
00366 
00367 #ifndef RUBINIUS
00368 static VALUE enumerable_to_value_set_i(VALUE i, VALUE* memo)
00369 {
00370     ValueSet& result = *reinterpret_cast<ValueSet*>(memo);
00371     result.insert(i);
00372     return Qnil;
00373 }
00374 
00375 /* call-seq:
00376  *  enum.to_value_set           => value_set
00377  *
00378  * Builds a ValueSet object from this enumerable
00379  */
00380 static VALUE enumerable_to_value_set(VALUE self)
00381 {
00382     VALUE vresult = rb_funcall2(cValueSet, id_new, 0, NULL);
00383     ValueSet& result = get_wrapped_set(vresult);
00384 
00385     rb_iterate(rb_each, self, RUBY_METHOD_FUNC(enumerable_to_value_set_i), reinterpret_cast<VALUE>(&result));
00386     return vresult;
00387 }
00388 #endif
00389 
00390 /*
00391  * Document-class: ValueSet
00392  *
00393  * ValueSet is a wrapper around the C++ set<> template. set<> is an ordered container,
00394  * for which union(), intersection() and difference() is done in linear time. For performance
00395  * reasons, in the case of ValueSet, the values are ordered by their VALUE, which roughly is
00396  * their object_id.
00397  */
00398 
00399 extern "C" void Init_value_set()
00400 {
00401 #ifndef RUBINIUS
00402     rb_define_method(rb_mEnumerable, "to_value_set", RUBY_METHOD_FUNC(enumerable_to_value_set), 0);
00403 #endif
00404     rb_define_method(rb_cArray, "to_value_set", RUBY_METHOD_FUNC(array_to_value_set), 0);
00405 
00406     cValueSet = rb_define_class("ValueSet", rb_cObject);
00407     id_new = rb_intern("new");
00408     rb_define_alloc_func(cValueSet, value_set_alloc);
00409     rb_define_method(cValueSet, "each", RUBY_METHOD_FUNC(value_set_each), 0);
00410     rb_define_method(cValueSet, "include?", RUBY_METHOD_FUNC(value_set_include_p), 1);
00411     rb_define_method(cValueSet, "include_all?", RUBY_METHOD_FUNC(value_set_include_all_p), 1);
00412     rb_define_method(cValueSet, "union", RUBY_METHOD_FUNC(value_set_union), 1);
00413     rb_define_method(cValueSet, "intersection", RUBY_METHOD_FUNC(value_set_intersection), 1);
00414     rb_define_method(cValueSet, "intersection!", RUBY_METHOD_FUNC(value_set_intersection_bang), 1);
00415     rb_define_method(cValueSet, "intersects?", RUBY_METHOD_FUNC(value_set_intersects), 1);
00416     rb_define_method(cValueSet, "difference", RUBY_METHOD_FUNC(value_set_difference), 1);
00417     rb_define_method(cValueSet, "difference!", RUBY_METHOD_FUNC(value_set_difference_bang), 1);
00418     rb_define_method(cValueSet, "insert", RUBY_METHOD_FUNC(value_set_insert), 1);
00419     rb_define_method(cValueSet, "merge", RUBY_METHOD_FUNC(value_set_merge), 1);
00420     rb_define_method(cValueSet, "delete", RUBY_METHOD_FUNC(value_set_delete), 1);
00421     rb_define_method(cValueSet, "==", RUBY_METHOD_FUNC(value_set_equal), 1);
00422     rb_define_method(cValueSet, "to_value_set", RUBY_METHOD_FUNC(value_set_to_value_set), 0);
00423     rb_define_method(cValueSet, "dup", RUBY_METHOD_FUNC(value_set_dup), 0);
00424     rb_define_method(cValueSet, "empty?", RUBY_METHOD_FUNC(value_set_empty_p), 0);
00425     rb_define_method(cValueSet, "size", RUBY_METHOD_FUNC(value_set_size), 0);
00426     rb_define_method(cValueSet, "clear", RUBY_METHOD_FUNC(value_set_clear), 0);
00427     rb_define_method(cValueSet, "initialize_copy", RUBY_METHOD_FUNC(value_set_initialize_copy), 1);
00428     rb_define_method(cValueSet, "delete_if", RUBY_METHOD_FUNC(value_set_delete_if), 0);
00429 }
00430 
00431 


utilrb
Author(s): Sylvain Joyeux/sylvain.joyeux@m4x.org
autogenerated on Thu Jan 2 2014 11:38:28