class Immutable::SortedSet

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.

Public Class Methods

[](*items) click to toggle source

Create a new `SortedSet` populated with the given items. This method does not accept a comparator block.

@return [SortedSet]

# File lib/immutable/sorted_set.rb, line 59
def [](*items)
  new(items)
end
alloc(node) click to toggle source

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

@return [Set] @private

# File lib/immutable/sorted_set.rb, line 76
def alloc(node)
  allocate.tap { |s| s.instance_variable_set(:@node, node) }.freeze
end
empty() click to toggle source

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

@return [SortedSet]

# File lib/immutable/sorted_set.rb, line 67
def empty
  @empty ||= self.alloc(PlainAVLNode::EmptyNode)
end
new(items=[], &block) click to toggle source
# File lib/immutable/sorted_set.rb, line 101
def initialize(items=[], &block)
  items = items.to_a
  if block
    if block.arity == 1 || block.arity == -1
      items = items.uniq(&block)
      items.sort_by!(&block)
      comparator = lambda { |a,b| block.call(a) <=> block.call(b) }
    else
      items = items.sort(&block)
      SortedSet.uniq_by_comparator!(items, block)
      comparator = block
    end
    @node = AVLNode.from_items(items, comparator)
  else
    @node = PlainAVLNode.from_items(items.uniq.sort!)
  end
  freeze
end
uniq_by_comparator!(array, comparator) click to toggle source

@private Unfortunately, Ruby's stdlib doesn't do this for us array must be sorted

# File lib/immutable/sorted_set.rb, line 83
def uniq_by_comparator!(array, comparator)
  to_check, shift, sz, prev_obj = 1, 0, array.size, array[0]
  while to_check < sz
    next_obj = array[to_check]
    if comparator.call(prev_obj, next_obj) == 0
      shift += 1
    else
      if shift > 0
        array[to_check - shift] = next_obj
      end
      prev_obj = next_obj
    end
    to_check += 1
  end
  array.pop(shift) if shift > 0
end

Public Instance Methods

&(other)
Alias for: intersection
+(other)
Alias for: union
-(other)
Alias for: difference
<<(item)
Alias for: add
[](arg, length = (missing_length = true))
Alias for: slice
^(other)
Alias for: exclusion
above(item, &block) click to toggle source

Select elements greater than a value.

@overload above(item)

Return a new `SortedSet` containing all items greater than `item`.
@return [SortedSet]
@example
  s = Immutable::SortedSet[2, 4, 6, 8, 10]
  s.above(6)
  # => Immutable::SortedSet[8, 10]

@overload above(item)

@yield [item] Once for each item greater than `item`, in order from
              lowest to highest.
@return [nil]
@example
  s = Immutable::SortedSet[2, 4, 6, 8, 10]
  s.above(6) { |e| puts "Element: #{e}" }

  Element: 8
  Element: 10
  # => nil

@param item [Object]

# File lib/immutable/sorted_set.rb, line 781
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) click to toggle source

Return a new `SortedSet` with `item` added. If `item` is already in the set, return `self`.

@example

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

@param item [Object] The object to add @return [SortedSet]

# File lib/immutable/sorted_set.rb, line 147
def add(item)
  catch :present do
    node = @node.insert(item)
    return self.class.alloc(node)
  end
  self
end
Also aliased as: <<
add?(item) click to toggle source

If `item` is not a member of this `SortedSet`, return a new `SortedSet` with `item` added. Otherwise, return `false`.

@example

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

@param item [Object] The object to add @return [SortedSet, false]

# File lib/immutable/sorted_set.rb, line 167
def add?(item)
  !include?(item) && add(item)
end
at(index) click to toggle source

Retrieve the item at `index`. If there is none (either the provided index is too high or too low), return `nil`.

@example

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

@param index [Integer] The index to retrieve @return [Object]

# File lib/immutable/sorted_set.rb, line 231
def at(index)
  index += @node.size if index < 0
  return nil if index >= @node.size || index < 0
  @node.at(index)
