Class: Hamster::SortedSet

Inherits:
Object
  • Object
show all
Includes:
Enumerable, Immutable
Defined in:
lib/hamster/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:

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.

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

Methods included from Immutable

included

Constructor Details

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

Returns a new instance of SortedSet.


85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
# 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

Class Method Details

.[](*items) ⇒ SortedSet

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

Returns:


61
62
63
# File 'lib/hamster/sorted_set.rb', line 61

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:


78
79
80
81
82
# File 'lib/hamster/sorted_set.rb', line 78

def alloc(node)
  result = allocate
  result.instance_variable_set(:@node, node)
  result
end

.emptySortedSet

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

Returns:


69
70
71
# File 'lib/hamster/sorted_set.rb', line 69

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 = Hamster::SortedSet[2, 4, 6, 8, 10]
    s.above(6)
    # => Hamster::SortedSet[8, 10]

    Returns:

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

    Examples:

    s = Hamster::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)

760
761
762
763
764
765
766
# 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) ⇒ SortedSet Also known as: <<

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

Examples:

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

Parameters:

  • item (Object)

    The object to add

Returns:


128
129
130
131
132
133
134
# 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

#add?(item) ⇒ SortedSet, false

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

Examples:

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

Parameters:

  • item (Object)

    The object to add

Returns:


148
149
150
# File 'lib/hamster/sorted_set.rb', line 148

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 = Hamster::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)

212
213
214
215
216
# 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) ⇒ 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 = Hamster::SortedSet[2, 4, 6, 8, 10]
    s.below(6)
    # => Hamster::SortedSet[2, 4]

    Returns:

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

    Examples:

    s = Hamster::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)

791
792
793
794
795
796
797
# 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) ⇒ 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 = Hamster::SortedSet[2, 4, 6, 8, 10]
    s.between(5, 8)
    # => Hamster::SortedSet[6, 8]

    Returns:

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

    Examples:

    s = Hamster::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)

891
892
893
894
895
896
897
# 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

#clearSortedSet

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:


913
914
915
916
917
918
919
# 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

#delete(item) ⇒ SortedSet

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

Examples:

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

Parameters:

  • item (Object)

    The object to remove

Returns:


161
162
163
164
165
166
167
168
169
170
171
# 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) ⇒ SortedSet, false

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

Examples:

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

Parameters:

  • item (Object)

    The object to remove

Returns:


184
185
186
# File 'lib/hamster/sorted_set.rb', line 184

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:

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

Parameters:

  • index (Integer)

    The index to remove

Returns:


197
198
199
# File 'lib/hamster/sorted_set.rb', line 197

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:

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

Parameters:

  • other (Enumerable)

    The collection to subtract from this set

Returns:


637
638
639
# File 'lib/hamster/sorted_set.rb', line 637

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:

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

Parameters:

Returns:

  • (Boolean)

714
715
716
717
718
719
720
721
# 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) ⇒ SortedSet

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

Examples:

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

Parameters:

  • n (Integer)

    The number of elements to remove

Returns:


542
543
544
# File 'lib/hamster/sorted_set.rb', line 542

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:

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

Yields:

  • (item)

Returns:


568
569
570
571
572
573
574
575
576
# 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 {|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:

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

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

Yields:

  • (item)

Returns:

  • (self, Enumerator)

357
358
359
360
361
# 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?Boolean

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

Returns:

  • (Boolean)

104
105
106
# File 'lib/hamster/sorted_set.rb', line 104

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)

925
926
927
928
929
930
931
932
933
934
935
# 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) ⇒ 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:

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

Parameters:

  • other (Enumerable)

    The collection to take the exclusive disjunction of

Returns:


652
653
654
# File 'lib/hamster/sorted_set.rb', line 652

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:

    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

    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:

    v = Hamster::SortedSet["A", "B", "C", "D"]
    v.fetch(2) { |i| i * i }   # => "C"
    v.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:

    v = Hamster::SortedSet["A", "B", "C", "D"]
    v.fetch(2, "Z")  # => "C"
    v.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)

257
258
259
260
261
262
263
264
265
266
267
# 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_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 = Hamster::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 = Hamster::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.


510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
# 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

#firstObject

Return the “lowest” element in this set, as determined by its sort order.

Returns:

  • (Object)

