Class: Set

Inherits:
Object show all
Includes:
Enumerable
Defined in:
lib/extensions/set/set.rb,
lib/extensions/rhoxml/rexml/set.rb

Overview

Set implements a collection of unordered values with no duplicates. This is a hybrid of Array’s intuitive inter-operation facilities and Hash’s fast lookup.

The equality of each couple of elements is determined according to Object#eql? and Object#hash, since Set uses Hash as storage.

Set is easy to use with Enumerable objects (implementing each). Most of the initializer methods and binary operators accept generic Enumerable objects besides sets and arrays. An Enumerable object can be converted to Set using the to_set method.

Example

require 'set'
s1 = Set.new [1, 2]                   # -> #<Set: {1, 2}>
s2 = [1, 2].to_set                    # -> #<Set: {1, 2}>
s1 == s2                              # -> true
s1.add("foo")                         # -> #<Set: {1, 2, "foo"}>
s1.merge([2, 6])                      # -> #<Set: {6, 1, 2, "foo"}>
s1.subset? s2                         # -> false
s2.subset? s1                         # -> true

Contact

- Akinori MUSHA <[email protected]> (current maintainer)

Direct Known Subclasses

SortedSet

Constant Summary collapse

InspectKey =

:nodoc:

:__inspect_key__

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Enumerable

#all?, #any?, #collect, #detect, #each_with_index, #find_all, #group_by, #inject, #max, #min, #sort, #sort_by, #to_set

Constructor Details

#initialize(enum = nil, &block) ⇒ Set

Creates a new set containing the elements of the given enumerable object.

If a block is given, the elements of enum are preprocessed by the given block.



67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/extensions/set/set.rb', line 67

def initialize(enum = nil, &block) # :yields: o
  @hash ||= Hash.new

  enum.nil? and return

  if block
    do_with_enum(enum) { |o| add(block[o]) }
  else
    merge(enum)
  end
end

Class Method Details

.[](*ary) ⇒ Object

Creates a new set containing the given objects.



58
59
60
 
# File 'lib/extensions/set/set.rb', line 58

def self.[](*ary)
  new(ary)
end

Instance Method Details

#&(enum) ⇒ Object Also known as: intersection

Returns a new set containing elements common to the set and the given enumerable object.



340
341
342
343
344
 
# File 'lib/extensions/set/set.rb', line 340

def &(enum)
  n = self.class.new
  do_with_enum(enum) { |o| n.add(o) if include?(o) }
  n
end

#-(enum) ⇒ Object Also known as: difference

Returns a new set built by duplicating the set, removing every element that appears in the given enumerable object.



333
334
335
 
# File 'lib/extensions/set/set.rb', line 333

def -(enum)
  dup.subtract(enum)
end

#==(set) ⇒ Object

Returns true if two sets are equal. The equality of each couple of elements is defined according to Object#eql?.



358
359
360
361
362
363
364
365
366
367
368
 
# File 'lib/extensions/set/set.rb', line 358

def ==(other)
  if self.equal?(other)
    true
  elsif other.instance_of?(self.class)
    @hash == other.instance_variable_get(:@hash)
  elsif other.is_a?(Set) && self.size == other.size
    other.all? { |o| @hash.include?(o) }
  else
    false
  end
end

#^(enum) ⇒ Object

Returns a new set containing elements exclusive between the set and the given enumerable object. (set ^ enum) is equivalent to ((set | enum) - (set & enum)).



350
351
352
353
354
 
# File 'lib/extensions/set/set.rb', line 350

def ^(enum)
  n = Set.new(enum)
  each { |o| if n.include?(o) then n.delete(o) else n.add(o) end }
  n
end

#add(o) ⇒ Object Also known as: <<

Adds the given object to the set and returns self. Use merge to add many elements at once.



228
229
230
231
 
# File 'lib/extensions/set/set.rb', line 228

def add(o)
  @hash[o] = true
  self
end

#add?(o) ⇒ Boolean

Adds the given object to the set and returns self. If the object is already in the set, returns nil.

