Class: Immutable::SortedSet

Inherits:
Object
  • Object
show all
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.

Defined Under Namespace

Classes: AVLNode, PlainAVLNode

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Enumerable

#<=>, #==, #compact, #each_index, #grep, #grep_v, #group_by, #inspect, #join, #partition, #pretty_print, #product, #reject, #sum, #to_set

Methods included from Enumerable

#to_list

Constructor Details

#initialize(items = [], &block) ⇒ SortedSet

Returns a new instance of SortedSet.



81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/immutable/sorted_set.rb', line 81

def initialize(items=[], &block)
  items = items.to_a
  if block
    if block.arity == 1 || block.arity == -1
      comparator = lambda { |a,b| block.call(a) <=> block.call(b) }
      items = items.sort_by(&block)
    else
      comparator = block
      items = items.sort(&block)
    end
    @node = AVLNode.from_items(items, comparator)
  else
    @node = PlainAVLNode.from_items(items.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.

Returns:



59
60
61
 
# File 'lib/immutable/sorted_set.rb', line 59

def [](*items)
  new(items)
end

.alloc(node) ⇒ Set

“Raw” allocation of a new SortedSet. Used internally to create a new instance quickly after obtaining a modified binary tree.

Returns:



76
77
78
 
# File 'lib/immutable/sorted_set.rb', line 76

def alloc(node)
  allocate.tap { |s| s.instance_variable_set(:@node, node) }.freeze
end

.empty ⇒ SortedSet

Return an empty SortedSet. If used on a subclass, returns an empty instance of that class.

Returns:



67
68
69
 
# File 'lib/immutable/sorted_set.rb', line 67

def empty
  @empty ||= self.alloc(PlainAVLNode::EmptyNode)
end

Instance Method Details

#above(item) ⇒ SortedSet #above(item) {|item| ... } ⇒ nil

Select elements greater than a value.

Overloads:

  • #above(item) ⇒ SortedSet

    Return a new SortedSet containing all items greater than item.

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.above(6)
# => Immutable::SortedSet[8, 10]

    Returns:

  • #above(item) {|item| ... } ⇒ nil

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.above(6) { |e| puts "Element: #{e}" }

Element: 8
Element: 10
# => nil

    Yields:

    • (item) —

      Once for each item greater than item, in order from lowest to highest.

    Returns:

    • (nil)

Parameters:

  • item (Object) 


757
758
759
760
761
762
763
 
# File 'lib/immutable/sorted_set.rb', line 757

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.

Examples:

Immutable::SortedSet["Dog", "Lion"].add("Elephant")
# => Immutable::SortedSet["Dog", "Elephant", "Lion"]

Parameters:

  • item (Object) —

    The object to add

Returns:



125
126
127
128
129
130
131
 
# File 'lib/immutable/sorted_set.rb', line 125

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.

Examples:

Immutable::SortedSet["Dog", "Lion"].add?("Elephant")
# => Immutable::SortedSet["Dog", "Elephant", "Lion"]
Immutable::SortedSet["Dog", "Lion"].add?("Lion")
# => false

Parameters:

  • item (Object) —

    The object to add

Returns:



145
146
147
 
# File 'lib/immutable/sorted_set.rb', line 145

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.

Examples:

s = Immutable::SortedSet["A", "B", "C", "D", "E", "F"]
s.at(2)   # => "C"
s.at(-2)  # => "E"
s.at(6)   # => nil

Parameters:

  • index (Integer) —

    The index to retrieve

Returns:

  • (Object) 


209
210
211
212
213
 
# File 'lib/immutable/sorted_set.rb', line 209

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.

Overloads:

  • #below(item) ⇒ SortedSet

    Return a new SortedSet containing all items less than item.

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.below(6)
# => Immutable::SortedSet[2, 4]

    Returns:

  • #below(item) {|item| ... } ⇒ nil

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.below(6) { |e| puts "Element: #{e}" }

Element: 2
Element: 4 
# => nil

    Yields:

    • (item) —

      Once for each item less than item, in order from lowest to highest.

    Returns:

    • (nil)

Parameters:

  • item (Object) 


788
789
790
791
792
793
794
 
# File 'lib/immutable/sorted_set.rb', line 788

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.

Overloads:

  • #between(from, to) ⇒ SortedSet

    Return a new SortedSet containing all items less than or equal to to and greater than or equal to from.

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.between(5, 8)
# => Immutable::SortedSet[6, 8]

    Returns:

  • #between(item) {|item| ... } ⇒ nil

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.between(5, 8) { |e| puts "Element: #{e}" }

Element: 6
Element: 8 
# => nil

    Yields:

    • (item) —

      Once for each item less than or equal to to and greater than or equal to from, in order from lowest to highest.

    Returns:

    • (nil)

Parameters:

  • from (Object)
  • to (Object) 


888
889
890
891
892
893
894
 
# File 'lib/immutable/sorted_set.rb', line 888

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.

Returns:



910
911
912
913
914
915
916
 
# File 'lib/immutable/sorted_set.rb', line 910

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.

Examples:

Immutable::SortedSet["A", "B", "C"].delete("B")
# => Immutable::SortedSet["A", "C"]

Parameters:

  • item (Object) —

    The object to remove

Returns:



158
159
160
161
162
163
164
165
166
167
168
 
# File 'lib/immutable/sorted_set.rb', line 158

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.

Examples:

Immutable::SortedSet["A", "B", "C"].delete?("B")
# => Immutable::SortedSet["A", "C"]
Immutable::SortedSet["A", "B", "C"].delete?("Z")
# => false

Parameters:

  • item (Object) —

    The object to remove

Returns:



181
182
183
 
# File 'lib/immutable/sorted_set.rb', line 181

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.

Examples:

Immutable::SortedSet["A", "B", "C", "D"].delete_at(2)
# => Immutable::SortedSet["A", "B", "D"]

Parameters:

  • index (Integer) —

    The index to remove

Returns:



194
195
196
 
# File 'lib/immutable/sorted_set.rb', line 194

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.

Examples:

Immutable::SortedSet[1, 2] - Immutable::SortedSet[2, 3]
# => Immutable::SortedSet[1]

Parameters:

  • other (Enumerable) —

    The collection to subtract from this set

Returns:



634
635
636
 
# File 'lib/immutable/sorted_set.rb', line 634

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.

Examples:

Immutable::SortedSet[1, 2].disjoint?(Immutable::SortedSet[3, 4])  # => true

Parameters:

Returns:

  • (Boolean) 


711
712
713
714
715
716
717
718
 
# File 'lib/immutable/sorted_set.rb', line 711

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.

Examples:

Immutable::SortedSet["A", "B", "C", "D", "E", "F"].drop(2)
# => Immutable::SortedSet["C", "D", "E", "F"]

Parameters:

  • n (Integer) —

    The number of elements to remove

Returns:



539
540
541
 
# File 'lib/immutable/sorted_set.rb', line 539

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.

Examples:

Immutable::SortedSet[2, 4, 6, 7, 8, 9].drop_while { |e| e.even? }
# => Immutable::SortedSet[7, 8, 9]

Yields:

  • (item)

Returns:



565
566
567
568
569
570
571
572
573
 
# File 'lib/immutable/sorted_set.rb', line 565

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.

Returns:



943
944
945
 
# File 'lib/immutable/sorted_set.rb', line 943

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.

Examples:

Immutable::SortedSet["A", "B", "C"].each { |e| puts "Element: #{e}" }

Element: A
Element: B
Element: C
# => Immutable::SortedSet["A", "B", "C"]

Yields:

  • (item)

Returns:

  • (self, Enumerator) 


354
355
356
357
358
 
# File 'lib/immutable/sorted_set.rb', line 354

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.

Returns:

  • (Boolean) 


101
102
103
 
# File 'lib/immutable/sorted_set.rb', line 101

def empty?
  @node.empty?
end

#eql?(other) ⇒ Boolean

Return true if other has the same type and contents as this SortedSet.

Parameters:

  • other (Object) —

    The object to compare with

Returns:

  • (Boolean) 


922
923
924
925
926
927
928
929
930
931
932
 
# File 'lib/immutable/sorted_set.rb', line 922

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 = self.to_enum, other.to_enum
  while true
    return false if !a.next.eql?(b.next)
  end
rescue StopIteration
  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.

Examples:

Immutable::SortedSet[1, 2] ^ Immutable::SortedSet[2, 3]
# => Immutable::SortedSet[1, 3]

Parameters:

  • other (Enumerable) —

    The collection to take the exclusive disjunction of

Returns:



649
650
651
 
# File 'lib/immutable/sorted_set.rb', line 649

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.

Overloads:

  • #fetch(index) ⇒ Object

    Retrieve the value at the given index, or raise an IndexError if not found.

    Examples:

    s = Immutable::SortedSet["A", "B", "C", "D"]
s.fetch(2)       # => "C"
s.fetch(-1)      # => "D"
s.fetch(4)       # => IndexError: index 4 outside of vector bounds

    Parameters:

    • index (Integer) —

      The index to look up

    Raises:

    • (IndexError) —

      if index does not exist

  • #fetch(index) {|index| ... } ⇒ Object

    Retrieve the value at the given index, or return the result of yielding the block if not found.

    Examples:

    s = Immutable::SortedSet["A", "B", "C", "D"]
s.fetch(2) { |i| i * i }   # => "C"
s.fetch(4) { |i| i * i }   # => 16

    Parameters:

    • index (Integer) —

      The index to look up

    Yields:

    • Once if the index is not found.

    Yield Parameters:

    • index (Integer) —

      The index which does not exist

    Yield Returns:

    • (Object) —

      Default value to return

  • #fetch(index, default) ⇒ Object

    Retrieve the value at the given index, or return the provided default value if not found.

    Examples:

    s = Immutable::SortedSet["A", "B", "C", "D"]
s.fetch(2, "Z")  # => "C"
s.fetch(4, "Z")  # => "Z"

    Parameters:

    • index (Integer) —

      The index to look up

    • default (Object) —

      Object to return if the key is not found

Returns:

  • (Object) 


254
255
256
257
258
259
260
261
262
263
264
 
# File 'lib/immutable/sorted_set.rb', line 254

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.

Overloads:

  • #find_index(obj) ⇒ Integer

    Return the index of the first object in this set which is equal to obj. Rather than using ‘#==`, we use `#<=>` (or our comparator block) for comparisons. This means we can find the index in `O(log N)` time, rather than `O(N)`.

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.find_index(8)  # => 3

    Parameters:

    • obj (Object) —

      The object to search for

  • #find_index {|element| ... } ⇒ Integer

    Return the index of the first object in this sorted set for which the block returns to true. This takes ‘O(N)` time.

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.find_index { |e| e > 7 }  # => 3

    Yields:

    • (element) —

      An element in the sorted set

    Yield Returns:

    • (Boolean) —

      True if this is element matches

Returns:

  • (Integer) —

    The index of the object, or nil if not found.



507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
 
# File 'lib/immutable/sorted_set.rb', line 507

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.

Returns:

  • (Object) 


394
395
396
 
# File 'lib/immutable/sorted_set.rb', line 394

def first
  @node.min
end

#from(item) ⇒ SortedSet #from(item) {|item| ... } ⇒ nil

Select elements greater than or equal to a value.

Overloads:

  • #from(item) ⇒ SortedSet

    Return a new SortedSet containing all items greater than or equal item.

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.from(6)
# => Immutable::SortedSet[6, 8, 10]

    Returns:

  • #from(item) {|item| ... } ⇒ nil

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.from(6) { |e| puts "Element: #{e}" }

Element: 6
Element: 8
Element: 10
# => nil

    Yields:

    • (item) —

      Once for each item greater than or equal to item, in order from lowest to highest.

    Returns:

    • (nil)

Parameters:

  • item (Object) 


820
821
822
823
824
825
826
 
# File 'lib/immutable/sorted_set.rb', line 820

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

Returns:

  • (Integer) 


936
937
938
 
# File 'lib/immutable/sorted_set.rb', line 936

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.

Examples:

Immutable::SortedSet["A", "B", "C"].include?("B")  # => true

Parameters:

  • item (Object) —

    The object to check for

Returns:

  • (Boolean) 


461
462
463
 
# File 'lib/immutable/sorted_set.rb', line 461

def include?(item)
  @node.include?(item)
end

#intersect?(other) ⇒ Boolean

Return true if this set and other have at least one item in common.

Examples:

Immutable::SortedSet[1, 2].intersect?(Immutable::SortedSet[2, 3])  # => true

Parameters:

Returns:

  • (Boolean) 


727
728
729
 
# File 'lib/immutable/sorted_set.rb', line 727

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.

Examples:

Immutable::SortedSet[1, 2] & Immutable::SortedSet[2, 3]
# => Immutable::SortedSet[2]

Parameters:

  • other (Enumerable) —

    The collection to intersect with

Returns:



620
621
622
 
# File 'lib/immutable/sorted_set.rb', line 620

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.

Returns:

  • (Object) 


413
414
415
 
# File 'lib/immutable/sorted_set.rb', line 413

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.

Examples:

Immutable::SortedSet[1, 2, 3].map { |e| -(e * e) }
# => Immutable::SortedSet[-9, -4, -1]

Yields:

  • (item) —

    Once for each item.

Returns:



445
446
447
448
449
 
# File 'lib/immutable/sorted_set.rb', line 445

def map
  return enum_for(:map) if not block_given?
  return self if empty?
  self.class.alloc(@node.from_items(super))
end

#marshal_dump ⇒ ::Array

Returns:

  • (::Array) 


950
951
952
953
954
955
956
 
# File 'lib/immutable/sorted_set.rb', line 950

def marshal_dump
  if @node.natural_order?
    to_a
  else
    raise TypeError, "can't dump SortedSet with custom sort order"
  end
end

#marshal_load(array) ⇒ Object 



959
960
961
 
# File 'lib/immutable/sorted_set.rb', line 959

def marshal_load(array)
  initialize(array)
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`.)