397
398
399
# File 'lib/hamster/sorted_set.rb', line 397

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 = Hamster::SortedSet[2, 4, 6, 8, 10]
    s.from(6)
    # => Hamster::SortedSet[6, 8, 10]

    Returns:

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

    Examples:

    s = Hamster::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)

823
824
825
826
827
828
829
# 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

#hashInteger

See `Object#hash`.

Returns:

  • (Integer)

939
940
941
# File 'lib/hamster/sorted_set.rb', line 939

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:

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

Parameters:

  • item (Object)

    The object to check for

Returns:

  • (Boolean)

464
465
466
# File 'lib/hamster/sorted_set.rb', line 464

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:

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

Parameters:

Returns:

  • (Boolean)

730
731
732
# File 'lib/hamster/sorted_set.rb', line 730

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:

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

Parameters:

  • other (Enumerable)

    The collection to intersect with

Returns:


623
624
625
# File 'lib/hamster/sorted_set.rb', line 623

def intersection(other)
  self.class.alloc(@node.keep_only(other))
end

#lastObject

Return the “highest” element in this set, as determined by its sort order.

Returns:

  • (Object)

416
417
418
# File 'lib/hamster/sorted_set.rb', line 416

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:

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

Yields:

  • (item)

    Once for each item.

Returns:


448
449
450
451
452
# 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

#marshal_dump::Array

Returns:

  • (::Array)

945
946
947
948
949
950
951
# 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) ⇒ Object


954
955
956
# File 'lib/hamster/sorted_set.rb', line 954

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:

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

Yields:

  • (a, b)

    Any number of times with different pairs of elements.

Returns:

  • (Object)

410
411
412
# File 'lib/hamster/sorted_set.rb', line 410

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:

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

Yields:

  • (a, b)

    Any number of times with different pairs of elements.

Returns:

  • (Object)

391
392
393
# File 'lib/hamster/sorted_set.rb', line 391

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:

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

Parameters:

Returns:

  • (Boolean)

689
690
691
692
# 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) ⇒ Boolean

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

Examples:

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

Parameters:

Returns:

  • (Boolean)

703
704
705
# File 'lib/hamster/sorted_set.rb', line 703

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:

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

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

Returns:

  • (self)

376
377
378
379
380
# 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

#sampleObject

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

Examples:

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

Returns:

  • (Object)

905
906
907
# File 'lib/hamster/sorted_set.rb', line 905

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:

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

Yields:

  • (item)

    Once for each item.

Returns:


429
430
431
432
433
434
# 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

#sizeInteger Also known as: length

Return the number of items in this `SortedSet`.

Examples:

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

Returns:

  • (Integer)

114
115
116
# File 'lib/hamster/sorted_set.rb', line 114

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

    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 = 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

    Parameters:

    • range (Range)

      The range of indices to retrieve.

    Returns:


309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
# 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

#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:

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

Returns:


479
480
481
482
483
484
485
# 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

#subset?(other) ⇒ Boolean

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

Examples:

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

Parameters:

Returns:

  • (Boolean)

664
665
666
667
# File 'lib/hamster/sorted_set.rb', line 664

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:

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

Parameters:

Returns:

  • (Boolean)

676
677
678
# File 'lib/hamster/sorted_set.rb', line 676

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

#take(n) ⇒ SortedSet

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

Examples:

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

Parameters:

  • n (Integer)

    The number of elements to retain

Returns:


554
555
556
# File 'lib/hamster/sorted_set.rb', line 554

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:

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

Yields:

  • (item)

Returns:


588
589
590
591
592
593
594
595
596
# 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) ⇒ 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:

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

Parameters:

  • other (Enumerable)

    The collection to merge with

Returns:


607
608
609
# File 'lib/hamster/sorted_set.rb', line 607

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 = Hamster::SortedSet[2, 4, 6, 8, 10]
    s.upto(6)
    # => Hamster::SortedSet[2, 4, 6]

    Returns:

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

    Examples:

    s = Hamster::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)

857
858
859
860
861
862
863
# 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) ⇒ 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 = Hamster::SortedSet["A", "B", "C", "D", "E", "F"]
s.values_at(2, 4, 5)   # => Hamster::SortedSet["C", "E", "F"]

Parameters:

  • indices (Array)

    The indices to retrieve and gather into a new `SortedSet`

Returns:


338
339
340
341
# 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