Debian Codegraph @

v2/orderedmap.go

raw
1 package orderedmap
2
3 type OrderedMap[K comparable, V any] struct {
4 kv map[K]*Element[K, V]
5 ll list[K, V]
6 }
7
8 func NewOrderedMap[K comparable, V any]() *OrderedMap[K, V] {
9 return &OrderedMap[K, V]{
10 kv: make(map[K]*Element[K, V]),
11 }
12 }
13
14 // NewOrderedMapWithCapacity creates a map with enough pre-allocated space to
15 // hold the specified number of elements.
16 func NewOrderedMapWithCapacity[K comparable, V any](capacity int) *OrderedMap[K, V] {
17 return &OrderedMap[K, V]{
18 kv: make(map[K]*Element[K, V], capacity),
19 }
20 }
21
22 func NewOrderedMapWithElements[K comparable, V any](els ...*Element[K, V]) *OrderedMap[K, V] {
23 om := NewOrderedMapWithCapacity[K, V](len(els))
24 for _, el := range els {
25 om.Set(el.Key, el.Value)
26 }
27 return om
28 }
29
30 // Get returns the value for a key. If the key does not exist, the second return
31 // parameter will be false and the value will be nil.
32 func (m *OrderedMap[K, V]) Get(key K) (value V, ok bool) {
33 v, ok := m.kv[key]
34 if ok {
35 value = v.Value
36 }
37
38 return
39 }
40
41 // Set will set (or replace) a value for a key. If the key was new, then true
42 // will be returned. The returned value will be false if the value was replaced
43 // (even if the value was the same).
44 func (m *OrderedMap[K, V]) Set(key K, value V) bool {
45 _, alreadyExist := m.kv[key]
46 if alreadyExist {
47 m.kv[key].Value = value
48 return false
49 }
50
51 element := m.ll.PushBack(key, value)
52 m.kv[key] = element
53 return true
54 }
55
56 // ReplaceKey replaces an existing key with a new key while preserving order of
57 // the value. This function will return true if the operation was successful, or
58 // false if 'originalKey' is not found OR 'newKey' already exists (which would be an overwrite).
59 func (m *OrderedMap[K, V]) ReplaceKey(originalKey, newKey K) bool {
60 element, originalExists := m.kv[originalKey]
61 _, newKeyExists := m.kv[newKey]
62 if originalExists && !newKeyExists {
63 delete(m.kv, originalKey)
64 m.kv[newKey] = element
65 element.Key = newKey
66 return true
67 }
68 return false
69 }
70
71 // GetOrDefault returns the value for a key. If the key does not exist, returns
72 // the default value instead.
73 func (m *OrderedMap[K, V]) GetOrDefault(key K, defaultValue V) V {
74 if value, ok := m.kv[key]; ok {
75 return value.Value
76 }
77
78 return defaultValue
79 }
80
81 // GetElement returns the element for a key. If the key does not exist, the
82 // pointer will be nil.
83 func (m *OrderedMap[K, V]) GetElement(key K) *Element[K, V] {
84 element, ok := m.kv[key]
85 if ok {
86 return element
87 }
88
89 return nil
90 }
91
92 // Len returns the number of elements in the map.
93 func (m *OrderedMap[K, V]) Len() int {
94 return len(m.kv)
95 }
96
97 // Keys returns all of the keys in the order they were inserted. If a key was
98 // replaced it will retain the same position. To ensure most recently set keys
99 // are always at the end you must always Delete before Set.
100 func (m *OrderedMap[K, V]) Keys() (keys []K) {
101 keys = make([]K, 0, m.Len())
102 for el := m.Front(); el != nil; el = el.Next() {
103 keys = append(keys, el.Key)
104 }
105 return keys
106 }
107
108 // Delete will remove a key from the map. It will return true if the key was
109 // removed (the key did exist).
110 func (m *OrderedMap[K, V]) Delete(key K) (didDelete bool) {
111 element, ok := m.kv[key]
112 if ok {
113 m.ll.Remove(element)
114 delete(m.kv, key)
115 }
116
117 return ok
118 }
119
120 // Front will return the element that is the first (oldest Set element). If
121 // there are no elements this will return nil.
122 func (m *OrderedMap[K, V]) Front() *Element[K, V] {
123 return m.ll.Front()
124 }
125
126 // Back will return the element that is the last (most recent Set element). If
127 // there are no elements this will return nil.
128 func (m *OrderedMap[K, V]) Back() *Element[K, V] {
129 return m.ll.Back()
130 }
131
132 // Copy returns a new OrderedMap with the same elements.
133 // Using Copy while there are concurrent writes may mangle the result.
134 func (m *OrderedMap[K, V]) Copy() *OrderedMap[K, V] {
135 m2 := NewOrderedMapWithCapacity[K, V](m.Len())
136 for el := m.Front(); el != nil; el = el.Next() {
137 m2.Set(el.Key, el.Value)
138 }
139 return m2
140 }
141
142 // Has checks if a key exists in the map.
143 func (m *OrderedMap[K, V]) Has(key K) bool {
144 _, exists := m.kv[key]
145 return exists
146 }