Examples:

Immutable::SortedSet["A", "B", "C"].max  # => "C"

Yields:

  • (a, b) —

    Any number of times with different pairs of elements.

Returns:

  • (Object) 


407
408
409
 
# File 'lib/immutable/sorted_set.rb', line 407

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

Examples:

Immutable::SortedSet["A", "B", "C"].min  # => "A"

Yields:

  • (a, b) —

    Any number of times with different pairs of elements.

Returns:

  • (Object) 


388
389
390
 
# File 'lib/immutable/sorted_set.rb', line 388

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.

Examples:

Immutable::SortedSet[2, 3].proper_subset?(Immutable::SortedSet[1, 2, 3])     # => true
Immutable::SortedSet[1, 2, 3].proper_subset?(Immutable::SortedSet[1, 2, 3])  # => false

Parameters:

Returns:

  • (Boolean) 


686
687
688
689
 
# File 'lib/immutable/sorted_set.rb', line 686

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.

Examples:

Immutable::SortedSet[1, 2, 3].proper_superset?(Immutable::SortedSet[2, 3])     # => true
Immutable::SortedSet[1, 2, 3].proper_superset?(Immutable::SortedSet[1, 2, 3])  # => false

Parameters:

Returns:

  • (Boolean) 


700
701
702
 
