diff options
Diffstat (limited to 'lib/pure/collections/lists.nim')
| -rw-r--r-- | lib/pure/collections/lists.nim | 795 |
1 files changed, 537 insertions, 258 deletions
diff --git a/lib/pure/collections/lists.nim b/lib/pure/collections/lists.nim index bd22949bf..6b88747ef 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -13,119 +13,90 @@ ## * `singly linked rings <#SinglyLinkedRing>`_ (circular lists) ## * `doubly linked rings <#DoublyLinkedRing>`_ (circular lists) ## -## -## Basic Usage -## =========== -## +## # Basic Usage ## Because it makes no sense to do otherwise, the `next` and `prev` pointers ## are not hidden from you and can be manipulated directly for efficiency. ## -## Lists -## ----- -## -## .. code-block:: -## import lists -## -## var -## l = initDoublyLinkedList[int]() -## a = newDoublyLinkedNode[int](3) -## b = newDoublyLinkedNode[int](7) -## c = newDoublyLinkedNode[int](9) -## -## l.append(a) -## l.append(b) -## l.prepend(c) -## -## assert a.next == b -## assert a.prev == c -## assert c.next == a -## assert c.next.next == b -## assert c.prev == nil -## assert b.next == nil -## -## -## Rings -## ----- -## -## .. code-block:: -## import lists -## -## var -## l = initSinglyLinkedRing[int]() -## a = newSinglyLinkedNode[int](3) -## b = newSinglyLinkedNode[int](7) -## c = newSinglyLinkedNode[int](9) -## -## l.append(a) -## l.append(b) -## l.prepend(c) -## -## assert c.next == a -## assert a.next == b -## assert c.next.next == b -## assert b.next == c -## assert c.next.next.next == c -## -## See also -## ======== -## +## ## Lists +runnableExamples: + var list = initDoublyLinkedList[int]() + let + a = newDoublyLinkedNode[int](3) + b = newDoublyLinkedNode[int](7) + c = newDoublyLinkedNode[int](9) + + list.add(a) + list.add(b) + list.prepend(c) + + assert a.next == b + assert a.prev == c + assert c.next == a + assert c.next.next == b + assert c.prev == nil + assert b.next == nil + +## ## Rings +runnableExamples: + var ring = initSinglyLinkedRing[int]() + let + a = newSinglyLinkedNode[int](3) + b = newSinglyLinkedNode[int](7) + c = newSinglyLinkedNode[int](9) + + ring.add(a) + ring.add(b) + ring.prepend(c) + + assert c.next == a + assert a.next == b + assert c.next.next == b + assert b.next == c + assert c.next.next.next == c + +## # See also ## * `deques module <deques.html>`_ for double-ended queues -## * `sharedlist module <sharedlist.html>`_ for shared singly-linked lists - -when not defined(nimhygiene): - {.pragma: dirty.} +import std/private/since -when not defined(nimHasCursor): - {.pragma: cursor.} +when defined(nimPreviewSlimSystem): + import std/assertions type - DoublyLinkedNodeObj*[T] = object ## \ - ## A node a doubly linked list consists of. + DoublyLinkedNodeObj*[T] = object + ## A node of a doubly linked list. ## ## It consists of a `value` field, and pointers to `next` and `prev`. - next*: <//>(ref DoublyLinkedNodeObj[T]) - prev* {.cursor.}: ref DoublyLinkedNodeObj[T] + next*: DoublyLinkedNode[T] + prev* {.cursor.}: DoublyLinkedNode[T] value*: T DoublyLinkedNode*[T] = ref DoublyLinkedNodeObj[T] - SinglyLinkedNodeObj*[T] = object ## \ - ## A node a singly linked list consists of. + SinglyLinkedNodeObj*[T] = object + ## A node of a singly linked list. ## ## It consists of a `value` field, and a pointer to `next`. - next*: <//>(ref SinglyLinkedNodeObj[T]) + next*: SinglyLinkedNode[T] value*: T SinglyLinkedNode*[T] = ref SinglyLinkedNodeObj[T] - SinglyLinkedList*[T] = object ## \ + SinglyLinkedList*[T] = object ## A singly linked list. - ## - ## Use `initSinglyLinkedList proc <#initSinglyLinkedList>`_ to create - ## a new empty list. - head*: <//>(SinglyLinkedNode[T]) + head*: SinglyLinkedNode[T] tail* {.cursor.}: SinglyLinkedNode[T] - DoublyLinkedList*[T] = object ## \ + DoublyLinkedList*[T] = object ## A doubly linked list. - ## - ## Use `initDoublyLinkedList proc <#initDoublyLinkedList>`_ to create - ## a new empty list. - head*: <//>(DoublyLinkedNode[T]) + head*: DoublyLinkedNode[T] tail* {.cursor.}: DoublyLinkedNode[T] - SinglyLinkedRing*[T] = object ## \ + SinglyLinkedRing*[T] = object ## A singly linked ring. - ## - ## Use `initSinglyLinkedRing proc <#initSinglyLinkedRing>`_ to create - ## a new empty ring. - head*: <//>(SinglyLinkedNode[T]) + head*: SinglyLinkedNode[T] tail* {.cursor.}: SinglyLinkedNode[T] - DoublyLinkedRing*[T] = object ## \ + DoublyLinkedRing*[T] = object ## A doubly linked ring. - ## - ## Use `initDoublyLinkedRing proc <#initDoublyLinkedRing>`_ to create - ## a new empty ring. head*: DoublyLinkedNode[T] SomeLinkedList*[T] = SinglyLinkedList[T] | DoublyLinkedList[T] @@ -138,54 +109,70 @@ type proc initSinglyLinkedList*[T](): SinglyLinkedList[T] = ## Creates a new singly linked list that is empty. + ## + ## Singly linked lists are initialized by default, so it is not necessary to + ## call this function explicitly. runnableExamples: - var a = initSinglyLinkedList[int]() + let a = initSinglyLinkedList[int]() + discard proc initDoublyLinkedList*[T](): DoublyLinkedList[T] = ## Creates a new doubly linked list that is empty. + ## + ## Doubly linked lists are initialized by default, so it is not necessary to + ## call this function explicitly. runnableExamples: - var a = initDoublyLinkedList[int]() + let a = initDoublyLinkedList[int]() + discard proc initSinglyLinkedRing*[T](): SinglyLinkedRing[T] = ## Creates a new singly linked ring that is empty. + ## + ## Singly linked rings are initialized by default, so it is not necessary to + ## call this function explicitly. runnableExamples: - var a = initSinglyLinkedRing[int]() + let a = initSinglyLinkedRing[int]() + discard proc initDoublyLinkedRing*[T](): DoublyLinkedRing[T] = ## Creates a new doubly linked ring that is empty. + ## + ## Doubly linked rings are initialized by default, so it is not necessary to + ## call this function explicitly. runnableExamples: - var a = initDoublyLinkedRing[int]() + let a = initDoublyLinkedRing[int]() + discard -proc newDoublyLinkedNode*[T](value: T): <//>(DoublyLinkedNode[T]) = +proc newDoublyLinkedNode*[T](value: T): DoublyLinkedNode[T] = ## Creates a new doubly linked node with the given `value`. runnableExamples: - var n = newDoublyLinkedNode[int](5) + let n = newDoublyLinkedNode[int](5) assert n.value == 5 new(result) result.value = value -proc newSinglyLinkedNode*[T](value: T): <//>(SinglyLinkedNode[T]) = +proc newSinglyLinkedNode*[T](value: T): SinglyLinkedNode[T] = ## Creates a new singly linked node with the given `value`. runnableExamples: - var n = newSinglyLinkedNode[int](5) + let n = newSinglyLinkedNode[int](5) assert n.value == 5 new(result) result.value = value template itemsListImpl() {.dirty.} = - var it = L.head + var it {.cursor.} = L.head while it != nil: yield it.value it = it.next template itemsRingImpl() {.dirty.} = - var it = L.head + var it {.cursor.} = L.head if it != nil: while true: yield it.value @@ -195,101 +182,91 @@ template itemsRingImpl() {.dirty.} = iterator items*[T](L: SomeLinkedList[T]): T = ## Yields every value of `L`. ## - ## See also: + ## **See also:** ## * `mitems iterator <#mitems.i,SomeLinkedList[T]>`_ ## * `nodes iterator <#nodes.i,SomeLinkedList[T]>`_ - ## - ## **Examples:** - ## - ## .. code-block:: - ## var a = initSinglyLinkedList[int]() - ## for i in 1 .. 3: - ## a.append(10*i) - ## - ## for x in a: # the same as: for x in items(a): - ## echo x - ## - ## # 10 - ## # 20 - ## # 30 + runnableExamples: + from std/sugar import collect + from std/sequtils import toSeq + let a = collect(initSinglyLinkedList): + for i in 1..3: 10 * i + assert toSeq(items(a)) == toSeq(a) + assert toSeq(a) == @[10, 20, 30] + itemsListImpl() iterator items*[T](L: SomeLinkedRing[T]): T = ## Yields every value of `L`. ## - ## See also: + ## **See also:** ## * `mitems iterator <#mitems.i,SomeLinkedRing[T]>`_ ## * `nodes iterator <#nodes.i,SomeLinkedRing[T]>`_ - ## - ## **Examples:** - ## - ## .. code-block:: - ## var a = initSinglyLinkedRing[int]() - ## for i in 1 .. 3: - ## a.append(10*i) - ## - ## for x in a: # the same as: for x in items(a): - ## echo x - ## - ## # 10 - ## # 20 - ## # 30 + runnableExamples: + from std/sugar import collect + from std/sequtils import toSeq + let a = collect(initSinglyLinkedRing): + for i in 1..3: 10 * i + assert toSeq(items(a)) == toSeq(a) + assert toSeq(a) == @[10, 20, 30] + itemsRingImpl() iterator mitems*[T](L: var SomeLinkedList[T]): var T = ## Yields every value of `L` so that you can modify it. ## - ## See also: + ## **See also:** ## * `items iterator <#items.i,SomeLinkedList[T]>`_ ## * `nodes iterator <#nodes.i,SomeLinkedList[T]>`_ runnableExamples: var a = initSinglyLinkedList[int]() - for i in 1 .. 5: - a.append(10*i) + for i in 1..5: + a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in mitems(a): - x = 5*x - 1 + x = 5 * x - 1 assert $a == "[49, 99, 149, 199, 249]" + itemsListImpl() iterator mitems*[T](L: var SomeLinkedRing[T]): var T = ## Yields every value of `L` so that you can modify it. ## - ## See also: + ## **See also:** ## * `items iterator <#items.i,SomeLinkedRing[T]>`_ ## * `nodes iterator <#nodes.i,SomeLinkedRing[T]>`_ runnableExamples: var a = initSinglyLinkedRing[int]() - for i in 1 .. 5: - a.append(10*i) + for i in 1..5: + a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in mitems(a): - x = 5*x - 1 + x = 5 * x - 1 assert $a == "[49, 99, 149, 199, 249]" + itemsRingImpl() iterator nodes*[T](L: SomeLinkedList[T]): SomeLinkedNode[T] = ## Iterates over every node of `x`. Removing the current node from the ## list during traversal is supported. ## - ## See also: + ## **See also:** ## * `items iterator <#items.i,SomeLinkedList[T]>`_ ## * `mitems iterator <#mitems.i,SomeLinkedList[T]>`_ runnableExamples: var a = initDoublyLinkedList[int]() - for i in 1 .. 5: - a.append(10*i) + for i in 1..5: + a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in nodes(a): if x.value == 30: a.remove(x) else: - x.value = 5*x.value - 1 + x.value = 5 * x.value - 1 assert $a == "[49, 99, 199, 249]" - var it = L.head + var it {.cursor.} = L.head while it != nil: - var nxt = it.next + let nxt = it.next yield it it = nxt @@ -297,31 +274,35 @@ iterator nodes*[T](L: SomeLinkedRing[T]): SomeLinkedNode[T] = ## Iterates over every node of `x`. Removing the current node from the ## list during traversal is supported. ## - ## See also: + ## **See also:** ## * `items iterator <#items.i,SomeLinkedRing[T]>`_ ## * `mitems iterator <#mitems.i,SomeLinkedRing[T]>`_ runnableExamples: var a = initDoublyLinkedRing[int]() - for i in 1 .. 5: - a.append(10*i) + for i in 1..5: + a.add(10 * i) assert $a == "[10, 20, 30, 40, 50]" for x in nodes(a): if x.value == 30: a.remove(x) else: - x.value = 5*x.value - 1 + x.value = 5 * x.value - 1 assert $a == "[49, 99, 199, 249]" - var it = L.head + var it {.cursor.} = L.head if it != nil: while true: - var nxt = it.next + let nxt = it.next yield it it = nxt if it == L.head: break proc `$`*[T](L: SomeLinkedCollection[T]): string = ## Turns a list into its string representation for logging and printing. + runnableExamples: + let a = [1, 2, 3, 4].toSinglyLinkedList + assert $a == "[1, 2, 3, 4]" + result = "[" for x in nodes(L): if result.len > 1: result.add(", ") @@ -332,12 +313,10 @@ proc find*[T](L: SomeLinkedCollection[T], value: T): SomeLinkedNode[T] = ## Searches in the list for a value. Returns `nil` if the value does not ## exist. ## - ## See also: + ## **See also:** ## * `contains proc <#contains,SomeLinkedCollection[T],T>`_ runnableExamples: - var a = initSinglyLinkedList[int]() - a.append(9) - a.append(8) + let a = [9, 8].toSinglyLinkedList assert a.find(9).value == 9 assert a.find(1) == nil @@ -346,14 +325,13 @@ proc find*[T](L: SomeLinkedCollection[T], value: T): SomeLinkedNode[T] = proc contains*[T](L: SomeLinkedCollection[T], value: T): bool {.inline.} = ## Searches in the list for a value. Returns `false` if the value does not - ## exist, `true` otherwise. + ## exist, `true` otherwise. This allows the usage of the `in` and `notin` + ## operators. ## - ## See also: + ## **See also:** ## * `find proc <#find,SomeLinkedCollection[T],T>`_ runnableExamples: - var a = initSinglyLinkedList[int]() - a.append(9) - a.append(8) + let a = [9, 8].toSinglyLinkedList assert a.contains(9) assert 8 in a assert(not a.contains(1)) @@ -361,20 +339,65 @@ proc contains*[T](L: SomeLinkedCollection[T], value: T): bool {.inline.} = result = find(L, value) != nil -proc append*[T](L: var SinglyLinkedList[T], - n: SinglyLinkedNode[T]) {.inline.} = +proc prepend*[T: SomeLinkedList](a: var T, b: T) {.since: (1, 5, 1).} = + ## Prepends a shallow copy of `b` to the beginning of `a`. + ## + ## **See also:** + ## * `prependMoved proc <#prependMoved,T,T>`_ + ## for moving the second list instead of copying + runnableExamples: + from std/sequtils import toSeq + var a = [4, 5].toSinglyLinkedList + let b = [1, 2, 3].toSinglyLinkedList + a.prepend(b) + assert a.toSeq == [1, 2, 3, 4, 5] + assert b.toSeq == [1, 2, 3] + a.prepend(a) + assert a.toSeq == [1, 2, 3, 4, 5, 1, 2, 3, 4, 5] + + var tmp = b.copy + tmp.addMoved(a) + a = tmp + +proc prependMoved*[T: SomeLinkedList](a, b: var T) {.since: (1, 5, 1).} = + ## Moves `b` before the head of `a`. Efficiency: O(1). + ## Note that `b` becomes empty after the operation unless it has the same address as `a`. + ## Self-prepending results in a cycle. + ## + ## **See also:** + ## * `prepend proc <#prepend,T,T>`_ + ## for prepending a copy of a list + runnableExamples: + import std/[sequtils, enumerate, sugar] + var + a = [4, 5].toSinglyLinkedList + b = [1, 2, 3].toSinglyLinkedList + c = [0, 1].toSinglyLinkedList + a.prependMoved(b) + assert a.toSeq == [1, 2, 3, 4, 5] + assert b.toSeq == [] + c.prependMoved(c) + let s = collect: + for i, ci in enumerate(c): + if i == 6: break + ci + assert s == [0, 1, 0, 1, 0, 1] + + b.addMoved(a) + swap a, b + +proc add*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedList[T],T>`_ for appending a value + ## **See also:** + ## * `add proc <#add,SinglyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,SinglyLinkedList[T],T>`_ for prepending a value runnableExamples: - var - a = initSinglyLinkedList[int]() - n = newSinglyLinkedNode[int](9) - a.append(n) + var a = initSinglyLinkedList[int]() + let n = newSinglyLinkedNode[int](9) + a.add(n) assert a.contains(9) n.next = nil @@ -384,34 +407,34 @@ proc append*[T](L: var SinglyLinkedList[T], L.tail = n if L.head == nil: L.head = n -proc append*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = +proc add*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedList[T],T>`_ for appending a value + ## **See also:** + ## * `add proc <#add,SinglyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,SinglyLinkedList[T],T>`_ for prepending a value runnableExamples: var a = initSinglyLinkedList[int]() - a.append(9) - a.append(8) + a.add(9) + a.add(8) assert a.contains(9) - append(L, newSinglyLinkedNode(value)) + + add(L, newSinglyLinkedNode(value)) proc prepend*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = ## Prepends (adds to the beginning) a node to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,SinglyLinkedList[T],T>`_ for appending a value + ## * `add proc <#add,SinglyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedList[T],T>`_ for prepending a value runnableExamples: - var - a = initSinglyLinkedList[int]() - n = newSinglyLinkedNode[int](9) + var a = initSinglyLinkedList[int]() + let n = newSinglyLinkedNode[int](9) a.prepend(n) assert a.contains(9) @@ -422,10 +445,10 @@ proc prepend*[T](L: var SinglyLinkedList[T], proc prepend*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = ## Prepends (adds to the beginning) a node to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,SinglyLinkedList[T],T>`_ for appending a value + ## * `add proc <#add,SinglyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ ## for prepending a node runnableExamples: @@ -433,25 +456,80 @@ proc prepend*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = a.prepend(9) a.prepend(8) assert a.contains(9) - prepend(L, newSinglyLinkedNode(value)) + prepend(L, newSinglyLinkedNode(value)) +func copy*[T](a: SinglyLinkedList[T]): SinglyLinkedList[T] {.since: (1, 5, 1).} = + ## Creates a shallow copy of `a`. + runnableExamples: + from std/sequtils import toSeq + type Foo = ref object + x: int + var + f = Foo(x: 1) + a = [f].toSinglyLinkedList + let b = a.copy + a.add([f].toSinglyLinkedList) + assert a.toSeq == [f, f] + assert b.toSeq == [f] # b isn't modified... + f.x = 42 + assert a.head.value.x == 42 + assert b.head.value.x == 42 # ... but the elements are not deep copied + + let c = [1, 2, 3].toSinglyLinkedList + assert $c == $c.copy + + result = initSinglyLinkedList[T]() + for x in a.items: + result.add(x) + +proc addMoved*[T](a, b: var SinglyLinkedList[T]) {.since: (1, 5, 1).} = + ## Moves `b` to the end of `a`. Efficiency: O(1). + ## Note that `b` becomes empty after the operation unless it has the same address as `a`. + ## Self-adding results in a cycle. + ## + ## **See also:** + ## * `add proc <#add,T,T>`_ for adding a copy of a list + runnableExamples: + import std/[sequtils, enumerate, sugar] + var + a = [1, 2, 3].toSinglyLinkedList + b = [4, 5].toSinglyLinkedList + c = [0, 1].toSinglyLinkedList + a.addMoved(b) + assert a.toSeq == [1, 2, 3, 4, 5] + assert b.toSeq == [] + c.addMoved(c) + let s = collect: + for i, ci in enumerate(c): + if i == 6: break + ci + assert s == [0, 1, 0, 1, 0, 1] + + if b.head != nil: + if a.head == nil: + a.head = b.head + else: + a.tail.next = b.head + a.tail = b.tail + if a.addr != b.addr: + b.head = nil + b.tail = nil -proc append*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = +proc add*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedList[T],T>`_ for appending a value + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,DoublyLinkedList[T],T>`_ for prepending a value ## * `remove proc <#remove,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for removing a node runnableExamples: - var - a = initDoublyLinkedList[int]() - n = newDoublyLinkedNode[int](9) - a.append(n) + var a = initDoublyLinkedList[int]() + let n = newDoublyLinkedNode[int](9) + a.add(n) assert a.contains(9) n.next = nil @@ -462,11 +540,11 @@ proc append*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = L.tail = n if L.head == nil: L.head = n -proc append*[T](L: var DoublyLinkedList[T], value: T) = +proc add*[T](L: var DoublyLinkedList[T], value: T) = ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for appending a node ## * `prepend proc <#prepend,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for prepending a node @@ -475,25 +553,25 @@ proc append*[T](L: var DoublyLinkedList[T], value: T) = ## for removing a node runnableExamples: var a = initDoublyLinkedList[int]() - a.append(9) - a.append(8) + a.add(9) + a.add(8) assert a.contains(9) - append(L, newDoublyLinkedNode(value)) + + add(L, newDoublyLinkedNode(value)) proc prepend*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = ## Prepends (adds to the beginning) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,DoublyLinkedList[T],T>`_ for appending a value + ## * `add proc <#add,DoublyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedList[T],T>`_ for prepending a value ## * `remove proc <#remove,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for removing a node runnableExamples: - var - a = initDoublyLinkedList[int]() - n = newDoublyLinkedNode[int](9) + var a = initDoublyLinkedList[int]() + let n = newDoublyLinkedNode[int](9) a.prepend(n) assert a.contains(9) @@ -508,10 +586,10 @@ proc prepend*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = proc prepend*[T](L: var DoublyLinkedList[T], value: T) = ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,DoublyLinkedList[T],T>`_ for appending a value + ## * `add proc <#add,DoublyLinkedList[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for prepending a node ## * `remove proc <#remove,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ @@ -521,18 +599,147 @@ proc prepend*[T](L: var DoublyLinkedList[T], value: T) = a.prepend(9) a.prepend(8) assert a.contains(9) + prepend(L, newDoublyLinkedNode(value)) +func copy*[T](a: DoublyLinkedList[T]): DoublyLinkedList[T] {.since: (1, 5, 1).} = + ## Creates a shallow copy of `a`. + runnableExamples: + from std/sequtils import toSeq + type Foo = ref object + x: int + var + f = Foo(x: 1) + a = [f].toDoublyLinkedList + let b = a.copy + a.add([f].toDoublyLinkedList) + assert a.toSeq == [f, f] + assert b.toSeq == [f] # b isn't modified... + f.x = 42 + assert a.head.value.x == 42 + assert b.head.value.x == 42 # ... but the elements are not deep copied + + let c = [1, 2, 3].toDoublyLinkedList + assert $c == $c.copy + + result = initDoublyLinkedList[T]() + for x in a.items: + result.add(x) + +proc addMoved*[T](a, b: var DoublyLinkedList[T]) {.since: (1, 5, 1).} = + ## Moves `b` to the end of `a`. Efficiency: O(1). + ## Note that `b` becomes empty after the operation unless it has the same address as `a`. + ## Self-adding results in a cycle. + ## + ## **See also:** + ## * `add proc <#add,T,T>`_ + ## for adding a copy of a list + runnableExamples: + import std/[sequtils, enumerate, sugar] + var + a = [1, 2, 3].toDoublyLinkedList + b = [4, 5].toDoublyLinkedList + c = [0, 1].toDoublyLinkedList + a.addMoved(b) + assert a.toSeq == [1, 2, 3, 4, 5] + assert b.toSeq == [] + c.addMoved(c) + let s = collect: + for i, ci in enumerate(c): + if i == 6: break + ci + assert s == [0, 1, 0, 1, 0, 1] + + if b.head != nil: + if a.head == nil: + a.head = b.head + else: + b.head.prev = a.tail + a.tail.next = b.head + a.tail = b.tail + if a.addr != b.addr: + b.head = nil + b.tail = nil + +proc add*[T: SomeLinkedList](a: var T, b: T) {.since: (1, 5, 1).} = + ## Appends a shallow copy of `b` to the end of `a`. + ## + ## **See also:** + ## * `addMoved proc <#addMoved,SinglyLinkedList[T],SinglyLinkedList[T]>`_ + ## * `addMoved proc <#addMoved,DoublyLinkedList[T],DoublyLinkedList[T]>`_ + ## for moving the second list instead of copying + runnableExamples: + from std/sequtils import toSeq + var a = [1, 2, 3].toSinglyLinkedList + let b = [4, 5].toSinglyLinkedList + a.add(b) + assert a.toSeq == [1, 2, 3, 4, 5] + assert b.toSeq == [4, 5] + a.add(a) + assert a.toSeq == [1, 2, 3, 4, 5, 1, 2, 3, 4, 5] + + var tmp = b.copy + a.addMoved(tmp) + +proc remove*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]): bool {.discardable.} = + ## Removes a node `n` from `L`. + ## Returns `true` if `n` was found in `L`. + ## Efficiency: O(n); the list is traversed until `n` is found. + ## Attempting to remove an element not contained in the list is a no-op. + ## When the list is cyclic, the cycle is preserved after removal. + runnableExamples: + import std/[sequtils, enumerate, sugar] + var a = [0, 1, 2].toSinglyLinkedList + let n = a.head.next + assert n.value == 1 + assert a.remove(n) == true + assert a.toSeq == [0, 2] + assert a.remove(n) == false + assert a.toSeq == [0, 2] + a.addMoved(a) # cycle: [0, 2, 0, 2, ...] + a.remove(a.head) + let s = collect: + for i, ai in enumerate(a): + if i == 4: break + ai + assert s == [2, 2, 2, 2] + + if n == L.head: + L.head = n.next + if L.tail.next == n: + L.tail.next = L.head # restore cycle + else: + var prev {.cursor.} = L.head + while prev.next != n and prev.next != nil: + prev = prev.next + if prev.next == nil: + return false + prev.next = n.next + if L.tail == n: + L.tail = prev # update tail if we removed the last node + true + proc remove*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = ## Removes a node `n` from `L`. Efficiency: O(1). + ## This function assumes, for the sake of efficiency, that `n` is contained in `L`, + ## otherwise the effects are undefined. + ## When the list is cyclic, the cycle is preserved after removal. runnableExamples: - var - a = initDoublyLinkedList[int]() - n = newDoublyLinkedNode[int](5) - a.append(n) - assert 5 in a + import std/[sequtils, enumerate, sugar] + var a = [0, 1, 2].toSinglyLinkedList + let n = a.head.next + assert n.value == 1 a.remove(n) - assert 5 notin a + assert a.toSeq == [0, 2] + a.remove(n) + assert a.toSeq == [0, 2] + a.addMoved(a) # cycle: [0, 2, 0, 2, ...] + a.remove(a.head) + let s = collect: + for i, ai in enumerate(a): + if i == 4: break + ai + assert s == [2, 2, 2, 2] if n == L.tail: L.tail = n.prev if n == L.head: L.head = n.next @@ -541,59 +748,57 @@ proc remove*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = -proc append*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = +proc add*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedRing[T],T>`_ for appending a value + ## **See also:** + ## * `add proc <#add,SinglyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,SinglyLinkedRing[T],T>`_ for prepending a value runnableExamples: - var - a = initSinglyLinkedRing[int]() - n = newSinglyLinkedNode[int](9) - a.append(n) + var a = initSinglyLinkedRing[int]() + let n = newSinglyLinkedNode[int](9) + a.add(n) assert a.contains(9) if L.head != nil: n.next = L.head assert(L.tail != nil) L.tail.next = n - L.tail = n else: n.next = n L.head = n - L.tail = n + L.tail = n -proc append*[T](L: var SinglyLinkedRing[T], value: T) = +proc add*[T](L: var SinglyLinkedRing[T], value: T) = ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for appending a node ## * `prepend proc <#prepend,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,SinglyLinkedRing[T],T>`_ for prepending a value runnableExamples: var a = initSinglyLinkedRing[int]() - a.append(9) - a.append(8) + a.add(9) + a.add(8) assert a.contains(9) - append(L, newSinglyLinkedNode(value)) + + add(L, newSinglyLinkedNode(value)) proc prepend*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = ## Prepends (adds to the beginning) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,SinglyLinkedRing[T],T>`_ for appending a value + ## * `add proc <#add,SinglyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedRing[T],T>`_ for prepending a value runnableExamples: - var - a = initSinglyLinkedRing[int]() - n = newSinglyLinkedNode[int](9) + var a = initSinglyLinkedRing[int]() + let n = newSinglyLinkedNode[int](9) a.prepend(n) assert a.contains(9) @@ -609,10 +814,10 @@ proc prepend*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = proc prepend*[T](L: var SinglyLinkedRing[T], value: T) = ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,SinglyLinkedRing[T],T>`_ for appending a value + ## * `add proc <#add,SinglyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ ## for prepending a node runnableExamples: @@ -620,25 +825,25 @@ proc prepend*[T](L: var SinglyLinkedRing[T], value: T) = a.prepend(9) a.prepend(8) assert a.contains(9) + prepend(L, newSinglyLinkedNode(value)) -proc append*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = +proc add*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedRing[T],T>`_ for appending a value + ## **See also:** + ## * `add proc <#add,DoublyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for prepending a node ## * `prepend proc <#prepend,DoublyLinkedRing[T],T>`_ for prepending a value ## * `remove proc <#remove,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for removing a node runnableExamples: - var - a = initDoublyLinkedRing[int]() - n = newDoublyLinkedNode[int](9) - a.append(n) + var a = initDoublyLinkedRing[int]() + let n = newDoublyLinkedNode[int](9) + a.add(n) assert a.contains(9) if L.head != nil: @@ -651,11 +856,11 @@ proc append*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = n.next = n L.head = n -proc append*[T](L: var DoublyLinkedRing[T], value: T) = +proc add*[T](L: var DoublyLinkedRing[T], value: T) = ## Appends (adds to the end) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for appending a node ## * `prepend proc <#prepend,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for prepending a node @@ -664,25 +869,25 @@ proc append*[T](L: var DoublyLinkedRing[T], value: T) = ## for removing a node runnableExamples: var a = initDoublyLinkedRing[int]() - a.append(9) - a.append(8) + a.add(9) + a.add(8) assert a.contains(9) - append(L, newDoublyLinkedNode(value)) + + add(L, newDoublyLinkedNode(value)) proc prepend*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = ## Prepends (adds to the beginning) a node `n` to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,DoublyLinkedRing[T],T>`_ for appending a value + ## * `add proc <#add,DoublyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedRing[T],T>`_ for prepending a value ## * `remove proc <#remove,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for removing a node runnableExamples: - var - a = initDoublyLinkedRing[int]() - n = newDoublyLinkedNode[int](9) + var a = initDoublyLinkedRing[int]() + let n = newDoublyLinkedNode[int](9) a.prepend(n) assert a.contains(9) @@ -699,10 +904,10 @@ proc prepend*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = proc prepend*[T](L: var DoublyLinkedRing[T], value: T) = ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). ## - ## See also: - ## * `append proc <#append,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## **See also:** + ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for appending a node - ## * `append proc <#append,DoublyLinkedRing[T],T>`_ for appending a value + ## * `add proc <#add,DoublyLinkedRing[T],T>`_ for appending a value ## * `prepend proc <#prepend,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for prepending a node ## * `remove proc <#remove,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ @@ -712,15 +917,17 @@ proc prepend*[T](L: var DoublyLinkedRing[T], value: T) = a.prepend(9) a.prepend(8) assert a.contains(9) + prepend(L, newDoublyLinkedNode(value)) proc remove*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = ## Removes `n` from `L`. Efficiency: O(1). + ## This function assumes, for the sake of efficiency, that `n` is contained in `L`, + ## otherwise the effects are undefined. runnableExamples: - var - a = initDoublyLinkedRing[int]() - n = newDoublyLinkedNode[int](5) - a.append(n) + var a = initDoublyLinkedRing[int]() + let n = newDoublyLinkedNode[int](5) + a.add(n) assert 5 in a a.remove(n) assert 5 notin a @@ -728,9 +935,81 @@ proc remove*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = n.next.prev = n.prev n.prev.next = n.next if n == L.head: - var p = L.head.prev + let p = L.head.prev if p == L.head: # only one element left: L.head = nil else: - L.head = L.head.prev + L.head = p + +proc append*[T](a: var (SinglyLinkedList[T] | SinglyLinkedRing[T]), + b: SinglyLinkedList[T] | SinglyLinkedNode[T] | T) = + ## Alias for `a.add(b)`. + ## + ## **See also:** + ## * `add proc <#add,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## * `add proc <#add,SinglyLinkedList[T],T>`_ + ## * `add proc <#add,T,T>`_ + a.add(b) + +proc append*[T](a: var (DoublyLinkedList[T] | DoublyLinkedRing[T]), + b: DoublyLinkedList[T] | DoublyLinkedNode[T] | T) = + ## Alias for `a.add(b)`. + ## + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## * `add proc <#add,DoublyLinkedList[T],T>`_ + ## * `add proc <#add,T,T>`_ + a.add(b) + +proc appendMoved*[T: SomeLinkedList](a, b: var T) {.since: (1, 5, 1).} = + ## Alias for `a.addMoved(b)`. + ## + ## **See also:** + ## * `addMoved proc <#addMoved,SinglyLinkedList[T],SinglyLinkedList[T]>`_ + ## * `addMoved proc <#addMoved,DoublyLinkedList[T],DoublyLinkedList[T]>`_ + a.addMoved(b) + +func toSinglyLinkedList*[T](elems: openArray[T]): SinglyLinkedList[T] {.since: (1, 5, 1).} = + ## Creates a new `SinglyLinkedList` from the members of `elems`. + runnableExamples: + from std/sequtils import toSeq + let a = [1, 2, 3, 4, 5].toSinglyLinkedList + assert a.toSeq == [1, 2, 3, 4, 5] + + result = initSinglyLinkedList[T]() + for elem in elems.items: + result.add(elem) + +func toSinglyLinkedRing*[T](elems: openArray[T]): SinglyLinkedRing[T] = + ## Creates a new `SinglyLinkedRing` from the members of `elems`. + runnableExamples: + from std/sequtils import toSeq + let a = [1, 2, 3, 4, 5].toSinglyLinkedRing + assert a.toSeq == [1, 2, 3, 4, 5] + + result = initSinglyLinkedRing[T]() + for elem in elems.items: + result.add(elem) + +func toDoublyLinkedList*[T](elems: openArray[T]): DoublyLinkedList[T] {.since: (1, 5, 1).} = + ## Creates a new `DoublyLinkedList` from the members of `elems`. + runnableExamples: + from std/sequtils import toSeq + let a = [1, 2, 3, 4, 5].toDoublyLinkedList + assert a.toSeq == [1, 2, 3, 4, 5] + + result = initDoublyLinkedList[T]() + for elem in elems.items: + result.add(elem) + +func toDoublyLinkedRing*[T](elems: openArray[T]): DoublyLinkedRing[T] = + ## Creates a new `DoublyLinkedRing` from the members of `elems`. + runnableExamples: + from std/sequtils import toSeq + let a = [1, 2, 3, 4, 5].toDoublyLinkedRing + assert a.toSeq == [1, 2, 3, 4, 5] + + result = initDoublyLinkedRing[T]() + for elem in elems.items: + result.add(elem) |