1/**
2 * Mutable lists for collecting ordered values and draining them from the front.
3 * A `MutableList<A>` can append values to the end, prepend values to the
4 * beginning, take one or more values from the front, inspect its contents as an
5 * array, filter values, remove values, and clear itself. All operations update
6 * the same list object in place and keep its `length` field current. Taking
7 * from an empty list returns the `Empty` symbol.
8 *
9 * @since 4.0.0
10 */
11import * as Arr from "./Array.ts"
12import * as Count from "./internal/count.ts"
13
14/**
15 * A mutable linked list data structure optimized for high-throughput operations.
16 * MutableList provides efficient append/prepend operations and is ideal for
17 * producer-consumer patterns, queues, and streaming scenarios.
18 *
19 * **Example** (Creating and consuming a mutable list)
20 *
21 * ```ts import.meta.vitest
22 * import { MutableList } from "effect"
23 *
24 * const list: MutableList.MutableList<number> = MutableList.make()
25 * MutableList.append(list, 1)
26 * MutableList.append(list, 2)
27 * MutableList.prepend(list, 0)
28 *
29 * MutableList.takeAll(list) // => [0, 1, 2]
30 * list.length // => 0
31 * ```
32 *
33 * @category models
34 * @since 2.0.0
35 */
36export interface MutableList<in out A> {
37 head: MutableList.Bucket<A> | undefined
38 tail: MutableList.Bucket<A> | undefined
39 length: number
40}
41
42/**
43 * The MutableList namespace contains type definitions and utilities for working
44 * with mutable linked lists.
45 *
46 * @since 2.0.0
47 */
48export declare namespace MutableList {
49 /**
50 * Storage node used by the exposed `head` and `tail` fields of a
51 * `MutableList`.
52 *
53 * **Details**
54 *
55 * Most code should treat buckets as an implementation detail and use
56 * `MutableList` operations such as `append`, `prepend`, and `take` instead
57 * of constructing or mutating buckets directly.
58 *
59 * **Example** (Inspecting buckets)
60 *
61 * ```ts import.meta.vitest
62 * import { MutableList } from "effect"
63 *
64 * const list = MutableList.make<number>()
65 * MutableList.append(list, 1)
66 * MutableList.append(list, 2)
67 *
68 * const bucket: MutableList.MutableList.Bucket<number> = list.head!
69 *
70 * bucket.array // => [1, 2]
71 * bucket.offset // => 0
72 * bucket.mutable // => true
73 * bucket.next === undefined // => true
74 * ```
75 *
76 * @category models
77 * @since 4.0.0
78 */
79 export interface Bucket<A> {
80 readonly array: Array<A>
81 mutable: boolean
82 offset: number
83 next: Bucket<A> | undefined
84 }
85}
86
87/**
88 * Defines the unique symbol used to represent an empty result when taking elements from a MutableList.
89 * This symbol is returned by `take` when the list is empty, allowing for safe type checking.
90 *
91 * **When to use**
92 *
93 * Use to detect that `take` returned no element before handling the result as a
94 * list item.
95 *
96 * **Example** (Checking for empty results)
97 *
98 * ```ts import.meta.vitest
99 * import { MutableList } from "effect"
100 *
101 * const list = MutableList.make<string>()
102 *
103 * MutableList.take(list) === MutableList.Empty // => true
104 * ```
105 *
106 * @category symbols
107 * @since 4.0.0
108 */
109export const Empty: unique symbol = Symbol.for("effect/MutableList/Empty")
110
111/**
112 * The type of the Empty symbol, used for type checking when taking elements from a MutableList.
113 * This provides compile-time safety when checking for empty results.
114 *
115 * **Example** (Handling empty results type-safely)
116 *
117 * ```ts import.meta.vitest
118 * import { MutableList } from "effect"
119 *
120 * const list = MutableList.make<number>()
121 *
122 * const takeAndDouble = (queue: MutableList.MutableList<number>): number | null => {
123 * const item: number | MutableList.Empty = MutableList.take(queue)
124 * return item === MutableList.Empty ? null : item * 2
125 * }
126 *
127 * takeAndDouble(list) // => null
128 * MutableList.append(list, 5)
129 * takeAndDouble(list) // => 10
130 * ```
131 *
132 * @category symbols
133 * @since 4.0.0
134 */
135export type Empty = typeof Empty
136
137/**
138 * Creates an empty MutableList.
139 *
140 * **Example** (Creating an empty mutable list)
141 *
142 * ```ts import.meta.vitest
143 * import { MutableList } from "effect"
144 *
145 * const list = MutableList.make<string>()
146 *
147 * list.length // => 0
148 * MutableList.append(list, "first")
149 * MutableList.take(list) // => "first"
150 * list.length // => 0
151 * ```
152 *
153 * @category constructors
154 * @since 2.0.0
155 */
156export const make = <A>(): MutableList<A> => ({
157 head: undefined,
158 tail: undefined,
159 length: 0
160})
161
162// A mutable tail bucket grows with every append while takes only advance its
163// offset, so a list that never drains keeps every slot it ever used. Copy the
164// live values into a fresh bucket once consumed slots dominate.
165const compactHead = <A>(self: MutableList<A>): void => {
166 const head = self.head!
167 if (
168 head.offset >= 1024 && head === self.tail && head.mutable &&
169 (head.array.length - head.offset) * 8 <= head.offset
170 ) {
171 self.head = self.tail = {
172 array: head.array.slice(head.offset),
173 mutable: true,
174 offset: 0,
175 next: undefined
176 }
177 }
178}
179
180const emptyBucket = <A = never>(): MutableList.Bucket<A> => ({
181 array: [],
182 mutable: true,
183 offset: 0,
184 next: undefined
185})
186
187/**
188 * Appends an element to the end of the MutableList.
189 * This operation is optimized for high-frequency usage.
190 *
191 * **Example** (Appending elements)
192 *
193 * ```ts import.meta.vitest
194 * import { MutableList } from "effect"
195 *
196 * const list = MutableList.make<number>()
197 * MutableList.append(list, 1)
198 * MutableList.append(list, 2)
199 * MutableList.append(list, 3)
200 *
201 * MutableList.toArray(list) // => [1, 2, 3]
202 * list.length // => 3
203 * ```
204 *
205 * @category mutations
206 * @since 2.0.0
207 */
208export const append = <A>(self: MutableList<A>, message: A): void => {
209 if (!self.tail) {
210 self.head = self.tail = emptyBucket()
211 } else if (!self.tail.mutable) {
212 self.tail.next = emptyBucket()
213 self.tail = self.tail.next
214 }
215 self.tail!.array.push(message)
216 self.length++
217}
218
219/**
220 * Prepends an element to the beginning of the MutableList.
221 * This operation is optimized for high-frequency usage.
222 *
223 * **Example** (Prepending elements)
224 *
225 * ```ts import.meta.vitest
226 * import { MutableList } from "effect"
227 *
228 * const list = MutableList.make<string>()
229 * MutableList.append(list, "last")
230 * MutableList.prepend(list, "third")
231 * MutableList.prepend(list, "second")
232 * MutableList.prepend(list, "first")
233 *
234 * MutableList.toArray(list) // => ["first", "second", "third", "last"]
235 * ```
236 *
237 * @category mutations
238 * @since 2.0.0
239 */
240export const prepend = <A>(self: MutableList<A>, message: A): void => {
241 self.head = {
242 array: [message],
243 mutable: true,
244 offset: 0,
245 next: self.head
246 }
247 if (!self.tail) self.tail = self.head
248 self.length++
249}
250
251/**
252 * Prepends all elements from an iterable to the beginning of the MutableList.
253 * The elements are added in order, so the first element in the iterable becomes
254 * the new head of the list.
255 *
256 * **Example** (Prepending multiple elements)
257 *
258 * ```ts import.meta.vitest
259 * import { MutableList } from "effect"
260 *
261 * const list = MutableList.make<number>()
262 * MutableList.append(list, 4)
263 * MutableList.append(list, 5)
264 * MutableList.prependAll(list, [1, 2, 3])
265 *
266 * MutableList.toArray(list) // => [1, 2, 3, 4, 5]
267 * ```
268 *
269 * @category mutations
270 * @since 4.0.0
271 */
272export const prependAll = <A>(self: MutableList<A>, messages: Iterable<A>): void =>
273 prependAllUnsafe(self, Arr.fromIterable(messages), !Array.isArray(messages))
274
275/**
276 * Prepends all elements from a ReadonlyArray to the beginning of the MutableList.
277 * This is an optimized version that can reuse the array when mutable=true.
278 *
279 * **When to use**
280 *
281 * Use when prepending a trusted array directly is worth the optimized path and
282 * you can transfer ownership of the input when enabling mutation.
283 *
284 * **Gotchas**
285 *
286 * When mutable=true, ownership of the input array transfers to the list. Do not
287 * read or modify the array afterward.
288 *
289 * **Example** (Transferring an array when prepending)
290 *
291 * ```ts import.meta.vitest
292 * import { MutableList } from "effect"
293 *
294 * const list = MutableList.make<number>()
295 * MutableList.append(list, 4)
296 * const items = [1, 2, 3]
297 * MutableList.prependAllUnsafe(list, items, true)
298 *
299 * MutableList.toArray(list) // => [1, 2, 3, 4]
300 * ```
301 *
302 * @category mutations
303 * @since 4.0.0
304 */
305export const prependAllUnsafe = <A>(self: MutableList<A>, messages: ReadonlyArray<A>, mutable = false): void => {
306 if (messages.length === 0) {
307 return
308 }
309 self.head = {
310 array: messages as Array<A>,
311 mutable,
312 offset: 0,
313 next: self.head
314 }
315 if (!self.tail) self.tail = self.head
316 self.length += self.head.array.length
317}
318
319/**
320 * Appends all elements from an iterable to the end of the MutableList.
321 * Returns the number of elements added.
322 *
323 * **Example** (Appending multiple elements)
324 *
325 * ```ts import.meta.vitest
326 * import { MutableList } from "effect"
327 *
328 * const list = MutableList.make<number>()
329 * MutableList.append(list, 1)
330 * MutableList.append(list, 2)
331 *
332 * MutableList.appendAll(list, [3, 4, 5]) // => 3
333 * MutableList.toArray(list) // => [1, 2, 3, 4, 5]
334 * list.length // => 5
335 * ```
336 *
337 * @category mutations
338 * @since 4.0.0
339 */
340export const appendAll = <A>(self: MutableList<A>, messages: Iterable<A>): number =>
341 appendAllUnsafe(self, Arr.fromIterable(messages), !Array.isArray(messages))
342
343/**
344 * Appends all elements from a ReadonlyArray to the end of the MutableList.
345 * This is an optimized version that can reuse the array when mutable=true.
346 * Returns the number of elements added.
347 *
348 * **When to use**
349 *
350 * Use when appending a trusted array directly is worth the optimized path and
351 * you can transfer ownership of the input when enabling mutation.
352 *
353 * **Gotchas**
354 *
355 * When mutable=true, ownership of the input array transfers to the list. Do not
356 * read or modify the array afterward.
357 *
358 * **Example** (Transferring an array when appending)
359 *
360 * ```ts import.meta.vitest
361 * import { MutableList } from "effect"
362 *
363 * const list = MutableList.make<number>()
364 * MutableList.append(list, 1)
365 * const items = [2, 3, 4]
366 * MutableList.appendAllUnsafe(list, items, true) // => 3
367 *
368 * MutableList.toArray(list) // => [1, 2, 3, 4]
369 * ```
370 *
371 * @category mutations
372 * @since 4.0.0
373 */
374export const appendAllUnsafe = <A>(self: MutableList<A>, messages: ReadonlyArray<A>, mutable = false): number => {
375 if (messages.length === 0) {
376 return 0
377 }
378 const chunk: MutableList.Bucket<A> = {
379 array: messages as Array<A>,
380 mutable,
381 offset: 0,
382 next: undefined
383 }
384 if (self.head) {
385 self.tail = self.tail!.next = chunk
386 } else {
387 self.head = self.tail = chunk
388 }
389 self.length += messages.length
390 return messages.length
391}
392
393/**
394 * Removes all elements from the MutableList, resetting it to an empty state.
395 * This operation is highly optimized and releases all internal memory.
396 *
397 * **Example** (Clearing a mutable list)
398 *
399 * ```ts import.meta.vitest
400 * import { MutableList } from "effect"
401 *
402 * const list = MutableList.make<number>()
403 * MutableList.appendAll(list, [1, 2, 3, 4, 5])
404 *
405 * MutableList.clear(list)
406 *
407 * MutableList.toArray(list) // => []
408 * list.length // => 0
409 * MutableList.take(list) === MutableList.Empty // => true
410 * ```
411 *
412 * @category mutations
413 * @since 4.0.0
414 */
415export const clear = <A>(self: MutableList<A>): void => {
416 self.head = self.tail = undefined
417 self.length = 0
418}
419
420/**
421 * Takes up to N elements from the beginning of the MutableList and returns them as an array.
422 * The taken elements are removed from the list. This operation is optimized for performance
423 * and includes zero-copy optimizations when possible.
424 *
425 * **Details**
426 *
427 * Finite fractional values of `n` are rounded down. `NaN` and non-positive
428 * values leave the list unchanged and return an empty array.
429 *
430 * **Example** (Taking batches)
431 *
432 * ```ts import.meta.vitest
433 * import { MutableList } from "effect"
434 *
435 * const list = MutableList.make<number>()
436 * MutableList.appendAll(list, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
437 *
438 * MutableList.takeN(list, 3) // => [1, 2, 3]
439 * MutableList.toArray(list) // => [4, 5, 6, 7, 8, 9, 10]
440 * list.length // => 7
441 * ```
442 *
443 * @category mutations
444 * @since 4.0.0
445 */
446export const takeN = <A>(self: MutableList<A>, n: number): Array<A> => {
447 n = Count.normalize(n)
448 if (n <= 0 || !self.head) return []
449 n = Math.min(n, self.length)
450 if (n === self.length && self.head?.offset === 0 && !self.head.next) {
451 const array = self.head.array
452 clear(self)
453 return array
454 }
455 const array = new Array<A>(n)
456 let index = 0
457 let chunk: MutableList.Bucket<A> | undefined = self.head
458 while (chunk) {
459 while (chunk.offset < chunk.array.length) {
460 array[index++] = chunk.array[chunk.offset]
461 if (chunk.mutable) chunk.array[chunk.offset] = undefined as any
462 chunk.offset++
463 if (index === n) {
464 self.head = chunk.offset === chunk.array.length && chunk.next ? chunk.next : chunk
465 self.length -= n
466 if (self.length === 0) clear(self)
467 else compactHead(self)
468 return array
469 }
470 }
471 chunk = chunk.next
472 }
473 clear(self)
474 return array
475}
476
477/**
478 * Removes up to `n` elements from the beginning of the `MutableList` without
479 * returning them.
480 *
481 * **When to use**
482 *
483 * Use to discard a bounded number of values from the head of a `MutableList`
484 * when the removed values are not needed.
485 *
486 * **Details**
487 *
488 * Finite fractional values of `n` are rounded down. If `n` is `NaN` or
489 * non-positive, or the list is empty, the list is left unchanged. If the
490 * normalized count is greater than or equal to the current length, the list is
491 * cleared.
492 *
493 * @see {@link takeN} for removing up to `n` values and returning them as an array
494 * @see {@link clear} for removing every value from the list
495 *
496 * @category mutations
497 * @since 4.0.0
498 */
499export const takeNVoid = <A>(self: MutableList<A>, n: number): void => {
500 n = Count.normalize(n)
501 if (n <= 0 || !self.head) return
502 n = Math.min(n, self.length)
503 if (n === self.length && self.head?.offset === 0 && !self.head.next) {
504 clear(self)
505 return
506 }
507 let count = 0
508 let chunk: MutableList.Bucket<A> | undefined = self.head
509 while (chunk) {
510 const size = chunk.array.length - chunk.offset
511 if (count + size > n) {
512 chunk.offset += n - count
513 self.head = chunk
514 self.length -= n
515 compactHead(self)
516 return
517 }
518 count += size
519 chunk = chunk.next
520 }
521 clear(self)
522 return
523}
524
525/**
526 * Takes all elements from the MutableList and returns them as an array.
527 * The list becomes empty after this operation. This is equivalent to takeN(list, list.length).
528 *
529 * **Example** (Draining all elements)
530 *
531 * ```ts import.meta.vitest
532 * import { MutableList } from "effect"
533 *
534 * const list = MutableList.make<string>()
535 * MutableList.appendAll(list, ["apple", "banana", "cherry"])
536 *
537 * MutableList.takeAll(list) // => ["apple", "banana", "cherry"]
538 * list.length // => 0
539 * ```
540 *
541 * @category mutations
542 * @since 4.0.0
543 */
544export const takeAll = <A>(self: MutableList<A>): Array<A> => takeN(self, self.length)
545
546/**
547 * Takes a single element from the beginning of the MutableList.
548 * Returns the element if available, or the Empty symbol if the list is empty.
549 * The taken element is removed from the list.
550 *
551 * **Example** (Taking one element)
552 *
553 * ```ts import.meta.vitest
554 * import { MutableList } from "effect"
555 *
556 * const list = MutableList.make<string>()
557 * MutableList.appendAll(list, ["first", "second", "third"])
558 *
559 * MutableList.take(list) // => "first"
560 * MutableList.toArray(list) // => ["second", "third"]
561 * list.length // => 2
562 * ```
563 *
564 * @category mutations
565 * @since 4.0.0
566 */
567export const take = <A>(self: MutableList<A>): Empty | A => {
568 if (!self.head) return Empty
569 const message = self.head.array[self.head.offset]
570 if (self.head.mutable) self.head.array[self.head.offset] = undefined as any
571 self.head.offset++
572 self.length--
573 if (self.head.offset === self.head.array.length) {
574 if (self.head.next) {
575 self.head = self.head.next
576 } else {
577 clear(self)
578 }
579 } else {
580 compactHead(self)
581 }
582 return message
583}
584
585/**
586 * Copies up to `n` elements from the beginning of the `MutableList` into a new
587 * array without modifying the list.
588 *
589 * **When to use**
590 *
591 * Use when you need to inspect or snapshot a bounded prefix of the list without
592 * consuming it.
593 *
594 * **Details**
595 *
596 * Finite fractional values of `n` are rounded down. `NaN` and non-positive
597 * values return an empty array.
598 *
599 * @see {@link takeN} for removing up to `n` values and returning them as an array
600 *
601 * @category converting
602 * @since 4.0.0
603 */
604export const toArrayN = <A>(self: MutableList<A>, n: number): Array<A> => {
605 n = Count.normalize(n)
606 if (n <= 0) return []
607 const length = Math.min(n, self.length)
608 const out = new Array<A>(length)
609 let index = 0
610 let bucket = self.head
611 while (bucket) {
612 for (let i = bucket.offset; i < bucket.array.length; i++) {
613 out[index++] = bucket.array[i]
614 if (index === length) return out
615 }
616 bucket = bucket.next
617 }
618 return out
619}
620
621/**
622 * Copies all current elements of the `MutableList` into a new array without
623 * modifying the list.
624 *
625 * **When to use**
626 *
627 * Use when you need a snapshot of all current elements while keeping the list
628 * unchanged.
629 *
630 * @see {@link takeAll} for converting all elements to an array and clearing the list
631 *
632 * @category converting
633 * @since 4.0.0
634 */
635export const toArray = <A>(self: MutableList<A>): Array<A> => toArrayN(self, self.length)
636
637/**
638 * Filters the MutableList in place, keeping only elements that satisfy the predicate.
639 * This operation modifies the list and rebuilds its internal structure for efficiency.
640 * The predicate receives each element's current index.
641 *
642 * **Example** (Filtering in place)
643 *
644 * ```ts import.meta.vitest
645 * import { MutableList } from "effect"
646 *
647 * const list = MutableList.make<number>()
648 * MutableList.appendAll(list, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
649 *
650 * MutableList.filter(list, (n) => n % 2 === 0)
651 *
652 * MutableList.toArray(list) // => [2, 4, 6, 8, 10]
653 * ```
654 *
655 * @category mutations
656 * @since 4.0.0
657 */
658export const filter = <A>(self: MutableList<A>, f: (value: A, i: number) => boolean): void => {
659 const array: Array<A> = []
660 let chunk: MutableList.Bucket<A> | undefined = self.head
661 let index = 0
662 while (chunk) {
663 for (let i = chunk.offset; i < chunk.array.length; i++) {
664 if (f(chunk.array[i], index++)) {
665 array.push(chunk.array[i])
666 }
667 }
668 chunk = chunk.next
669 }
670 if (array.length === 0) {
671 clear(self)
672 return
673 }
674 self.head = self.tail = {
675 array,
676 mutable: true,
677 offset: 0,
678 next: undefined
679 }
680 self.length = array.length
681}
682
683/**
684 * Removes all occurrences of a value from the `MutableList` using JavaScript
685 * strict equality semantics.
686 *
687 * **When to use**
688 *
689 * Use when in-place removal should use JavaScript identity/strict equality
690 * rather than Effect structural equality.
691 *
692 * **Details**
693 *
694 * The list is modified in place.
695 *
696 * **Gotchas**
697 *
698 * Values are compared with `!==`, so this does not use Effect structural
699 * equality.
700 *
701 * **Example** (Removing matching values)
702 *
703 * ```ts import.meta.vitest
704 * import { MutableList } from "effect"
705 *
706 * const list = MutableList.make<string>()
707 * MutableList.appendAll(list, ["apple", "banana", "apple", "cherry", "apple"])
708 *
709 * MutableList.remove(list, "apple")
710 *
711 * MutableList.toArray(list) // => ["banana", "cherry"]
712 * ```
713 *
714 * @category mutations
715 * @since 4.0.0
716 */
717export const remove = <A>(self: MutableList<A>, value: A): void => filter(self, (v) => v !== value)