| 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 |
} |