README
¶
bst set/map
Fast and generic Set and Map implementations using binary-search-trees.
Documentation
Full documentation is available on GoDoc
Examples
As a Set:
{
set := bst.NewSet(5)
set.Add(bst.Int(3))
set.Add(bst.Int(5))
set.Add(bst.Int(1))
set.Add(bst.Int(3))
for iter := set.Iterator(); iter.Next(); {
fmt.Println(iter.Value())
}
}
As a Map:
{
set := bst.NewMap(5)
set.Set(bst.Int(5), "bar")
set.Set(bst.Int(3), "foo")
for iter := set.Iterator(); iter.Next(); {
fmt.Println(iter.Key(), iter.Value())
}
}
Documentation
¶
Overview ¶
Package bst is a fast and generic implementation of sets/maps using binary-search-trees in Go. Performance is optimised towards reads. Both, inserts and lookups are binary searches and therefore O(log n). Others tructures, such as b-trees and skiplists may be better suited if you are looking for a more balanced performance.
Please see examples for more details on usage.
Index ¶
- type Element
- type Float64
- type Int
- type Map
- func (m *Map) Add(key Element, value interface{}) (ok bool)
- func (m *Map) Delete(key Element) (ok bool)
- func (m *Map) Exists(key Element) bool
- func (m *Map) Get(key Element) (value interface{}, found bool)
- func (m *Map) Iterator() *MapIterator
- func (p Map) Len() int
- func (m *Map) Set(key Element, value interface{}) (replaced bool)
- type MapIterator
- type Set
- type SetIterator
- type String
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Element ¶
type Element interface {
// Must return true if element is less than the other
Less(other Element) bool
// Must return true if element is the equivalent of the other
Equals(other Element) bool
}
Element represents a value that is stores in the set
type Map ¶
type Map struct {
// contains filtered or unexported fields
}
Map is an extension of Set and allows to store additional information in the Element. It is NOT thread-safe, please implement your own locking when reading and writing it from multiple goroutines.
Example ¶
package main
import (
"fmt"
"github.com/bsm/bst"
)
func main() {
set := bst.NewMap(5)
set.Set(bst.Int(5), "bar")
set.Set(bst.Int(3), "foo")
value, ok := set.Get(bst.Int(3))
fmt.Println(value, ok)
value, ok = set.Get(bst.Int(4))
fmt.Println(value, ok)
}
Output: foo true <nil> false
func (*Map) Add ¶
Add acts like Set, but only adds the key if it does not exist, returns true if successful.
func (*Map) Get ¶
Get retrieves a value from the map, returns false as a second argument to indicate that key was not found.
func (*Map) Iterator ¶
func (m *Map) Iterator() *MapIterator
Iterator creates a new iterator
Example ¶
package main
import (
"fmt"
"github.com/bsm/bst"
)
func main() {
set := bst.NewMap(5)
set.Set(bst.Int(5), "bar")
set.Set(bst.Int(3), "foo")
for iter := set.Iterator(); iter.Next(); {
fmt.Println(iter.Key(), iter.Value())
}
}
Output: 3 foo 5 bar
type MapIterator ¶
type MapIterator struct {
// contains filtered or unexported fields
}
MapIterator is used to iterate over a map
func (*MapIterator) Key ¶
func (i *MapIterator) Key() Element
Key returns the current key or nil if invalid
func (*MapIterator) Next ¶
func (i *MapIterator) Next() bool
Next advances the cursor to the next position
func (*MapIterator) Previous ¶
func (i *MapIterator) Previous() bool
Previous advances the cursor to the previous position
func (*MapIterator) Seek ¶
func (i *MapIterator) Seek(pivot Element) bool
Seek places the cursor to the value greater or equal to pivot
func (*MapIterator) Value ¶
func (i *MapIterator) Value() interface{}
Value returns the current key or nil if invalid
type Set ¶
type Set struct {
// contains filtered or unexported fields
}
Set stores elements as a sorted slice. It is NOT thread-safe, please implement your own locking when reading and writing it from multiple goroutines.
Example ¶
package main
import (
"fmt"
"github.com/bsm/bst"
)
func main() {
set := bst.NewSet(5)
set.Add(bst.Int(3))
set.Add(bst.Int(5))
set.Add(bst.Int(1))
set.Add(bst.Int(3))
fmt.Println(set.Len())
}
Output: 3
func (*Set) Add ¶
Add adds a value to the set
Example ¶
package main
import (
"fmt"
"github.com/bsm/bst"
)
func main() {
set := bst.NewSet(5)
fmt.Println(set.Add(bst.Int(1)))
fmt.Println(set.Add(bst.Int(2)))
fmt.Println(set.Add(bst.Int(1)))
}
Output: true true false
func (*Set) Intersects ¶
Intersects checks if the set is intersectable with other
func (*Set) Iterator ¶
func (s *Set) Iterator() *SetIterator
Iterator creates a new iterator
Example ¶
package main
import (
"fmt"
"github.com/bsm/bst"
)
func main() {
set := bst.NewSet(5)
set.Add(bst.Int(3))
set.Add(bst.Int(5))
set.Add(bst.Int(1))
set.Add(bst.Int(3))
for iter := set.Iterator(); iter.Next(); {
fmt.Println(iter.Value())
}
}
Output: 1 3 5
type SetIterator ¶
type SetIterator struct {
// contains filtered or unexported fields
}
SetIterator is used to iterate over a set
func (*SetIterator) Next ¶
func (i *SetIterator) Next() bool
Next advances the cursor to the next position
func (*SetIterator) Previous ¶
func (i *SetIterator) Previous() bool
Previous advances the cursor to the previous position
func (*SetIterator) Value ¶
func (i *SetIterator) Value() Element
Value returns the value at the current cursor position or nil if cursor is invalid
Source Files