| 1 |
package orderedmap |
| 2 |
|
| 3 |
// Element is an element of a null terminated (non circular) intrusive doubly linked list that contains the key of the correspondent element in the ordered map too. |
| 4 |
type Element[K comparable, V any] struct { |
| 5 |
// Next and previous pointers in the doubly-linked list of elements. |
| 6 |
// To simplify the implementation, internally a list l is implemented |
| 7 |
// as a ring, such that &l.root is both the next element of the last |
| 8 |
// list element (l.Back()) and the previous element of the first list |
| 9 |
// element (l.Front()). |
| 10 |
next, prev *Element[K, V] |
| 11 |
|
| 12 |
// The key that corresponds to this element in the ordered map. |
| 13 |
Key K |
| 14 |
|
| 15 |
// The value stored with this element. |
| 16 |
Value V |
| 17 |
} |
| 18 |
|
| 19 |
// Next returns the next list element or nil. |
| 20 |
func (e *Element[K, V]) Next() *Element[K, V] { |
| 21 |
return e.next |
| 22 |
} |
| 23 |
|
| 24 |
// Prev returns the previous list element or nil. |
| 25 |
func (e *Element[K, V]) Prev() *Element[K, V] { |
| 26 |
return e.prev |
| 27 |
} |
| 28 |
|
| 29 |
// list represents a null terminated (non circular) intrusive doubly linked list. |
| 30 |
// The list is immediately usable after instantiation without the need of a dedicated initialization. |
| 31 |
type list[K comparable, V any] struct { |
| 32 |
root Element[K, V] // list head and tail |
| 33 |
} |
| 34 |
|
| 35 |
func (l *list[K, V]) IsEmpty() bool { |
| 36 |
return l.root.next == nil |
| 37 |
} |
| 38 |
|
| 39 |
// Front returns the first element of list l or nil if the list is empty. |
| 40 |
func (l *list[K, V]) Front() *Element[K, V] { |
| 41 |
return l.root.next |
| 42 |
} |
| 43 |
|
| 44 |
// Back returns the last element of list l or nil if the list is empty. |
| 45 |
func (l *list[K, V]) Back() *Element[K, V] { |
| 46 |
return l.root.prev |
| 47 |
} |
| 48 |
|
| 49 |
// Remove removes e from its list |
| 50 |
func (l *list[K, V]) Remove(e *Element[K, V]) { |
| 51 |
if e.prev == nil { |
| 52 |
l.root.next = e.next |
| 53 |
} else { |
| 54 |
e.prev.next = e.next |
| 55 |
} |
| 56 |
if e.next == nil { |
| 57 |
l.root.prev = e.prev |
| 58 |
} else { |
| 59 |
e.next.prev = e.prev |
| 60 |
} |
| 61 |
e.next = nil // avoid memory leaks |
| 62 |
e.prev = nil // avoid memory leaks |
| 63 |
} |
| 64 |
|
| 65 |
// PushFront inserts a new element e with value v at the front of list l and returns e. |
| 66 |
func (l *list[K, V]) PushFront(key K, value V) *Element[K, V] { |
| 67 |
e := &Element[K, V]{Key: key, Value: value} |
| 68 |
if l.root.next == nil { |
| 69 |
// It's the first element |
| 70 |
l.root.next = e |
| 71 |
l.root.prev = e |
| 72 |
return e |
| 73 |
} |
| 74 |
|
| 75 |
e.next = l.root.next |
| 76 |
l.root.next.prev = e |
| 77 |
l.root.next = e |
| 78 |
return e |
| 79 |
} |
| 80 |
|
| 81 |
// PushBack inserts a new element e with value v at the back of list l and returns e. |
| 82 |
func (l *list[K, V]) PushBack(key K, value V) *Element[K, V] { |
| 83 |
e := &Element[K, V]{Key: key, Value: value} |
| 84 |
if l.root.prev == nil { |
| 85 |
// It's the first element |
| 86 |
l.root.next = e |
| 87 |
l.root.prev = e |
| 88 |
return e |
| 89 |
} |
| 90 |
|
| 91 |
e.prev = l.root.prev |
| 92 |
l.root.prev.next = e |
| 93 |
l.root.prev = e |
| 94 |
return e |
| 95 |
} |