Documentation
¶
Overview ¶
Package tree contains an implementation of a B-tree Map and Set. These are similar to Go's map built-in, but keep elements in sorted order.
Index ¶
- type Bound
- type KVPair
- type Map
- func (m Map[K, V]) Contains(k K) bool
- func (m Map[K, V]) Delete(k K)
- func (m Map[K, V]) First() (K, V)
- func (m Map[K, V]) Get(k K) V
- func (m Map[K, V]) Iterate() iterator.Iterator[KVPair[K, V]]
- func (m Map[K, V]) Last() (K, V)
- func (m Map[K, V]) Len() int
- func (m Map[K, V]) Put(k K, v V)
- func (m Map[K, V]) Range(lower Bound[K], upper Bound[K]) iterator.Iterator[KVPair[K, V]]
- func (m Map[K, V]) RangeReverse(lower Bound[K], upper Bound[K]) iterator.Iterator[KVPair[K, V]]
- type Set
- func (s Set[T]) Add(item T)
- func (s Set[T]) Contains(item T) bool
- func (s Set[T]) First() T
- func (s Set[T]) Iterate() iterator.Iterator[T]
- func (s Set[T]) Last() T
- func (s Set[T]) Len() int
- func (s Set[T]) Range(lower Bound[T], upper Bound[T]) iterator.Iterator[T]
- func (s Set[T]) RangeReverse(lower Bound[T], upper Bound[T]) iterator.Iterator[T]
- func (s Set[T]) Remove(item T)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Bound ¶ added in v0.5.0
type Bound[K any] struct { // contains filtered or unexported fields }
Bound is an endpoint for a range.
type Map ¶
Map is a tree-structured key-value map, similar to Go's built-in map but keeps elements in sorted order by key.
It is safe for multiple goroutines to Put concurrently with keys that are already in the map.
func NewMap ¶
NewMap returns a Map that uses less to determine the sort order of keys. If !less(a, b) && !less(b, a), then a and b are considered the same key. The output of less must not change for any pair of keys while they are in the map.
func (Map[K, V]) First ¶
func (m Map[K, V]) First() (K, V)
First returns the lowest-keyed entry in the map according to less.
func (Map[K, V]) Get ¶
func (m Map[K, V]) Get(k K) V
Get returns the value associated with the given key if it is present in the map. Otherwise, it returns the zero-value of V.
func (Map[K, V]) Iterate ¶
Iterate returns an iterator that yields the elements of the map in ascending order by key.
The map may be safely modified during iteration and the iterator will continue from the next-lowest key. Thus the iterator will see new elements that are after the current position of the iterator according to less, but will not necessarily see a consistent snapshot of the state of the map.
func (Map[K, V]) Last ¶
func (m Map[K, V]) Last() (K, V)
Last returns the highest-keyed entry in the map according to less.
func (Map[K, V]) Put ¶
func (m Map[K, V]) Put(k K, v V)
Put inserts the key-value pair into the map, overwriting the value for the key if it already exists.
func (Map[K, V]) Range ¶ added in v0.5.0
Range returns an iterator that yields the elements of the map between the given bounds in ascending order by key.
The map may be safely modified during iteration and the iterator will continue from the next-lowest key. Thus the iterator will see new elements that are after the current position of the iterator according to less, but will not necessarily see a consistent snapshot of the state of the map.
func (Map[K, V]) RangeReverse ¶ added in v0.5.0
RangeReverse returns an iterator that yields the elements of the map between the given bounds in descending order by key.
The map may be safely modified during iteration and the iterator will continue from the next-lowest key. Thus the iterator will see new elements that are after the current position of the iterator according to less, but will not necessarily see a consistent snapshot of the state of the map.
type Set ¶
type Set[T any] struct { // contains filtered or unexported fields }
Set is a tree-structured set. Sets are a collection of unique elements. Similar to Go's built-in map[T]struct{} but keeps elements in sorted order.
func NewSet ¶
NewSet returns a Set that uses less to determine the sort order of items. If !less(a, b) && !less(b, a), then a and b are considered the same item. The output of less must not change for any pair of items while they are in the set.
func (Set[T]) Add ¶
func (s Set[T]) Add(item T)
Add adds item to the set if it is not already present.
func (Set[T]) First ¶
func (s Set[T]) First() T
First returns the lowest item in the set according to less.
func (Set[T]) Iterate ¶
Iterate returns an iterator that yields the elements of the set in ascending order.
The set may be safely modified during iteration and the iterator will continue from the next-lowest item. Thus the iterator will see new items that are after the current position of the iterator according to less, but will not necessarily see a consistent snapshot of the state of the set.
func (Set[T]) Last ¶
func (s Set[T]) Last() T
Last returns the highest item in the set according to less.
func (Set[T]) Range ¶ added in v0.5.0
Range returns an iterator that yields the elements of the set between the given bounds in ascending order.
The set may be safely modified during iteration and the iterator will continue from the next-lowest item. Thus the iterator will see new items that are after the current position of the iterator according to less, but will not necessarily see a consistent snapshot of the state of the set.
func (Set[T]) RangeReverse ¶ added in v0.5.0
RangeReverse returns an iterator that yields the elements of the set between the given bounds in descending order.
The set may be safely modified during iteration and the iterator will continue from the next-lowest item. Thus the iterator will see new items that are after the current position of the iterator according to less, but will not necessarily see a consistent snapshot of the state of the set.
Source Files