1 | import { id } from './function.js'
|
2 | import * as error from './error.js'
|
3 |
|
4 | export class ListNode {
|
5 | constructor () {
|
6 | /**
|
7 | * @type {this|null}
|
8 | */
|
9 | this.next = null
|
10 | /**
|
11 | * @type {this|null}
|
12 | */
|
13 | this.prev = null
|
14 | }
|
15 | }
|
16 |
|
17 | /**
|
18 | * @template {ListNode} N
|
19 | */
|
20 | export class List {
|
21 | constructor () {
|
22 | /**
|
23 | * @type {N | null}
|
24 | */
|
25 | this.start = null
|
26 | /**
|
27 | * @type {N | null}
|
28 | */
|
29 | this.end = null
|
30 | this.len = 0
|
31 | }
|
32 | }
|
33 |
|
34 | /**
|
35 | * @note The queue implementation is experimental and unfinished.
|
36 | * Don't use this in production yet.
|
37 | *
|
38 | * @template {ListNode} N
|
39 | *
|
40 | * @return {List<N>}
|
41 | */
|
42 | export const create = () => new List()
|
43 |
|
44 | /**
|
45 | * @template {ListNode} N
|
46 | *
|
47 | * @param {List<N>} queue
|
48 | */
|
49 | export const isEmpty = queue => queue.start === null
|
50 |
|
51 | /**
|
52 | * Remove a single node from the queue. Only works with Queues that operate on Doubly-linked lists of nodes.
|
53 | *
|
54 | * @template {ListNode} N
|
55 | *
|
56 | * @param {List<N>} queue
|
57 | * @param {N} node
|
58 | */
|
59 | export const remove = (queue, node) => {
|
60 | const prev = node.prev
|
61 | const next = node.next
|
62 | if (prev) {
|
63 | prev.next = next
|
64 | } else {
|
65 | queue.start = next
|
66 | }
|
67 | if (next) {
|
68 | next.prev = prev
|
69 | } else {
|
70 | queue.end = prev
|
71 | }
|
72 | queue.len--
|
73 | return node
|
74 | }
|
75 |
|
76 | /**
|
77 | * @deprecated @todo remove in next major release
|
78 | */
|
79 | export const removeNode = remove
|
80 |
|
81 | /**
|
82 | * @template {ListNode} N
|
83 | *
|
84 | * @param {List<N>} queue
|
85 | * @param {N| null} left
|
86 | * @param {N| null} right
|
87 | * @param {N} node
|
88 | */
|
89 | export const insertBetween = (queue, left, right, node) => {
|
90 | /* c8 ignore start */
|
91 | if (left != null && left.next !== right) {
|
92 | throw error.unexpectedCase()
|
93 | }
|
94 | /* c8 ignore stop */
|
95 | if (left) {
|
96 | left.next = node
|
97 | } else {
|
98 | queue.start = node
|
99 | }
|
100 | if (right) {
|
101 | right.prev = node
|
102 | } else {
|
103 | queue.end = node
|
104 | }
|
105 | node.prev = left
|
106 | node.next = right
|
107 | queue.len++
|
108 | }
|
109 |
|
110 | /**
|
111 | * Remove a single node from the queue. Only works with Queues that operate on Doubly-linked lists of nodes.
|
112 | *
|
113 | * @template {ListNode} N
|
114 | *
|
115 | * @param {List<N>} queue
|
116 | * @param {N} node
|
117 | * @param {N} newNode
|
118 | */
|
119 | export const replace = (queue, node, newNode) => {
|
120 | insertBetween(queue, node, node.next, newNode)
|
121 | remove(queue, node)
|
122 | }
|
123 |
|
124 | /**
|
125 | * @template {ListNode} N
|
126 | *
|
127 | * @param {List<N>} queue
|
128 | * @param {N} n
|
129 | */
|
130 | export const pushEnd = (queue, n) =>
|
131 | insertBetween(queue, queue.end, null, n)
|
132 |
|
133 | /**
|
134 | * @template {ListNode} N
|
135 | *
|
136 | * @param {List<N>} queue
|
137 | * @param {N} n
|
138 | */
|
139 | export const pushFront = (queue, n) =>
|
140 | insertBetween(queue, null, queue.start, n)
|
141 |
|
142 | /**
|
143 | * @template {ListNode} N
|
144 | *
|
145 | * @param {List<N>} list
|
146 | * @return {N| null}
|
147 | */
|
148 | export const popFront = list =>
|
149 | list.start ? removeNode(list, list.start) : null
|
150 |
|
151 | /**
|
152 | * @template {ListNode} N
|
153 | *
|
154 | * @param {List<N>} list
|
155 | * @return {N| null}
|
156 | */
|
157 | export const popEnd = list =>
|
158 | list.end ? removeNode(list, list.end) : null
|
159 |
|
160 | /**
|
161 | * @template {ListNode} N
|
162 | * @template M
|
163 | *
|
164 | * @param {List<N>} list
|
165 | * @param {function(N):M} f
|
166 | * @return {Array<M>}
|
167 | */
|
168 | export const map = (list, f) => {
|
169 | /**
|
170 | * @type {Array<M>}
|
171 | */
|
172 | const arr = []
|
173 | let n = list.start
|
174 | while (n) {
|
175 | arr.push(f(n))
|
176 | n = n.next
|
177 | }
|
178 | return arr
|
179 | }
|
180 |
|
181 | /**
|
182 | * @template {ListNode} N
|
183 | *
|
184 | * @param {List<N>} list
|
185 | */
|
186 | export const toArray = list => map(list, id)
|
187 |
|
188 | /**
|
189 | * @template {ListNode} N
|
190 | * @template M
|
191 | *
|
192 | * @param {List<N>} list
|
193 | * @param {function(N):M} f
|
194 | */
|
195 | export const forEach = (list, f) => {
|
196 | let n = list.start
|
197 | while (n) {
|
198 | f(n)
|
199 | n = n.next
|
200 | }
|
201 | }
|