Class: Hamster::SortedSet

Inherits:
Object
  • Object
show all
Includes:
Enumerable
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 Strings and Integers 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 any of the following ways:

Hamster.sorted_set('Tom', 'Dick', 'Harry')
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.sorted_set('Tom', 'Dick', 'Harry') { |a, b| a.reverse <=> b.reverse }
Hamster.sorted_set('Tom', 'Dick', 'Harry') { |str| str.reverse }
Hamster::SortedSet.new([1,2,3]) { |a, b| -a <=> -b }
Hamster::SortedSet.new([1, 2, 3]) { |num| -num }

As you can see, 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, SortedSets 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 SortedSets are ordered, they also support indexed retrieval of items (or slices of items) using #at or #[]. Like Vector (or Array), 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 very efficient.

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Enumerable

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

Methods included from Enumerable

#to_list

Constructor Details

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


100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
# File 'lib/hamster/sorted_set.rb', line 100

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.


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

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

.emptySortedSet

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


84
85
86
# File 'lib/hamster/sorted_set.rb', line 84

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

Instance Method Details

#setObject #setObject #setObject Also known as: slice

Element reference. Return the item at a specific index, or a specified, contiguous range of items (as a new SortedSet).

Examples:

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

Overloads:

  • #setObject

    Return the item at index.

  • #setObject

    Return a subset starting at index start and continuing for length elements.

  • #setObject

    Return a subset specified by the given range of indices.


300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
# File 'lib/hamster/sorted_set.rb', line 300

def [](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

#above(item, &block) ⇒ Object

With a block, yield all the items which are greater than item (as defined by the set's comparator). Otherwise, return them as a new SortedSet.

Examples:

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

s.above(6) { |e| puts "Element: #{e}" }

Element: 8
Element: 10
# => nil

733
734
735
736
737
738
739
# File 'lib/hamster/sorted_set.rb', line 733

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

143
144
145
146
147
148
149
# File 'lib/hamster/sorted_set.rb', line 143

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

163
164
165
# File 'lib/hamster/sorted_set.rb', line 163

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

227
228
229
230
231
# File 'lib/hamster/sorted_set.rb', line 227

def at(index)
  index += @node.size if index < 0
  return nil if index >= @node.size || index < 0
  @node.at(index)
end

#below(item, &block) ⇒ Object

With a block, yield all the items which are less than item (as defined by the set's comparator). Otherwise, return them as a new SortedSet.

Examples:

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

s.below(6) { |e| puts "Element: #{e}" }

Element: 2
Element: 4
# => nil

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

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) ⇒ Object

With a block, yield all the items which are equal or higher than from and equal or less than to (as determined by the set's comparator). Otherwise, return the specified range of items as a new SortedSet.

Examples:

s = Hamster::SortedSet[2, 4, 6, 7, 8, 9]
s.between(5, 8)
# => Hamster::SortedSet[6, 7, 8]

s.between(5, 8) { |e| puts "Element: #{e}" }

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

832
833
834
835
836
837
838
# File 'lib/hamster/sorted_set.rb', line 832

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.


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

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

176
177
178
179
180
181
182
183
184
185
186
# File 'lib/hamster/sorted_set.rb', line 176

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

199
200
201
# File 'lib/hamster/sorted_set.rb', line 199

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

212
213
214
# File 'lib/hamster/sorted_set.rb', line 212

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]

618
619
620
# File 'lib/hamster/sorted_set.rb', line 618

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

695
696
697
698
699
700
701
702
# File 'lib/hamster/sorted_set.rb', line 695

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

525
526
527
# File 'lib/hamster/sorted_set.rb', line 525

def drop(n)
  derive_new_sorted_set(@node.drop(n))
end

#drop_whileSortedSet, 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]

550
551
552
553
554
555
556
557
558
# File 'lib/hamster/sorted_set.rb', line 550

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) ⇒ self

Call the given block once for each item in the set, passing each item from first to last successively to the block.

Examples:

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

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

346
347
348
349
350
# File 'lib/hamster/sorted_set.rb', line 346

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.


119
120
121
# File 'lib/hamster/sorted_set.rb', line 119

def empty?
  @node.empty?
end

#eql?(other) ⇒ Boolean

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


866
867
868
869
870
871
872
873
874
875
876
# File 'lib/hamster/sorted_set.rb', line 866

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]

633
634
635
# File 'lib/hamster/sorted_set.rb', line 633

def exclusion(other)
  ((self | other) - (self & other))
end

