-
Notifications
You must be signed in to change notification settings - Fork 1
/
ordered-map-func.go
57 lines (51 loc) · 1.81 KB
/
ordered-map-func.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*
© 2023–present Harald Rudell <harald.rudell@gmail.com> (https://haraldrudell.github.io/haraldrudell/)
ISC License
*/
package omaps
import (
"github.com/google/btree"
)
// OrderedMapFunc is a mapping whose values are provided in custom order
// - mapping implementation is Go map
// - ordering structure is B-tree
// - B-tree offers:
// - — avoiding vector-copy of large sorted slices which is slow and
// - — avoiding linear traversal of linked-lists which is slow and
// - — is a more efficient structure than binary tree
type OrderedMapFunc[K comparable, V any] struct {
// Get() Length() Range() Delete() Clear() List()
btreeMap[K, V]
// type LessFunc[T any] func(a, b T) bool.
// - less(a, b) implements sort order and returns:
// - — true if a sorts before b
// - — false if a is of equal rank to b, or a is after b
// - — a equals b must not return true
less btree.LessFunc[V]
}
// NewOrderedMapFunc returns a mapping whose values are provided in custom order.
// - less(a, b) implements sort order and returns:
// - — true if a sorts before b
// - — false if a is of equal rank to b, or a is after b
// - — a equals b must not return true
// - btree.Ordered does not include ~uintptr
func NewOrderedMapFunc[K comparable, V any](
less func(a, b V) (aBeforeB bool),
) (orderedMap *OrderedMapFunc[K, V]) {
return &OrderedMapFunc[K, V]{
btreeMap: *newBTreeMap2Any[K, V](less),
less: less,
}
}
// Put creates or replaces a mapping
func (m *OrderedMapFunc[K, V]) Put(key K, value V) {
m.btreeMap.put(key, value, m.less)
}
// Clone returns a shallow clone of the map
// - clone is done by ranging all keys
func (m *OrderedMapFunc[K, V]) Clone() (clone *OrderedMapFunc[K, V]) {
return &OrderedMapFunc[K, V]{
btreeMap: *m.btreeMap.Clone(),
less: m.less,
}
}