treemap

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
  • func (i ForwardIterator[Key, Value]) Key() Key
  • func (i *ForwardIterator[Key, Value]) Next()
  • func (i *ForwardIterator[Key, Value]) Prev()
  • func (i ForwardIterator[Key, Value]) Valid() bool
  • func (i ForwardIterator[Key, Value]) Value() Value
• type ReverseIterator
  • func (i ReverseIterator[Key, Value]) Key() Key
  • func (i *ReverseIterator[Key, Value]) Next()
  • func (i *ReverseIterator[Key, Value]) Prev()
  • func (i ReverseIterator[Key, Value]) Valid() bool
  • func (i ReverseIterator[Key, Value]) Value() Value
• type TreeMap
  • func New[Key constraints.Ordered, Value any]() *TreeMap[Key, Value]
  • func NewWithKeyCompare[Key, Value any](keyCompare func(a, b Key) bool) *TreeMap[Key, Value]
  • 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]) KeyCompare() func(a Key, b Key) bool
  • 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

• TreeMap.Clear
• TreeMap.Contains
• TreeMap.Del
• TreeMap.Get
• TreeMap.Iterator
• TreeMap.Len
• TreeMap.Range
• TreeMap.Reverse
• TreeMap.Set

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

func NewWithKeyCompare[Key, Value any](
	keyCompare func(a, b Key) bool,
) *TreeMap[Key, Value]

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

func (t *TreeMap[Key, Value]) Contains(id Key) bool

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

func (t *TreeMap[Key, Value]) Get(id Key) (Value, bool)

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

func (t *TreeMap[Key, Value]) KeyCompare() func(a Key, b Key) bool

func (*TreeMap[Key, Value]) Len

func (t *TreeMap[Key, Value]) Len() int

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