#fetch(index) ⇒ Object #fetch(index) {|index| ... } ⇒ Object #fetch(index, default) ⇒ Object

Retrieve the value at index, or use the provided default value or block, or otherwise raise an IndexError.

Examples:

s = Hamster::SortedSet["A", "B", "C", "D"]
s.fetch(2)       # => "C"
s.fetch(-1)      # => "D"
s.fetch(4)       # => IndexError: index 4 outside of sorted set bounds
# With default value:
s.fetch(2, "Z")  # => "C"
s.fetch(4, "Z")  # => "Z"
# With block:
s.fetch(2) { |i| i * i }   # => "C"
s.fetch(4) { |i| i * i }   # => 16

Overloads:

  • #fetch(index) ⇒ Object

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

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

    Retrieve the value at the given index, or call the optional code block (with the non-existent index) and get its return value.

    Yields:

    • (index)

      The index which does not exist

    Yield Returns:

    • (Object)

      Object to return instead

  • #fetch(index, default) ⇒ Object

    Retrieve the value at the given index, or else return the provided default value.


265
266
267
268
269
270
271
272
273
274
275
# File 'lib/hamster/sorted_set.rb', line 265

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| ... }) {|Object| ... } ⇒ Integer Also known as: index

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

Examples:

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

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

  • #find_index({ |element| ... }) {|Object| ... } ⇒ Integer

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

    Yields:

    • (Object)

      An element in the sorted set

    Yield Returns:

    • (Boolean)

      True if this is element matches


493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
# File 'lib/hamster/sorted_set.rb', line 493

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.


385
386
387
# File 'lib/hamster/sorted_set.rb', line 385

def first
  @node.min
end

#from(item, &block) ⇒ Object

With a block, yield all the items which are equal or greater than item (as determined by the set's comparator). Otherwise, return them as a new SortedSet.

Examples:

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

s.from(6) { |e| puts "Element: #{e}" }

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

781
782
783
784
785
786
787
# File 'lib/hamster/sorted_set.rb', line 781

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.


880
881
882
# File 'lib/hamster/sorted_set.rb', line 880

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

448
449
450
# File 'lib/hamster/sorted_set.rb', line 448

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

711
712
713
# File 'lib/hamster/sorted_set.rb', line 711

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]

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

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.


403
404
405
# File 'lib/hamster/sorted_set.rb', line 403

def last
  @node.max
end

#mapSortedSet 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.

Examples:

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

432
433
434
435
436
# File 'lib/hamster/sorted_set.rb', line 432

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

#maxObject

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"

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

def max
  block_given? ? super : @node.max
end

#minObject

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"

379
380
381
# File 'lib/hamster/sorted_set.rb', line 379

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

670
671
672
673
# File 'lib/hamster/sorted_set.rb', line 670

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

684
685
686
# File 'lib/hamster/sorted_set.rb', line 684

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

365
366
367
368
369
# File 'lib/hamster/sorted_set.rb', line 365

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

846
847
848
# File 'lib/hamster/sorted_set.rb', line 846

def sample
  @node.at(rand(@node.size))
end

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

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

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

129
130
131
# File 'lib/hamster/sorted_set.rb', line 129

def size
  @node.size
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"]

463
464
465
466
467
468
469
# File 'lib/hamster/sorted_set.rb', line 463

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

645
646
647
648
# File 'lib/hamster/sorted_set.rb', line 645

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

657
658
659
# File 'lib/hamster/sorted_set.rb', line 657

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

537
538
539
# File 'lib/hamster/sorted_set.rb', line 537

def take(n)
  derive_new_sorted_set(@node.take(n))
end

#take_whileSortedSet, 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]

569
570
571
572
573
574
575
576
577
# File 'lib/hamster/sorted_set.rb', line 569

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

#to_ruby::SortedSet

Deeply convert to Ruby SortedSet.


887
888
889
# File 'lib/hamster/sorted_set.rb', line 887

def to_ruby
  Hamster.to_ruby(self)
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]

588
589
590
# File 'lib/hamster/sorted_set.rb', line 588

def union(other)
  self.class.alloc(@node.bulk_insert(other))
end

#up_to(item, &block) ⇒ Object

With a block, yield all the items which are equal or less than item (as defined by the set's comparator). Otherwise, return them as a new SortedSet.

Examples:

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

s.up_to(6) { |e| puts "Element: #{e}" }

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

806
807
808
809
810
811
812
# File 'lib/hamster/sorted_set.rb', line 806

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

329
330
331
332
# File 'lib/hamster/sorted_set.rb', line 329

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