Returns:

  • (Boolean) 


236
237
238
239
240
241
242
 
# File 'lib/extensions/set/set.rb', line 236

def add?(o)
  if include?(o)
    nil
  else
    add(o)
  end
end

#classify ⇒ Object

Classifies the set by the return value of the given block and returns a hash of => set of elements pairs. The block is called once for each element of the set, passing the element as parameter.

e.g.:

require 'set'
files = Set.new(Dir.glob("*.rb"))
hash = files.classify { |f| File.mtime(f).year }
p hash    # => {2000=>#<Set: {"a.rb", "b.rb"}>,
          #     2001=>#<Set: {"c.rb", "d.rb", "e.rb"}>,
          #     2002=>#<Set: {"f.rb"}>}



392
393
394
395
396
397
398
399
400
401
402
403
 
# File 'lib/extensions/set/set.rb', line 392

def classify # :yields: o
  block_given? or return enum_for(__method__)

  h = {}

  each { |i|
    x = yield(i)
    (h[x] ||= self.class.new).add(i)
  }

  h
end

#clear ⇒ Object

Removes all elements and returns self.



125
126
127
128
 
# File 'lib/extensions/set/set.rb', line 125

def clear
  @hash.clear
  self
end

#collect! ⇒ Object Also known as: map!

Replaces the elements with ones returned by collect().



278
279
280
281
282
283
 
# File 'lib/extensions/set/set.rb', line 278

def collect!
  block_given? or return enum_for(__method__)
  set = self.class.new
  each { |o| set << yield(o) }
  replace(set)
end

#delete(o) ⇒ Object

Deletes the given object from the set and returns self. Use subtract to delete many items at once.



246
247
248
249
 
# File 'lib/extensions/set/set.rb', line 246

def delete(o)
  @hash.delete(o)
  self
end

#delete?(o) ⇒ Boolean

Deletes the given object from the set and returns self. If the object is not in the set, returns nil.

Returns:

  • (Boolean) 


253
254
255
256
257
258
259
 
# File 'lib/extensions/set/set.rb', line 253

def delete?(o)
  if include?(o)
    delete(o)
  else
    nil
  end
end

#delete_if ⇒ Object

Deletes every element of the set for which block evaluates to true, and returns self.



263
264
265
266
267
 
# File 'lib/extensions/set/set.rb', line 263

def delete_if
  block_given? or return enum_for(__method__)
  to_a.each { |o| @hash.delete(o) if yield(o) }
  self
end

#divide(&func) ⇒ Object

Divides the set into a set of subsets according to the commonality defined by the given block.

If the arity of the block is 2, elements o1 and o2 are in common if block.call(o1, o2) is true. Otherwise, elements o1 and o2 are in common if block.call(o1) == block.call(o2).

e.g.:

require 'set'
numbers = Set[1, 3, 4, 6, 9, 10, 11]
set = numbers.divide { |i,j| (i - j).abs == 1 }
p set     # => #<Set: {#<Set: {1}>,
          #            #<Set: {11, 9, 10}>,
          #            #<Set: {3, 4}>,
          #            #<Set: {6}>}>



421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
 
# File 'lib/extensions/set/set.rb', line 421

def divide(&func)
  func or return enum_for(__method__)

  if func.arity == 2
    require 'tsort'

    class << dig = {}		# :nodoc:
	include TSort

	alias tsort_each_node each_key
	def tsort_each_child(node, &block)
 fetch(node).each(&block)
	end
    end

    each { |u|
	dig[u] = a = []
	each{ |v| func.call(u, v) and a << v }
    }

    set = Set.new()
    dig.each_strongly_connected_component { |css|
	set.add(self.class.new(css))
    }
    set
  else
    Set.new(classify(&func).values)
  end
end

#each ⇒ Object

Calls the given block once for each element in the set, passing the element as parameter. Returns an enumerator if no block is given.



220
221
222
223
224
 
# File 'lib/extensions/set/set.rb', line 220

