AVLTree::SortedMap(K, V)
Inherits Iterable < Enumerable < Reference < Object
SortedMap implements a associative array that guarantees that its keys are yielded in sorted order
(according to the return keys of their #<=> methods) when iterating over them.
SortedMap is implemented using an AVL tree.
While it often has slower computational speed compared to a Hash implemented using a hash-based approach, it offers potential optimizations for operations related to order. For example, retrieving the maximum and minimum keys of the map can be performed in logarithmic time.
SortedMap does not allow duplicates and only stores unique keys.
Example
require "avltree"
map = AVLTree::SortedMap(String, Int32).new({"bob" => 3, "alice" => 1, "carol" => -2})
map.to_a == [{"alice", 1}, {"bob", 3}, {"carol", -2}] # => true
map.to_a == [{"bob", 3}, {"alice", 1}, {"carol", -2}] # => false
map["dave"] = 4
map["oscar"] = 3
map # => {alice => 1, bob => 3, carol => -2, dave => 4, oscar => 3}
map.min # => {"alice", 1} (O(logN))
map.max # => {"oscar", 3} (O(logN))
map.lower_bound("a") # => 0 (O(logN))
map.lower_bound("bryan") # => 2 (O(logN))
map.lower_bound("zoe") # => 5 (O(logN))Constructors
Class methods
Instance methods
Like at, but returns nil
if trying to access an key-value outside the set's range.
Returns a shallow copy of this object.
This allocates a new object and copies the contents of
self into it.
Returns true if self does not contain any element.
([] of Int32).empty? # => true
([1]).empty? # => false
[nil, false].empty? # => false#present?returns the inverse.
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>Like at, but returns nil
if trying to access an key outside the set's range.
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.
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.
Returns an Array with all the elements in the collection for which
the passed block is falsey.
[1, 2, 3, 4, 5, 6].reject { |i| i % 2 == 0 } # => [1, 3, 5]Returns an Array with all the elements in the collection.
(1..5).to_a # => [1, 2, 3, 4, 5]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>Like at, but returns nil
if trying to access an value outside the set's range.