Class: Immutable::SortedSet
- Inherits:
-
Object
- Object
- Immutable::SortedSet
- Includes:
- Enumerable
- Defined in:
- lib/immutable/sorted_set.rb
Overview
A SortedSet
is a collection of ordered values with no duplicates. Unlike a
Vector, in which items can appear in any arbitrary order, a SortedSet
always
keeps items either in their natural order, or in an order defined by a comparator
block which is provided at initialization time.
SortedSet
uses #<=>
(or its comparator block) to determine which items are
equivalent. If the comparator indicates that an existing item and a new item are
equal, any attempt to insert the new item will have no effect.
This means that all the items inserted into any one SortedSet
must all be
comparable. For example, you cannot put String
s and Integer
s in the same
SortedSet
. This is unlike Set, which can store items of any type, as long
as they all support #hash
and #eql?
.
A SortedSet
can be created in either of the following ways:
Immutable::SortedSet.new([1, 2, 3]) # any Enumerable can be used to initialize
Immutable::SortedSet['A', 'B', 'C', 'D']
Or if you want to use a custom ordering:
Immutable::SortedSet.new([1,2,3]) { |a, b| -a <=> -b }
Immutable::SortedSet.new([1, 2, 3]) { |num| -num }
SortedSet
can use a 2-parameter block which returns 0, 1, or -1
as a comparator (like Array#sort
), or use a 1-parameter block to derive sort
keys (like Array#sort_by
) which will be compared using #<=>
.
Like all immutable-ruby
collections, SortedSet
s are immutable. Any operation
which you might expect to "modify" a SortedSet
will actually return a new
collection and leave the existing one unchanged.
SortedSet
supports the same basic set-theoretic operations as Set, including
#union, #intersection, #difference, and #exclusion, as well as #subset?,
#superset?, and so on. Unlike Set, it does not define comparison operators like
#>
or #<
as aliases for the superset/subset predicates. Instead, these comparison
operators do a item-by-item comparison between the SortedSet
and another sequential
collection. (See Array#<=>
for details.)
Additionally, since SortedSet
s are ordered, they also support indexed retrieval
of items using #at or #[]. Like Vector,
negative indices count back from the end of the SortedSet
.
Getting the #max or #min item from a SortedSet
, as defined by its comparator,
is a constant time operation.
Class Method Summary collapse
-
.[](*items) ⇒ SortedSet
Create a new
SortedSet
populated with the given items. -
.empty ⇒ SortedSet
Return an empty
SortedSet
.
Instance Method Summary collapse
-
#above(item, &block) ⇒ Object
Select elements greater than a value.
-
#add(item) ⇒ SortedSet
(also: #<<)
Return a new
SortedSet
withitem
added. -
#add?(item) ⇒ SortedSet, false
If
item
is not a member of thisSortedSet
, return a newSortedSet
withitem
added. -
#at(index) ⇒ Object
Retrieve the item at
index
. -
#below(item, &block) ⇒ Object
Select elements less than a value.
-
#between(from, to, &block) ⇒ Object
Select elements between two values.
-
#clear ⇒ SortedSet
Return an empty
SortedSet
instance, of the same class as this one. -
#delete(item) ⇒ SortedSet
Return a new
SortedSet
withitem
removed. -
#delete?(item) ⇒ SortedSet, false
If
item
is a member of thisSortedSet
, return a newSortedSet
withitem
removed. -
#delete_at(index) ⇒ SortedSet
Return a new
SortedSet
with the item atindex
removed. -
#difference(other) ⇒ SortedSet
(also: #subtract, #-)
Return a new
SortedSet
with all the items inother
removed. -
#disjoint?(other) ⇒ Boolean
Return
true
if this set andother
do not share any items. -
#drop(n) ⇒ SortedSet
Drop the first
n
elements and return the rest in a newSortedSet
. -
#drop_while {|item| ... } ⇒ SortedSet, Enumerator
Drop elements up to, but not including, the first element for which the block returns
nil
orfalse
. -
#dup ⇒ SortedSet
(also: #clone)
Return
self
. -
#each {|item| ... } ⇒ self, Enumerator
Call the given block once for each item in the set, passing each item from first to last successively to the block.
-
#empty? ⇒ Boolean
Return
true
if thisSortedSet
contains no items. -
#eql?(other) ⇒ Boolean
Return true if
other
has the same type and contents as thisSortedSet
. -
#exclusion(other) ⇒ SortedSet
(also: #^)
Return a new
SortedSet
with all the items which are members of this set or ofother
, but not both. -
#fetch(index, default = (missing_default = true)) ⇒ Object
Retrieve the value at
index
with optional default. -
#find_index(obj = (missing_obj = true), &block) ⇒ Integer
(also: #index)
Find the index of a given object or an element that satisfies the given block.
-
#first ⇒ Object
Return the "lowest" element in this set, as determined by its sort order.
-
#from(item, &block) ⇒ Object
Select elements greater than or equal to a value.
-
#hash ⇒ Integer
See
Object#hash
. -
#include?(item) ⇒ Boolean
(also: #member?)
Return
true
if the given item is present in thisSortedSet
. -
#initialize(items = [], &block) ⇒ SortedSet
constructor
A new instance of SortedSet.
-
#intersect?(other) ⇒ Boolean
Return
true
if this set andother
have at least one item in common. -
#intersection(other) ⇒ SortedSet
(also: #&)
Return a new
SortedSet
which contains all the items which are members of both this set andother
. -
#last ⇒ Object
Return the "highest" element in this set, as determined by its sort order.
-
#map {|item| ... } ⇒ SortedSet, Enumerator
(also: #collect)
Invoke the given block once for each item in the set, and return a new
SortedSet
containing the values returned by the block. -
#max {|a, b| ... } ⇒ Object
Return the "highest" element in this set, as determined by its sort order.
-
#min {|a, b| ... } ⇒ Object
Return the "lowest" element in this set, as determined by its sort order.
-
#proper_subset?(other) ⇒ Boolean
Returns
true
ifother
contains all the items in this set, plus at least one item which is not in this set. -
#proper_superset?(other) ⇒ Boolean
Returns
true
if this set contains all the items inother
, plus at least one item which is not inother
. -
#reverse_each(&block) ⇒ self
Call the given block once for each item in the set, passing each item starting from the last, and counting back to the first, successively to the block.
-
#sample ⇒ Object
Return a randomly chosen item from this set.
-
#select {|item| ... } ⇒ SortedSet
(also: #find_all, #keep_if)
Return a new
SortedSet
containing all elements for which the given block returns true. -
#size ⇒ Integer
(also: #length)
Return the number of items in this
SortedSet
. -
#slice(arg, length = (missing_length = true)) ⇒ Object
(also: #[])
Return specific objects from the
Vector
. -
#sort(&block) ⇒ SortedSet
(also: #sort_by)
Return a new
SortedSet
with the same items, but a sort order determined by the given block. -
#subset?(other) ⇒ Boolean
Return
true
if all items in this set are also inother
. -
#superset?(other) ⇒ Boolean
Return
true
if all items inother
are also in this set. -
#take(n) ⇒ SortedSet
Return only the first
n
elements in a newSortedSet
. -
#take_while {|item| ... } ⇒ SortedSet, Enumerator
Gather elements up to, but not including, the first element for which the block returns
nil
orfalse
, and return them in a newSortedSet
. -
#union(other) ⇒ SortedSet
(also: #|, #+, #merge)
Return a new
SortedSet
which contains all the members of both this set andother
. -
#up_to(item, &block) ⇒ Object
Select elements less than or equal to a value.
-
#values_at(*indices) ⇒ SortedSet
Return a new
SortedSet
with only the elements at the givenindices
.
Methods included from Enumerable
#<=>, #==, #compact, #each_index, #grep, #grep_v, #group_by, #inspect, #join, #partition, #product, #reject, #sum, #to_set
Methods included from Enumerable
Constructor Details
#initialize(items = [], &block) ⇒ SortedSet
Returns a new instance of SortedSet.
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
# File 'lib/immutable/sorted_set.rb', line 101 def initialize(items=[], &block) items = items.to_a if block # In Ruby 2, &:method blocks have arity -1; in Ruby 3, it's -2 if block.arity == 1 || block.arity == -1 || block.arity == -2 items = items.uniq(&block) items.sort_by!(&block) comparator = lambda { |a,b| block.call(a) <=> block.call(b) } elsif block.arity == 2 || block.arity == -3 items = items.sort(&block) SortedSet.uniq_by_comparator!(items, block) comparator = block else raise "Comparator block for Immutable::SortedSet must accept 1 or 2 arguments" end @node = AVLNode.from_items(items, comparator) else @node = PlainAVLNode.from_items(items.uniq.sort!) end freeze end |
Class Method Details
.[](*items) ⇒ SortedSet
Create a new SortedSet
populated with the given items. This method does not
accept a comparator block.
59 60 61 |
# File 'lib/immutable/sorted_set.rb', line 59 def [](*items) new(items) end |
.empty ⇒ SortedSet
Return an empty SortedSet
. If used on a subclass, returns an empty instance
of that class.
67 68 69 |
# File 'lib/immutable/sorted_set.rb', line 67 def empty @empty ||= alloc(PlainAVLNode::EmptyNode) end |
Instance Method Details
#above(item) ⇒ SortedSet #above(item) {|item| ... } ⇒ nil
Select elements greater than a value.
784 785 786 787 788 789 790 |
# File 'lib/immutable/sorted_set.rb', line 784 def above(item, &block) if block_given? @node.each_greater(item, false, &block) else self.class.alloc(@node.suffix(item, false)) end end |
#add(item) ⇒ SortedSet Also known as: <<
Return a new SortedSet
with item
added. If item
is already in the set,
return self
.
150 151 152 153 154 155 156 |
# File 'lib/immutable/sorted_set.rb', line 150 def add(item) catch :present do node = @node.insert(item) return self.class.alloc(node) end self end |
#add?(item) ⇒ SortedSet, false
If item
is not a member of this SortedSet
, return a new SortedSet
with
item
added. Otherwise, return false
.
170 171 172 |
# File 'lib/immutable/sorted_set.rb', line 170 def add?(item) !include?(item) && add(item) end |
#at(index) ⇒ Object
Retrieve the item at index
. If there is none (either the provided index
is too high or too low), return nil
.
234 235 236 237 238 |
# File 'lib/immutable/sorted_set.rb', line 234 def at(index) index += @node.size if index < 0 return nil if index >= @node.size || index < 0 @node.at(index) end |
#below(item) ⇒ SortedSet #below(item) {|item| ... } ⇒ nil
Select elements less than a value.
815 816 817 818 819 820 821 |
# File 'lib/immutable/sorted_set.rb', line 815 def below(item, &block) if block_given? @node.each_less(item, false, &block) else self.class.alloc(@node.prefix(item, false)) end end |
#between(from, to) ⇒ SortedSet #between(item) {|item| ... } ⇒ nil
Select elements between two values.
915 916 917 918 919 920 921 |
# File 'lib/immutable/sorted_set.rb', line 915 def between(from, to, &block) if block_given? @node.each_between(from, to, &block) else self.class.alloc(@node.between(from, to)) end end |
#clear ⇒ SortedSet
Return an empty SortedSet
instance, of the same class as this one. Useful if you
have multiple subclasses of SortedSet
and want to treat them polymorphically.
937 938 939 940 941 942 943 |
# File 'lib/immutable/sorted_set.rb', line 937 def clear if @node.natural_order? self.class.empty else self.class.alloc(@node.clear) end end |
#delete(item) ⇒ SortedSet
Return a new SortedSet
with item
removed. If item
is not a member of the set,
return self
.
183 184 185 186 187 188 189 190 191 192 193 |
# File 'lib/immutable/sorted_set.rb', line 183 def delete(item) catch :not_present do node = @node.delete(item) if node.empty? && node.natural_order? return self.class.empty else return self.class.alloc(node) end end self end |
#delete?(item) ⇒ SortedSet, false
If item
is a member of this SortedSet
, return a new SortedSet
with
item
removed. Otherwise, return false
.
206 207 208 |
# File 'lib/immutable/sorted_set.rb', line 206 def delete?(item) include?(item) && delete(item) end |
#delete_at(index) ⇒ SortedSet
Return a new SortedSet
with the item at index
removed. If the given index
does not exist (if it is too high or too low), return self
.
219 220 221 |
# File 'lib/immutable/sorted_set.rb', line 219 def delete_at(index) (item = at(index)) ? delete(item) : self end |
#difference(other) ⇒ SortedSet Also known as: subtract, -
Return a new SortedSet
with all the items in other
removed. other
can be
any Enumerable
object.
661 662 663 |
# File 'lib/immutable/sorted_set.rb', line 661 def difference(other) self.class.alloc(@node.bulk_delete(other)) end |
#disjoint?(other) ⇒ Boolean
Return true
if this set and other
do not share any items.
738 739 740 741 742 743 744 745 |
# File 'lib/immutable/sorted_set.rb', line 738 def disjoint?(other) if size < other.size each { |item| return false if other.include?(item) } else other.each { |item| return false if include?(item) } end true end |
#drop(n) ⇒ SortedSet
Drop the first n
elements and return the rest in a new SortedSet
.
566 567 568 |
# File 'lib/immutable/sorted_set.rb', line 566 def drop(n) derive_new_sorted_set(@node.drop(n)) end |
#drop_while {|item| ... } ⇒ SortedSet, Enumerator
Drop elements up to, but not including, the first element for which the
block returns nil
or false
. Gather the remaining elements into a new
SortedSet
. If no block is given, an Enumerator
is returned instead.
592 593 594 595 596 597 598 599 600 |
# File 'lib/immutable/sorted_set.rb', line 592 def drop_while return enum_for(:drop_while) if not block_given? n = 0 each do |item| break unless yield item n += 1 end drop(n) end |
#dup ⇒ SortedSet Also known as: clone
Return self
. Since this is an immutable object duplicates are
equivalent.
969 970 971 |
# File 'lib/immutable/sorted_set.rb', line 969 def dup self end |
#each {|item| ... } ⇒ self, Enumerator
Call the given block once for each item in the set, passing each
item from first to last successively to the block. If no block is
provided, returns an Enumerator
.
379 380 381 382 383 |
# File 'lib/immutable/sorted_set.rb', line 379 def each(&block) return @node.to_enum if not block_given? @node.each(&block) self end |
#empty? ⇒ Boolean
Return true
if this SortedSet
contains no items.
126 127 128 |
# File 'lib/immutable/sorted_set.rb', line 126 def empty? @node.empty? end |
#eql?(other) ⇒ Boolean
Return true if other
has the same type and contents as this SortedSet
.
949 950 951 952 953 954 955 956 957 958 |
# File 'lib/immutable/sorted_set.rb', line 949 def eql?(other) return true if other.equal?(self) return false if not instance_of?(other.class) return false if size != other.size a, b = to_enum, other.to_enum loop do return false if !a.next.eql?(b.next) end true end |
#exclusion(other) ⇒ SortedSet Also known as: ^
Return a new SortedSet
with all the items which are members of this
set or of other
, but not both. other
can be any Enumerable
object.
676 677 678 |
# File 'lib/immutable/sorted_set.rb', line 676 def exclusion(other) ((self | other) - (self & other)) end |
#fetch(index) ⇒ Object #fetch(index) {|index| ... } ⇒ Object #fetch(index, default) ⇒ Object
Retrieve the value at index
with optional default.
279 280 281 282 283 284 285 286 287 288 289 |
# File 'lib/immutable/sorted_set.rb', line 279 def fetch(index, default = (missing_default = true)) if index >= -@node.size && index < @node.size at(index) elsif block_given? yield(index) elsif !missing_default default else raise IndexError, "index #{index} outside of sorted set bounds" end end |
#find_index(obj) ⇒ Integer #find_index {|element| ... } ⇒ Integer Also known as: index
Find the index of a given object or an element that satisfies the given block.
534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 |
# File 'lib/immutable/sorted_set.rb', line 534 def find_index(obj = (missing_obj = true), &block) if !missing_obj # Enumerable provides a default implementation, but this is more efficient node = @node index = node.left.size while !node.empty? direction = node.direction(obj) if direction > 0 node = node.right index += (node.left.size + 1) elsif direction < 0 node = node.left index -= (node.right.size + 1) else return index end end nil else super(&block) end end |
#first ⇒ Object
Return the "lowest" element in this set, as determined by its sort order.
419 420 421 |
# File 'lib/immutable/sorted_set.rb', line 419 def first @node.min end |
#from(item) ⇒ SortedSet #from(item) {|item| ... } ⇒ nil
Select elements greater than or equal to a value.
847 848 849 850 851 852 853 |
# File 'lib/immutable/sorted_set.rb', line 847 def from(item, &block) if block_given? @node.each_greater(item, true, &block) else self.class.alloc(@node.suffix(item, true)) end end |
#hash ⇒ Integer
See Object#hash
.
962 963 964 |
# File 'lib/immutable/sorted_set.rb', line 962 def hash reduce(0) { |hash, item| (hash << 5) - hash + item.hash } end |
#include?(item) ⇒ Boolean Also known as: member?
Return true
if the given item is present in this SortedSet
. More precisely,
return true
if an object which compares as "equal" using this set's
comparator is present.
486 487 488 |
# File 'lib/immutable/sorted_set.rb', line 486 def include?(item) @node.include?(item) end |
#intersect?(other) ⇒ Boolean
Return true
if this set and other
have at least one item in common.
754 755 756 |
# File 'lib/immutable/sorted_set.rb', line 754 def intersect?(other) !disjoint?(other) end |
#intersection(other) ⇒ SortedSet Also known as: &
Return a new SortedSet
which contains all the items which are members of both
this set and other
. other
can be any Enumerable
object.
647 648 649 |
# File 'lib/immutable/sorted_set.rb', line 647 def intersection(other) self.class.alloc(@node.keep_only(other)) end |
#last ⇒ Object
Return the "highest" element in this set, as determined by its sort order.
438 439 440 |
# File 'lib/immutable/sorted_set.rb', line 438 def last @node.max end |
#map {|item| ... } ⇒ SortedSet, Enumerator Also known as: collect
Invoke the given block once for each item in the set, and return a new
SortedSet
containing the values returned by the block. If no block is
given, returns an Enumerator
.
470 471 472 473 474 |
# File 'lib/immutable/sorted_set.rb', line 470 def map return enum_for(:map) if not block_given? return self if empty? self.class.alloc(@node.from_items(super)) end |
#max {|a, b| ... } ⇒ Object
Return the "highest" element in this set, as determined by its sort order.
Or, if a block is provided, use the block as a comparator to find the
"highest" element. (See Enumerable#max
.)
432 433 434 |
# File 'lib/immutable/sorted_set.rb', line 432 def max block_given? ? super : @node.max end |
#min {|a, b| ... } ⇒ Object
Return the "lowest" element in this set, as determined by its sort order.
Or, if a block is provided, use the block as a comparator to find the
"lowest" element. (See Enumerable#min
.)
413 414 415 |
# File 'lib/immutable/sorted_set.rb', line 413 def min block_given? ? super : @node.min end |
#proper_subset?(other) ⇒ Boolean
Returns true
if other
contains all the items in this set, plus at least
one item which is not in this set.
713 714 715 716 |
# File 'lib/immutable/sorted_set.rb', line 713 def proper_subset?(other) return false if other.size <= size all? { |item| other.include?(item) } end |
#proper_superset?(other) ⇒ Boolean
Returns true
if this set contains all the items in other
, plus at least
one item which is not in other
.
727 728 729 |
# File 'lib/immutable/sorted_set.rb', line 727 def proper_superset?(other) other.proper_subset?(self) end |
#reverse_each(&block) ⇒ self
Call the given block once for each item in the set, passing each item starting from the last, and counting back to the first, successively to the block.
398 399 400 401 402 |
# File 'lib/immutable/sorted_set.rb', line 398 def reverse_each(&block) return @node.enum_for(:reverse_each) if not block_given? @node.reverse_each(&block) self end |
#sample ⇒ Object
Return a randomly chosen item from this set. If the set is empty, return nil
.
929 930 931 |
# File 'lib/immutable/sorted_set.rb', line 929 def sample @node.at(rand(@node.size)) end |
#select {|item| ... } ⇒ SortedSet Also known as: find_all, keep_if
Return a new SortedSet
containing all elements for which the given block returns
true.
451 452 453 454 455 456 |
# File 'lib/immutable/sorted_set.rb', line 451 def select return enum_for(:select) unless block_given? items_to_delete = [] each { |item| items_to_delete << item unless yield(item) } derive_new_sorted_set(@node.bulk_delete(items_to_delete)) end |
#size ⇒ Integer Also known as: length
Return the number of items in this SortedSet
.
136 137 138 |
# File 'lib/immutable/sorted_set.rb', line 136 def size @node.size end |
#set.slice(index) ⇒ Object #set.slice(index, length) ⇒ SortedSet #set.slice(index..end) ⇒ SortedSet Also known as: []
Return specific objects from the Vector
. All overloads return nil
if
the starting index is out of range.
331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 |
# File 'lib/immutable/sorted_set.rb', line 331 def slice(arg, length = (missing_length = true)) if missing_length if arg.is_a?(Range) from, to = arg.begin, arg.end from += @node.size if from < 0 to += @node.size if to < 0 to += 1 if !arg.exclude_end? length = to - from length = 0 if length < 0 subsequence(from, length) else at(arg) end else arg += @node.size if arg < 0 subsequence(arg, length) end end |
#sort(&block) ⇒ SortedSet Also known as: sort_by
Return a new SortedSet
with the same items, but a sort order determined
by the given block.
501 502 503 504 505 506 507 508 509 |
# File 'lib/immutable/sorted_set.rb', line 501 def sort(&block) if block self.class.new(to_a, &block) elsif @node.natural_order? self else self.class.new(self) end end |
#subset?(other) ⇒ Boolean
Return true
if all items in this set are also in other
.
688 689 690 691 |
# File 'lib/immutable/sorted_set.rb', line 688 def subset?(other) return false if other.size < size all? { |item| other.include?(item) } end |
#superset?(other) ⇒ Boolean
Return true
if all items in other
are also in this set.
700 701 702 |
# File 'lib/immutable/sorted_set.rb', line 700 def superset?(other) other.subset?(self) end |
#take(n) ⇒ SortedSet
Return only the first n
elements in a new SortedSet
.
578 579 580 |
# File 'lib/immutable/sorted_set.rb', line 578 def take(n) derive_new_sorted_set(@node.take(n)) end |
#take_while {|item| ... } ⇒ SortedSet, Enumerator
Gather elements up to, but not including, the first element for which the
block returns nil
or false
, and return them in a new SortedSet
. If no block
is given, an Enumerator
is returned instead.
612 613 614 615 616 617 618 619 620 |
# File 'lib/immutable/sorted_set.rb', line 612 def take_while return enum_for(:take_while) if not block_given? n = 0 each do |item| break unless yield item n += 1 end take(n) end |
#union(other) ⇒ SortedSet Also known as: |, +, merge
Return a new SortedSet
which contains all the members of both this set and other
.
other
can be any Enumerable
object.
631 632 633 |
# File 'lib/immutable/sorted_set.rb', line 631 def union(other) self.class.alloc(@node.bulk_insert(other)) end |
#up_to(item) ⇒ SortedSet #up_to(item) {|item| ... } ⇒ nil
Select elements less than or equal to a value.
881 882 883 884 885 886 887 |
# File 'lib/immutable/sorted_set.rb', line 881 def up_to(item, &block) if block_given? @node.each_less(item, true, &block) else self.class.alloc(@node.prefix(item, true)) end end |
#values_at(*indices) ⇒ SortedSet
Return a new SortedSet
with only the elements at the given indices
.
If any of the indices
do not exist, they will be skipped.
360 361 362 363 |
# File 'lib/immutable/sorted_set.rb', line 360 def values_at(*indices) indices.select! { |i| i >= -@node.size && i < @node.size } self.class.new(indices.map! { |i| at(i) }) end |