class

AVLTree::SortedSet(T)

Inherits Iterable < Indexable < Enumerable < Iterable < Enumerable < Reference < Object

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

Constructors

new(other : Indexable(T))

new(enumerable : Enumerable(T))

new

Instance methods

&(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.

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

count(object)

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

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

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.

This allocates a new object and copies the contents of self into it.

each

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

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

produces:

a -- b -- c --

each

Must return an Iterator over the elements in this collection.

empty?

Returns true if self is empty, false otherwise.

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

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.

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

fetch(index : Int, default)

first

Returns the first element in the collection. Raises Enumerable::EmptyError if the collection is empty.

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

first?

Returns the first element in the collection. When the collection is empty, returns nil.

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

hash(hasher)

See Object#hash(hasher)

includes?(object)

Returns true if the collection contains obj, false otherwise.

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

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.

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

index!(object)

Returns the index of the first appearance of obj in self starting from the given offset. Raises Enumerable::NotFoundError if obj is not in self.

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

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.

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

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

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.

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

last?

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

([1, 2, 3]).last?   # => 3
([] of Int32).last? # => 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.

It compares using > so it will work for any type that supports that method.

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

Raises Enumerable::EmptyError if the collection is empty.

max?

Like max but returns nil if the collection is empty.

min

Returns the element with the minimum value in the collection.

It compares using < so it will work for any type that supports that method.

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

Raises Enumerable::EmptyError if the collection is empty.

min?

Like min but returns nil if the collection is empty.

object_id

Returns a UInt64 that uniquely identifies this object.

The returned value is the memory address of this object.

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

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

pop

pop

pop?

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.

If offset is given, it defines the position to end the search (elements beyond this point are ignored).

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

rindex!(object)

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

If offset is given, it defines the position to end the search (elements beyond this point are ignored).

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

Raises Enumerable::NotFoundError if value is not in self.

same?(other : SortedSet)

Returns true if this reference is the same as other. This is only true if this reference's object_id is the same as other's.

shift

shift

shift?

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.

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

to_s(io : IO) : Nil

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

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

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

unordered_each

Yields each element of the set, and returns self.

It doesn't guarantee that its elements are yielded in sorted order when iterating over them.

unsafe_fetch(index : Int)

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

Indexable makes sure to invoke this method with index in 0...size, so converting negative indices to positive ones is not needed here.

Clients never invoke this method directly. Instead, they access elements with #[](index) and #[]?(index).

This method should only be directly invoked if you are absolutely sure the index is in bounds, to avoid a bounds check for a small boost of performance.

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