lib/set.rb
DEFINITIONS
This source file includes following functions.
1 #!/usr/bin/env ruby
2 #
3 # set - defines the Set class
4 #
5 # Copyright (c) 2002 Akinori MUSHA <knu@iDaemons.org>
6 #
7 # All rights reserved.
8 #
9 # You can redistribute and/or modify it under the same terms as Ruby.
10 #
11
12 =begin
13 = set.rb
14
15 This library provides the Set class that deals with a collection of
16 unordered values with no duplicates. It is a hybrid of Array's
17 intuitive inter-operation facilities and Hash's fast lookup.
18
19 == Example
20
21 require 'set'
22
23 set1 = Set.new ["foo", "bar", "baz"]
24
25 p set1 #=> #<Set: {"baz", "foo", "bar"}>
26
27 p set1.include?("bar") #=> true
28
29 set1.add("heh")
30 set1.delete("foo")
31
32 p set1 #=> #<Set: {"heh", "baz", "bar"}>
33
34 == Set class
35 Set implements a collection of unordered values with no duplicates.
36 This is a hybrid of Array's intuitive inter-operation facilities and
37 Hash's fast lookup.
38
39 The equality of each couple of elements is determined according to
40 Object#eql? and Object#hash, since Set uses Hash as storage.
41
42 === Included Modules
43 Enumerable
44
45 === Class Methods
46 --- Set::new(enum = nil)
47 Creates a new set containing the elements of the given enumerable
48 object.
49
50 --- Set[*ary]
51 Creates a new set containing the given objects.
52
53 === Instance Methods
54 --- dup
55 Duplicates the set.
56
57 --- size
58 --- length
59 Returns the number of elements.
60
61 --- empty?
62 Returns true if the set contains no elements.
63
64 --- clear
65 Removes all elements and returns self.
66
67 --- replace(enum)
68 Replaces the contents of the set with the contents of the given
69 enumerable object and returns self.
70
71 --- flatten
72 Returns a new set that is a copy of the set, flattening each
73 containing set recursively.
74
75 --- flatten!
76 Equivalent to Set#flatten, but replaces the receiver with the
77 result in place. Returns nil if no modifications were made.
78
79 --- to_a
80 Converts the set to an array. (the order is uncertain)
81
82 --- include?(o)
83 --- member?(o)
84 Returns true if the set contains the given object.
85
86 --- contain?(enum)
87 Returns true if the set contains every element of the given
88 enumerable object.
89
90 --- each { |o| ... }
91 Calls the given block once for each element in the set, passing
92 the element as parameter.
93
94 --- add(o)
95 --- << o
96 Adds the given object to the set and returns self.
97
98 --- delete(o)
99 Deletes the given object from the set and returns the object. If
100 the object is not found, returns nil.
101
102 --- delete_if { |o| ... }
103 Deletes every element of the set for which block evaluates to
104 true, and returns self.
105
106 --- reject! { |o| ... }
107 Equivalent to Set#delete_if, but returns nil if no changes were
108 made.
109
110 --- merge(enum)
111 Merges the elements of the given enumerable object to the set and
112 returns self.
113
114 --- subtract(enum)
115 Deletes every element that appears in the given enumerable object
116 and returns self.
117
118 --- + enum
119 --- | enum
120 Returns a new set built by merging the set and the elements of the
121 given enumerable object.
122
123 --- - enum
124 Returns a new set built by duplicating the set, removing every
125 element that appear in the given enumerable object.
126
127 --- & enum
128 Returns a new array containing elements common to the set and the
129 given enumerable object.
130
131 --- ^ enum
132 Returns a new array containing elements exclusive between the set
133 and the given enumerable object. (set ^ enum) is equivalent to
134 ((set | enum) - (set & enum)).
135
136 --- == set
137 Returns true if two sets are equal. The equality of each couple
138 of elements is defined according to Object#eql?.
139
140 --- classify { |o| ... }
141 Classifies the set by the return value of the given block and
142 returns a hash of {value => set of elements} pairs. The block is
143 called once for each element of the set, passing the element as
144 parameter.
145
146 e.g.:
147
148 require 'set'
149 files = Set.new(Dir.glob("*.rb"))
150 hash = files.classify { |f| File.mtime(f).year }
151 p hash #=> {2000=>#<Set: {"a.rb", "b.rb"}>,
152 # 2001=>#<Set: {"c.rb", "d.rb", "e.rb"}>,
153 # 2002=>#<Set: {"f.rb"}>}
154
155 --- divide { |o| ... }
156 --- divide { |o1, o2| ... }
157
158 Divides the set into a set of subsets according to the commonality
159 defined by the given block.
160
161 If the arity of the block is 2, elements o1 and o2 are in common
162 if block.call(o1, o2) is true. Otherwise, elements o1 and o2 are
163 in common if block.call(o1) == block.call(o2).
164
165 e.g.:
166
167 require 'set'
168 numbers = Set[1, 3, 4, 6, 9, 10, 11]
169 set = numbers.divide { |i,j| (i - j).abs == 1 }
170 p set #=> #<Set: {#<Set: {1}>,
171 # #<Set: {11, 9, 10}>,
172 # #<Set: {3, 4}>,
173 # #<Set: {6}>}>
174
175 --- inspect
176 Returns a string containing a human-readable representation of the
177 set. ("#<Set: {element1, element2, ...}>")
178
179 =end
180
181 class Set
182 include Enumerable
183
184 def self.[](*ary)
185 new(ary)
186 end
187
188 def initialize(enum = nil)
189 @hash = {}
190
191 enum.nil? and return
192
193 enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
194 enum.each { |o| @hash[o] = true }
195 end
196
197 def dup
198 n = type.new
199 @hash.each_key { |o| n.add(o) }
200 n
201 end
202
203 def size
204 @hash.size
205 end
206 alias length size
207
208 def empty?
209 @hash.empty?
210 end
211
212 def clear
213 @hash.clear
214 self
215 end
216
217 def replace(enum)
218 enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
219 clear
220 enum.each { |o| add(o) }
221 self
222 end
223
224 def to_a
225 @hash.keys
226 end
227
228 def flatten_merge(set, seen = Set.new)
229 set.each { |e|
230 if e.is_a?(Set)
231 if seen.include?(e_id = e.id)
232 raise ArgumentError, "tried to flatten recursive Set"
233 end
234
235 seen.add(e_id)
236 flatten_merge(e, seen)
237 seen.delete(e_id)
238 else
239 add(e)
240 end
241 }
242
243 self
244 end
245 protected :flatten_merge
246
247 def flatten
248 type.new.flatten_merge(self)
249 end
250
251 def flatten!
252 if detect { |e| e.is_a?(Set) }
253 replace(flatten())
254 else
255 nil
256 end
257 end
258
259 def include?(o)
260 @hash.include?(o)
261 end
262 alias member? include?
263
264 def contain?(enum)
265 enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
266 enum.all? { |o| include?(o) }
267 end
268
269 def each
270 @hash.each_key { |o| yield o }
271 end
272
273 def add(o)
274 @hash[o] = true
275 self
276 end
277 alias << add
278
279 def delete(o)
280 @hash.delete(o) ? o : nil
281 end
282
283 def delete_if
284 @hash.delete_if { |key, value| yield(key) }
285 self
286 end
287
288 def reject!
289 n = @hash.size
290 @hash.delete_if { |key, value| yield(key) }
291 @hash.size == n ? nil : self
292 end
293
294 def merge(enum)
295 enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
296 enum.each { |o| add(o) }
297 self
298 end
299
300 def subtract(enum)
301 enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
302 enum.each { |o| delete(o) }
303 self
304 end
305
306 def +(enum)
307 enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
308 n = dup
309 enum.each { |o| n.add(o) }
310 n
311 end
312 alias | + ##
313
314 def -(enum)
315 enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
316 n = dup
317 enum.each { |o| n.delete(o) }
318 n
319 end
320
321 def &(enum)
322 enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
323 n = type.new
324 enum.each { |o| include?(o) and n.add(o) }
325 n
326 end
327
328 def ^(enum)
329 enum.is_a?(Enumerable) or raise ArgumentError, "value must be enumerable"
330 n = dup
331 enum.each { |o| if n.include?(o) then n.delete(o) else n.add(o) end }
332 n
333 end
334
335 def ==(set)
336 equal?(set) and return true
337
338 set.is_a?(Set) && size == set.size or return false
339
340 set.all? { |o| include?(o) }
341 end
342
343 def hash
344 @hash.hash
345 end
346
347 def eql?(o)
348 @hash.hash == o.hash
349 end
350
351 def classify
352 h = {}
353
354 each { |i|
355 x = yield(i)
356 (h[x] ||= type.new).add(i)
357 }
358
359 h
360 end
361
362 def divide(&func)
363 if func.arity == 2
364 require 'tsort'
365
366 class << dig = {}
367 include TSort
368
369 alias tsort_each_node each_key
370 def tsort_each_child(node, &block)
371 fetch(node).each(&block)
372 end
373 end
374
375 each { |u|
376 dig[u] = a = []
377 each{ |v| func.call(u, v) and a << v }
378 }
379
380 set = type.new()
381 dig.each_strongly_connected_component { |css|
382 set.add(Set.new(css))
383 }
384 set
385 else
386 type.new(classify(&func).values)
387 end
388 end
389
390 InspectKey = :__inspect_key__
391
392 def inspect
393 ids = (Thread.current[InspectKey] ||= [])
394
395 if ids.include?(id)
396 return sprintf('#<%s: {...}>', type.name)
397 end
398
399 begin
400 ids << id
401 return sprintf('#<%s: {%s}>', type, to_a.inspect[1..-2])
402 ensure
403 ids.pop
404 end
405 end
406
407 def pretty_print(pp)
408 pp.text sprintf('#<%s: {', type.name)
409 pp.nest(1) {
410 first = true
411 each { |o|
412 if first
413 first = false
414 else
415 pp.text ","
416 pp.breakable
417 end
418 pp.pp o
419 }
420 }
421 pp.text "}>"
422 end
423
424 def pretty_print_cycle(pp)
425 pp.text sprintf('#<%s: {%s}>', type.name, empty? ? '' : '...')
426 end
427 end
428
429 if $0 == __FILE__
430 eval DATA.read
431 end
432
433 __END__
434
435 require 'test/unit'
436 require 'test/unit/ui/console/testrunner'
437
438 class TC_Set < Test::Unit::TestCase
439 def test_aref
440 assert_nothing_raised {
441 Set[]
442 Set[nil]
443 Set[1,2,3]
444 }
445
446 assert_equal(0, Set[].size)
447 assert_equal(1, Set[nil].size)
448 assert_equal(1, Set[[]].size)
449 assert_equal(1, Set[[nil]].size)
450
451 set = Set[2,4,6,4]
452 assert_equal(Set.new([2,4,6]), set)
453 end
454
455 def test_s_new
456 assert_nothing_raised {
457 Set.new()
458 Set.new(nil)
459 Set.new([])
460 Set.new([1,2])
461 Set.new('a'..'c')
462 Set.new('XYZ')
463 }
464 assert_raises(ArgumentError) {
465 Set.new(false)
466 }
467 assert_raises(ArgumentError) {
468 Set.new(1)
469 }
470 assert_raises(ArgumentError) {
471 Set.new(1,2)
472 }
473
474 assert_equal(0, Set.new().size)
475 assert_equal(0, Set.new(nil).size)
476 assert_equal(0, Set.new([]).size)
477 assert_equal(1, Set.new([nil]).size)
478
479 ary = [2,4,6,4]
480 set = Set.new(ary)
481 ary.clear
482 assert_equal(false, set.empty?)
483 assert_equal(3, set.size)
484 end
485
486 def test_dup
487 set1 = Set[1,2]
488 set2 = set1.dup
489
490 assert_not_same(set1, set2)
491
492 assert_equal(set1, set2)
493
494 set1.add(3)
495
496 assert_not_equal(set1, set2)
497 end
498
499 def test_size
500 assert_equal(0, Set[].size)
501 assert_equal(2, Set[1,2].size)
502 assert_equal(2, Set[1,2,1].size)
503 end
504
505 def test_empty?
506 assert_equal(true, Set[].empty?)
507 assert_equal(false, Set[1, 2].empty?)
508 end
509
510 def test_clear
511 set = Set[1,2]
512 ret = set.clear
513
514 assert_same(set, ret)
515 assert_equal(true, set.empty?)
516 end
517
518 def test_replace
519 set = Set[1,2]
520 ret = set.replace('a'..'c')
521
522 assert_same(set, ret)
523 assert_equal(Set['a','b','c'], set)
524 end
525
526 def test_to_a
527 set = Set[1,2,3,2]
528 ary = set.to_a
529
530 assert_equal([1,2,3], ary.sort)
531 end
532
533 def test_flatten
534 # test1
535 set1 = Set[
536 1,
537 Set[
538 5,
539 Set[7,
540 Set[0]
541 ],
542 Set[6,2],
543 1
544 ],
545 3,
546 Set[3,4]
547 ]
548
549 set2 = set1.flatten
550 set3 = Set.new(0..7)
551
552 assert_not_same(set2, set1)
553 assert_equal(set3, set2)
554
555 # test2; destructive
556 orig_set1 = set1
557 set1.flatten!
558
559 assert_same(orig_set1, set1)
560 assert_equal(set3, set1)
561
562 # test3; multiple occurences of a set in an set
563 set1 = Set[1, 2]
564 set2 = Set[set1, Set[set1, 4], 3]
565
566 assert_nothing_raised {
567 set2.flatten!
568 }
569
570 assert_equal(Set.new(1..4), set2)
571
572 # test4; recursion
573 set2 = Set[]
574 set1 = Set[1, set2]
575 set2.add(set1)
576
577 assert_raises(ArgumentError) {
578 set1.flatten!
579 }
580
581 # test5; miscellaneus
582 empty = Set[]
583 set = Set[Set[empty, "a"],Set[empty, "b"]]
584
585 assert_nothing_raised {
586 set.flatten
587 }
588
589 set1 = empty.merge(Set["no_more", set])
590
591 assert_nil(Set.new(0..31).flatten!)
592
593 x = Set[Set[],Set[1,2]].flatten!
594 y = Set[1,2]
595
596 assert_equal(x, y)
597 end
598
599 def test_include?
600 set = Set[1,2,3]
601
602 assert_equal(true, set.include?(1))
603 assert_equal(true, set.include?(2))
604 assert_equal(true, set.include?(3))
605 assert_equal(false, set.include?(0))
606 assert_equal(false, set.include?(nil))
607
608 set = Set["1",nil,"2",nil,"0","1",false]
609 assert_equal(true, set.include?(nil))
610 assert_equal(true, set.include?(false))
611 assert_equal(true, set.include?("1"))
612 assert_equal(false, set.include?(0))
613 assert_equal(false, set.include?(true))
614 end
615
616 def test_contain?
617 set = Set[1,2,3]
618
619 assert_raises(ArgumentError) {
620 set.contain?()
621 }
622
623 assert_raises(ArgumentError) {
624 set.contain?(2)
625 }
626
627 assert_equal(true, set.contain?([]))
628 assert_equal(true, set.contain?([3,1]))
629 assert_equal(false, set.contain?([1,2,0]))
630
631 assert_equal(true, Set[].contain?([]))
632 end
633
634 def test_each
635 ary = [1,3,5,7,10,20]
636 set = Set.new(ary)
637
638 assert_raises(LocalJumpError) {
639 set.each
640 }
641
642 assert_nothing_raised {
643 set.each { |o|
644 ary.delete(o) or raise "unexpected element: #{o}"
645 }
646
647 ary.empty? or raise "forgotten elements: #{ary.join(', ')}"
648 }
649 end
650
651 def test_add
652 set = Set[1,2,3]
653
654 ret = set.add(2)
655 assert_same(set, ret)
656 assert_equal(Set[1,2,3], set)
657
658 ret = set.add(4)
659 assert_same(set, ret)
660 assert_equal(Set[1,2,3,4], set)
661 end
662
663 def test_delete
664 set = Set[1,2,3]
665
666 ret = set.delete(4)
667 assert_same(nil, ret)
668 assert_equal(Set[1,2,3], set)
669
670 ret = set.delete(2)
671 assert_equal(2, ret)
672 assert_equal(Set[1,3], set)
673 end
674
675 def test_delete_if
676 set = Set.new(1..10)
677 ret = set.delete_if { |i| i > 10 }
678 assert_same(set, ret)
679 assert_equal(Set.new(1..10), set)
680
681 set = Set.new(1..10)
682 ret = set.delete_if { |i| i % 3 == 0 }
683 assert_same(set, ret)
684 assert_equal(Set[1,2,4,5,7,8,10], set)
685 end
686
687 def test_reject!
688 set = Set.new(1..10)
689 ret = set.reject! { |i| i > 10 }
690 assert_same(nil, ret)
691 assert_equal(Set.new(1..10), set)
692
693 set = Set.new(1..10)
694 ret = set.delete_if { |i| i % 3 == 0 }
695 assert_same(set, ret)
696 assert_equal(Set[1,2,4,5,7,8,10], set)
697 end
698
699 def test_merge
700 set = Set[1,2,3]
701
702 ret = set.merge([2,4,6])
703 assert_same(set, ret)
704 assert_equal(Set[1,2,3,4,6], set)
705 end
706
707 def test_subtract
708 set = Set[1,2,3]
709
710 ret = set.subtract([2,4,6])
711 assert_same(set, ret)
712 assert_equal(Set[1,3], set)
713 end
714
715 def test_plus
716 set = Set[1,2,3]
717
718 ret = set + [2,4,6]
719 assert_not_same(set, ret)
720 assert_equal(Set[1,2,3,4,6], ret)
721 end
722
723 def test_minus
724 set = Set[1,2,3]
725
726 ret = set - [2,4,6]
727 assert_not_same(set, ret)
728 assert_equal(Set[1,3], ret)
729 end
730
731 def test_and
732 set = Set[1,2,3,4]
733
734 ret = set & [2,4,6]
735 assert_not_same(set, ret)
736 assert_equal(Set[2,4], ret)
737 end
738
739 def test_eq
740 set1 = Set[2,3,1]
741 set2 = Set[1,2,3]
742
743 assert_equal(set1, set1)
744 assert_equal(set1, set2)
745 assert_not_equal(Set[1], [1])
746
747 set1 = Class.new(Set)["a", "b"]
748 set2 = Set["a", "b", set1]
749 set1 = set1.add(set1.clone)
750
751 assert_equal(set1, set2)
752 assert_equal(set2, set1)
753 assert_equal(set2, set2.clone)
754 assert_equal(set1.clone, set1)
755 end
756
757 # def test_hash
758 # end
759
760 # def test_eql?
761 # end
762
763 def test_classify
764 set = Set.new(1..10)
765 ret = set.classify { |i| i % 3 }
766
767 assert_equal(3, ret.size)
768 assert_instance_of(Hash, ret)
769 ret.each_value { |value| assert_instance_of(Set, value) }
770 assert_equal(Set[3,6,9], ret[0])
771 assert_equal(Set[1,4,7,10], ret[1])
772 assert_equal(Set[2,5,8], ret[2])
773 end
774
775 def test_divide
776 set = Set.new(1..10)
777 ret = set.divide { |i| i % 3 }
778
779 assert_equal(3, ret.size)
780 n = 0
781 ret.each { |s| n += s.size }
782 assert_equal(set.size, n)
783 assert_equal(set, ret.flatten)
784
785 set = Set[7,10,5,11,1,3,4,9,0]
786 ret = set.divide { |a,b| (a - b).abs == 1 }
787
788 assert_equal(4, ret.size)
789 n = 0
790 ret.each { |s| n += s.size }
791 assert_equal(set.size, n)
792 assert_equal(set, ret.flatten)
793 ret.each { |s|
794 if s.include?(0)
795 assert_equal(Set[0,1], s)
796 elsif s.include?(3)
797 assert_equal(Set[3,4,5], s)
798 elsif s.include?(7)
799 assert_equal(Set[7], s)
800 elsif s.include?(9)
801 assert_equal(Set[9,10,11], s)
802 else
803 raise "unexpected group: #{s.inspect}"
804 end
805 }
806 end
807
808 def test_inspect
809 set1 = Set[1]
810
811 assert_equal('#<Set: {1}>', set1.inspect)
812
813 set2 = Set[Set[0], 1, 2, set1]
814 assert_equal(false, set2.inspect.include?('#<Set: {...}>'))
815
816 set1.add(set2)
817 assert_equal(true, set1.inspect.include?('#<Set: {...}>'))
818 end
819
820 # def test_pretty_print
821 # end
822
823 # def test_pretty_print_cycle
824 # end
825 end
826
827 Test::Unit::UI::Console::TestRunner.run(TC_Set)