end
below(item, &block) click to toggle source

Select elements less than a value.

@overload below(item)

Return a new `SortedSet` containing all items less than `item`.
@return [SortedSet]
@example
  s = Immutable::SortedSet[2, 4, 6, 8, 10]
  s.below(6)
  # => Immutable::SortedSet[2, 4]

@overload below(item)

@yield [item] Once for each item less than `item`, in order from lowest
              to highest.
@return [nil]
@example
  s = Immutable::SortedSet[2, 4, 6, 8, 10]
  s.below(6) { |e| puts "Element: #{e}" }

  Element: 2
  Element: 4 
  # => nil

@param item [Object]

# File lib/immutable/sorted_set.rb, line 812
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, &block) click to toggle source

Select elements between two values.

@overload between(from, to)

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

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

@overload between(item)

@yield [item] Once for each item less than or equal to `to` and greater
              than or equal to `from`, in order from lowest to highest.
@return [nil]
@example
  s = Immutable::SortedSet[2, 4, 6, 8, 10]
  s.between(5, 8) { |e| puts "Element: #{e}" }

  Element: 6
  Element: 8 
  # => nil

@param from [Object] @param to [Object]

# File lib/immutable/sorted_set.rb, line 912
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() click to toggle source

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.

@return [SortedSet]

# File lib/immutable/sorted_set.rb, line 934
def clear
  if @node.natural_order?
    self.class.empty
  else
    self.class.alloc(@node.clear)
  end
end
clone()
Alias for: dup
collect()
Alias for: map
delete(item) click to toggle source

Return a new `SortedSet` with `item` removed. If `item` is not a member of the set, return `self`.

@example

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

@param item [Object] The object to remove @return [SortedSet]

# File lib/immutable/sorted_set.rb, line 180
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) click to toggle source

If `item` is a member of this `SortedSet`, return a new `SortedSet` with `item` removed. Otherwise, return `false`.

@example

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

@param item [Object] The object to remove @return [SortedSet, false]

# File lib/immutable/sorted_set.rb, line 203
def delete?(item)
  include?(item) && delete(item)
end
delete_at(index) click to toggle source

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

@example

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

@param index [Integer] The index to remove @return [SortedSet]

# File lib/immutable/sorted_set.rb, line 216
def delete_at(index)
  (item = at(index)) ? delete(item) : self
end
difference(other) click to toggle source

Return a new `SortedSet` with all the items in `other` removed. `other` can be any `Enumerable` object.

@example

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

@param other [Enumerable] The collection to subtract from this set @return [SortedSet]

# File lib/immutable/sorted_set.rb, line 658
def difference(other)
  self.class.alloc(@node.bulk_delete(other))
end
Also aliased as: subtract, -
disjoint?(other) click to toggle source

Return `true` if this set and `other` do not share any items.

@example

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

@param other [Enumerable] @return [Boolean]

# File lib/immutable/sorted_set.rb, line 735
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) click to toggle source

Drop the first `n` elements and return the rest in a new `SortedSet`.

@example

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

@param n [Integer] The number of elements to remove @return [SortedSet]

# File lib/immutable/sorted_set.rb, line 563
def drop(n)
  derive_new_sorted_set(@node.drop(n))
end
drop_while() { |item| ... } click to toggle source

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.

@example

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

@yield [item] @return [SortedSet, Enumerator]

# File lib/immutable/sorted_set.rb, line 589
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() click to toggle source

Return `self`. Since this is an immutable object duplicates are equivalent. @return [SortedSet]

# File lib/immutable/sorted_set.rb, line 967
def dup
  self
end
Also aliased as: clone
each(&block) click to toggle source

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

@example

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

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

@yield [item] @return [self, Enumerator]

# File lib/immutable/sorted_set.rb, line 376
def each(&block)
  return @node.to_enum if not block_given?
  @node.each(&block)
  self
end
empty?() click to toggle source

Return `true` if this `SortedSet` contains no items.

@return [Boolean]

