TreeMap

This repository is fully merged into gotemplate. However, if you just need an untyped tree map, it is easier to use this repository.

TreeMap is a generic key-sorted map. It uses red-black tree under the hood. This is gotemplate ready package. You can use it as a template to generate a sorted map with specific key and value types. See example folder for an illustration of generating a map with int key and string value. The package is useful without a generation as well. It uses interface{} type for both a key and a value in this case. Iterators are designed after C++.

Usage

package main

import "fmt"

//go:generate gotemplate "github.com/igrmk/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())
	}
}

To build it you need to run

go generate
go build

Command go generate will generate a file gotemplate_intStringTreeMap.go in the same directory. This file will contain ready to use tree map.

Install

go get github.com/ncw/gotemplate/...
go get github.com/igrmk/treemap

Complexity

Name	Time
Set	O(logN)
Del	O(logN)
Get	O(logN)
Contains	O(logN)
Len	O(1)
Clear	O(1)
Range	O(logN)
Iterator	O(1)
Reverse	O(logN)
Iteration	O(N)

Memory usage

TreeMap uses O(N) memory.

Licensing

Copyright © 2018 Igor Mikushkin <[email protected]>. This work is free. You can redistribute it and/or modify it under the terms of the Unlicense. See the LICENSE file for more details.

Thanks to