treemap

Documentation

Overview

Package treemap provides a generic key-sorted map. It uses red-black tree under the hood. You can use it as a template to generate a sorted map with specific key and value types. Iterators are designed after C++.

Example:

package main

import "fmt"

//go:generate gotemplate "github.com/ncw/gotemplate/treemap" "intStringTreeMap(int, string)"

func less(x, y int) bool { return x < y }

func main() {
    tr := newIntStringTreeMap(less)
    tr.Set(0, "Hello")
    tr.Set(1, "World")

    for it := tr.Iterator(); it.Valid(); it.Next() {
        fmt.Println(it.Key(), it.Value())
    }
}

Index

• type ForwardIterator
  • func (i ForwardIterator) Key() Key
  • func (i *ForwardIterator) Next()
  • func (i *ForwardIterator) Prev()
  • func (i ForwardIterator) Valid() bool
  • func (i ForwardIterator) Value() Value
• type Key
• type ReverseIterator
  • func (i ReverseIterator) Key() Key
  • func (i *ReverseIterator) Next()
  • func (i *ReverseIterator) Prev()
  • func (i ReverseIterator) Valid() bool
  • func (i ReverseIterator) Value() Value
• type TreeMap
  • func New(less func(a Key, b Key) bool) *TreeMap
  • func (t *TreeMap) Clear()
  • func (t *TreeMap) Contains(id Key) bool
  • func (t *TreeMap) Del(key Key)
  • func (t *TreeMap) Get(id Key) (Value, bool)
  • func (t *TreeMap) Iterator() ForwardIterator
  • func (t *TreeMap) Len() int
  • func (t *TreeMap) LowerBound(key Key) ForwardIterator
  • func (t *TreeMap) Range(from, to Key) (ForwardIterator, ForwardIterator)
  • func (t *TreeMap) Reverse() ReverseIterator
  • func (t *TreeMap) Set(key Key, value Value)
  • func (t *TreeMap) UpperBound(key Key) ForwardIterator
• type 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 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

func (i ForwardIterator) Key() Key

Key returns a key at an iterator's position

func (*ForwardIterator) Next

func (i *ForwardIterator) Next()

Next moves an iterator to the next element. It panics if goes out of bounds.

func (*ForwardIterator) Prev

func (i *ForwardIterator) Prev()

Prev moves an iterator to the previous element. It panics if goes out of bounds.

func (ForwardIterator) Valid

func (i ForwardIterator) Valid() bool

Valid reports if an iterator's position is valid. In other words it returns true if an iterator is not at the one-past-the-end position.

func (ForwardIterator) Value

func (i ForwardIterator) Value() Value

Value returns a value at an iterator's position

type Key

type Key interface{}

Key is a generic key type of the map

type ReverseIterator

type ReverseIterator 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

func (i ReverseIterator) Key() Key

Key returns a key at an iterator's position

func (*ReverseIterator) Next

func (i *ReverseIterator) Next()

Next moves an iterator to the next element in reverse order. It panics if goes out of bounds.

func (*ReverseIterator) Prev

func (i *ReverseIterator) Prev()

Prev moves an iterator to the previous element in reverse order. It panics if goes out of bounds.

func (ReverseIterator) Valid

func (i ReverseIterator) Valid() bool

Valid reports if an iterator's position is valid. In other words it returns true if an iterator is not at the one-before-the-start position.

func (ReverseIterator) Value

func (i ReverseIterator) Value() Value

Value returns a value at an iterator's position

type TreeMap

type TreeMap struct {

	// Less returns a < b
	Less func(a Key, b Key) bool
	// contains filtered or unexported fields
}

TreeMap is the red-black tree based map

func New

func New(less func(a Key, b Key) bool) *TreeMap

New creates and returns new TreeMap. Parameter less is a function returning a < b.

func (*TreeMap) Clear

func (t *TreeMap) Clear()

Clear clears the map. Complexity: O(1).

Example

tr := New(less)
tr.Set(0, "hello")
tr.Set(1, "world")
tr.Clear()
fmt.Println(tr.Len())

Output:

0

func (*TreeMap) Contains

func (t *TreeMap) Contains(id Key) bool

Contains checks if key exists in a map. Complexity: O(log N)

Example

tr := New(less)
tr.Set(0, "hello")
fmt.Println(tr.Contains(0))

Output:

true

func (*TreeMap) Del

func (t *TreeMap) Del(key Key)

Del deletes the value. Complexity: O(log N).

Example

tr := New(less)
tr.Set(0, "hello")
tr.Del(0)
fmt.Println(tr.Contains(0))

Output:

false

func (*TreeMap) Get

func (t *TreeMap) 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(less)
tr.Set(0, "hello")
v, _ := tr.Get(0)
fmt.Println(v)

Output:

hello

func (*TreeMap) Iterator

func (t *TreeMap) Iterator() ForwardIterator

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(less)
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) Len

func (t *TreeMap) Len() int

Len returns total count of elements in a map. Complexity: O(1).

Example

tr := New(less)
tr.Set(0, "hello")
tr.Set(1, "world")
fmt.Println(tr.Len())

Output:

2

func (*TreeMap) LowerBound

func (t *TreeMap) LowerBound(key Key) ForwardIterator

LowerBound returns an iterator pointing to the first element that is not less than the given key. Complexity: O(log N).

func (*TreeMap) Range

func (t *TreeMap) Range(from, to Key) (ForwardIterator, ForwardIterator)

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(less)
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) Reverse

func (t *TreeMap) Reverse() ReverseIterator

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(less)
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) Set

func (t *TreeMap) Set(key Key, value Value)

Set sets the value and silently overrides previous value if it exists. Complexity: O(log N).

Example

tr := New(less)
tr.Set(0, "hello")
v, _ := tr.Get(0)
fmt.Println(v)

Output:

hello

func (*TreeMap) UpperBound

func (t *TreeMap) UpperBound(key Key) ForwardIterator

UpperBound returns an iterator pointing to the first element that is greater than the given key. Complexity: O(log N).

type Value

type Value interface{}

Value is a generic value type of the map