# File 'lib/immutable/sorted_set.rb', line 700

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.

Examples:

Immutable::SortedSet["A", "B", "C"].reverse_each { |e| puts "Element: #{e}" }

Element: C
Element: B
Element: A
# => Immutable::SortedSet["A", "B", "C"]

Returns:

  • (self) 


373
374
375
376
377
 
# File 'lib/immutable/sorted_set.rb', line 373

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.

Examples:

Immutable::SortedSet[1, 2, 3, 4, 5].sample  # => 2

Returns:

  • (Object) 


902
903
904
 
# File 'lib/immutable/sorted_set.rb', line 902

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.

Examples:

Immutable::SortedSet["Bird", "Cow", "Elephant"].select { |e| e.size >= 4 }
# => Immutable::SortedSet["Bird", "Elephant"]

Yields:

  • (item) —

    Once for each item.

Returns:



426
427
428
429
430
431
 
# File 'lib/immutable/sorted_set.rb', line 426

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.

Examples:

Immutable::SortedSet["A", "B", "C"].size # => 3

Returns:

  • (Integer) 


111
112
113
 
# File 'lib/immutable/sorted_set.rb', line 111

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.

Overloads:

  • #set.slice(index) ⇒ Object

    Returns a single object at the given index. If index is negative, count backwards from the end.

    Examples:

    s = Immutable::SortedSet["A", "B", "C", "D", "E", "F"]
