1 | import { id } from './function.js'
|
2 | import * as error from './error.js'
|
3 |
|
4 | export class ListNode {
|
5 | constructor () {
|
6 | |
7 |
|
8 |
|
9 | this.next = null
|
10 | |
11 |
|
12 |
|
13 | this.prev = null
|
14 | }
|
15 | }
|
16 |
|
17 |
|
18 |
|
19 |
|
20 | export class List {
|
21 | constructor () {
|
22 | |
23 |
|
24 |
|
25 | this.start = null
|
26 | |
27 |
|
28 |
|
29 | this.end = null
|
30 | this.len = 0
|
31 | }
|
32 | }
|
33 |
|
34 |
|
35 |
|
36 |
|
37 |
|
38 |
|
39 |
|
40 |
|
41 |
|
42 | export const create = () => new List()
|
43 |
|
44 |
|
45 |
|
46 |
|
47 |
|
48 |
|
49 | export const isEmpty = queue => queue.start === null
|
50 |
|
51 |
|
52 |
|
53 |
|
54 |
|
55 |
|
56 |
|
57 |
|
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 |
|
78 |
|
79 | export const removeNode = remove
|
80 |
|
81 |
|
82 |
|
83 |
|
84 |
|
85 |
|
86 |
|
87 |
|
88 |
|
89 | export const insertBetween = (queue, left, right, node) => {
|
90 |
|
91 | if (left != null && left.next !== right) {
|
92 | throw error.unexpectedCase()
|
93 | }
|
94 | if (left) {
|
95 | left.next = node
|
96 | } else {
|
97 | queue.start = node
|
98 | }
|
99 | if (right) {
|
100 | right.prev = node
|
101 | } else {
|
102 | queue.end = node
|
103 | }
|
104 | node.prev = left
|
105 | node.next = right
|
106 | queue.len++
|
107 | }
|
108 |
|
109 |
|
110 |
|
111 |
|
112 |
|
113 |
|
114 |
|
115 |
|
116 |
|
117 |
|
118 | export const replace = (queue, node, newNode) => {
|
119 | insertBetween(queue, node, node.next, newNode)
|
120 | remove(queue, node)
|
121 | }
|
122 |
|
123 |
|
124 |
|
125 |
|
126 |
|
127 |
|
128 |
|
129 | export const pushEnd = (queue, n) =>
|
130 | insertBetween(queue, queue.end, null, n)
|
131 |
|
132 |
|
133 |
|
134 |
|
135 |
|
136 |
|
137 |
|
138 | export const pushFront = (queue, n) =>
|
139 | insertBetween(queue, null, queue.start, n)
|
140 |
|
141 |
|
142 |
|
143 |
|
144 |
|
145 |
|
146 |
|
147 | export const popFront = list =>
|
148 | list.start ? removeNode(list, list.start) : null
|
149 |
|
150 |
|
151 |
|
152 |
|
153 |
|
154 |
|
155 |
|
156 | export const popEnd = list =>
|
157 | list.end ? removeNode(list, list.end) : null
|
158 |
|
159 |
|
160 |
|
161 |
|
162 |
|
163 |
|
164 |
|
165 |
|
166 |
|
167 | export const map = (list, f) => {
|
168 | |
169 |
|
170 |
|
171 | const arr = []
|
172 | let n = list.start
|
173 | while (n) {
|
174 | arr.push(f(n))
|
175 | n = n.next
|
176 | }
|
177 | return arr
|
178 | }
|
179 |
|
180 |
|
181 |
|
182 |
|
183 |
|
184 |
|
185 | export const toArray = list => map(list, id)
|
186 |
|
187 |
|
188 |
|
189 |
|
190 |
|
191 |
|
192 |
|
193 |
|
194 | export const forEach = (list, f) => {
|
195 | let n = list.start
|
196 | while (n) {
|
197 | f(n)
|
198 | n = n.next
|
199 | }
|
200 | }
|