class AVLTree::SortedSet(T)

• AVLTree::SortedSet(T)
• Reference
• Object

Overview

SortedSet implements a Set that guarantees that its elements are yielded in sorted order (according to the return values of their #<=> methods) when iterating over them.

SortedSet utilizes an internally implemented SortedMap using an AVL tree.

While it often has slower computational speed compared to a Set implemented using a hash-based approach, it offers potential optimizations for operations related to order. For example, retrieving the maximum and minimum values of the set can be performed in logarithmic time.

SortedSet does not allow duplicates and only stores unique values.

Example

require "avltree"

set = AVLTree::SortedSet.new [3, 1, 4]
set.to_a == [1, 3, 4] # => true
set.to_a == [3, 1, 4] # => false

set << 1 << 5
set                 # => SortedSet{1, 3, 4, 5}
set.min             # => 1  (O(logN))
set.max             # => 5  (O(logN))
set.index(4)        # => 2  (O(logN))
set.upper_bound(2)  # => 1  (O(logN))
set.upper_bound(3)  # => 1  (O(logN))
set.upper_bound(10) # => 4  (O(logN))

Included Modules

• Enumerable(T)
• Indexable(T)
• Iterable(T)

Defined in:

Constructors

• .new(other : Indexable(T))
• .new(enumerable : Enumerable(T))
• .new

Instance Method Summary

• #&(other : SortedSet) : SortedSet(T)
• #+(other : SortedSet(U)) : SortedSet(T | U) forall U
• #-(other : SortedSet)
• #-(other : Enumerable)
• #<<(object : T)
• #==(other : SortedSet)
• #===(other : T)
• #^(other : SortedSet(U)) forall U
• #^(other : Enumerable(U)) forall U
• #|(other : SortedSet(U)) : SortedSet(U | T) forall U
• #add(object : T)
• #add?(object : T)
• #at(index : Int)

  Returns the element at the index-th.

• #at(index : Int, &)

  Returns the element at the index-th.

• #at?(index : Int)

  Like #at, but returns nil if trying to access an element outside the set's range.

• #clear

  Removes all elements in the set, and returns self.

• #clone
• #concat(elems)
• #count(range : Range(T | Nil, T | Nil))

  Returns the number of elements in the set that exist within the range.

• #count(object)

  Returns the number of times that the passed item is present in the collection.

• #delete(object)

  Removes the object from the set and returns true if it was present, otherwise returns false.

• #delete_at(index : Int, &)

  Removes the index-th object and returns the deleted object, else yields #index with given block.

• #delete_at(index : Int) : T

  Removes the index-th object from the set and returns the deleted object.

• #delete_at?(index : Int) : T | Nil

  Removes the index-th object from the set and returns the deleted object if it was present, otherwise returns nil.

• #dup

  Returns a shallow copy of this object.

• #each(&)

  Calls the given block once for each element in self, passing that element as a parameter.

• #each

  Must return an Iterator over the elements in this collection.

• #empty?

  Returns true if self is empty, false otherwise.

• #fetch(index : Int, &)

  Returns the element at the given index, if in bounds, otherwise executes the given block with the index and returns its value.

• #fetch(index : Int, default)
• #first

  Returns the first element in the collection.

• #first?

  Returns the first element in the collection.

• #hash(hasher)

  See Object#hash(hasher)

• #includes?(object)

  Returns true if the collection contains obj, false otherwise.

• #index(object)

  Returns the index of the first appearance of object in self starting from the given offset, or nil if object is not in self.

• #index!(object)

  Returns the index of the first appearance of obj in self starting from the given offset.

• #index_of_largest_leq(object) : Int32 | Nil

  See SortedMap#largest_leq_index

• #index_of_largest_lt(object) : Int32 | Nil

  See SortedMap#largest_lt_index

• #index_of_smallest_geq(object) : Int32 | Nil

  See SortedMap#smallest_geq_index

• #index_of_smallest_gt(object) : Int32 | Nil

  See SortedMap#smallest_gt_index

• #inspect(io : IO) : Nil

  Appends a String representation of this object which includes its class name, its object address and the values of all instance variables.

• #intersects?(other : Set)
• #largest_leq(object) : T | Nil

  See SortedMap#largest_leq

• #largest_leq_with_index(object) : Tuple(T | Nil, Int32 | Nil)

  See SortedMap#largest_leq_with_index

• #largest_lt(object) : T | Nil

  See SortedMap#largest_lt

• #largest_lt_with_index(object) : Tuple(T | Nil, Int32 | Nil)

  See SortedMap#largest_lt_with_index

• #last

  Returns the last element of self if it's not empty, or raises IndexError.

• #last?

  Returns the last element of self if it's not empty, or nil.

• #lower_bound(object) : Int32

  set = AVLTree::SortedSet(String){"A", "B", "B", "C", "E"} set # => SortedSet{"A", "B", "C", "E"} set.lower_bound("@") # => 0 set.lower_bound("A") # => 0 set.lower_bound("B") # => 1 set.lower_bound("C") # => 2 set.lower_bound("D") # => 3 set.lower_bound("E") # => 3 set.lower_bound("F") # => 4 set.lower_bound("Z") # => 4

• #max

  Returns the element with the maximum value in the collection.

• #max?

  Like #max but returns nil if the collection is empty.

• #min

  Returns the element with the minimum value in the collection.

• #min?

  Like #min but returns nil if the collection is empty.

• #object_id

  Returns a UInt64 that uniquely identifies this object.

• #pop : T
• #pop(&)
• #pop? : T | Nil
• #pretty_print(pp) : Nil
• #proper_subset_of?(other : SortedSet)
• #proper_superset_of?(other : SortedSet)
• #rindex(object)

  Returns the index of the last appearance of value in self, or nil if the value is not in self.

• #rindex!(object)

  Returns the index of the last appearance of value in self, or nil if the value is not in self.

• #same?(other : SortedSet)

  Returns true if this reference is the same as other.

• #shift : T
• #shift(&)
• #shift? : T | Nil
• #size

  Returns the number of elements in this container.

• #smallest_geq(object) : T | Nil

  See SortedMap#smallest_geq

• #smallest_geq_with_index(object) : Tuple(T | Nil, Int32 | Nil)

  See SortedMap#smallest_geq_with_index

• #smallest_gt(object) : T | Nil

  See SortedMap#smallest_gt

• #smallest_gt_with_index(object) : Tuple(T | Nil, Int32 | Nil)

  See SortedMap#smallest_gt_with_index

• #subset_of?(other : SortedSet)
• #subtract(other : Enumerable)
• #superset_of?(other : SortedSet)
• #to_a

  Returns an Array with all the elements in the collection.

• #to_s(io : IO) : Nil

  Appends a short String representation of this object which includes its class name and its object address.

• #unordered_each(&)

  Yields each element of the set, and returns self.

• #unsafe_fetch(index : Int)

  Returns the element at the given index, without doing any bounds check.

• #upper_bound(object) : Int32

  set = AVLTree::SortedSet(String){"A", "B", "B", "C", "E"} set # => SortedSet{"A", "B", "C", "E"} set.upper_bound("@") # => 0 set.upper_bound("A") # => 1 set.upper_bound("B") # => 2 set.upper_bound("C") # => 3 set.upper_bound("D") # => 3 set.upper_bound("E") # => 4 set.upper_bound("F") # => 4 set.upper_bound("Z") # => 4

Constructor Detail

Instance Method Detail

set = AVLTree::SortedSet(Int32){3, 1, 4, 1, 5, 9}
set.count(2..3)  # => 1
set.count(2...3) # => 0
set.count(2..9)  # => 4
set.count(2...9) # => 3
set.count(2...)  # => 4
set.count(...)   # => 5
set.count(...9)  # => 4

[1, 2, 3, 4].count(3) # => 1

a = ["a", "b", "c"]
a.each { |x| print x, " -- " }

a -- b -- c --

([] of Int32).empty? # => true
([1]).empty?         # => false

a = [:foo, :bar]
a.fetch(0) { :default_value }    # => :foo
a.fetch(2) { :default_value }    # => :default_value
a.fetch(2) { |index| index * 3 } # => 6

([1, 2, 3]).first   # => 1
([] of Int32).first # raises Enumerable::EmptyError

([1, 2, 3]).first?   # => 1
([] of Int32).first? # => nil

[1, 2, 3].includes?(2) # => true
[1, 2, 3].includes?(5) # => false

[1, 2, 3, 1, 2, 3].index(2, offset: 2) # => 4

[1, 2, 3, 1, 2, 3].index!(2, offset: 2) # => 4

class Person
  def initialize(@name : String, @age : Int32)
  end
end

Person.new("John", 32).inspect # => #<Person:0x10fd31f20 @name="John", @age=32>

([1, 2, 3]).last   # => 3
([] of Int32).last # raises IndexError

([1, 2, 3]).last?   # => 3
([] of Int32).last? # => nil

set = AVLTree::SortedSet(String){"A", "B", "B", "C", "E"}
set                  # => SortedSet{"A", "B", "C", "E"}
set.lower_bound("@") # => 0
set.lower_bound("A") # => 0
set.lower_bound("B") # => 1
set.lower_bound("C") # => 2
set.lower_bound("D") # => 3
set.lower_bound("E") # => 3
set.lower_bound("F") # => 4
set.lower_bound("Z") # => 4

[1, 2, 3].max        # => 3
["Alice", "Bob"].max # => "Bob"

[1, 2, 3].min        # => 1
["Alice", "Bob"].min # => "Alice"

string = "hello"
string.object_id # => 4460249568

pointer = Pointer(String).new(string.object_id)
string2 = pointer.as(String)
string2.object_id == string.object_id # => true

[1, 2, 3, 2, 3].rindex(2)            # => 3
[1, 2, 3, 2, 3].rindex(2, offset: 2) # => 1

[1, 2, 3, 2, 3].rindex(2)            # => 3
[1, 2, 3, 2, 3].rindex(2, offset: 2) # => 1

{1, 2, 3}.to_a # => [1, 2, 3]

class Person
  def initialize(@name : String, @age : Int32)
  end
end

Person.new("John", 32).to_s # => #<Person:0x10a199f20>

set = AVLTree::SortedSet(String){"A", "B", "B", "C", "E"}
set                  # => SortedSet{"A", "B", "C", "E"}
set.upper_bound("@") # => 0
set.upper_bound("A") # => 1
set.upper_bound("B") # => 2
set.upper_bound("C") # => 3
set.upper_bound("D") # => 3
set.upper_bound("E") # => 4
set.upper_bound("F") # => 4
set.upper_bound("Z") # => 4