Documentation
¶
Overview ¶
Package tree implements an in-memory ordered map using a tree. The map supports arbitrary keys and comparison functions.
Index ¶
- type Map
- func (m *Map[K, V]) Above(lo K) MapSpan[K, V]
- func (m *Map[K, V]) All() iter.Seq2[K, V]
- func (m *Map[K, V]) At(key K) V
- func (m *Map[K, V]) Backward() iter.Seq2[K, V]
- func (m *Map[K, V]) Below(hi K) MapSpan[K, V]
- func (m *Map[K, V]) Clear()
- func (m *Map[K, V]) Clone() *Map[K, V]
- func (m *Map[K, V]) Contains(key K) bool
- func (m *Map[K, V]) ContainsAll(keys iter.Seq[K]) bool
- func (m *Map[K, V]) Delete(key K) (V, bool)
- func (m *Map[K, V]) DeleteAll(keys iter.Seq[K]) bool
- func (m *Map[K, V]) From(lo K) MapSpan[K, V]
- func (m *Map[K, V]) Get(key K) (V, bool)
- func (m *Map[K, V]) Index(key K) int
- func (m *Map[K, V]) Keys() iter.Seq[K]
- func (m *Map[K, V]) Len() int
- func (m *Map[K, V]) Max() (K, V, bool)
- func (m *Map[K, V]) Min() (K, V, bool)
- func (m *Map[K, V]) Nth(i int) (K, V)
- func (m *Map[K, V]) Set(key K, val V) (old V, added bool)
- func (m *Map[K, V]) SetAll(seq iter.Seq2[K, V]) bool
- func (m *Map[K, V]) String() string
- func (m *Map[K, V]) To(hi K) MapSpan[K, V]
- func (m *Map[K, V]) Values() iter.Seq[V]
- type MapSpan
- func (s MapSpan[K, V]) Above(lo K) MapSpan[K, V]
- func (s MapSpan[K, V]) All() iter.Seq2[K, V]
- func (s MapSpan[K, V]) Backward() iter.Seq2[K, V]
- func (s MapSpan[K, V]) Below(hi K) MapSpan[K, V]
- func (s MapSpan[K, V]) Clear()
- func (s MapSpan[K, V]) Clone() *Map[K, V]
- func (s MapSpan[K, V]) From(lo K) MapSpan[K, V]
- func (s MapSpan[K, V]) Index(key K) int
- func (s MapSpan[K, V]) Keys() iter.Seq[K]
- func (s MapSpan[K, V]) Len() int
- func (s MapSpan[K, V]) Max() (K, V, bool)
- func (s MapSpan[K, V]) Min() (K, V, bool)
- func (s MapSpan[K, V]) Nth(i int) (K, V)
- func (s MapSpan[K, V]) String() string
- func (s MapSpan[K, V]) To(hi K) MapSpan[K, V]
- func (s MapSpan[K, V]) Values() iter.Seq[V]
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Map ¶
type Map[K, V any] struct { // contains filtered or unexported fields }
A Map is a map[K]V ordered according to an arbitrary comparison function. The zero value of a Map is not meaningful since it has no comparison function. Use NewMap to create a Map. A nil *Map, like a nil Go map, can be read but not written and contains no entries.
func (*Map[K, V]) Above ¶
Above returns a MapSpan with lower bound lo, exclusive, and no upper bound.
func (*Map[K, V]) All ¶
All returns an iterator over the map m from smallest to largest key. If m is modified during the iteration, All guarantees that when a key is yielded, it is the successor of the key that was previously yielded (or the minimum key in the map, if it is the first key).
For example, if the map contains keys 10 and 20, the iterator has yielded 10, and then 15 is inserted, then the next yielded key will be 15.
Another example: if the map contains keys 10, 20 and 30, the iterator has yielded 10, and then 20 is deleted, then the next yielded key will be 30.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/jba/omap/ordered"
)
func main() {
m := ordered.NewMap[int, string](cmp.Compare)
m.Set(1, "one")
m.Set(2, "two")
m.Set(3, "three")
for k, v := range m.All() {
fmt.Println(k, v)
}
}
Output: 1 one 2 two 3 three
func (*Map[K, V]) At ¶
func (m *Map[K, V]) At(key K) V
At returns the value of m[key], or the zero value if key is not present.
func (*Map[K, V]) Backward ¶
Backward returns an iterator over the map m from largest to smallest key. See Map.All for the guarantee provided if m is modified during the iteration.
func (*Map[K, V]) Below ¶
Below returns a MapSpan with upper bound hi, exclusive, and no lower bound.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/jba/omap/ordered"
)
func main() {
m := ordered.NewMap[int, string](cmp.Compare)
m.Set(1, "one")
m.Set(2, "two")
m.Set(3, "three")
for k, v := range m.Above(1).Below(3).All() {
fmt.Println(k, v)
}
}
Output: 2 two
func (*Map[K, V]) ContainsAll ¶
ContainsAll reports whether the map contains an entry for each key in the sequence.
func (*Map[K, V]) Delete ¶
Delete removes the entry with the given key, if present. It reports whether the map changed, and returns the previous value, if any.
func (*Map[K, V]) DeleteAll ¶
DeleteAll removes all the entries whose keys are in the sequence. It reports whether the map changed.
func (*Map[K, V]) From ¶
From returns a MapSpan with lower bound lo, inclusive, and no upper bound.
Example ¶
package main
import (
"cmp"
"fmt"
"github.com/jba/omap/ordered"
)
func main() {
m := ordered.NewMap[int, string](cmp.Compare)
m.Set(1, "one")
m.Set(2, "two")
m.Set(3, "three")
for k, v := range m.From(2).All() {
fmt.Println(k, v)
}
}
Output: 2 two 3 three
func (*Map[K, V]) Keys ¶
Keys returns an iterator over the keys in m from smallest to largest. See Map.All for the guarantee provided if m is modified during the iteration.
func (*Map[K, V]) Max ¶
Max returns the maximum key in m, its value, and true. If m is empty, the third return value is false.
func (*Map[K, V]) Min ¶
Min returns the minimum key in m, its value, and true. If m is empty, the third return value is false.
func (*Map[K, V]) Nth ¶
Nth returns the key and value at index i. It panics if i < 0 or i >= m.Len().
func (*Map[K, V]) Set ¶
Set sets m[key] = val. If the entry was present, Set returns the former value and false. Otherwise it returns the zero value and true.
func (*Map[K, V]) SetAll ¶
SetAll calls Set(k, v) for each key/value pair in the sequence. It reports whether the number of map entries increased.
func (*Map[K, V]) String ¶
String returns a string representation of m in the form "{k1: v1, k2: v2}".
type MapSpan ¶
type MapSpan[K, V any] struct { // contains filtered or unexported fields }
A MapSpan is a subsequence of keys in a Map.
func (MapSpan[K, V]) Above ¶
Above returns a MapSpan with lower bound lo, exclusive and the same upper bound as s, if lo is within s's current lower bound. Otherwise, it returns s.
func (MapSpan[K, V]) All ¶
All returns an iterator over r's underlying map from smallest to largest key in r. See Map.All for the guarantee provided if m is modified during the iteration.
func (MapSpan[K, V]) Backward ¶
Backward returns an iterator over r's underlying map from largest to smallest key in r. See Map.All for the guarantee provided if m is modified during the iteration.
func (MapSpan[K, V]) Below ¶
Below returns a MapSpan with upper bound hi, exclusive and the same lower bound as s, if hi is within s's current upper bound. Otherwise, it returns s.
func (MapSpan[K, V]) Clear ¶
func (s MapSpan[K, V]) Clear()
Clear deletes all the entries in r from r's underlying map.
func (MapSpan[K, V]) From ¶
From returns a MapSpan with lower bound lo, inclusive and the same upper bound as s, if lo is within s's current lower bound. Otherwise, it returns s.
func (MapSpan[K, V]) Index ¶
Index returns the index of key within r, or -1 if key is not present or not in bounds.
func (MapSpan[K, V]) Keys ¶
Keys returns an iterator over the keys in r from smallest to largest. See Map.All for the guarantee provided if m is modified during the iteration.
func (MapSpan[K, V]) Max ¶
Max returns the maximum key from r's underlying map that is in r, its value, and true. If m is empty, the third return value is false.
func (MapSpan[K, V]) Min ¶
Min returns the minimum key from r's underlying map that is in r, its value, and true. If m is empty, the third return value is false.
func (MapSpan[K, V]) Nth ¶
Nth returns the key and value at index i within r. It panics if i < 0 or i >= r.Len().
Source Files