s[2]  # => "C"
s[-1] # => "F"
s[6]  # => nil

    Parameters:

    • index (Integer) —

      The index to retrieve. May be negative.

    Returns:

    • (Object)
  • #set.slice(index, length) ⇒ SortedSet

    Return a subset starting at index and continuing for length elements or until the end of the SortedSet, whichever occurs first.

    Examples:

    s = Immutable::SortedSet["A", "B", "C", "D", "E", "F"]
s[2, 3]  # => Immutable::SortedSet["C", "D", "E"]
s[-2, 3] # => Immutable::SortedSet["E", "F"]
s[20, 1] # => nil

    Parameters:

    • start (Integer) —

      The index to start retrieving items from. May be negative.

    • length (Integer) —

      The number of items to retrieve.

    Returns:

  • #set.slice(index..end) ⇒ SortedSet

    Return a subset starting at index and continuing to index end or the end of the SortedSet, whichever occurs first.

    Examples:

    s = Immutable::SortedSet["A", "B", "C", "D", "E", "F"]
s[2..3]    # => Immutable::SortedSet["C", "D"]
s[-2..100] # => Immutable::SortedSet["E", "F"]
s[20..21]  # => nil

    Parameters:

    • range (Range) —

      The range of indices to retrieve.

    Returns:



