Documentation
¶
Overview ¶
Package tree implements in-memory ordered maps. OrderedMap[K, V] is suitable for ordered types K, while Map[K, V] supports arbitrary keys and comparison functions.
Index ¶
- type Map
- func (m *Map[K, V]) Above(lo K) Range[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) Range[K, V]
- func (m *Map[K, V]) Clear()
- func (m *Map[K, V]) Clone() *Map[K, V]
- func (m *Map[K, V]) Delete(key K) bool
- func (m *Map[K, V]) From(lo K) Range[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]) Insert(key K, val V) (old V, added bool)
- 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]) To(hi K) Range[K, V]
- type OrderedMap
- func (m *OrderedMap[K, V]) Above(lo K) OrderedRange[K, V]
- func (m *OrderedMap[K, V]) All() iter.Seq2[K, V]
- func (m *OrderedMap[K, V]) At(key K) V
- func (m *OrderedMap[K, V]) Backward() iter.Seq2[K, V]
- func (m *OrderedMap[K, V]) Below(hi K) OrderedRange[K, V]
- func (m *OrderedMap[K, V]) Clear()
- func (m *OrderedMap[K, V]) Clone() *OrderedMap[K, V]
- func (m *OrderedMap[K, V]) Delete(key K) bool
- func (m *OrderedMap[K, V]) From(lo K) OrderedRange[K, V]
- func (m *OrderedMap[K, V]) Get(key K) (V, bool)
- func (m *OrderedMap[K, V]) Index(key K) int
- func (m *OrderedMap[K, V]) Insert(key K, val V) (old V, added bool)
- func (m *OrderedMap[K, V]) Len() int
- func (m *OrderedMap[K, V]) Max() (K, V, bool)
- func (m *OrderedMap[K, V]) Min() (K, V, bool)
- func (m *OrderedMap[K, V]) Nth(i int) (K, V)
- func (m *OrderedMap[K, V]) To(hi K) OrderedRange[K, V]
- type OrderedRange
- func (r OrderedRange[K, V]) All() iter.Seq2[K, V]
- func (r OrderedRange[K, V]) Backward() iter.Seq2[K, V]
- func (r OrderedRange[K, V]) Below(hi K) OrderedRange[K, V]
- func (r OrderedRange[K, V]) Clear()
- func (r OrderedRange[K, V]) Clone() *OrderedMap[K, V]
- func (r OrderedRange[K, V]) Index(key K) int
- func (r OrderedRange[K, V]) Len() int
- func (r OrderedRange[K, V]) Max() (K, V, bool)
- func (r OrderedRange[K, V]) Min() (K, V, bool)
- func (r OrderedRange[K, V]) Nth(i int) (K, V)
- func (r OrderedRange[K, V]) To(hi K) OrderedRange[K, V]
- type Range
- func (r Range[K, V]) All() iter.Seq2[K, V]
- func (r Range[K, V]) Backward() iter.Seq2[K, V]
- func (r Range[K, V]) Below(hi K) Range[K, V]
- func (r Range[K, V]) Clear()
- func (r Range[K, V]) Clone() *Map[K, V]
- func (r Range[K, V]) Index(key K) int
- func (r Range[K, V]) Len() int
- func (r Range[K, V]) Max() (K, V, bool)
- func (r Range[K, V]) Min() (K, V, bool)
- func (r Range[K, V]) Nth(i int) (K, V)
- func (r Range[K, V]) To(hi K) Range[K, 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 an Range 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. See OrderedMap.All for the guarantee provided if m is modified during the iteration.
Example ¶
package main
import (
"fmt"
"github.com/jba/omap/tree"
)
func main() {
m := &tree.OrderedMap[int, string]{}
m.Insert(1, "one")
m.Insert(2, "two")
m.Insert(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 OrderedMap.All for the guarantee provided if m is modified during the iteration.
func (*Map[K, V]) Below ¶
Below returns an Range with upper bound hi, exclusive, and no lower bound.
Example ¶
package main
import (
"fmt"
"github.com/jba/omap/tree"
)
func main() {
m := &tree.OrderedMap[int, string]{}
m.Insert(1, "one")
m.Insert(2, "two")
m.Insert(3, "three")
for k, v := range m.Above(1).Below(3).All() {
fmt.Println(k, v)
}
}
Output: 2 two
func (*Map[K, V]) From ¶
From returns an Range with lower bound lo, inclusive, and no upper bound.
Example ¶
package main
import (
"fmt"
"github.com/jba/omap/tree"
)
func main() {
m := &tree.OrderedMap[int, string]{}
m.Insert(1, "one")
m.Insert(2, "two")
m.Insert(3, "three")
for k, v := range m.From(2).All() {
fmt.Println(k, v)
}
}
Output: 2 two 3 three
func (*Map[K, V]) Insert ¶
Insert sets m[key] = val. If the entry was present, Insert returns the former value and false. Otherwise it returns the zero value and true.
func (*Map[K, V]) Max ¶
Max returns the maximum key in m, is 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.
type OrderedMap ¶
A OrderedMap is a map[K]V ordered according to K's standard Go ordering. The zero value of a OrderedMap is an empty OrderedMap ready to use.
func (*OrderedMap[K, V]) Above ¶
func (m *OrderedMap[K, V]) Above(lo K) OrderedRange[K, V]
Above returns an OrderedRange with lower bound lo, exclusive, and no upper bound.
func (*OrderedMap[K, V]) All ¶
func (m *OrderedMap[K, V]) All() iter.Seq2[K, V]
All returns an iterator over the map m from smallest to largest key. If m is modified during the iteration, All makes this guarantee: 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.
func (*OrderedMap[K, V]) At ¶
func (m *OrderedMap[K, V]) At(key K) V
At returns the value of m[key], or the zero value if key is not present.
func (*OrderedMap[K, V]) Backward ¶
func (m *OrderedMap[K, V]) Backward() iter.Seq2[K, V]
Backward returns an iterator over the map m from largest to smallest key. See OrderedMap.All for the guarantee provided if m is modified during the iteration.
func (*OrderedMap[K, V]) Below ¶
func (m *OrderedMap[K, V]) Below(hi K) OrderedRange[K, V]
Below returns an OrderedRange with upper bound hi, exclusive, and no lower bound.
func (*OrderedMap[K, V]) Clear ¶
func (m *OrderedMap[K, V]) Clear()
Clear deletes m[k] for all keys in m.
func (*OrderedMap[K, V]) Clone ¶
func (m *OrderedMap[K, V]) Clone() *OrderedMap[K, V]
Clone returns a shallow copy of m.
func (*OrderedMap[K, V]) Delete ¶
func (m *OrderedMap[K, V]) Delete(key K) bool
Delete deletes m[key] if it exists.
func (*OrderedMap[K, V]) From ¶
func (m *OrderedMap[K, V]) From(lo K) OrderedRange[K, V]
From returns an OrderedRange with lower bound lo, inclusive, and no upper bound.
func (*OrderedMap[K, V]) Get ¶
func (m *OrderedMap[K, V]) Get(key K) (V, bool)
Get returns the value of m[key] and reports whether it exists.
func (*OrderedMap[K, V]) Index ¶
func (m *OrderedMap[K, V]) Index(key K) int
Index returns the index of key in m, or -1 if key is not present.
func (*OrderedMap[K, V]) Insert ¶
func (m *OrderedMap[K, V]) Insert(key K, val V) (old V, added bool)
Insert sets m[key] = val. If the entry was present, Insert returns the former value and false. Otherwise it returns the zero value and true.
func (*OrderedMap[K, V]) Len ¶
func (m *OrderedMap[K, V]) Len() int
Len returns the number of keys in m.
func (*OrderedMap[K, V]) Max ¶
func (m *OrderedMap[K, V]) Max() (K, V, bool)
Max returns the maximum key in m, its value, and true. If m is empty, the third return value is false.
func (*OrderedMap[K, V]) Min ¶
func (m *OrderedMap[K, V]) Min() (K, V, bool)
Min returns the minimum key in m, its value, and true. If m is empty, the third return value is false.
func (*OrderedMap[K, V]) Nth ¶
func (m *OrderedMap[K, V]) Nth(i int) (K, V)
Nth returns the key and value at index i. It panics if i < 0 or i >= m.Len().
func (*OrderedMap[K, V]) To ¶
func (m *OrderedMap[K, V]) To(hi K) OrderedRange[K, V]
To returns an OrderedRange with upper bound hi, inclusive, and no lower bound.
type OrderedRange ¶
A OrderedRange is a subsequence of keys in a OrderedMap.
func (OrderedRange[K, V]) All ¶
func (r OrderedRange[K, V]) All() iter.Seq2[K, V]
All returns an iterator over r's underlying map from smallest to largest key in r. See OrderedMap.All for the guarantee provided if m is modified during the iteration.
func (OrderedRange[K, V]) Backward ¶
func (r OrderedRange[K, V]) Backward() iter.Seq2[K, V]
Backward returns an iterator over r's underlying map from largest to smallest key in r. See OrderedMap.All for the guarantee provided if m is modified during the iteration.
func (OrderedRange[K, V]) Below ¶
func (r OrderedRange[K, V]) Below(hi K) OrderedRange[K, V]
Below returns an OrderedRange with upper bound hi, exclusive and the same lower bound as r. It panics if r already has an upper bound.
func (OrderedRange[K, V]) Clear ¶
func (r OrderedRange[K, V]) Clear()
Clear deletes all the entries in r from r's underlying map.
func (OrderedRange[K, V]) Clone ¶
func (r OrderedRange[K, V]) Clone() *OrderedMap[K, V]
Clone returns a new OrderedMap containing only the keys in r.
func (OrderedRange[K, V]) Index ¶
func (r OrderedRange[K, V]) Index(key K) int
Index returns the index of key within r, or -1 if key is not present or not in bounds.
func (OrderedRange[K, V]) Len ¶
func (r OrderedRange[K, V]) Len() int
Len returns the number of keys in r.
func (OrderedRange[K, V]) Max ¶
func (r OrderedRange[K, V]) Max() (K, V, bool)
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 (OrderedRange[K, V]) Min ¶
func (r OrderedRange[K, V]) Min() (K, V, bool)
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 (OrderedRange[K, V]) Nth ¶
func (r OrderedRange[K, V]) Nth(i int) (K, V)
Nth returns the key and value at index i within r. It panics if i < 0 or i >= r.Len().
func (OrderedRange[K, V]) To ¶
func (r OrderedRange[K, V]) To(hi K) OrderedRange[K, V]
To returns an OrderedRange with upper bound hi, inclusive and the same lower bound as r. It panics if r already has an upper bound.
type Range ¶
type Range[K, V any] struct { // contains filtered or unexported fields }
A Range is a subsequence of keys in a Map.
func (Range[K, V]) All ¶
All returns an iterator over r's underlying map from smallest to largest key in r. See OrderedMap.All for the guarantee provided if m is modified during the iteration.
func (Range[K, V]) Backward ¶
Backward returns an iterator over r's underlying map from largest to smallest key in r. See OrderedMap.All for the guarantee provided if m is modified during the iteration.
func (Range[K, V]) Below ¶
Below returns a Range with upper bound hi, exclusive and the same lower bound as r. It panics if r already has an upper bound.
func (Range[K, V]) Clear ¶
func (r Range[K, V]) Clear()
Clear deletes all the entries in r from r's underlying map.
func (Range[K, V]) Index ¶
Index returns the index of key within r, or -1 if key is not present or not in bounds.
func (Range[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 (Range[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.
Source Files