-
Notifications
You must be signed in to change notification settings - Fork 0
/
orderedmap.go
117 lines (102 loc) · 2.66 KB
/
orderedmap.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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package orderedmap
type NodeI[K any, V any] interface {
GetValue() V
SetValue(V)
String() string
}
type IterI[K any, V any] interface {
Next() bool
KV() (K, V)
}
type ListI[K any, V any] interface {
Insert(K, V) NodeI[K, V]
Delete(NodeI[K, V])
Iter() IterI[K, V]
String() string
}
type Compare[K any] func(k1, k2 K) int
type CmpValue[V any] func(v1, v2 V) int
type OrderedMap[K comparable, V any] struct {
kv map[K]NodeI[K, V]
l ListI[K, V]
cmpVal bool
}
func New[K comparable, V any]() *OrderedMap[K, V] {
return &OrderedMap[K, V]{
kv: make(map[K]NodeI[K, V]),
l: NewDoubleList[K, V](),
}
}
// NewCmp compare key
func NewCmp[K comparable, V any](cmp Compare[K]) *OrderedMap[K, V] {
return &OrderedMap[K, V]{
kv: make(map[K]NodeI[K, V]),
l: NewSkipList[K, V](func(k1, k2 K, v1, v2 V) int { return cmp(k1, k2) }),
}
}
// NewCmpVal compare value
func NewCmpVal[K comparable, V any](cmp CmpValue[V]) *OrderedMap[K, V] {
return &OrderedMap[K, V]{
kv: make(map[K]NodeI[K, V]),
l: NewSkipList[K, V](func(k1, k2 K, v1, v2 V) int { return cmp(v1, v2) }),
cmpVal: true,
}
}
// Get returns the value for a key. If the key does not exist, the second return
// parameter will be false and the value will be the zero value of V.
func (m *OrderedMap[K, V]) Get(key K) (value V, ok bool) {
var v NodeI[K, V]
v, ok = m.kv[key]
if ok {
value = v.GetValue()
}
return
}
// GetOrDefault returns the value for a key. If the key does not exist, returns
// the default value instead.
func (m *OrderedMap[K, V]) GetOrDefault(key K, defaultValue V) V {
if value, ok := m.kv[key]; ok {
return value.GetValue()
}
return defaultValue
}
// Set will set (or update) a value for a key. If the key was new, then true
// will be returned. The returned value will be false if the value was replaced.
func (m *OrderedMap[K, V]) Set(key K, value V) {
node, ok := m.kv[key]
if ok && !m.cmpVal {
node.SetValue(value)
return
}
if ok && m.cmpVal {
m.l.Delete(node)
}
m.kv[key] = m.l.Insert(key, value)
return
}
// Len returns the number of elements in the map.
func (m *OrderedMap[K, V]) Len() int {
return len(m.kv)
}
// Del will remove a key from the map. It will return true if the key was
// exist,otherwise return false
func (m *OrderedMap[K, V]) Del(key K) {
node, ok := m.kv[key]
if ok {
m.l.Delete(node)
delete(m.kv, key)
}
}
// Iter iterate all keys in the map.
func (m *OrderedMap[K, V]) Iter() IterI[K, V] {
return m.l.Iter()
}
// Keys returns all the keys in the map.
func (m *OrderedMap[K, V]) Keys() (keys []K) {
keys = make([]K, 0, m.Len())
for iter := m.l.Iter(); iter.Next(); {
k, _ := iter.KV()
keys = append(keys, k)
}
return keys
}