Class: ValueSet

Inherits:
Object show all
Defined in:
ext/utilrb/value_set.cc,
ext/utilrb/value_set.cc

Overview

ValueSet is a wrapper around the C++ set<> template. set<> is an ordered container, for which union(), intersection() and difference() is done in linear time. For performance reasons, in the case of ValueSet, the values are ordered by their VALUE, which roughly is their object_id.

Instance Method Summary collapse

Instance Method Details

#==(other = >true) ⇒ Object

Equality



313
314
315
316
317
318
319
320
 
# File 'ext/utilrb/value_set.cc', line 313

static VALUE value_set_equal(VALUE vself, VALUE vother)
{
    ValueSet const& self  = get_wrapped_set(vself);
    if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
  return Qfalse;
    ValueSet const& other = get_wrapped_set(vother);
    return (self == other) ? Qtrue : Qfalse;
}

#clear ⇒ Object

Remove all elements of this set



327
328
329
330
331
 
# File 'ext/utilrb/value_set.cc', line 327

static VALUE value_set_clear(VALUE self)
{
    get_wrapped_set(self).clear();
    return self;
}

#delete(value) ⇒ Object

Removes value from set. Returns true if the value did exist in the set yet (it has actually been removed), and false otherwise.



301
302
303
304
305
306
 
# File 'ext/utilrb/value_set.cc', line 301

static VALUE value_set_delete(VALUE vself, VALUE v)
{
    ValueSet& self  = get_wrapped_set(vself);
    size_t count = self.erase(v);
    return count > 0 ? Qtrue : Qfalse;
}

#delete_if ⇒ Object

Deletes all objects for which the block returns true



71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
# File 'ext/utilrb/value_set.cc', line 71

static VALUE value_set_delete_if(VALUE self)
{
    ValueSet& set = get_wrapped_set(self);
    for (ValueSet::iterator it = set.begin(); it != set.end();)
    {
  // Increment before calling yield() so that 
  // the current element can be deleted safely
  ValueSet::iterator this_it = it++;
  bool do_delete = RTEST(rb_yield(*this_it));
  if (do_delete)
      set.erase(this_it);
    }
    return self;
}

#difference(other) ⇒ Object #-(other = >difference_set) ⇒ Object

Computes the set of all elements of set not in other. This operation is O(N + M).



268
269
270
271
272
273
274
275
276
277
278
279
280
 
# File 'ext/utilrb/value_set.cc', line 268

static VALUE value_set_difference(VALUE vself, VALUE vother)
{
    ValueSet const& self  = get_wrapped_set(vself);
    if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
  rb_raise(rb_eArgError, "expected a ValueSet");
    ValueSet const& other = get_wrapped_set(vother);
    
    VALUE vresult = rb_funcall2(cValueSet, id_new, 0, NULL);
    ValueSet& result = get_wrapped_set(vresult);
    std::set_difference(self.begin(), self.end(), other.begin(), other.end(), 
      std::inserter(result, result.end()));
    return vresult;
}

#difference!(other) ⇒ Object

Modifies set so that it is the set of all elements of set not in other. This operation is O(N + M).



246
247
248
249
250
251
252
253
254
255
256
257
258
259
 
# File 'ext/utilrb/value_set.cc', line 246

static VALUE value_set_difference_bang(VALUE vself, VALUE vother)
{
    ValueSet& self  = get_wrapped_set(vself);
    if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
  rb_raise(rb_eArgError, "expected a ValueSet");
    ValueSet const& other = get_wrapped_set(vother);
    
    ValueSet result;
    std::set_difference(self.begin(), self.end(), other.begin(), other.end(), 
      std::inserter(result, result.end()));
    if (result.size() != self.size())
        self.swap(result);
    return vself;
}

#dup ⇒ Object

Duplicates this set, without duplicating the pointed-to objects



107
108
109
110
111
112
113
114
115
116
 
# File 'ext/utilrb/value_set.cc', line 107

static VALUE value_set_dup(VALUE vself, VALUE vother)
{
    ValueSet const& self  = get_wrapped_set(vself);
    VALUE vresult = rb_funcall2(cValueSet, id_new, 0, NULL);
    ValueSet& result = get_wrapped_set(vresult);
    for (ValueSet::const_iterator it = self.begin(); it != self.end(); ++it)
  result.insert(result.end(), *it);

    return vresult;
}

#each {|obj| ... } ⇒ Object

Yields:

  • (obj) 


53
54
55
56
57
58
59
60
61
62
63
64
 
# File 'ext/utilrb/value_set.cc', line 53

static VALUE value_set_each(VALUE self)
{
    ValueSet& set = get_wrapped_set(self);
    for (ValueSet::iterator it = set.begin(); it != set.end();)
    {
  // Increment before calling yield() so that 
  // the current element can be deleted safely
  ValueSet::iterator this_it = it++;
  rb_yield(*this_it);
    }
    return self;
}

#empty? ⇒ Boolean

Checks if this set is empty



31
32
33
34
35
 
# File 'ext/utilrb/value_set.cc', line 31

static VALUE value_set_empty_p(VALUE self)
{ 
    ValueSet& set = get_wrapped_set(self);
    return set.empty() ? Qtrue : Qfalse;
}

#include?(value) ⇒ Boolean

Checks if value is in set



91
92
93
94
95
 
# File 'ext/utilrb/value_set.cc', line 91

static VALUE value_set_include_p(VALUE vself, VALUE vother)
{
    ValueSet const& self  = get_wrapped_set(vself);
    return self.find(vother) == self.end() ? Qfalse : Qtrue;
}

#include_all?(other) ⇒ Boolean

Checks if all elements of other are in set



