diff options
| -rw-r--r-- | changelog.md | 5 | ||||
| -rw-r--r-- | lib/pure/collections/lists.nim | 148 | ||||
| -rw-r--r-- | tests/stdlib/tlists.nim | 69 |
3 files changed, 220 insertions, 2 deletions
diff --git a/changelog.md b/changelog.md index 01eff1cd7..89d8fd423 100644 --- a/changelog.md +++ b/changelog.md @@ -66,6 +66,11 @@ - `echo` and `debugEcho` will now raise `IOError` if writing to stdout fails. Previous behavior silently ignored errors. See #16366. Use `-d:nimLegacyEchoNoRaise` for previous behavior. +- Added new operations for singly- and doubly linked lists: `lists.toSinglyLinkedList` + and `lists.toDoublyLinkedList` convert from `openArray`s; `lists.copy` implements + shallow copying; `lists.add` concatenates two lists - an O(1) variation that consumes + its argument, `addMoved`, is also supplied. + ## Language changes - `nimscript` now handles `except Exception as e`. diff --git a/lib/pure/collections/lists.nim b/lib/pure/collections/lists.nim index bd22949bf..8af0ed826 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -72,6 +72,7 @@ ## * `deques module <deques.html>`_ for double-ended queues ## * `sharedlist module <sharedlist.html>`_ for shared singly-linked lists +import std/private/since when not defined(nimhygiene): {.pragma: dirty.} @@ -178,6 +179,26 @@ proc newSinglyLinkedNode*[T](value: T): <//>(SinglyLinkedNode[T]) = new(result) result.value = value +func toSinglyLinkedList*[T](elems: openArray[T]): SinglyLinkedList[T] {.since: (1, 5, 1).} = + ## Creates a new `SinglyLinkedList` from members of `elems`. + runnableExamples: + import sequtils + 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.append(elem) + +func toDoublyLinkedList*[T](elems: openArray[T]): DoublyLinkedList[T] {.since: (1, 5, 1).} = + ## Creates a new `DoublyLinkedList` from members of `elems`. + runnableExamples: + import sequtils + 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.append(elem) + template itemsListImpl() {.dirty.} = var it = L.head while it != nil: @@ -435,7 +456,60 @@ proc prepend*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = assert a.contains(9) prepend(L, newSinglyLinkedNode(value)) - +func copy*[T](a: SinglyLinkedList[T]): SinglyLinkedList[T] {.since: (1, 5, 1).} = + ## Creates a shallow copy of `a`. + runnableExamples: + import sequtils + 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.append(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 sequtils, std/enumerate, std/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 a.tail != nil: + a.tail.next = b.head + a.tail = b.tail + if a.head == nil: + a.head = b.head + if a.addr != b.addr: + b.head = nil + b.tail = nil proc append*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1). @@ -523,6 +597,78 @@ proc prepend*[T](L: var DoublyLinkedList[T], value: T) = 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: + type Foo = ref object + x: int + var f = Foo(x: 1) + let + a = [f].toDoublyLinkedList + b = a.copy + f.x = 42 + assert a.head.value.x == 42 + assert b.head.value.x == 42 + + let c = [1, 2, 3].toDoublyLinkedList + assert $c == $c.copy + result = initDoublyLinkedList[T]() + for x in a.items: + result.append(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 sequtils, std/enumerate, std/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: + b.head.prev = a.tail + if a.tail != nil: + a.tail.next = b.head + a.tail = b.tail + if a.head == nil: + a.head = b.head + 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: + import sequtils + 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 DoublyLinkedList[T], n: DoublyLinkedNode[T]) = ## Removes a node `n` from `L`. Efficiency: O(1). runnableExamples: diff --git a/tests/stdlib/tlists.nim b/tests/stdlib/tlists.nim index fe814bb92..59ac8d7ee 100644 --- a/tests/stdlib/tlists.nim +++ b/tests/stdlib/tlists.nim @@ -2,7 +2,7 @@ discard """ targets: "c js" """ -import lists +import lists, sequtils, std/enumerate, std/sugar const data = [1, 2, 3, 4, 5, 6] @@ -81,3 +81,70 @@ block tlistsToString: l.append('2') l.append('3') doAssert $l == """['1', '2', '3']""" + +template testCommon(initList, toList) = + + block: # toSinglyLinkedList, toDoublyLinkedList + let l = seq[int].default + doAssert l.toList.toSeq == [] + doAssert [1].toList.toSeq == [1] + doAssert [1, 2, 3].toList.toSeq == [1, 2, 3] + + block copy: + doAssert array[0, int].default.toList.copy.toSeq == [] + doAssert [1].toList.copy.toSeq == [1] + doAssert [1, 2].toList.copy.toSeq == [1, 2] + doAssert [1, 2, 3].toList.copy.toSeq == [1, 2, 3] + type Foo = ref object + x: int + var f0 = Foo(x: 0) + let f1 = Foo(x: 1) + var a = [f0].toList + var b = a.copy + b.append f1 + doAssert a.toSeq == [f0] + doAssert b.toSeq == [f0, f1] + f0.x = 42 + assert a.head.value.x == 42 + assert b.head.value.x == 42 + + block: # add, addMoved + block: + var + l0 = initList[int]() + l1 = [1].toList + l2 = [2, 3].toList + l3 = [4, 5, 6].toList + l0.add l3 + l1.add l3 + l2.addMoved l3 + doAssert l0.toSeq == [4, 5, 6] + doAssert l1.toSeq == [1, 4, 5, 6] + doAssert l2.toSeq == [2, 3, 4, 5, 6] + doAssert l3.toSeq == [] + l2.add l3 # re-adding l3 that was destroyed is now a no-op + doAssert l2.toSeq == [2, 3, 4, 5, 6] + doAssert l3.toSeq == [] + block: + var + l0 = initList[int]() + l1 = [1].toList + l2 = [2, 3].toList + l3 = [4, 5, 6].toList + l3.addMoved l0 + l2.addMoved l1 + doAssert l3.toSeq == [4, 5, 6] + doAssert l2.toSeq == [2, 3, 1] + l3.add l0 + doAssert l3.toSeq == [4, 5, 6] + 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] + +testCommon initSinglyLinkedList, toSinglyLinkedList +testCommon initDoublyLinkedList, toDoublyLinkedList |