list.go (2695B)
1 package maps 2 3 // list is a doubly-linked list containing elemnts with key-value pairs of given generic parameter types. 4 type list[K comparable, V any] struct { 5 head *elem[K, V] 6 tail *elem[K, V] 7 len int 8 } 9 10 // Index returns the element at index from list. 11 func (l *list[K, V]) Index(idx int) *elem[K, V] { 12 switch { 13 // Idx in first half 14 case idx < l.len/2: 15 elem := l.head 16 for i := 0; i < idx; i++ { 17 elem = elem.next 18 } 19 return elem 20 21 // Index in last half 22 default: 23 elem := l.tail 24 for i := l.len - 1; i > idx; i-- { 25 elem = elem.prev 26 } 27 return elem 28 } 29 } 30 31 // PushFront will push the given element to the front of the list. 32 func (l *list[K, V]) PushFront(elem *elem[K, V]) { 33 if l.len == 0 { 34 // Set new tail + head 35 l.head = elem 36 l.tail = elem 37 38 // Link elem to itself 39 elem.next = elem 40 elem.prev = elem 41 } else { 42 oldHead := l.head 43 44 // Link to old head 45 elem.next = oldHead 46 oldHead.prev = elem 47 48 // Link up to tail 49 elem.prev = l.tail 50 l.tail.next = elem 51 52 // Set new head 53 l.head = elem 54 } 55 56 // Incr count 57 l.len++ 58 } 59 60 // PushBack will push the given element to the back of the list. 61 func (l *list[K, V]) PushBack(elem *elem[K, V]) { 62 if l.len == 0 { 63 // Set new tail + head 64 l.head = elem 65 l.tail = elem 66 67 // Link elem to itself 68 elem.next = elem 69 elem.prev = elem 70 } else { 71 oldTail := l.tail 72 73 // Link up to head 74 elem.next = l.head 75 l.head.prev = elem 76 77 // Link to old tail 78 elem.prev = oldTail 79 oldTail.next = elem 80 81 // Set new tail 82 l.tail = elem 83 } 84 85 // Incr count 86 l.len++ 87 } 88 89 // PopTail will pop the current tail of the list, returns nil if empty. 90 func (l *list[K, V]) PopTail() *elem[K, V] { 91 if l.len == 0 { 92 return nil 93 } 94 elem := l.tail 95 l.Unlink(elem) 96 return elem 97 } 98 99 // Unlink will unlink the given element from the doubly-linked list chain. 100 func (l *list[K, V]) Unlink(elem *elem[K, V]) { 101 if l.len <= 1 { 102 // Drop elem's links 103 elem.next = nil 104 elem.prev = nil 105 106 // Only elem in list 107 l.head = nil 108 l.tail = nil 109 l.len = 0 110 return 111 } 112 113 // Get surrounding elems 114 next := elem.next 115 prev := elem.prev 116 117 // Relink chain 118 next.prev = prev 119 prev.next = next 120 121 switch elem { 122 // Set new head 123 case l.head: 124 l.head = next 125 126 // Set new tail 127 case l.tail: 128 l.tail = prev 129 } 130 131 // Drop elem's links 132 elem.next = nil 133 elem.prev = nil 134 135 // Decr count 136 l.len-- 137 } 138 139 // elem represents an element in a doubly-linked list. 140 type elem[K comparable, V any] struct { 141 next *elem[K, V] 142 prev *elem[K, V] 143 K K 144 V V 145 } 146 147 // allocElems will allocate a slice of empty elements of length. 148 func allocElems[K comparable, V any](i int) []*elem[K, V] { 149 s := make([]*elem[K, V], i) 150 for i := range s { 151 s[i] = &elem[K, V]{} 152 } 153 return s 154 }