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
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
“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
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
# 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
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
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
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
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
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
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
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
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
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
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
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
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 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 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
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
Return `true` if this `SortedSet` contains no items.
@return [Boolean]
# File lib/hamster/sorted_set.rb, line 104 def empty? @node.empty? end
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
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
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 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.
# 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
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
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
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
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
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
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
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
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.
# 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
@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
@private
# File lib/hamster/sorted_set.rb, line 954 def marshal_load(array) initialize(array) end
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]
# File lib/hamster/sorted_set.rb, line 410 def max block_given? ? super : @node.max end
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.
# File lib/hamster/sorted_set.rb, line 391 def min block_given? ? super : @node.min end
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Private Instance Methods
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
# 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