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

.empty ⇒ SortedSet

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

#clear ⇒ SortedSet

Return an empty ‘SortedSet` instance, of the same class as this one. Useful if you have multiple subclasses of `SortedSet` and want to treat them polymorphically.

Returns:



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

#first ⇒ Object

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

#hash ⇒ Integer

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

#last ⇒ Object

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

#sample ⇒ Object

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

#size ⇒ Integer 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