Documentation
¶
Overview ¶
Package treemap provides a generic key-sorted map. It uses red-black tree under the hood. Iterators are designed after C++.
Example:
package main
import (
"fmt"
"github.com/igrmk/treemap/v2"
)
func main() {
tree := treemap.New[int, string]()
tree.Set(1, "World")
tree.Set(0, "Hello")
for it := tree.Iterator(); it.Valid(); it.Next() {
fmt.Println(it.Key(), it.Value())
}
}
// Output:
// 0 Hello
// 1 World
Index ¶
- type ForwardIterator
- type ReverseIterator
- type TreeMap
- func (t *TreeMap[Key, Value]) Clear()
- func (t *TreeMap[Key, Value]) Contains(id Key) bool
- func (t *TreeMap[Key, Value]) Del(key Key)
- func (t *TreeMap[Key, Value]) Get(id Key) (Value, bool)
- func (t *TreeMap[Key, Value]) Iterator() ForwardIterator[Key, Value]
- func (t *TreeMap[Key, Value]) Len() int
- func (t *TreeMap[Key, Value]) LowerBound(key Key) ForwardIterator[Key, Value]
- func (t *TreeMap[Key, Value]) Range(from, to Key) (ForwardIterator[Key, Value], ForwardIterator[Key, Value])
- func (t *TreeMap[Key, Value]) Reverse() ReverseIterator[Key, Value]
- func (t *TreeMap[Key, Value]) Set(key Key, value Value)
- func (t *TreeMap[Key, Value]) UpperBound(key Key) ForwardIterator[Key, Value]
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ForwardIterator ¶
type ForwardIterator[Key, Value any] struct { // contains filtered or unexported fields }
ForwardIterator represents a position in a tree map. It is designed to iterate a map in a forward order. It can point to any position from the first element to the one-past-the-end element.
func (ForwardIterator[Key, Value]) Key ¶
func (i ForwardIterator[Key, Value]) Key() Key
Key returns a key at the iterator position
func (*ForwardIterator[Key, Value]) Next ¶
func (i *ForwardIterator[Key, Value]) Next()
Next moves an iterator to the next element. It panics if it goes out of bounds.
func (*ForwardIterator[Key, Value]) Prev ¶
func (i *ForwardIterator[Key, Value]) Prev()
Prev moves an iterator to the previous element. It panics if it goes out of bounds.
func (ForwardIterator[Key, Value]) Valid ¶
func (i ForwardIterator[Key, Value]) Valid() bool
Valid reports if the iterator position is valid. In other words it returns true if an iterator is not at the one-past-the-end position.
func (ForwardIterator[Key, Value]) Value ¶
func (i ForwardIterator[Key, Value]) Value() Value
Value returns a value at the iterator position
type ReverseIterator ¶
type ReverseIterator[Key, Value any] struct { // contains filtered or unexported fields }
ReverseIterator represents a position in a tree map. It is designed to iterate a map in a reverse order. It can point to any position from the one-before-the-start element to the last element.
func (ReverseIterator[Key, Value]) Key ¶
func (i ReverseIterator[Key, Value]) Key() Key
Key returns a key at the iterator position
func (*ReverseIterator[Key, Value]) Next ¶
func (i *ReverseIterator[Key, Value]) Next()
Next moves an iterator to the next element in reverse order. It panics if it goes out of bounds.
func (*ReverseIterator[Key, Value]) Prev ¶
func (i *ReverseIterator[Key, Value]) Prev()
Prev moves an iterator to the previous element in reverse order. It panics if it goes out of bounds.
func (ReverseIterator[Key, Value]) Valid ¶
func (i ReverseIterator[Key, Value]) Valid() bool
Valid reports if the iterator position is valid. In other words it returns true if an iterator is not at the one-before-the-start position.
func (ReverseIterator[Key, Value]) Value ¶
func (i ReverseIterator[Key, Value]) Value() Value
Value returns a value at the iterator position
type TreeMap ¶
type TreeMap[Key, Value any] struct { // contains filtered or unexported fields }
TreeMap is the generic red-black tree based map
func New ¶
func New[Key constraints.Ordered, Value any]() *TreeMap[Key, Value]
New creates and returns new TreeMap.
func NewWithKeyCompare ¶
NewWithKeyCompare creates and returns new TreeMap with the specified key compare function. Parameter keyCompare is a function returning a < b.
func (*TreeMap[Key, Value]) Clear ¶
func (t *TreeMap[Key, Value]) Clear()
Clear clears the map. Complexity: O(1).
Example ¶
tr := New[int, string]() tr.Set(0, "hello") tr.Set(1, "world") tr.Clear() fmt.Println(tr.Len())
Output: 0
func (*TreeMap[Key, Value]) Contains ¶
Contains checks if key exists in a map. Complexity: O(log N)
Example ¶
tr := New[int, string]() tr.Set(0, "hello") fmt.Println(tr.Contains(0))
Output: true
func (*TreeMap[Key, Value]) Del ¶
func (t *TreeMap[Key, Value]) Del(key Key)
Del deletes the value. Complexity: O(log N).
Example ¶
tr := New[int, string]() tr.Set(0, "hello") tr.Del(0) fmt.Println(tr.Contains(0))
Output: false
func (*TreeMap[Key, Value]) Get ¶
Get retrieves a value from a map for specified key and reports if it exists. Complexity: O(log N).
Example ¶
tr := New[int, string]() tr.Set(0, "hello") v, _ := tr.Get(0) fmt.Println(v)
Output: hello
func (*TreeMap[Key, Value]) Iterator ¶
func (t *TreeMap[Key, Value]) Iterator() ForwardIterator[Key, Value]
Iterator returns an iterator for tree map. It starts at the first element and goes to the one-past-the-end position. You can iterate a map at O(N) complexity. Method complexity: O(1)
Example ¶
tr := New[int, string]()
tr.Set(1, "one")
tr.Set(2, "two")
tr.Set(3, "three")
for it := tr.Iterator(); it.Valid(); it.Next() {
fmt.Println(it.Key(), "-", it.Value())
}
Output: 1 - one 2 - two 3 - three
func (*TreeMap[Key, Value]) Len ¶
Len returns total count of elements in a map. Complexity: O(1).
Example ¶
tr := New[int, string]() tr.Set(0, "hello") tr.Set(1, "world") fmt.Println(tr.Len())
Output: 2
func (*TreeMap[Key, Value]) LowerBound ¶
func (t *TreeMap[Key, Value]) LowerBound(key Key) ForwardIterator[Key, Value]
LowerBound returns an iterator pointing to the first element that is not less than the given key. Complexity: O(log N).
func (*TreeMap[Key, Value]) Range ¶
func (t *TreeMap[Key, Value]) Range(from, to Key) (ForwardIterator[Key, Value], ForwardIterator[Key, Value])
Range returns a pair of iterators that you can use to go through all the keys in the range [from, to]. More specifically it returns iterators pointing to lower bound and upper bound. Complexity: O(log N).
Example ¶
tr := New[int, string]()
tr.Set(1, "one")
tr.Set(2, "two")
tr.Set(3, "three")
for it, end := tr.Range(1, 2); it != end; it.Next() {
fmt.Println(it.Key(), "-", it.Value())
}
Output: 1 - one 2 - two
func (*TreeMap[Key, Value]) Reverse ¶
func (t *TreeMap[Key, Value]) Reverse() ReverseIterator[Key, Value]
Reverse returns a reverse iterator for tree map. It starts at the last element and goes to the one-before-the-start position. You can iterate a map at O(N) complexity. Method complexity: O(log N)
Example ¶
tr := New[int, string]()
tr.Set(1, "one")
tr.Set(2, "two")
tr.Set(3, "three")
for it := tr.Reverse(); it.Valid(); it.Next() {
fmt.Println(it.Key(), "-", it.Value())
}
Output: 3 - three 2 - two 1 - one
func (*TreeMap[Key, Value]) Set ¶
func (t *TreeMap[Key, Value]) Set(key Key, value Value)
Set sets the value and silently overrides previous value if it exists. Complexity: O(log N).
Example ¶
tr := New[int, string]() tr.Set(0, "hello") v, _ := tr.Get(0) fmt.Println(v)
Output: hello
func (*TreeMap[Key, Value]) UpperBound ¶
func (t *TreeMap[Key, Value]) UpperBound(key Key) ForwardIterator[Key, Value]
UpperBound returns an iterator pointing to the first element that is greater than the given key. Complexity: O(log N).
Source Files
Directories