Class: ValueSet

Inherits:
Object show all
Defined in:
ext/value_set.cc,
ext/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



311
312
313
314
315
316
317
318
 
# File 'ext/value_set.cc', line 311

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



325
326
327
328
329
 
# File 'ext/value_set.cc', line 325

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.



299
300
301
302
303
304
 
# File 'ext/value_set.cc', line 299

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



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

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).



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

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).



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

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()));
    self.swap(result);
    return vself;
}

#dup ⇒ Object

Duplicates this set, without duplicating the pointed-to objects



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

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) 


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

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

Returns:

  • (Boolean) 


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

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

Returns:

  • (Boolean) 


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

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

Returns:

  • (Boolean) 


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

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



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

static VALUE value_set_initialize_copy(VALUE vself, VALUE vother)
{
    ValueSet const& other = get_wrapped_set(vother);
    set<VALUE> new_set(other.begin(), other.end());
    get_wrapped_set(vself).swap(new_set);
    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)



287
288
289
290
291
292
 
# File 'ext/value_set.cc', line 287

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



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

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



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

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

Returns:

  • (Boolean) 


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

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)



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

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



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

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

#to_value_set ⇒ Object 



99
 
# File 'ext/value_set.cc', line 99

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



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

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;
}