def each
  block_given? or return enum_for(__method__)
  @hash.each_key { |o| yield(o) }
  self
end

#empty? ⇒ Boolean

Returns true if the set contains no elements.

Returns:

  • (Boolean) 


120
121
122
 
# File 'lib/extensions/set/set.rb', line 120

def empty?
  @hash.empty?
end

#eql?(o) ⇒ Boolean

:nodoc:

Returns:

  • (Boolean) 


374
375
376
377
 
# File 'lib/extensions/set/set.rb', line 374

def eql?(o)	# :nodoc:
  return false unless o.is_a?(Set)
  @hash.eql?(o.instance_eval{@hash})
end

#flatten ⇒ Object

Returns a new set that is a copy of the set, flattening each containing set recursively.



169
170
171
 
# File 'lib/extensions/set/set.rb', line 169

def flatten
  self.class.new.flatten_merge(self)
end

#flatten! ⇒ Object

Equivalent to Set#flatten, but replaces the receiver with the result in place. Returns nil if no modifications were made.



175
176
177
178
179
180
181
 
# File 'lib/extensions/set/set.rb', line 175

def flatten!
  if detect { |e| e.is_a?(Set) }
    replace(flatten())
  else
    nil
  end
end

#freeze ⇒ Object

:nodoc:



95
96
97
98
99
 
# File 'lib/extensions/set/set.rb', line 95

def freeze	# :nodoc:
  super
  @hash.freeze
  self
end

#hash ⇒ Object

:nodoc:



370
371
372
 
# File 'lib/extensions/set/set.rb', line 370

def hash	# :nodoc:
  @hash.hash
end

#include?(o) ⇒ Boolean Also known as: member?

Returns true if the set contains the given object.

Returns:

  • (Boolean) 


184
185
186
 
# File 'lib/extensions/set/set.rb', line 184

def include?(o)
  @hash.include?(o)
end

#initialize_copy(orig) ⇒ Object

Copy internal hash.



91
92
93
 
# File 'lib/extensions/set/set.rb', line 91

def initialize_copy(orig)
  @hash = orig.instance_eval{@hash}.dup
end

#inspect ⇒ Object

