class Hamster::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:

Hamster::SortedSet.new([1, 2, 3]) # any Enumerable can be used to initialize
Hamster::SortedSet['A', 'B', 'C', 'D']

Or if you want to use a custom ordering:

Hamster::SortedSet.new([1,2,3]) { |a, b| -a <=> -b }
Hamster::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 Hamster 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/hamster/sorted_set.rb, line 61
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/hamster/sorted_set.rb, line 78
def alloc(node)
  result = allocate
  result.instance_variable_set(:@node, node)
  result
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/hamster/sorted_set.rb, line 69
def empty
  @empty ||= self.alloc(PlainAVLNode::EmptyNode)
end
new(items=[], &block) click to toggle source
# File lib/hamster/sorted_set.rb, line 85
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
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 = Hamster::SortedSet[2, 4, 6, 8, 10]
  s.above(6)
  # => Hamster::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 = Hamster::SortedSet[2, 4, 6, 8, 10]
  s.above(6) { |e| puts "Element: #{e}" }

  Element: 8
  Element: 10
  # => nil

@param item [Object]

# File lib/hamster/sorted_set.rb, line 760
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

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

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

# File lib/hamster/sorted_set.rb, line 128
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

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

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

# File lib/hamster/sorted_set.rb, line 148
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 = Hamster::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/hamster/sorted_set.rb, line 212
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 = Hamster::SortedSet[2, 4, 6, 8, 10]
  s.below(6)
  # => Hamster::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 = Hamster::SortedSet[2, 4, 6, 8, 10]
  s.below(6) { |e| puts "Element: #{e}" }

  Element: 2
  Element: 4 
  # => nil

@param item [Object]

# File lib/hamster/sorted_set.rb, line 791
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 = Hamster::SortedSet[2, 4, 6, 8, 10]
  s.between(5, 8)
  # => Hamster::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 = Hamster::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/hamster/sorted_set.rb, line 891
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/hamster/sorted_set.rb, line 913
def clear
  if @node.natural_order?
    self.class.empty
  else
    self.class.alloc(@node.clear)
  end
end
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

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

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

# File lib/hamster/sorted_set.rb, line 161
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

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

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

# File lib/hamster/sorted_set.rb, line 184
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

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

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

# File lib/hamster/sorted_set.rb, line 197
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

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

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

# File lib/hamster/sorted_set.rb, line 637
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

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

@param other [Enumerable] @return [Boolean]

# File lib/hamster/sorted_set.rb, line 714
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

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

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

# File lib/hamster/sorted_set.rb, line 542
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

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

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

# File lib/hamster/sorted_set.rb, line 568
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
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

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

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

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

# File lib/hamster/sorted_set.rb, line 357
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/hamster/sorted_set.rb, line 104
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/hamster/sorted_set.rb, line 925
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

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

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

# File lib/hamster/sorted_set.rb, line 652
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
  v = Hamster::SortedSet["A", "B", "C", "D"]
  v.fetch(2)       # => "C"
  v.fetch(-1)      # => "D"
  v.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
  v = Hamster::SortedSet["A", "B", "C", "D"]
  v.fetch(2) { |i| i * i }   # => "C"
  v.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
  v = Hamster::SortedSet["A", "B", "C", "D"]
  v.fetch(2, "Z")  # => "C"
  v.fetch(4, "Z")  # => "Z"

@return [Object]

# File lib/hamster/sorted_set.rb, line 257
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 = Hamster::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 = Hamster::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/hamster/sorted_set.rb, line 510
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/hamster/sorted_set.rb, line 397
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 = Hamster::SortedSet[2, 4, 6, 8, 10]
  s.from(6)
  # => Hamster::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 = Hamster::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/hamster/sorted_set.rb, line 823
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/hamster/sorted_set.rb, line 939
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

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

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

# File lib/hamster/sorted_set.rb, line 464
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

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

@param other [Enumerable] @return [Boolean]

# File lib/hamster/sorted_set.rb, line 730
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

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

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

# File lib/hamster/sorted_set.rb, line 623
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/hamster/sorted_set.rb, line 416
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

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

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

Calls superclass method
# File lib/hamster/sorted_set.rb, line 448
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/hamster/sorted_set.rb, line 945
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/hamster/sorted_set.rb, line 954
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

Hamster::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/hamster/sorted_set.rb, line 410
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

Hamster::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/hamster/sorted_set.rb, line 391
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

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

@param other [Enumerable] @return [Boolean]

# File lib/hamster/sorted_set.rb, line 689
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

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

@param other [Enumerable] @return [Boolean]

# File lib/hamster/sorted_set.rb, line 703
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

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

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

@return [self]

# File lib/hamster/sorted_set.rb, line 376
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

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

@return [Object]

# File lib/hamster/sorted_set.rb, line 905
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

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

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

# File lib/hamster/sorted_set.rb, line 429
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

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

@return [Integer]

# File lib/hamster/sorted_set.rb, line 114
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 = Hamster::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 = Hamster::SortedSet["A", "B", "C", "D", "E", "F"]
  s[2, 3]  # => Hamster::SortedSet["C", "D", "E"]
  s[-2, 3] # => Hamster::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 = Hamster::SortedSet["A", "B", "C", "D", "E", "F"]
  s[2..3]    # => Hamster::SortedSet["C", "D"]
  s[-2..100] # => Hamster::SortedSet["E", "F"]
  s[20..21]  # => nil
# File lib/hamster/sorted_set.rb, line 309
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

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

@return [SortedSet]

# File lib/hamster/sorted_set.rb, line 479
def sort(&block)
  if block
    self.class.new(self.to_a, &block)
  else
    self.class.new(self.to_a.sort)
  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

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

@param other [Enumerable] @return [Boolean]

# File lib/hamster/sorted_set.rb, line 664
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

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

@param other [Enumerable] @return [Boolean]

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

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

@example

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

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

# File lib/hamster/sorted_set.rb, line 554
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

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

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

# File lib/hamster/sorted_set.rb, line 588
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

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

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

# File lib/hamster/sorted_set.rb, line 607
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 = Hamster::SortedSet[2, 4, 6, 8, 10]
  s.upto(6)
  # => Hamster::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 = Hamster::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/hamster/sorted_set.rb, line 857
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 = Hamster::SortedSet["A", "B", "C", "D", "E", "F"]
s.values_at(2, 4, 5)   # => Hamster::SortedSet["C", "E", "F"]

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

# File lib/hamster/sorted_set.rb, line 338
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/hamster/sorted_set.rb, line 976
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/hamster/sorted_set.rb, line 960
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