Documentation
¶
Index ¶
- type Map
- func (m *Map[K, V]) Delete(key K) (value V, deleted bool)
- func (m *Map[K, V]) Init(cmp func(K, K) int)
- func (m *Map[K, V]) Insert(key K, value V) (previous V, replaced bool)
- func (m *Map[K, V]) Len() int
- func (m *Map[K, V]) Lookup(key K) (value V, found bool)
- func (m *Map[K, V]) Max() (key K, value V, found bool)
- func (m *Map[K, V]) Min() (key K, value V, found bool)
- func (m *Map[K, V]) Range(min K, f func(K, V) bool)
- func (m *Map[K, V]) Search(key K) (matchKey K, matchValue V, found bool)
- type Tree
- func (t *Tree[E]) Contains(elem E) (found bool)
- func (t *Tree[E]) Delete(elem E) (deleted bool)
- func (t *Tree[E]) Init(cmp func(E, E) int)
- func (t *Tree[E]) Insert(elem E) (replaced bool)
- func (t *Tree[E]) Len() int
- func (t *Tree[E]) Max() (max E, found bool)
- func (t *Tree[E]) Min() (min E, found bool)
- func (t *Tree[E]) Range(min E, f func(E) bool)
- func (t *Tree[E]) Search(elem E) (match E, found bool)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Map ¶
type Map[K, V any] struct { // contains filtered or unexported fields }
Map is a map type associating keys to values in a similar way to the standard Go map type, but backed by a balanced binary tree instead of a hashmap, which maintains ordering of keys.
The zero-value is a valid empty map which supports lookups and deletes, but must be initialized prior to inserting any keys.
func (*Map[K, V]) Delete ¶
Delete deletes the given key from the map. If the key does not exist, the map is not modified. The method returns the value removed from the map and a boolean indicating whether the key was found.
Complexity: O(log n)
func (*Map[K, V]) Init ¶
Init initializes (or re-initializes) the map. The comparison function passed as argument will be used to order the keys.
Init must be called prior to inserting keys in the map, otherwise inserts will panic.
Complexity: O(1)
func (*Map[K, V]) Insert ¶
Insert inserts a new entry in the map, or replaces the value if the key already existed. The method returns the previous value associated with the key or the zero-value if the key did not exist, and a boolean indicating whether the value was replaced.
The map must have been initialized by a call to NewMap or Init or the call to Insert will panic.
Complexity: O(log n)
func (*Map[K, V]) Len ¶
Len returns the number of entries currently held in the map.
Complexity: O(1)
func (*Map[K, V]) Lookup ¶
Lookup returns the value associated with the given key in the map, and a boolean value indicating whether the key was found in the map.
Complexity: O(log n)
func (*Map[K, V]) Min ¶
Min returns the entry with the smallest key in the map.
Complexity: O(log n)
func (*Map[K, V]) Range ¶
Range calls f for each entry of the map for each key greater or equal to the min key passed as first argument. The keys and values are presented in ascending order according to the comparison function installed on the map.
Complexity: O(log n) + O(k) with k being the number of calls to f
type Tree ¶
type Tree[E any] struct { // contains filtered or unexported fields }
Tree is a balanced binary tree containing elements of type E.
func New ¶
New constructs a new tree using the comparison function passed as argument to order the elements.
func (*Tree[E]) Contains ¶
Contains returns true if the given element exists in the tree.
Complexity: O(log n)
func (*Tree[E]) Init ¶
Init initializes the tree with the given comparison function to order the elements.
Complexity: O(1)
func (*Tree[E]) Insert ¶
Insert inserts a new element in the tree. The method panics if the tree had not been initialized by a call to New or Init.
Complexity: O(log n)
func (*Tree[E]) Max ¶ added in v2.5.0
Max returns the largest element in the tree.
Complexity: O(log n)
func (*Tree[E]) Min ¶ added in v2.5.0
Min returns the smallest element in the tree.
Complexity: O(log n)
Source Files