# File lib/immutable/sorted_set.rb, line 123
def empty?
  @node.empty?
end
eql?(other) click to toggle source

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

@param other [Object] The object to compare with @return [Boolean]

# File lib/immutable/sorted_set.rb, line 946
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) click to toggle source

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.

@example

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

@param other [Enumerable] The collection to take the exclusive disjunction of @return [SortedSet]

# File lib/immutable/sorted_set.rb, line 673
def exclusion(other)
  ((self | other) - (self & other))
end
Also aliased as: ^
fetch(index, default = (missing_default = true)) { |index| ... } click to toggle source

Retrieve the value at `index` with optional default.

@overload fetch(index)

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

@param index [Integer] The index to look up
@raise [IndexError] if index does not exist
@example
  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

@overload fetch(index) { |index| … }

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

@yield Once if the index is not found.
@yieldparam [Integer] index The index which does not exist
@yieldreturn [Object] Default value to return
@param index [Integer] The index to look up
@example
  s = Immutable::SortedSet["A", "B", "C", "D"]
  s.fetch(2) { |i| i * i }   # => "C"
  s.fetch(4) { |i| i * i }   # => 16

@overload fetch(index, default)

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

@param index [Integer] The index to look up
@param default [Object] Object to return if the key is not found
@example
  s = Immutable::SortedSet["A", "B", "C", "D"]
  s.fetch(2, "Z")  # => "C"
  s.fetch(4, "Z")  # => "Z"

@return [Object]

# File lib/immutable/sorted_set.rb, line 276
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_all()
Alias for: select
find_index(obj = (missing_obj = true), &block) click to toggle source

Find the index of a given object or an element that satisfies the given block.

@overload find_index(obj)

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)`.
@param obj [Object] The object to search for
@example
  s = Immutable::SortedSet[2, 4, 6, 8, 10]
  s.find_index(8)  # => 3

@overload find_index

Return the index of the first object in this sorted set for which the
block returns to true. This takes `O(N)` time.
@yield [element] An element in the sorted set
@yieldreturn [Boolean] True if this is element matches
@example
  s = Immutable::SortedSet[2, 4, 6, 8, 10]
  s.find_index { |e| e > 7 }  # => 3

@return [Integer] The index of the object, or `nil` if not found.

Calls superclass method
# File lib/immutable/sorted_set.rb, line 531
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
Also aliased as: index
first() click to toggle source

Return the “lowest” element in this set, as determined by its sort order. @return [Object]

# File lib/immutable/sorted_set.rb, line 416
def first
  @node.min
end
from(item, &block) click to toggle source

Select elements greater than or equal to a value.

@overload from(item)

Return a new `SortedSet` containing all items greater than or equal `item`.
@return [SortedSet]
@example
  s = Immutable::SortedSet[2, 4, 6, 8, 10]
  s.from(6)
  # => Immutable::SortedSet[6, 8, 10]

@overload from(item)

@yield [item] Once for each item greater than or equal to `item`, in
              order from lowest to highest.
@return [nil]
@example
  s = Immutable::SortedSet[2, 4, 6, 8, 10]
  s.from(6) { |e| puts "Element: #{e}" }

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

@param item [Object]

# File lib/immutable/sorted_set.rb, line 844
def from(item, &block)
  if block_given?
    @node.each_greater(item, true, &block)
  else
    self.class.alloc(@node.suffix(item, true))
  end
end
hash() click to toggle source

See `Object#hash`. @return [Integer]

# File lib/immutable/sorted_set.rb, line 960
def hash
  reduce(0) { |hash, item| (hash << 5) - hash + item.hash }
end
include?(item) click to toggle source

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.

@example

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

@param item [Object] The object to check for @return [Boolean]

# File lib/immutable/sorted_set.rb, line 483
def include?(item)
  @node.include?(item)
end
Also aliased as: member?
index(obj = (missing_obj = true), &block)
Alias for: find_index
intersect?(other) click to toggle source

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

@example

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

