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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
package maps
// list is a doubly-linked list containing elemnts with key-value pairs of given generic parameter types.
type list[K comparable, V any] struct {
head *elem[K, V]
tail *elem[K, V]
len int
}
// Index returns the element at index from list.
func (l *list[K, V]) Index(idx int) *elem[K, V] {
switch {
// Idx in first half
case idx < l.len/2:
elem := l.head
for i := 0; i < idx; i++ {
elem = elem.next
}
return elem
// Index in last half
default:
elem := l.tail
for i := l.len - 1; i > idx; i-- {
elem = elem.prev
}
return elem
}
}
// PushFront will push the given element to the front of the list.
func (l *list[K, V]) PushFront(elem *elem[K, V]) {
if l.len == 0 {
// Set new tail + head
l.head = elem
l.tail = elem
// Link elem to itself
elem.next = elem
elem.prev = elem
} else {
oldHead := l.head
// Link to old head
elem.next = oldHead
oldHead.prev = elem
// Link up to tail
elem.prev = l.tail
l.tail.next = elem
// Set new head
l.head = elem
}
// Incr count
l.len++
}
// PushBack will push the given element to the back of the list.
func (l *list[K, V]) PushBack(elem *elem[K, V]) {
if l.len == 0 {
// Set new tail + head
l.head = elem
l.tail = elem
// Link elem to itself
elem.next = elem
elem.prev = elem
} else {
oldTail := l.tail
// Link up to head
elem.next = l.head
l.head.prev = elem
// Link to old tail
elem.prev = oldTail
oldTail.next = elem
// Set new tail
l.tail = elem
}
// Incr count
l.len++
}
// PopTail will pop the current tail of the list, returns nil if empty.
func (l *list[K, V]) PopTail() *elem[K, V] {
if l.len == 0 {
return nil
}
elem := l.tail
l.Unlink(elem)
return elem
}
// Unlink will unlink the given element from the doubly-linked list chain.
func (l *list[K, V]) Unlink(elem *elem[K, V]) {
if l.len <= 1 {
// Drop elem's links
elem.next = nil
elem.prev = nil
// Only elem in list
l.head = nil
l.tail = nil
l.len = 0
return
}
// Get surrounding elems
next := elem.next
prev := elem.prev
// Relink chain
next.prev = prev
prev.next = next
switch elem {
// Set new head
case l.head:
l.head = next
// Set new tail
case l.tail:
l.tail = prev
}
// Drop elem's links
elem.next = nil
elem.prev = nil
// Decr count
l.len--
}
// elem represents an element in a doubly-linked list.
type elem[K comparable, V any] struct {
next *elem[K, V]
prev *elem[K, V]
K K
V V
}
// allocElems will allocate a slice of empty elements of length.
func allocElems[K comparable, V any](i int) []*elem[K, V] {
s := make([]*elem[K, V], i)
for i := range s {
s[i] = &elem[K, V]{}
}
return s
}
|
