Debian Codegraph @

v2/list.go

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