@param other [Enumerable] @return [Boolean]

# File lib/immutable/sorted_set.rb, line 751
def intersect?(other)
  !disjoint?(other)
end
intersection(other) click to toggle source

Return a new `SortedSet` which contains all the items which are members of both this set and `other`. `other` can be any `Enumerable` object.

@example

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

@param other [Enumerable] The collection to intersect with @return [SortedSet]

# File lib/immutable/sorted_set.rb, line 644
def intersection(other)
  self.class.alloc(@node.keep_only(other))
end
Also aliased as: &
keep_if()
Alias for: select
last() click to toggle source

Return the “highest” element in this set, as determined by its sort order. @return [Object]

# File lib/immutable/sorted_set.rb, line 435
def last
  @node.max
end
length()
Alias for: size
map() click to toggle source

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

@example

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

@return [SortedSet, Enumerator] @yield [item] Once for each item.

Calls superclass method
# File lib/immutable/sorted_set.rb, line 467
def map
  return enum_for(:map) if not block_given?
  return self if empty?
  self.class.alloc(@node.from_items(super))
end
Also aliased as: collect
marshal_dump() click to toggle source

@return [::Array] @private

# File lib/immutable/sorted_set.rb, line 974
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) click to toggle source

@private

# File lib/immutable/sorted_set.rb, line 983
def marshal_load(array)
  initialize(array)
end
max() click to toggle source

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

@example

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

@yield [a, b] Any number of times with different pairs of elements. @return [Object]

Calls superclass method
# File lib/immutable/sorted_set.rb, line 429
def max
  block_given? ? super : @node.max
end
member?(item)
Alias for: include?
merge(other)
Alias for: union
min() click to toggle source

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

@example

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

@return [Object] @yield [a, b] Any number of times with different pairs of elements.

Calls superclass method
# File lib/immutable/sorted_set.rb, line 410
def min
  block_given? ? super : @node.min
end
proper_subset?(other) click to toggle source

Returns `true` if `other` contains all the items in this set, plus at least one item which is not in this set.

@example

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

@param other [Enumerable] @return [Boolean]

# File lib/immutable/sorted_set.rb, line 710
def proper_subset?(other)
  return false if other.size <= size
  all? { |item| other.include?(item) }
end
proper_superset?(other) click to toggle source

Returns `true` if this set contains all the items in `other`, plus at least one item which is not in `other`.

@example

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

@param other [Enumerable] @return [Boolean]

# File lib/immutable/sorted_set.rb, line 724
def proper_superset?(other)
  other.proper_subset?(self)
end
reverse_each(&block) click to toggle source

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.

@example

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

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

@return [self]

# File lib/immutable/sorted_set.rb, line 395
def reverse_each(&block)
  return @node.enum_for(:reverse_each) if not block_given?
  @node.reverse_each(&block)
  self
end
sample() click to toggle source

Return a randomly chosen item from this set. If the set is empty, return `nil`.

@example

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

@return [Object]

# File lib/immutable/sorted_set.rb, line 926
def sample
  @node.at(rand(@node.size))
end
select() { |item| ... } click to toggle source

Return a new `SortedSet` containing all elements for which the given block returns true.

@example

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

@return [SortedSet] @yield [item] Once for each item.

# File lib/immutable/sorted_set.rb, line 448
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
Also aliased as: find_all, keep_if
size() click to toggle source

Return the number of items in this `SortedSet`.

@example

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

@return [Integer]

# File lib/immutable/sorted_set.rb, line 133
def size
  @node.size
end
Also aliased as: length
slice(arg, length = (missing_length = true)) click to toggle source

Return specific objects from the `Vector`. All overloads return `nil` if the starting index is out of range.

@overload set.slice(index)

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

@param index [Integer] The index to retrieve. May be negative.
@return [Object]
@example
  s = Immutable::SortedSet["A", "B", "C", "D", "E", "F"]
  s[2]  # => "C"
  s[-1] # => "F"
  s[6]  # => nil

