-
Notifications
You must be signed in to change notification settings - Fork 61
/
orderedmap.go
109 lines (92 loc) 路 2.81 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
package orderedmap
type OrderedMap[K comparable, V any] struct {
kv map[K]*Element[K, V]
ll list[K, V]
}
func NewOrderedMap[K comparable, V any]() *OrderedMap[K, V] {
return &OrderedMap[K, V]{
kv: make(map[K]*Element[K, V]),
}
}
// 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 nil.
func (m *OrderedMap[K, V]) Get(key K) (value V, ok bool) {
v, ok := m.kv[key]
if ok {
value = v.Value
}
return
}
// Set will set (or replace) 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
// (even if the value was the same).
func (m *OrderedMap[K, V]) Set(key K, value V) bool {
_, alreadyExist := m.kv[key]
if alreadyExist {
m.kv[key].Value = value
return false
}
element := m.ll.PushBack(key, value)
m.kv[key] = element
return true
}
// 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.Value
}
return defaultValue
}
// GetElement returns the element for a key. If the key does not exist, the
// pointer will be nil.
func (m *OrderedMap[K, V]) GetElement(key K) *Element[K, V] {
element, ok := m.kv[key]
if ok {
return element
}
return nil
}
// Len returns the number of elements in the map.
func (m *OrderedMap[K, V]) Len() int {
return len(m.kv)
}
// Keys returns all of the keys in the order they were inserted. If a key was
// replaced it will retain the same position. To ensure most recently set keys
// are always at the end you must always Delete before Set.
func (m *OrderedMap[K, V]) Keys() (keys []K) {
keys = make([]K, 0, m.Len())
for el := m.Front(); el != nil; el = el.Next() {
keys = append(keys, el.Key)
}
return keys
}
// Delete will remove a key from the map. It will return true if the key was
// removed (the key did exist).
func (m *OrderedMap[K, V]) Delete(key K) (didDelete bool) {
element, ok := m.kv[key]
if ok {
m.ll.Remove(element)
delete(m.kv, key)
}
return ok
}
// Front will return the element that is the first (oldest Set element). If
// there are no elements this will return nil.
func (m *OrderedMap[K, V]) Front() *Element[K, V] {
return m.ll.Front()
}
// Back will return the element that is the last (most recent Set element). If
// there are no elements this will return nil.
func (m *OrderedMap[K, V]) Back() *Element[K, V] {
return m.ll.Back()
}
// Copy returns a new OrderedMap with the same elements.
// Using Copy while there are concurrent writes may mangle the result.
func (m *OrderedMap[K, V]) Copy() *OrderedMap[K, V] {
m2 := NewOrderedMap[K, V]()
for el := m.Front(); el != nil; el = el.Next() {
m2.Set(el.Key, el.Value)
}
return m2
}