diff options
| -rw-r--r-- | changelog.md | 3 | ||||
| -rw-r--r-- | lib/pure/collections/lists.nim | 386 | ||||
| -rw-r--r-- | tests/stdlib/tlists.nim | 123 |
3 files changed, 350 insertions, 162 deletions
diff --git a/changelog.md b/changelog.md index 6228cc4b3..f184a3700 100644 --- a/changelog.md +++ b/changelog.md @@ -111,6 +111,9 @@ with other backends. see #9125. Use `-d:nimLegacyJsRound` for previous behavior. - Added `math.signbit`. - Removed the optional `longestMatch` parameter of the `critbits._WithPrefix` iterators (it never worked reliably) +- In `lists`: renamed `append` to `add` and retained `append` as an alias; + added `prepend` and `prependMoved` analogously to `add` and `addMoved`; + added `remove` for `SinglyLinkedList`s. - Added optional `options` argument to `copyFile`, `copyFileToDir`, and diff --git a/lib/pure/collections/lists.nim b/lib/pure/collections/lists.nim index 8af0ed826..2bfad9d95 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -22,50 +22,43 @@ ## ## 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 -## -## +runnableExamples: + var + l = initDoublyLinkedList[int]() + a = newDoublyLinkedNode[int](3) + b = newDoublyLinkedNode[int](7) + c = newDoublyLinkedNode[int](9) + + l.add(a) + l.add(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 -## +runnableExamples: + var + l = initSinglyLinkedRing[int]() + a = newSinglyLinkedNode[int](3) + b = newSinglyLinkedNode[int](7) + c = newSinglyLinkedNode[int](9) + + l.add(a) + l.add(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 ## ======== ## @@ -187,7 +180,7 @@ func toSinglyLinkedList*[T](elems: openArray[T]): SinglyLinkedList[T] {.since: ( assert a.toSeq == [1, 2, 3, 4, 5] result = initSinglyLinkedList[T]() for elem in elems.items: - result.append(elem) + result.add(elem) func toDoublyLinkedList*[T](elems: openArray[T]): DoublyLinkedList[T] {.since: (1, 5, 1).} = ## Creates a new `DoublyLinkedList` from members of `elems`. @@ -197,7 +190,7 @@ func toDoublyLinkedList*[T](elems: openArray[T]): DoublyLinkedList[T] {.since: ( assert a.toSeq == [1, 2, 3, 4, 5] result = initDoublyLinkedList[T]() for elem in elems.items: - result.append(elem) + result.add(elem) template itemsListImpl() {.dirty.} = var it = L.head @@ -219,20 +212,13 @@ iterator items*[T](L: SomeLinkedList[T]): T = ## 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 + doAssert toSeq(items(a)) == toSeq(a) + doAssert toSeq(a) == @[10, 20, 30] itemsListImpl() iterator items*[T](L: SomeLinkedRing[T]): T = @@ -241,20 +227,13 @@ iterator items*[T](L: SomeLinkedRing[T]): T = ## 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 + doAssert toSeq(items(a)) == toSeq(a) + doAssert toSeq(a) == @[10, 20, 30] itemsRingImpl() iterator mitems*[T](L: var SomeLinkedList[T]): var T = @@ -266,7 +245,7 @@ iterator mitems*[T](L: var SomeLinkedList[T]): var T = runnableExamples: var a = initSinglyLinkedList[int]() for i in 1 .. 5: - a.append(10*i) + a.add(10*i) assert $a == "[10, 20, 30, 40, 50]" for x in mitems(a): x = 5*x - 1 @@ -282,7 +261,7 @@ iterator mitems*[T](L: var SomeLinkedRing[T]): var T = runnableExamples: var a = initSinglyLinkedRing[int]() for i in 1 .. 5: - a.append(10*i) + a.add(10*i) assert $a == "[10, 20, 30, 40, 50]" for x in mitems(a): x = 5*x - 1 @@ -299,7 +278,7 @@ iterator nodes*[T](L: SomeLinkedList[T]): SomeLinkedNode[T] = runnableExamples: var a = initDoublyLinkedList[int]() for i in 1 .. 5: - a.append(10*i) + a.add(10*i) assert $a == "[10, 20, 30, 40, 50]" for x in nodes(a): if x.value == 30: @@ -324,7 +303,7 @@ iterator nodes*[T](L: SomeLinkedRing[T]): SomeLinkedNode[T] = runnableExamples: var a = initDoublyLinkedRing[int]() for i in 1 .. 5: - a.append(10*i) + a.add(10*i) assert $a == "[10, 20, 30, 40, 50]" for x in nodes(a): if x.value == 30: @@ -357,8 +336,8 @@ proc find*[T](L: SomeLinkedCollection[T], value: T): SomeLinkedNode[T] = ## * `contains proc <#contains,SomeLinkedCollection[T],T>`_ runnableExamples: var a = initSinglyLinkedList[int]() - a.append(9) - a.append(8) + a.add(9) + a.add(8) assert a.find(9).value == 9 assert a.find(1) == nil @@ -373,8 +352,8 @@ proc contains*[T](L: SomeLinkedCollection[T], value: T): bool {.inline.} = ## * `find proc <#find,SomeLinkedCollection[T],T>`_ runnableExamples: var a = initSinglyLinkedList[int]() - a.append(9) - a.append(8) + a.add(9) + a.add(8) assert a.contains(9) assert 8 in a assert(not a.contains(1)) @@ -382,12 +361,60 @@ 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,SinglyLinkedList[T],SinglyLinkedList[T]>`_ + ## * `prependMoved proc <#prependMoved,DoublyLinkedList[T],DoublyLinkedList[T]>`_ + ## for moving the second list instead of copying + runnableExamples: + import sequtils + 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 + when defined(js): # XXX: swap broken in js; bug #16771 + (b, a) = (a, b) + else: 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 + ## * `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 @@ -395,7 +422,7 @@ proc append*[T](L: var SinglyLinkedList[T], var a = initSinglyLinkedList[int]() n = newSinglyLinkedNode[int](9) - a.append(n) + a.add(n) assert a.contains(9) n.next = nil @@ -405,29 +432,29 @@ 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 + ## * `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]>`_ + ## * `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 @@ -444,9 +471,9 @@ 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]>`_ + ## * `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: @@ -477,7 +504,7 @@ func copy*[T](a: SinglyLinkedList[T]): SinglyLinkedList[T] {.since: (1, 5, 1).} assert $c == $c.copy result = initSinglyLinkedList[T]() for x in a.items: - result.append(x) + 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). @@ -488,7 +515,7 @@ proc addMoved*[T](a, b: var SinglyLinkedList[T]) {.since: (1, 5, 1).} = ## * `add proc <#add,T,T>`_ ## for adding a copy of a list runnableExamples: - import sequtils, std/enumerate, std/sugar + import std/[sequtils, enumerate, sugar] var a = [1, 2, 3].toSinglyLinkedList b = [4, 5].toSinglyLinkedList @@ -511,11 +538,11 @@ proc addMoved*[T](a, b: var SinglyLinkedList[T]) {.since: (1, 5, 1).} = 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 + ## * `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 @@ -525,7 +552,7 @@ proc append*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = var a = initDoublyLinkedList[int]() n = newDoublyLinkedNode[int](9) - a.append(n) + a.add(n) assert a.contains(9) n.next = nil @@ -536,11 +563,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]>`_ + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for appending a node ## * `prepend proc <#prepend,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ ## for prepending a node @@ -549,18 +576,18 @@ 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]>`_ + ## * `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 @@ -583,9 +610,9 @@ 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]>`_ + ## * `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]>`_ @@ -614,7 +641,7 @@ func copy*[T](a: DoublyLinkedList[T]): DoublyLinkedList[T] {.since: (1, 5, 1).} assert $c == $c.copy result = initDoublyLinkedList[T]() for x in a.items: - result.append(x) + 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). @@ -625,7 +652,7 @@ proc addMoved*[T](a, b: var DoublyLinkedList[T]) {.since: (1, 5, 1).} = ## * `add proc <#add,T,T>`_ ## for adding a copy of a list runnableExamples: - import sequtils, std/enumerate, std/sugar + import std/[sequtils, enumerate, sugar] var a = [1, 2, 3].toDoublyLinkedList b = [4, 5].toDoublyLinkedList @@ -669,16 +696,63 @@ proc add*[T: SomeLinkedList](a: var T, b: T) {.since: (1, 5, 1).} = 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 + doAssert n.value == 1 + doAssert a.remove(n) == true + doAssert a.toSeq == [0, 2] + doAssert a.remove(n) == false + doAssert 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 + doAssert 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 = L.head + while prev.next != n and prev.next != nil: + prev = prev.next + if prev.next == nil: + return false + prev.next = n.next + true + proc remove*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = ## Removes a node `n` from `L`. Efficiency: O(1). - runnableExamples: - var - a = initDoublyLinkedList[int]() - n = newDoublyLinkedNode[int](5) - a.append(n) - assert 5 in a - a.remove(n) - assert 5 notin a + ## 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: + import std/[sequtils, enumerate, sugar] + var a = [0, 1, 2].toSinglyLinkedList + let n = a.head.next + doAssert n.value == 1 + a.remove n + doAssert a.toSeq == [0, 2] + a.remove n + doAssert 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 + doAssert s == [2, 2, 2, 2] if n == L.tail: L.tail = n.prev if n == L.head: L.head = n.next @@ -687,11 +761,11 @@ 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 + ## * `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 @@ -699,7 +773,7 @@ proc append*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = var a = initSinglyLinkedRing[int]() n = newSinglyLinkedNode[int](9) - a.append(n) + a.add(n) assert a.contains(9) if L.head != nil: @@ -712,29 +786,29 @@ proc append*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = L.head = 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]>`_ + ## * `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]>`_ + ## * `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 @@ -756,9 +830,9 @@ 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]>`_ + ## * `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: @@ -770,11 +844,11 @@ proc prepend*[T](L: var SinglyLinkedRing[T], value: T) = -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 + ## * `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 @@ -784,7 +858,7 @@ proc append*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = var a = initDoublyLinkedRing[int]() n = newDoublyLinkedNode[int](9) - a.append(n) + a.add(n) assert a.contains(9) if L.head != nil: @@ -797,11 +871,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]>`_ + ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for appending a node ## * `prepend proc <#prepend,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ ## for prepending a node @@ -810,18 +884,18 @@ 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]>`_ + ## * `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 @@ -846,9 +920,9 @@ 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]>`_ + ## * `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]>`_ @@ -866,7 +940,7 @@ proc remove*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = var a = initDoublyLinkedRing[int]() n = newDoublyLinkedNode[int](5) - a.append(n) + a.add(n) assert 5 in a a.remove(n) assert 5 notin a @@ -880,3 +954,31 @@ proc remove*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = L.head = nil else: L.head = L.head.prev + +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 diff --git a/tests/stdlib/tlists.nim b/tests/stdlib/tlists.nim index b5a3d3f7e..2d3165c9c 100644 --- a/tests/stdlib/tlists.nim +++ b/tests/stdlib/tlists.nim @@ -2,7 +2,7 @@ discard """ targets: "c js" """ -import lists, sequtils, std/enumerate, std/sugar +import lists, sequtils const data = [1, 2, 3, 4, 5, 6] @@ -10,7 +10,7 @@ const block SinglyLinkedListTest1: var L: SinglyLinkedList[int] for d in items(data): L.prepend(d) - for d in items(data): L.append(d) + for d in items(data): L.add(d) doAssert($L == "[6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6]") doAssert(4 in L) @@ -26,7 +26,7 @@ block SinglyLinkedListTest2: block DoublyLinkedListTest1: var L: DoublyLinkedList[int] for d in items(data): L.prepend(d) - for d in items(data): L.append(d) + for d in items(data): L.add(d) L.remove(L.find(1)) doAssert($L == "[6, 5, 4, 3, 2, 1, 2, 3, 4, 5, 6]") @@ -51,8 +51,8 @@ block DoublyLinkedRingTest1: doAssert($L == "[4, 4]") doAssert(4 in L) - L.append(3) - L.append(5) + L.add(3) + L.add(5) doAssert($L == "[4, 4, 3, 5]") L.remove(L.find(3)) @@ -65,23 +65,35 @@ block DoublyLinkedRingTest1: block tlistsToString: block: var l = initDoublyLinkedList[int]() - l.append(1) - l.append(2) - l.append(3) + l.add(1) + l.add(2) + l.add(3) doAssert $l == "[1, 2, 3]" block: var l = initDoublyLinkedList[string]() - l.append("1") - l.append("2") - l.append("3") + l.add("1") + l.add("2") + l.add("3") doAssert $l == """["1", "2", "3"]""" block: var l = initDoublyLinkedList[char]() - l.append('1') - l.append('2') - l.append('3') + l.add('1') + l.add('2') + l.add('3') doAssert $l == """['1', '2', '3']""" +# Copied here until it is merged into sequtils +template take(a: untyped, max: int): untyped = + type T = typeof(block: (for ai in a: ai)) + var ret: seq[T] + var i = 0 + if max > 0: + for ai in a: + ret.add ai + i.inc + if i >= max: break + ret + template testCommon(initList, toList) = block: # toSinglyLinkedList, toDoublyLinkedList @@ -101,7 +113,7 @@ template testCommon(initList, toList) = let f1 = Foo(x: 1) var a = [f0].toList var b = a.copy - b.append f1 + b.add f1 doAssert a.toSeq == [f0] doAssert b.toSeq == [f0, f1] f0.x = 42 @@ -140,11 +152,82 @@ template testCommon(initList, toList) = block: var c = [0, 1].toList c.addMoved c - let s = collect: - for i, ci in enumerate(c): - if i == 6: break - ci - doAssert s == [0, 1, 0, 1, 0, 1] + doAssert c.take(6) == [0, 1, 0, 1, 0, 1] + + block: # prepend, prependMoved + block: + var + l0 = initList[int]() + l1 = [1].toList + l2 = [2, 3].toList + l3 = [4, 5, 6].toList + l0.prepend l3 + l1.prepend l3 + doAssert l3.toSeq == [4, 5, 6] + l2.prependMoved l3 + doAssert l0.toSeq == [4, 5, 6] + doAssert l1.toSeq == [4, 5, 6, 1] + doAssert l2.toSeq == [4, 5, 6, 2, 3] + doAssert l3.toSeq == [] + l2.prepend l3 # re-prepending l3 that was destroyed is now a no-op + doAssert l2.toSeq == [4, 5, 6, 2, 3] + doAssert l3.toSeq == [] + block: + var + l0 = initList[int]() + l1 = [1].toList + l2 = [2, 3].toList + l3 = [4, 5, 6].toList + l3.prependMoved l0 + l2.prependMoved l1 + doAssert l3.toSeq == [4, 5, 6] + doAssert l2.toSeq == [1, 2, 3] + l3.prepend l0 + doAssert l3.toSeq == [4, 5, 6] + block: + var c = [0, 1].toList + c.prependMoved c + doAssert c.take(6) == [0, 1, 0, 1, 0, 1] + + block remove: + var l = [0, 1, 2, 3].toList + let + l0 = l.head + l1 = l0.next + l2 = l1.next + l3 = l2.next + l.remove l0 + doAssert l.toSeq == [1, 2, 3] + l.remove l2 + doAssert l.toSeq == [1, 3] + l.remove l2 + doAssert l.toSeq == [1, 3] + l.remove l3 + doAssert l.toSeq == [1] + l.remove l1 + doAssert l.toSeq == [] + # Cycle preservation + var a = [10, 11, 12].toList + a.addMoved a + doAssert a.take(6) == @[10, 11, 12, 10, 11, 12] + a.remove a.head.next + doAssert a.take(6) == @[10, 12, 10, 12, 10, 12] + a.remove a.head + doAssert a.take(6) == @[12, 12, 12, 12, 12, 12] testCommon initSinglyLinkedList, toSinglyLinkedList testCommon initDoublyLinkedList, toDoublyLinkedList + +block remove: # return value check + var l = [0, 1, 2, 3].toSinglyLinkedList + let n = l.head.next.next + doAssert l.remove(n) == true + doAssert l.toSeq == [0, 1, 3] + doAssert l.remove(n) == false + doAssert l.toSeq == [0, 1, 3] + doAssert l.remove(l.head) == true + doAssert l.toSeq == [1, 3] + doAssert l.remove(l.head.next) == true + doAssert l.toSeq == [1] + doAssert l.remove(l.head) == true + doAssert l.toSeq == [] |