README
¶
Ordered Maps
This package provides ordered maps. It is a fork of github.com/rsc/omap, whose import path is rsc.io/omap.
An ordered map is an association between keys and values, where only comparisons are permitted between keys. Like standard Go maps, ordered maps support efficient access to keys and values. Unlike standard Go maps, they support iteration in key order, in both directions, for both the entire map and any subsequence of keys.
In this implementation, it takes logarithmic time (O(log n), where n is the number of keys in the map) to retrieve a value from a key, set a key to a value, or delete a key and its associated value. It also takes logarithmic time to retrieve the minimum or maximum key, or delete a subsequence of keys and their values. In the absence of modifications, the time to iterate over k keys is O(k). All these times are asymptotically optimal for data structures that allow only comparison of keys.
Ranges
This implementation supports iteration over, and deletion of, subsequences
via ranges. A Range consists of an underlying map and up to two bounds
specifying the Range's endpoints. Ranges are constructed with a natural API.
To iterate over all keys in a map m between a and b inclusive, write
for k, v := range m.From(a).To(b).All() {...}
To delete all keys in the map between a and b, but not including either
of those keys, write
m.Above(a).Below(b).Clear()
The range API supports subsequence operations for any contiguous subsequence of keys.
Iteration guarantees
When modifications to a map are interleaved with iteration, this implementation
guarantees that each key provided by the iterator is the successor of the previous
key at the time that the yield function is called. That is, the iteration will
skip deleted keys that it has not yet encountered, and will included inserted
keys that are greater than its current key.
An iterator may required extra time to achieve this guarantee. In the worst case, an iterator can take O(klogn) time to iterate over k keys in a map of size n. The extra time is only needed if the map is modified; if not, the iterator runs in the optimal O(k) time.
Documentation
¶
Overview ¶
Package omap implements in-memory ordered maps. Map[K, V] is suitable for ordered types K, while MapFunc[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(i int) (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]) Len() int
- func (m *Map[K, V]) Max() (K, bool)
- func (m *Map[K, V]) Min() (K, bool)
- func (m *Map[K, V]) Set(key K, val V) (old V, added bool)
- func (m *Map[K, V]) To(hi K) Range[K, V]
- type MapFunc
- func (m *MapFunc[K, V]) Above(lo K) RangeFunc[K, V]
- func (m *MapFunc[K, V]) All() iter.Seq2[K, V]
- func (m *MapFunc[K, V]) At(i int) (K, V)
- func (m *MapFunc[K, V]) Backward() iter.Seq2[K, V]
- func (m *MapFunc[K, V]) Below(hi K) RangeFunc[K, V]
- func (m *MapFunc[K, V]) Clear()
- func (m *MapFunc[K, V]) Clone() *MapFunc[K, V]
- func (m *MapFunc[K, V]) Delete(key K) bool
- func (m *MapFunc[K, V]) From(lo K) RangeFunc[K, V]
- func (m *MapFunc[K, V]) Get(key K) (V, bool)
- func (m *MapFunc[K, V]) Len() int
- func (m *MapFunc[K, v]) Max() (K, bool)
- func (m *MapFunc[K, v]) Min() (K, bool)
- func (m *MapFunc[K, V]) Set(key K, val V) (old V, added bool)
- func (m *MapFunc[K, V]) To(hi K) RangeFunc[K, V]
- type Range
- type RangeFunc
- func (r RangeFunc[K, V]) All() iter.Seq2[K, V]
- func (r RangeFunc[K, V]) Backward() iter.Seq2[K, V]
- func (r RangeFunc[K, V]) Below(hi K) RangeFunc[K, V]
- func (r RangeFunc[K, V]) Clear()
- func (r RangeFunc[K, V]) Max() (K, bool)
- func (r RangeFunc[K, V]) Min() (K, bool)
- func (r RangeFunc[K, V]) To(hi K) RangeFunc[K, V]
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Map ¶
A Map is a map[K]V ordered according to K's standard Go ordering. The zero value of a Map is an empty Map ready to use.
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 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.
Example ¶
package main
import (
"fmt"
"github.com/jba/omap"
)
func main() {
var m omap.Map[int, string]
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]) 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]) From ¶
From returns a Range with lower bound lo, inclusive, and no upper bound.
Example ¶
package main
import (
"fmt"
"github.com/jba/omap"
)
func main() {
var m omap.Map[int, string]
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]) Max ¶
Max returns the maximum key in m and true. If m is empty, the second return value is false.
func (*Map[K, V]) Min ¶
Min returns the minimum key in m and true. If m is empty, the second return value is false.
type MapFunc ¶
type MapFunc[K, V any] struct { // contains filtered or unexported fields }
A MapFunc is a map[K]V ordered according to an arbitrary comparison function. The zero value of a MapFunc is not meaningful since it has no comparison function. Use NewMapFunc to create a MapFunc. A nil *MapFunc, like a nil Go map, can be read but not written and contains no entries.
func NewMapFunc ¶
NewMapFunc returns a new MapFunc[K, V] ordered according to cmp.
func (*MapFunc[K, V]) Above ¶
Above returns a Range with lower bound lo, exclusive, and no upper bound.
func (*MapFunc[K, V]) All ¶
All returns an iterator over the map m from smallest to largest key. See Map.All for the guarantee provided if m is modified during the iteration.
func (*MapFunc[K, V]) At ¶
At returns the key and value at index i. It panics if i < 0 or i >= m.Len().
func (*MapFunc[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 (*MapFunc[K, V]) Below ¶
Below returns a Range with upper bound hi, exclusive, and no lower bound.
func (*MapFunc[K, V]) From ¶
From returns a Range with lower bound lo, inclusive, and no upper bound.
func (*MapFunc[K, v]) Max ¶
Max returns the maximum key in m and true. If m is empty, the second return value is false.
func (*MapFunc[K, v]) Min ¶
Min returns the minimum key in m and true. If m is empty, the second return value is false.
type Range ¶
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 Map.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 Map.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]) Max ¶
Max returns the maximum key from r's underlying map that is in r and true. If m is empty, the second return value is false.
type RangeFunc ¶
type RangeFunc[K, V any] struct { // contains filtered or unexported fields }
A RangeFunc is a subsequence of keys in a MapFunc.
func (RangeFunc[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 (RangeFunc[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 (RangeFunc[K, V]) Below ¶
Below returns a RangeFunc with upper bound hi, exclusive and the same lower bound as r. It panics if r already has an upper bound.
func (RangeFunc[K, V]) Clear ¶
func (r RangeFunc[K, V]) Clear()
Clear deletes all the entries in r from r's underlying map.
func (RangeFunc[K, V]) Max ¶
Max returns the maximum key from r's underlying map that is in r and true. If m is empty, the second return value is false.
Source Files