class AVLTree::SortedMap(K, V)

• AVLTree::SortedMap(K, V)
• Reference
• Object

Overview

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

Included Modules

• Enumerable({K, V})
• Iterable({K, V})

Defined in:

Constructors

• .new(hash : Hash(K, V))
• .new(defalut_value : V)
• .new
• .new(&block : self, K -> V)

Class Method Summary

• .zip(ary1 : Array(K), ary2 : Array(V))

Instance Method Summary

• #==(other : SortedMap) : Bool
• #[](key : K) : V
• #[]=(key : K, value : V) : V
• #[]?(key : K) : V | Nil
• #at(index : Int) : Tuple(K, V)

  Returns the key-value at the index-th.

• #at(index : Int, &)

  Returns the key-value at the index-th.

• #at?(index : Int) : Tuple(K, V) | Nil

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

• #clear : self
• #clone
• #compact
• #compact! : self
• #delete(key : K) : V | Nil
• #delete(key : K, &)
• #delete_at(index : Int, &)
• #delete_at(index : Int) : Tuple(K, V)
• #delete_at?(index : Int) : Tuple(K, V) | Nil
• #dig(key : K)
• #dig(key : K, *subkeys)
• #dig?(key : K)
• #dig?(key : K, *subkeys)
• #dup

  Returns a shallow copy of this object.

• #each(& : Tuple(K, V) -> ) : Nil

  Must yield this collection's elements to the block.

• #each

  Must return an Iterator over the elements in this collection.

• #each_key(& : K -> ) : Nil
• #each_key
• #each_value(& : V -> ) : Nil
• #each_value
• #empty?

  Returns true if self does not contain any element.

• #fetch(key : K, default)
• #fetch(key : K, &)
• #fetch_at(index : Int, &)
• #fetch_at(index : Int, default)
• #first_key : K
• #first_key? : K | Nil
• #first_value : K
• #first_value? : K | Nil
• #has_key?(key : K) : Bool
• #has_value?(value : V) : Bool
• #index(key : K) : Int32 | Nil
• #index!(key : K) : Int32
• #index_of_largest_leq(key : K) : Int32 | Nil
• #index_of_largest_lt(key : K) : Int32 | Nil
• #index_of_smallest_geq(key : K) : Int32 | Nil
• #index_of_smallest_gt(key : K) : Int32 | Nil
• #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.

• #invert : SortedMap(V, K)
• #key_at(index : Int) : K

  Returns the key at the index-th.

• #key_at?(index : Int) : K | Nil

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

• #key_for(value) : K
• #key_for(value, &)
• #key_for?(value) : K | Nil
• #keys : Array(K)
• #largest_leq(key : K) : Tuple(K, V) | Nil
• #largest_leq_with_index(key : K) : Tuple(Tuple(K, V) | Nil, Int32 | Nil)
• #largest_lt(key : K) : Tuple(K, V) | Nil
• #largest_lt_with_index(key : K) : Tuple(Tuple(K, V) | Nil, Int32 | Nil)
• #last_key : K
• #last_key? : K | Nil
• #last_value : K
• #last_value? : K | Nil
• #lower_bound(key : K) : Int32
• #max

  Returns the element with the maximum value in the collection.

• #min

  Returns the element with the minimum value in the collection.

• #pop : Tuple(K, V)
• #pop(&)
• #pop? : Tuple(K, V) | Nil
• #proper_superset_of?(other : Hash) : Bool
• #put(key : K, value : V, &)
• #reject(& : K, V -> ) : SortedMap(K, V)

  Returns an Array with all the elements in the collection for which the passed block is falsey.

• #reject(*keys) : SortedMap(K, V)
• #reject!(& : K, V -> ) : SortedMap(K, V)
• #reject!(keys : Enumerable) : SortedMap(K, V)
• #reject!(*keys) : SortedMap(K, V)
• #reverse_each(& : Tuple(K, V) -> ) : Nil
• #reverse_each
• #reverse_each_key(& : K -> ) : Nil
• #reverse_each_key
• #reverse_each_value(& : V -> ) : Nil
• #reverse_each_value
• #rindex(key : K) : Int32 | Nil
• #rindex!(key : K) : Int32
• #select(keys : Enumerable) : SortedMap(K, V)
• #select(*keys) : SortedMap(K, V)
• #select!(keys : Indexable) : self
• #select!(keys : Enumerable) : self
• #select!(*keys) : self
• #shift : Tuple(K, V)
• #shift(&)
• #shift? : Tuple(K, V) | Nil
• #size : Int32

  Returns the number of elements in the collection.

• #smallest_geq(key : K) : Tuple(K, V) | Nil
• #smallest_geq_with_index(key : K) : Tuple(Tuple(K, V) | Nil, Int32 | Nil)
• #smallest_gt(key : K) : Tuple(K, V) | Nil
• #smallest_gt_with_index(key : K) : Tuple(Tuple(K, V) | Nil, Int32 | Nil)
• #subset_of?(other : SortedMap(K, V)) : Bool
• #superset_of?(other : SortedMap(K, V)) : Bool
• #to_a : Array(Tuple(K, V))

  Returns an Array with all the elements in the collection.

• #to_hash
• #to_s(io : IO) : Nil

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

• #unordered_each(node = @root, & : Tuple(K, V) -> ) : Nil
• #unsafe_fetch(index : Int)
• #update(key : K, & : V -> V) : V
• #upper_bound(key : K) : Int32
• #value_at(index : Int) : V

  Returns the value at the index-th.

• #value_at?(index : Int) : V | Nil

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

• #values : Array(V)
• #values_at(*indices : Int)
• #values_by_key(*keys : K)

Constructor Detail

Class Method Detail

Instance Method Detail

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

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

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

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

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

[1, 2, 3, 4, 5, 6].reject { |i| i % 2 == 0 } # => [1, 3, 5]

[1, 2, 3, 4].size # => 4

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

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

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