@overload set.slice(index, length)

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

@param start [Integer] The index to start retrieving items from. May be
                       negative.
@param length [Integer] The number of items to retrieve.
@return [SortedSet]
@example
  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

@overload set.slice(index..end)

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

@param range [Range] The range of indices to retrieve.
@return [SortedSet]
@example
  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
# File lib/immutable/sorted_set.rb, line 328
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
Also aliased as: []
sort(&block) click to toggle source

Return a new `SortedSet` with the same items, but a sort order determined by the given block.

@example

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"]

@return [SortedSet]

# File lib/immutable/sorted_set.rb, line 498
def sort(&block)
  if block
    self.class.new(self.to_a, &block)
  elsif @node.natural_order?
    self
  else
    self.class.new(self)
  end
end
Also aliased as: sort_by
sort_by(&block)
Alias for: sort
subset?(other) click to toggle source

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

@example

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

@param other [Enumerable] @return [Boolean]

# File lib/immutable/sorted_set.rb, line 685
def subset?(other)
  return false if other.size < size
  all? { |item| other.include?(item) }
end
subtract(other)
Alias for: difference
superset?(other) click to toggle source

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

@example

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

@param other [Enumerable] @return [Boolean]

# File lib/immutable/sorted_set.rb, line 697
def superset?(other)
  other.subset?(self)
end
take(n) click to toggle source

Return only the first `n` elements in a new `SortedSet`.

@example

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

@param n [Integer] The number of elements to retain @return [SortedSet]

# File lib/immutable/sorted_set.rb, line 575
def take(n)
  derive_new_sorted_set(@node.take(n))
end
take_while() { |item| ... } click to toggle source

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.

@example

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

@return [SortedSet, Enumerator] @yield [item]

# File lib/immutable/sorted_set.rb, line 609
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) click to toggle source

Return a new `SortedSet` which contains all the members of both this set and `other`. `other` can be any `Enumerable` object.

@example

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

@param other [Enumerable] The collection to merge with @return [SortedSet]

# File lib/immutable/sorted_set.rb, line 628
def union(other)
  self.class.alloc(@node.bulk_insert(other))
end
Also aliased as: |, +, merge
up_to(item, &block) click to toggle source

Select elements less than or equal to a value.

@overload up_to(item)

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

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

@overload up_to(item)

@yield [item] Once for each item less than or equal to `item`, in order
              from lowest to highest.
@return [nil]
@example
  s = Immutable::SortedSet[2, 4, 6, 8, 10]
  s.up_to(6) { |e| puts "Element: #{e}" }

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

@param item [Object]

# File lib/immutable/sorted_set.rb, line 878
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) click to toggle source

Return a new `SortedSet` with only the elements at the given `indices`. If any of the `indices` do not exist, they will be skipped.

@example

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

@param indices [Array] The indices to retrieve and gather into a new `SortedSet` @return [SortedSet]

# File lib/immutable/sorted_set.rb, line 357
def values_at(*indices)
  indices.select! { |i| i >= -@node.size && i < @node.size }
  self.class.new(indices.map! { |i| at(i) })
end
|(other)
Alias for: union

Private Instance Methods

derive_new_sorted_set(node) click to toggle source

Return a new `SortedSet` which is derived from this one, using a modified {AVLNode}. The new `SortedSet` will retain the existing comparator, if there is one.

# File lib/immutable/sorted_set.rb, line 1005
def derive_new_sorted_set(node)
  if node.equal?(@node)
    self
  elsif node.empty?
    clear
  else
    self.class.alloc(node)
  end
end
subsequence(from, length) click to toggle source
# File lib/immutable/sorted_set.rb, line 989
def subsequence(from, length)
  return nil if from > @node.size || from < 0 || length < 0
  length = @node.size - from if @node.size < from + length
  if length == 0
    if @node.natural_order?
      return self.class.empty
    else
      return self.class.alloc(@node.clear)
    end
  end
  self.class.alloc(@node.slice(from, length))
end