Returns a string containing a human-readable representation of the set. (“#<Set: element2, …>”)



455
456
457
458
459
460
461
462
463
464
465
466
467
468
 
# File 'lib/extensions/set/set.rb', line 455

def inspect
  ids = (Thread.current[InspectKey] ||= [])

  if ids.include?(object_id)
    return sprintf('#<%s: {...}>', self.class.name)
  end

  begin
    ids << object_id
    return sprintf('#<%s: {%s}>', self.class, to_a.inspect[1..-2])
  ensure
    ids.pop
  end
end

#keep_if ⇒ Object

Deletes every element of the set for which block evaluates to false, and returns self.



271
272
273
274
275
 
# File 'lib/extensions/set/set.rb', line 271

def keep_if
  block_given? or return enum_for(__method__)
  to_a.each { |o| @hash.delete(o) unless yield(o) }
  self
end

#merge(enum) ⇒ Object

Merges the elements of the given enumerable object to the set and returns self.



306
307
308
309
310
311
312
313
314
 
# File 'lib/extensions/set/set.rb', line 306

def merge(enum)
  if enum.instance_of?(self.class)
    @hash.update(enum.instance_variable_get(:@hash))
  else
    do_with_enum(enum) { |o| add(o) }
  end

  self
end

#pretty_print(pp) ⇒ Object

:nodoc:



470
471
472
473
474
475
476
477
478
 
# File 'lib/extensions/set/set.rb', line 470

def pretty_print(pp)	# :nodoc:
  pp.text sprintf('#<%s: {', self.class.name)
  pp.nest(1) {
    pp.seplist(self) { |o|
	pp.pp o
    }
  }
  pp.text "}>"
end

#pretty_print_cycle(pp) ⇒ Object

:nodoc:



480
481
482
 
# File 'lib/extensions/set/set.rb', line 480

def pretty_print_cycle(pp)	# :nodoc:
  pp.text sprintf('#<%s: {%s}>', self.class.name, empty? ? '' : '...')
end

#proper_subset?(set) ⇒ Boolean

Returns true if the set is a proper subset of the given set.

Returns:

  • (Boolean) 


211
212
213
214
215
 
# File 'lib/extensions/set/set.rb', line 211

def proper_subset?(set)
  set.is_a?(Set) or raise ArgumentError, "value must be a set"
  return false if set.size <= size
  all? { |o| set.include?(o) }
end

#proper_superset?(set) ⇒ Boolean

Returns true if the set is a proper superset of the given set.

Returns:

  • (Boolean) 


197
198
199
200
201
 
# File 'lib/extensions/set/set.rb', line 197

def proper_superset?(set)
  set.is_a?(Set) or raise ArgumentError, "value must be a set"
  return false if size <= set.size
  set.all? { |o| include?(o) }
end

#reject! ⇒ Object

Equivalent to Set#delete_if, but returns nil if no changes were made.



288
289
290
291
292
293
 
# File 'lib/extensions/set/set.rb', line 288

def reject!
  block_given? or return enum_for(__method__)
  n = size
  delete_if { |o| yield(o) }
  size == n ? nil : self
end

#replace(enum) ⇒ Object

Replaces the contents of the set with the contents of the given enumerable object and returns self.



132
133
134
135
136
137
138
139
140
141
 
# File 'lib/extensions/set/set.rb', line 132

def replace(enum)
  if enum.class == self.class
    @hash.replace(enum.instance_eval { @hash })
  else
    clear
    merge(enum)
  end

  self
end

#select! ⇒ Object

Equivalent to Set#keep_if, but returns nil if no changes were made.



297
298
299
300
301
302
 
# File 'lib/extensions/set/set.rb', line 297

def select!
  block_given? or return enum_for(__method__)
  n = size
  keep_if { |o| yield(o) }
  size == n ? nil : self
end

#size ⇒ Object Also known as: length

Returns the number of elements.



114
115
116
 
# File 'lib/extensions/set/set.rb', line 114

def size
  @hash.size
end

#subset?(set) ⇒ Boolean

Returns true if the set is a subset of the given set.

Returns:

  • (Boolean) 


204
205
206
207
208
 
# File 'lib/extensions/set/set.rb', line 204

def subset?(set)
  set.is_a?(Set) or raise ArgumentError, "value must be a set"
  return false if set.size < size
  all? { |o| set.include?(o) }
end

#subtract(enum) ⇒ Object

Deletes every element that appears in the given enumerable object and returns self.



318
319
320
321
 
# File 'lib/extensions/set/set.rb', line 318

def subtract(enum)
  do_with_enum(enum) { |o| delete(o) }
  self
end

#superset?(set) ⇒ Boolean

Returns true if the set is a superset of the given set.

Returns:

  • (Boolean) 


190
191
192
193
194
 
# File 'lib/extensions/set/set.rb', line 190

def superset?(set)
  set.is_a?(Set) or raise ArgumentError, "value must be a set"
  return false if size < set.size
  set.all? { |o| include?(o) }
end

#taint ⇒ Object

:nodoc:



101
102
103
104
105
 
# File 'lib/extensions/set/set.rb', line 101

def taint	# :nodoc:
  super
  @hash.taint
  self
end

#to_a ⇒ Object

Converts the set to an array. The order of elements is uncertain.



144
145
146
 
# File 'lib/extensions/set/set.rb', line 144

def to_a
  @hash.keys
end

#untaint ⇒ Object

:nodoc:



107
108
109
110
111
 
# File 'lib/extensions/set/set.rb', line 107

def untaint	# :nodoc:
  super
  @hash.untaint
  self
end

#|(enum) ⇒ Object Also known as: +, union

Returns a new set built by merging the set and the elements of the given enumerable object.



325
326
327
 
# File 'lib/extensions/set/set.rb', line 325

def |(enum)
  dup.merge(enum)
end