123
124
125
126
127
128
129
130
 
# File 'ext/utilrb/value_set.cc', line 123

static VALUE value_set_include_all_p(VALUE vself, VALUE vother)
{
    ValueSet const& self  = get_wrapped_set(vself);
    if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
  rb_raise(rb_eArgError, "expected a ValueSet");
    ValueSet const& other = get_wrapped_set(vother);
    return std::includes(self.begin(), self.end(), other.begin(), other.end()) ? Qtrue : Qfalse;
}

#initialize_copy(other) ⇒ Object

Initializes set with the values in other. Needed by #dup



338
339
340
341
342
 
# File 'ext/utilrb/value_set.cc', line 338

static VALUE value_set_initialize_copy(VALUE vself, VALUE vother)
{
    get_wrapped_set(vself) = get_wrapped_set(vother);
    return vself;
}

#insert(value) ⇒ Object

Inserts value into set. Returns true if the value did not exist in the set yet (it has actually been inserted), and false otherwise. This operation is O(log N)



289
290
291
292
293
294
 
# File 'ext/utilrb/value_set.cc', line 289

static VALUE value_set_insert(VALUE vself, VALUE v)
{
    ValueSet& self  = get_wrapped_set(vself);
    bool exists = self.insert(v).second;
    return exists ? Qtrue : Qfalse;
}

#intersection(other) ⇒ Object #&(other = >intersection_set) ⇒ Object

Computes the intersection of set and other. This operation is O(N + M) if other is a ValueSet



196
197
198
199
200
201
202
203
204
205
206
207
208
 
# File 'ext/utilrb/value_set.cc', line 196

static VALUE value_set_intersection(VALUE vself, VALUE vother)
{
    ValueSet const& self  = get_wrapped_set(vself);
    if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
  rb_raise(rb_eArgError, "expected a ValueSet");
    ValueSet const& other = get_wrapped_set(vother);
    
    VALUE vresult = rb_funcall2(cValueSet, id_new, 0, NULL);
    ValueSet& result = get_wrapped_set(vresult);
    std::set_intersection(self.begin(), self.end(), other.begin(), other.end(), 
      std::inserter(result, result.end()));
    return vresult;
}

#intersection!(other) ⇒ Object

Computes the intersection of set and other, and modifies self to be that interesection. This operation is O(N + M) if other is a ValueSet



175
176
177
178
179
180
181
182
183
184
185
186
187
 
# File 'ext/utilrb/value_set.cc', line 175

static VALUE value_set_intersection_bang(VALUE vself, VALUE vother)
{
    ValueSet& self  = get_wrapped_set(vself);
    if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
  rb_raise(rb_eArgError, "expected a ValueSet");
    ValueSet const& other = get_wrapped_set(vother);
    
    ValueSet result;
    std::set_intersection(self.begin(), self.end(), other.begin(), other.end(), 
      std::inserter(result, result.end()));
    self.swap(result);
    return vself;
}

#intersects?(other) ⇒ Boolean

Returns true if there is elements in set that are also in +other



215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
 
# File 'ext/utilrb/value_set.cc', line 215

static VALUE value_set_intersects(VALUE vself, VALUE vother)
{
    ValueSet const& self  = get_wrapped_set(vself);
    if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
  rb_raise(rb_eArgError, "expected a ValueSet");
    ValueSet const& other = get_wrapped_set(vother);

    ValueSet::const_iterator 
  self_it   = self.begin(),
  self_end  = self.end(),
  other_it  = other.begin(),
  other_end = other.end();

    while(self_it != self_end && other_it != other_end)
    {
  if (*self_it < *other_it)
      ++self_it;
  else if (*other_it < *self_it)
      ++other_it;
  else
      return Qtrue;
    }
    return Qfalse;
}

#merge(other) ⇒ Object

Merges the elements of other into self. If other is a ValueSet, the operation is O(N + M)



158
159
160
161
162
163
164
165
166
167
 
# File 'ext/utilrb/value_set.cc', line 158

static VALUE value_set_merge(VALUE vself, VALUE vother)
{
    ValueSet& self  = get_wrapped_set(vself);
    if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
  rb_raise(rb_eArgError, "expected a ValueSet");
    ValueSet const& other = get_wrapped_set(vother);
    
    self.insert(other.begin(), other.end());
    return vself;
}

#size ⇒ Object

Returns this set size



42
43
44
45
46
 
# File 'ext/utilrb/value_set.cc', line 42

static VALUE value_set_size(VALUE self)
{ 
    ValueSet& set = get_wrapped_set(self);
    return INT2NUM(set.size());
}

#to_value_set ⇒ Object 



100
 
# File 'ext/utilrb/value_set.cc', line 100

static VALUE value_set_to_value_set(VALUE self) { return self; }

#union(other) ⇒ Object #|(other = >union_set) ⇒ Object

Computes the union of set and other. This operation is O(N + M) is other is a ValueSet



139
140
141
142
143
144
145
146
147
148
149
150
151
 
# File 'ext/utilrb/value_set.cc', line 139

static VALUE value_set_union(VALUE vself, VALUE vother)
{
    ValueSet const& self  = get_wrapped_set(vself);
    if (!RTEST(rb_obj_is_kind_of(vother, cValueSet)))
  rb_raise(rb_eArgError, "expected a ValueSet");
    ValueSet const& other = get_wrapped_set(vother);
    
    VALUE vresult = rb_funcall2(cValueSet, id_new, 0, NULL);
    ValueSet& result = get_wrapped_set(vresult);
    std::set_union(self.begin(), self.end(), other.begin(), other.end(), 
      std::inserter(result, result.end()));
    return vresult;
}