306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
 
# File 'lib/immutable/sorted_set.rb', line 306

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.

Examples:

Immutable::SortedSet["Bird", "Cow", "Elephant"].sort { |a, b| a.size <=> b.size }
# => Immutable::SortedSet["Cow", "Bird", "Elephant"]
Immutable::SortedSet["Bird", "Cow", "Elephant"].sort_by { |e| e.size }
# => Immutable::SortedSet["Cow", "Bird", "Elephant"]

Returns:



476
477
478
479
480
481
482
 
# File 'lib/immutable/sorted_set.rb', line 476

def sort(&block)
  if block
    self.class.new(self.to_a, &block)
  else
    self.class.new(self.to_a.sort)
  end      
end

#subset?(other) ⇒ Boolean

Return true if all items in this set are also in other.

Examples:

Immutable::SortedSet[2, 3].subset?(Immutable::SortedSet[1, 2, 3])  # => true

Parameters:

Returns:

  • (Boolean) 


661
662
663
664
 
# File 'lib/immutable/sorted_set.rb', line 661

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.

Examples:

Immutable::SortedSet[1, 2, 3].superset?(Immutable::SortedSet[2, 3])  # => true

Parameters:

Returns:

  • (Boolean) 


673
674
675
 
# File 'lib/immutable/sorted_set.rb', line 673

def superset?(other)
  other.subset?(self)
end

#take(n) ⇒ SortedSet

Return only the first n elements in a new SortedSet.

Examples:

Immutable::SortedSet["A", "B", "C", "D", "E", "F"].take(4)
# => Immutable::SortedSet["A", "B", "C", "D"]

Parameters:

  • n (Integer) —

    The number of elements to retain

Returns:



551
552
553
 
# File 'lib/immutable/sorted_set.rb', line 551

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.

Examples:

Immutable::SortedSet[2, 4, 6, 7, 8, 9].take_while { |e| e.even? }
# => Immutable::SortedSet[2, 4, 6]

Yields:

  • (item)

Returns:



585
586
587
588
589
590
591
592
593
 
# File 'lib/immutable/sorted_set.rb', line 585

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.

Examples:

Immutable::SortedSet[1, 2] | Immutable::SortedSet[2, 3]
# => Immutable::SortedSet[1, 2, 3]

Parameters:

  • other (Enumerable) —

    The collection to merge with

Returns:



604
605
606
 
# File 'lib/immutable/sorted_set.rb', line 604

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.

Overloads:

  • #up_to(item) ⇒ SortedSet

    Return a new SortedSet containing all items less than or equal to item.

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.upto(6)
# => Immutable::SortedSet[2, 4, 6]

    Returns:

  • #up_to(item) {|item| ... } ⇒ nil

    Examples:

    s = Immutable::SortedSet[2, 4, 6, 8, 10]
s.up_to(6) { |e| puts "Element: #{e}" }

Element: 2
Element: 4 
Element: 6 
# => nil

    Yields:

    • (item) —

      Once for each item less than or equal to item, in order from lowest to highest.

    Returns:

    • (nil)

Parameters:

  • item (Object) 


854
855
856
857
858
859
860
 
# File 'lib/immutable/sorted_set.rb', line 854

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.

Examples:

s = Immutable::SortedSet["A", "B", "C", "D", "E", "F"]
s.values_at(2, 4, 5)   # => Immutable::SortedSet["C", "E", "F"]

Parameters:

  • indices (Array) —

    The indices to retrieve and gather into a new SortedSet

Returns:



335
336
337
338
 
# File 'lib/immutable/sorted_set.rb', line 335

def values_at(*indices)
  indices.select! { |i| i >= -@node.size && i < @node.size }
  self.class.new(indices.map! { |i| at(i) })
end