diff options
Diffstat (limited to 'lib/pure/collections/lists.nim')
| -rw-r--r-- | lib/pure/collections/lists.nim | 1044 |
1 files changed, 858 insertions, 186 deletions
diff --git a/lib/pure/collections/lists.nim b/lib/pure/collections/lists.nim index 535d5e21d..6b88747ef 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -7,246 +7,574 @@ # distribution, for details about the copyright. # -## Implementation of singly and doubly linked lists. Because it makes no sense -## to do so, the 'next' and 'prev' pointers are not hidden from you and can -## be manipulated directly for efficiency. - -when not defined(nimhygiene): - {.pragma: dirty.} +## Implementation of: +## * `singly linked lists <#SinglyLinkedList>`_ +## * `doubly linked lists <#DoublyLinkedList>`_ +## * `singly linked rings <#SinglyLinkedRing>`_ (circular lists) +## * `doubly linked rings <#DoublyLinkedRing>`_ (circular lists) +## +## # 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 +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 + +import std/private/since + +when defined(nimPreviewSlimSystem): + import std/assertions type - DoublyLinkedNodeObj*[T] = object ## a node a doubly linked list consists of - next*, prev*: ref DoublyLinkedNodeObj[T] + DoublyLinkedNodeObj*[T] = object + ## A node of a doubly linked list. + ## + ## It consists of a `value` field, and pointers to `next` and `prev`. + 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 - next*: ref SinglyLinkedNodeObj[T] + SinglyLinkedNodeObj*[T] = object + ## A node of a singly linked list. + ## + ## It consists of a `value` field, and a pointer to `next`. + next*: SinglyLinkedNode[T] value*: T SinglyLinkedNode*[T] = ref SinglyLinkedNodeObj[T] - SinglyLinkedList*[T] = object ## a singly linked list - head*, tail*: SinglyLinkedNode[T] - - DoublyLinkedList*[T] = object ## a doubly linked list - head*, tail*: DoublyLinkedNode[T] + SinglyLinkedList*[T] = object + ## A singly linked list. + head*: SinglyLinkedNode[T] + tail* {.cursor.}: SinglyLinkedNode[T] + + DoublyLinkedList*[T] = object + ## A doubly linked list. + head*: DoublyLinkedNode[T] + tail* {.cursor.}: DoublyLinkedNode[T] + + SinglyLinkedRing*[T] = object + ## A singly linked ring. + head*: SinglyLinkedNode[T] + tail* {.cursor.}: SinglyLinkedNode[T] - SinglyLinkedRing*[T] = object ## a singly linked ring - head*, tail*: SinglyLinkedNode[T] - - DoublyLinkedRing*[T] = object ## a doubly linked ring + DoublyLinkedRing*[T] = object + ## A doubly linked ring. head*: DoublyLinkedNode[T] -{.deprecated: [TDoublyLinkedNode: DoublyLinkedNodeObj, - PDoublyLinkedNode: DoublyLinkedNode, - TSinglyLinkedNode: SinglyLinkedNodeObj, - PSinglyLinkedNode: SinglyLinkedNode, - TDoublyLinkedList: DoublyLinkedList, - TSinglyLinkedRing: SinglyLinkedRing, - TDoublyLinkedRing: DoublyLinkedRing, - TSinglyLinkedList: SinglyLinkedList].} + SomeLinkedList*[T] = SinglyLinkedList[T] | DoublyLinkedList[T] + + SomeLinkedRing*[T] = SinglyLinkedRing[T] | DoublyLinkedRing[T] + + SomeLinkedCollection*[T] = SomeLinkedList[T] | SomeLinkedRing[T] + + SomeLinkedNode*[T] = SinglyLinkedNode[T] | DoublyLinkedNode[T] proc initSinglyLinkedList*[T](): SinglyLinkedList[T] = - ## creates a new singly linked list that is empty. + ## 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: + let a = initSinglyLinkedList[int]() + discard proc initDoublyLinkedList*[T](): DoublyLinkedList[T] = - ## creates a new doubly linked list that is empty. + ## 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: + let a = initDoublyLinkedList[int]() + discard proc initSinglyLinkedRing*[T](): SinglyLinkedRing[T] = - ## creates a new singly linked ring that is empty. + ## 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: + let a = initSinglyLinkedRing[int]() + discard proc initDoublyLinkedRing*[T](): DoublyLinkedRing[T] = - ## creates a new doubly linked ring that is empty. + ## 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: + let a = initDoublyLinkedRing[int]() + discard proc newDoublyLinkedNode*[T](value: T): DoublyLinkedNode[T] = - ## creates a new doubly linked node with the given `value`. + ## Creates a new doubly linked node with the given `value`. + runnableExamples: + let n = newDoublyLinkedNode[int](5) + assert n.value == 5 + new(result) result.value = value proc newSinglyLinkedNode*[T](value: T): SinglyLinkedNode[T] = - ## creates a new singly linked node with the given `value`. + ## Creates a new singly linked node with the given `value`. + runnableExamples: + 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 it = it.next if it == L.head: break -template nodesListImpl() {.dirty.} = - var it = L.head - while it != nil: - var nxt = it.next - yield it - it = nxt +iterator items*[T](L: SomeLinkedList[T]): T = + ## Yields every value of `L`. + ## + ## **See also:** + ## * `mitems iterator <#mitems.i,SomeLinkedList[T]>`_ + ## * `nodes iterator <#nodes.i,SomeLinkedList[T]>`_ + 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] -template nodesRingImpl() {.dirty.} = - var it = L.head - if it != nil: - while true: - var nxt = it.next - yield it - it = nxt - if it == L.head: break - -template findImpl() {.dirty.} = - for x in nodes(L): - if x.value == value: return x - -iterator items*[T](L: DoublyLinkedList[T]): T = - ## yields every value of `L`. - itemsListImpl() - -iterator items*[T](L: SinglyLinkedList[T]): T = - ## yields every value of `L`. itemsListImpl() -iterator items*[T](L: SinglyLinkedRing[T]): T = - ## yields every value of `L`. - itemsRingImpl() +iterator items*[T](L: SomeLinkedRing[T]): T = + ## Yields every value of `L`. + ## + ## **See also:** + ## * `mitems iterator <#mitems.i,SomeLinkedRing[T]>`_ + ## * `nodes iterator <#nodes.i,SomeLinkedRing[T]>`_ + 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] -iterator items*[T](L: DoublyLinkedRing[T]): T = - ## yields every value of `L`. itemsRingImpl() -iterator mitems*[T](L: var DoublyLinkedList[T]): var T = - ## yields every value of `L` so that you can modify it. - itemsListImpl() +iterator mitems*[T](L: var SomeLinkedList[T]): var T = + ## Yields every value of `L` so that you can modify it. + ## + ## **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.add(10 * i) + assert $a == "[10, 20, 30, 40, 50]" + for x in mitems(a): + x = 5 * x - 1 + assert $a == "[49, 99, 149, 199, 249]" -iterator mitems*[T](L: var SinglyLinkedList[T]): var T = - ## yields every value of `L` so that you can modify it. itemsListImpl() -iterator mitems*[T](L: var SinglyLinkedRing[T]): var T = - ## yields every value of `L` so that you can modify it. - itemsRingImpl() +iterator mitems*[T](L: var SomeLinkedRing[T]): var T = + ## Yields every value of `L` so that you can modify it. + ## + ## **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.add(10 * i) + assert $a == "[10, 20, 30, 40, 50]" + for x in mitems(a): + x = 5 * x - 1 + assert $a == "[49, 99, 149, 199, 249]" -iterator mitems*[T](L: var DoublyLinkedRing[T]): var T = - ## yields every value of `L` so that you can modify it. itemsRingImpl() -iterator nodes*[T](L: SinglyLinkedList[T]): SinglyLinkedNode[T] = - ## iterates over every node of `x`. Removing the current node from the - ## list during traversal is supported. - nodesListImpl() - -iterator nodes*[T](L: DoublyLinkedList[T]): DoublyLinkedNode[T] = - ## iterates over every node of `x`. Removing the current node from the +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. - nodesListImpl() + ## + ## **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.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 + assert $a == "[49, 99, 199, 249]" + + var it {.cursor.} = L.head + while it != nil: + let nxt = it.next + yield it + it = nxt -iterator nodes*[T](L: SinglyLinkedRing[T]): SinglyLinkedNode[T] = - ## iterates over every node of `x`. Removing the current node from the +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. - nodesRingImpl() + ## + ## **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.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 + assert $a == "[49, 99, 199, 249]" + + var it {.cursor.} = L.head + if it != nil: + while true: + let nxt = it.next + yield it + it = nxt + if it == L.head: break -iterator nodes*[T](L: DoublyLinkedRing[T]): DoublyLinkedNode[T] = - ## iterates over every node of `x`. Removing the current node from the - ## list during traversal is supported. - nodesRingImpl() +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]" -template dollarImpl() {.dirty.} = result = "[" for x in nodes(L): if result.len > 1: result.add(", ") - result.add($x.value) + result.addQuoted(x.value) result.add("]") -proc `$`*[T](L: SinglyLinkedList[T]): string = - ## turns a list into its string representation. - dollarImpl() - -proc `$`*[T](L: DoublyLinkedList[T]): string = - ## turns a list into its string representation. - dollarImpl() - -proc `$`*[T](L: SinglyLinkedRing[T]): string = - ## turns a list into its string representation. - dollarImpl() - -proc `$`*[T](L: DoublyLinkedRing[T]): string = - ## turns a list into its string representation. - dollarImpl() - -proc find*[T](L: SinglyLinkedList[T], value: T): SinglyLinkedNode[T] = - ## searches in the list for a value. Returns nil if the value does not - ## exist. - findImpl() - -proc find*[T](L: DoublyLinkedList[T], value: T): DoublyLinkedNode[T] = - ## searches in the list for a value. Returns nil if the value does not +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. - findImpl() + ## + ## **See also:** + ## * `contains proc <#contains,SomeLinkedCollection[T],T>`_ + runnableExamples: + let a = [9, 8].toSinglyLinkedList + assert a.find(9).value == 9 + assert a.find(1) == nil -proc find*[T](L: SinglyLinkedRing[T], value: T): SinglyLinkedNode[T] = - ## searches in the list for a value. Returns nil if the value does not - ## exist. - findImpl() + for x in nodes(L): + if x.value == value: return x -proc find*[T](L: DoublyLinkedRing[T], value: T): DoublyLinkedNode[T] = - ## searches in the list for a value. Returns nil if the value does not - ## exist. - findImpl() +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. This allows the usage of the `in` and `notin` + ## operators. + ## + ## **See also:** + ## * `find proc <#find,SomeLinkedCollection[T],T>`_ + runnableExamples: + let a = [9, 8].toSinglyLinkedList + assert a.contains(9) + assert 8 in a + assert(not a.contains(1)) + assert 2 notin a -proc contains*[T](L: SinglyLinkedList[T], value: T): bool {.inline.} = - ## searches in the list for a value. Returns false if the value does not - ## exist, true otherwise. result = find(L, value) != nil -proc contains*[T](L: DoublyLinkedList[T], value: T): bool {.inline.} = - ## searches in the list for a value. Returns false if the value does not - ## exist, true otherwise. - result = find(L, value) != nil +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:** + ## * `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]() + let n = newSinglyLinkedNode[int](9) + a.add(n) + assert a.contains(9) -proc contains*[T](L: SinglyLinkedRing[T], value: T): bool {.inline.} = - ## searches in the list for a value. Returns false if the value does not - ## exist, true otherwise. - result = find(L, value) != nil + n.next = nil + if L.tail != nil: + assert(L.tail.next == nil) + L.tail.next = n + L.tail = n + if L.head == nil: L.head = n -proc contains*[T](L: DoublyLinkedRing[T], value: T): bool {.inline.} = - ## searches in the list for a value. Returns false if the value does not - ## exist, true otherwise. - result = find(L, value) != nil +proc add*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). + ## + ## **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.add(9) + a.add(8) + assert a.contains(9) + + 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:** + ## * `add proc <#add,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## for appending a node + ## * `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]() + let n = newSinglyLinkedNode[int](9) + a.prepend(n) + assert a.contains(9) -proc prepend*[T](L: var SinglyLinkedList[T], - n: SinglyLinkedNode[T]) {.inline.} = - ## prepends a node to `L`. Efficiency: O(1). n.next = L.head L.head = n + if L.tail == nil: L.tail = n + +proc prepend*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = + ## Prepends (adds to the beginning) a node to `L`. Efficiency: O(1). + ## + ## **See also:** + ## * `add proc <#add,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## for appending a node + ## * `add proc <#add,SinglyLinkedList[T],T>`_ for appending a value + ## * `prepend proc <#prepend,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## for prepending a node + runnableExamples: + var a = initSinglyLinkedList[int]() + a.prepend(9) + a.prepend(8) + assert a.contains(9) -proc prepend*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = - ## prepends a node to `L`. Efficiency: O(1). prepend(L, newSinglyLinkedNode(value)) - -proc append*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = - ## appends a node `n` to `L`. Efficiency: O(1). + +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 add*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = + ## Appends (adds to the end) a node `n` to `L`. Efficiency: O(1). + ## + ## **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]() + let n = newDoublyLinkedNode[int](9) + a.add(n) + assert a.contains(9) + n.next = nil n.prev = L.tail - if L.tail != nil: + if L.tail != nil: assert(L.tail.next == nil) L.tail.next = n L.tail = n if L.head == nil: L.head = n -proc append*[T](L: var DoublyLinkedList[T], value: T) = - ## appends a value to `L`. Efficiency: O(1). - append(L, newDoublyLinkedNode(value)) +proc add*[T](L: var DoublyLinkedList[T], value: T) = + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). + ## + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## for appending a node + ## * `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]() + a.add(9) + a.add(8) + assert a.contains(9) + + 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:** + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## for appending a node + ## * `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]() + let n = newDoublyLinkedNode[int](9) + a.prepend(n) + assert a.contains(9) -proc prepend*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = - ## prepends a node `n` to `L`. Efficiency: O(1). n.prev = nil n.next = L.head if L.head != nil: @@ -255,36 +583,225 @@ proc prepend*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = L.head = n if L.tail == nil: L.tail = n -proc prepend*[T](L: var DoublyLinkedList[T], value: T) = - ## prepends a value to `L`. Efficiency: O(1). +proc prepend*[T](L: var DoublyLinkedList[T], value: T) = + ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). + ## + ## **See also:** + ## * `add proc <#add,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## for appending a node + ## * `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]>`_ + ## for removing a node + runnableExamples: + var a = initDoublyLinkedList[int]() + a.prepend(9) + a.prepend(8) + assert a.contains(9) + prepend(L, newDoublyLinkedNode(value)) - -proc remove*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = - ## removes `n` from `L`. Efficiency: O(1). + +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: + import std/[sequtils, enumerate, sugar] + var a = [0, 1, 2].toSinglyLinkedList + let n = a.head.next + assert n.value == 1 + a.remove(n) + 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 if n.next != nil: n.next.prev = n.prev if n.prev != nil: n.prev.next = n.next -proc append*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = - ## appends a node `n` to `L`. Efficiency: O(1). + +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:** + ## * `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]() + 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) = - ## appends a value to `L`. Efficiency: O(1). - append(L, newSinglyLinkedNode(value)) +proc add*[T](L: var SinglyLinkedRing[T], value: T) = + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). + ## + ## **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.add(9) + a.add(8) + assert a.contains(9) + + 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:** + ## * `add proc <#add,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## for appending a node + ## * `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]() + let n = newSinglyLinkedNode[int](9) + a.prepend(n) + assert a.contains(9) -proc prepend*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = - ## prepends a node `n` to `L`. Efficiency: O(1). if L.head != nil: n.next = L.head assert(L.tail != nil) @@ -294,12 +811,41 @@ proc prepend*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = L.tail = n L.head = n -proc prepend*[T](L: var SinglyLinkedRing[T], value: T) = - ## prepends a value to `L`. Efficiency: O(1). +proc prepend*[T](L: var SinglyLinkedRing[T], value: T) = + ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). + ## + ## **See also:** + ## * `add proc <#add,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## for appending a node + ## * `add proc <#add,SinglyLinkedRing[T],T>`_ for appending a value + ## * `prepend proc <#prepend,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## for prepending a node + runnableExamples: + var a = initSinglyLinkedRing[int]() + a.prepend(9) + a.prepend(8) + assert a.contains(9) + prepend(L, newSinglyLinkedNode(value)) -proc append*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = - ## appends a node `n` to `L`. Efficiency: O(1). + + +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:** + ## * `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]() + let n = newDoublyLinkedNode[int](9) + a.add(n) + assert a.contains(9) + if L.head != nil: n.next = L.head n.prev = L.head.prev @@ -310,13 +856,42 @@ 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) = - ## appends a value to `L`. Efficiency: O(1). - append(L, newDoublyLinkedNode(value)) +proc add*[T](L: var DoublyLinkedRing[T], value: T) = + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). + ## + ## **See also:** + ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## for appending a node + ## * `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]() + a.add(9) + a.add(8) + assert a.contains(9) + + 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:** + ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## for appending a node + ## * `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]() + let n = newDoublyLinkedNode[int](9) + a.prepend(n) + assert a.contains(9) -proc prepend*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = - ## prepends a node `n` to `L`. Efficiency: O(1). - if L.head != nil: + if L.head != nil: n.next = L.head n.prev = L.head.prev L.head.prev.next = n @@ -326,18 +901,115 @@ proc prepend*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = n.next = n L.head = n -proc prepend*[T](L: var DoublyLinkedRing[T], value: T) = - ## prepends a value to `L`. Efficiency: O(1). +proc prepend*[T](L: var DoublyLinkedRing[T], value: T) = + ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). + ## + ## **See also:** + ## * `add proc <#add,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## for appending a node + ## * `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]>`_ + ## for removing a node + runnableExamples: + var a = initDoublyLinkedRing[int]() + 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). + +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]() + let n = newDoublyLinkedNode[int](5) + a.add(n) + assert 5 in a + a.remove(n) + assert 5 notin a + n.next.prev = n.prev n.prev.next = n.next - if n == L.head: - var p = L.head.prev - if p == L.head: + if n == L.head: + 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) |