diff options
Diffstat (limited to 'lib/pure/collections/lists.nim')
| -rw-r--r-- | lib/pure/collections/lists.nim | 384 |
1 files changed, 203 insertions, 181 deletions
diff --git a/lib/pure/collections/lists.nim b/lib/pure/collections/lists.nim index c1fcb0743..6b88747ef 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -19,15 +19,15 @@ ## ## ## Lists runnableExamples: - var l = initDoublyLinkedList[int]() + var list = initDoublyLinkedList[int]() let a = newDoublyLinkedNode[int](3) b = newDoublyLinkedNode[int](7) c = newDoublyLinkedNode[int](9) - l.add(a) - l.add(b) - l.prepend(c) + list.add(a) + list.add(b) + list.prepend(c) assert a.next == b assert a.prev == c @@ -38,15 +38,15 @@ runnableExamples: ## ## Rings runnableExamples: - var l = initSinglyLinkedRing[int]() + var ring = initSinglyLinkedRing[int]() let a = newSinglyLinkedNode[int](3) b = newSinglyLinkedNode[int](7) c = newSinglyLinkedNode[int](9) - l.add(a) - l.add(b) - l.prepend(c) + ring.add(a) + ring.add(b) + ring.prepend(c) assert c.next == a assert a.next == b @@ -56,19 +56,18 @@ runnableExamples: ## # See also ## * `deques module <deques.html>`_ for double-ended queues -## * `sharedlist module <sharedlist.html>`_ for shared singly-linked lists import std/private/since -when not defined(nimHasCursor): - {.pragma: cursor.} +when defined(nimPreviewSlimSystem): + import std/assertions type 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]) + next*: DoublyLinkedNode[T] prev* {.cursor.}: DoublyLinkedNode[T] value*: T DoublyLinkedNode*[T] = ref DoublyLinkedNodeObj[T] @@ -77,23 +76,23 @@ type ## A node of a singly linked list. ## ## It consists of a `value` field, and a pointer to `next`. - next*: <//>(SinglyLinkedNode[T]) + next*: SinglyLinkedNode[T] value*: T SinglyLinkedNode*[T] = ref SinglyLinkedNodeObj[T] SinglyLinkedList*[T] = object ## A singly linked list. - head*: <//>(SinglyLinkedNode[T]) + head*: SinglyLinkedNode[T] tail* {.cursor.}: SinglyLinkedNode[T] DoublyLinkedList*[T] = object ## A doubly linked list. - head*: <//>(DoublyLinkedNode[T]) + head*: DoublyLinkedNode[T] tail* {.cursor.}: DoublyLinkedNode[T] SinglyLinkedRing*[T] = object ## A singly linked ring. - head*: <//>(SinglyLinkedNode[T]) + head*: SinglyLinkedNode[T] tail* {.cursor.}: SinglyLinkedNode[T] DoublyLinkedRing*[T] = object @@ -148,7 +147,7 @@ proc initDoublyLinkedRing*[T](): DoublyLinkedRing[T] = 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: let n = newDoublyLinkedNode[int](5) @@ -157,7 +156,7 @@ proc newDoublyLinkedNode*[T](value: T): <//>(DoublyLinkedNode[T]) = 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: let n = newSinglyLinkedNode[int](5) @@ -166,44 +165,22 @@ 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 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 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) - template itemsListImpl() {.dirty.} = - var it = list.head + var it {.cursor.} = L.head while it != nil: yield it.value it = it.next template itemsRingImpl() {.dirty.} = - var it = ring.head + var it {.cursor.} = L.head if it != nil: while true: yield it.value it = it.next - if it == ring.head: break + if it == L.head: break -iterator items*[T](list: SomeLinkedList[T]): T = - ## Yields every value of `list`. +iterator items*[T](L: SomeLinkedList[T]): T = + ## Yields every value of `L`. ## ## **See also:** ## * `mitems iterator <#mitems.i,SomeLinkedList[T]>`_ @@ -218,8 +195,8 @@ iterator items*[T](list: SomeLinkedList[T]): T = itemsListImpl() -iterator items*[T](ring: SomeLinkedRing[T]): T = - ## Yields every value of `ring`. +iterator items*[T](L: SomeLinkedRing[T]): T = + ## Yields every value of `L`. ## ## **See also:** ## * `mitems iterator <#mitems.i,SomeLinkedRing[T]>`_ @@ -234,8 +211,8 @@ iterator items*[T](ring: SomeLinkedRing[T]): T = itemsRingImpl() -iterator mitems*[T](list: var SomeLinkedList[T]): var T = - ## Yields every value of `list` so that you can modify it. +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]>`_ @@ -251,8 +228,8 @@ iterator mitems*[T](list: var SomeLinkedList[T]): var T = itemsListImpl() -iterator mitems*[T](ring: var SomeLinkedRing[T]): var T = - ## Yields every value of `ring` so that you can modify it. +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]>`_ @@ -268,7 +245,7 @@ iterator mitems*[T](ring: var SomeLinkedRing[T]): var T = itemsRingImpl() -iterator nodes*[T](list: SomeLinkedList[T]): SomeLinkedNode[T] = +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. ## @@ -287,13 +264,13 @@ iterator nodes*[T](list: SomeLinkedList[T]): SomeLinkedNode[T] = x.value = 5 * x.value - 1 assert $a == "[49, 99, 199, 249]" - var it = list.head + var it {.cursor.} = L.head while it != nil: let nxt = it.next yield it it = nxt -iterator nodes*[T](ring: SomeLinkedRing[T]): SomeLinkedNode[T] = +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. ## @@ -312,27 +289,27 @@ iterator nodes*[T](ring: SomeLinkedRing[T]): SomeLinkedNode[T] = x.value = 5 * x.value - 1 assert $a == "[49, 99, 199, 249]" - var it = ring.head + var it {.cursor.} = L.head if it != nil: while true: let nxt = it.next yield it it = nxt - if it == ring.head: break + if it == L.head: break -proc `$`*[T](l: SomeLinkedCollection[T]): string = +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): + for x in nodes(L): if result.len > 1: result.add(", ") result.addQuoted(x.value) result.add("]") -proc find*[T](l: SomeLinkedCollection[T], value: T): SomeLinkedNode[T] = +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. ## @@ -343,10 +320,10 @@ proc find*[T](l: SomeLinkedCollection[T], value: T): SomeLinkedNode[T] = assert a.find(9).value == 9 assert a.find(1) == nil - for x in nodes(l): + for x in nodes(L): if x.value == value: return x -proc contains*[T](l: SomeLinkedCollection[T], value: T): bool {.inline.} = +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. @@ -360,7 +337,7 @@ proc contains*[T](l: SomeLinkedCollection[T], value: T): bool {.inline.} = assert(not a.contains(1)) assert 2 notin a - result = find(l, value) != nil + 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`. @@ -407,12 +384,10 @@ proc prependMoved*[T: SomeLinkedList](a, b: var T) {.since: (1, 5, 1).} = 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 + swap a, b -proc add*[T](list: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = - ## Appends (adds to the end) a node `n` to `list`. Efficiency: O(1). +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 @@ -426,14 +401,14 @@ proc add*[T](list: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = assert a.contains(9) n.next = nil - if list.tail != nil: - assert(list.tail.next == nil) - list.tail.next = n - list.tail = n - if list.head == nil: list.head = n + if L.tail != nil: + assert(L.tail.next == nil) + L.tail.next = n + L.tail = n + if L.head == nil: L.head = n -proc add*[T](list: var SinglyLinkedList[T], value: T) {.inline.} = - ## Appends (adds to the end) a value to `list`. Efficiency: O(1). +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 @@ -446,11 +421,11 @@ proc add*[T](list: var SinglyLinkedList[T], value: T) {.inline.} = a.add(8) assert a.contains(9) - add(list, newSinglyLinkedNode(value)) + add(L, newSinglyLinkedNode(value)) -proc prepend*[T](list: var SinglyLinkedList[T], +proc prepend*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = - ## Prepends (adds to the beginning) a node to `list`. Efficiency: O(1). + ## Prepends (adds to the beginning) a node to `L`. Efficiency: O(1). ## ## **See also:** ## * `add proc <#add,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ @@ -463,12 +438,12 @@ proc prepend*[T](list: var SinglyLinkedList[T], a.prepend(n) assert a.contains(9) - n.next = list.head - list.head = n - if list.tail == nil: list.tail = n + n.next = L.head + L.head = n + if L.tail == nil: L.tail = n -proc prepend*[T](list: var SinglyLinkedList[T], value: T) {.inline.} = - ## Prepends (adds to the beginning) a node to `list`. Efficiency: O(1). +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]>`_ @@ -482,7 +457,7 @@ proc prepend*[T](list: var SinglyLinkedList[T], value: T) {.inline.} = a.prepend(8) assert a.contains(9) - prepend(list, newSinglyLinkedNode(value)) + prepend(L, newSinglyLinkedNode(value)) func copy*[T](a: SinglyLinkedList[T]): SinglyLinkedList[T] {.since: (1, 5, 1).} = ## Creates a shallow copy of `a`. @@ -531,17 +506,18 @@ proc addMoved*[T](a, b: var SinglyLinkedList[T]) {.since: (1, 5, 1).} = 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 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](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = - ## Appends (adds to the end) a node `n` to `list`. Efficiency: O(1). +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 @@ -557,15 +533,15 @@ proc add*[T](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = assert a.contains(9) n.next = nil - n.prev = list.tail - if list.tail != nil: - assert(list.tail.next == nil) - list.tail.next = n - list.tail = n - if list.head == nil: list.head = n + n.prev = L.tail + if L.tail != nil: + assert(L.tail.next == nil) + L.tail.next = n + L.tail = n + if L.head == nil: L.head = n -proc add*[T](list: var DoublyLinkedList[T], value: T) = - ## Appends (adds to the end) a value to `list`. Efficiency: O(1). +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]>`_ @@ -581,10 +557,10 @@ proc add*[T](list: var DoublyLinkedList[T], value: T) = a.add(8) assert a.contains(9) - add(list, newDoublyLinkedNode(value)) + add(L, newDoublyLinkedNode(value)) -proc prepend*[T](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = - ## Prepends (adds to the beginning) a node `n` to `list`. Efficiency: O(1). +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]>`_ @@ -600,15 +576,15 @@ proc prepend*[T](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = assert a.contains(9) n.prev = nil - n.next = list.head - if list.head != nil: - assert(list.head.prev == nil) - list.head.prev = n - list.head = n - if list.tail == nil: list.tail = n + n.next = L.head + if L.head != nil: + assert(L.head.prev == nil) + L.head.prev = n + L.head = n + if L.tail == nil: L.tail = n -proc prepend*[T](list: var DoublyLinkedList[T], value: T) = - ## Prepends (adds to the beginning) a value to `list`. 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]>`_ @@ -624,7 +600,7 @@ proc prepend*[T](list: var DoublyLinkedList[T], value: T) = a.prepend(8) assert a.contains(9) - prepend(list, newDoublyLinkedNode(value)) + prepend(L, newDoublyLinkedNode(value)) func copy*[T](a: DoublyLinkedList[T]): DoublyLinkedList[T] {.since: (1, 5, 1).} = ## Creates a shallow copy of `a`. @@ -675,12 +651,12 @@ proc addMoved*[T](a, b: var DoublyLinkedList[T]) {.since: (1, 5, 1).} = 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.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 @@ -705,9 +681,9 @@ proc add*[T: SomeLinkedList](a: var T, b: T) {.since: (1, 5, 1).} = var tmp = b.copy a.addMoved(tmp) -proc remove*[T](list: var SinglyLinkedList[T], n: SinglyLinkedNode[T]): bool {.discardable.} = - ## Removes a node `n` from `list`. - ## Returns `true` if `n` was found in `list`. +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. @@ -728,22 +704,24 @@ proc remove*[T](list: var SinglyLinkedList[T], n: SinglyLinkedNode[T]): bool {.d ai assert s == [2, 2, 2, 2] - if n == list.head: - list.head = n.next - if list.tail.next == n: - list.tail.next = list.head # restore cycle + if n == L.head: + L.head = n.next + if L.tail.next == n: + L.tail.next = L.head # restore cycle else: - var prev = list.head + 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](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = - ## Removes a node `n` from `list`. Efficiency: O(1). - ## This function assumes, for the sake of efficiency, that `n` is contained in `list`, +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: @@ -763,15 +741,15 @@ proc remove*[T](list: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = ai assert s == [2, 2, 2, 2] - if n == list.tail: list.tail = n.prev - if n == list.head: list.head = n.next + 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 add*[T](ring: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = - ## Appends (adds to the end) a node `n` to `ring`. 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 @@ -784,17 +762,17 @@ proc add*[T](ring: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = a.add(n) assert a.contains(9) - if ring.head != nil: - n.next = ring.head - assert(ring.tail != nil) - ring.tail.next = n + if L.head != nil: + n.next = L.head + assert(L.tail != nil) + L.tail.next = n else: n.next = n - ring.head = n - ring.tail = n + L.head = n + L.tail = n -proc add*[T](ring: var SinglyLinkedRing[T], value: T) = - ## Appends (adds to the end) a value to `ring`. Efficiency: O(1). +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]>`_ @@ -808,10 +786,10 @@ proc add*[T](ring: var SinglyLinkedRing[T], value: T) = a.add(8) assert a.contains(9) - add(ring, newSinglyLinkedNode(value)) + add(L, newSinglyLinkedNode(value)) -proc prepend*[T](ring: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = - ## Prepends (adds to the beginning) a node `n` to `ring`. Efficiency: O(1). +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]>`_ @@ -824,17 +802,17 @@ proc prepend*[T](ring: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = a.prepend(n) assert a.contains(9) - if ring.head != nil: - n.next = ring.head - assert(ring.tail != nil) - ring.tail.next = n + if L.head != nil: + n.next = L.head + assert(L.tail != nil) + L.tail.next = n else: n.next = n - ring.tail = n - ring.head = n + L.tail = n + L.head = n -proc prepend*[T](ring: var SinglyLinkedRing[T], value: T) = - ## Prepends (adds to the beginning) a value to `ring`. 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]>`_ @@ -848,12 +826,12 @@ proc prepend*[T](ring: var SinglyLinkedRing[T], value: T) = a.prepend(8) assert a.contains(9) - prepend(ring, newSinglyLinkedNode(value)) + prepend(L, newSinglyLinkedNode(value)) -proc add*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = - ## Appends (adds to the end) a node `n` to `ring`. 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 @@ -868,18 +846,18 @@ proc add*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = a.add(n) assert a.contains(9) - if ring.head != nil: - n.next = ring.head - n.prev = ring.head.prev - ring.head.prev.next = n - ring.head.prev = n + if L.head != nil: + n.next = L.head + n.prev = L.head.prev + L.head.prev.next = n + L.head.prev = n else: n.prev = n n.next = n - ring.head = n + L.head = n -proc add*[T](ring: var DoublyLinkedRing[T], value: T) = - ## Appends (adds to the end) a value to `ring`. Efficiency: O(1). +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]>`_ @@ -895,10 +873,10 @@ proc add*[T](ring: var DoublyLinkedRing[T], value: T) = a.add(8) assert a.contains(9) - add(ring, newDoublyLinkedNode(value)) + add(L, newDoublyLinkedNode(value)) -proc prepend*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = - ## Prepends (adds to the beginning) a node `n` to `ring`. Efficiency: O(1). +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]>`_ @@ -913,18 +891,18 @@ proc prepend*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = a.prepend(n) assert a.contains(9) - if ring.head != nil: - n.next = ring.head - n.prev = ring.head.prev - ring.head.prev.next = n - ring.head.prev = n + if L.head != nil: + n.next = L.head + n.prev = L.head.prev + L.head.prev.next = n + L.head.prev = n else: n.prev = n n.next = n - ring.head = n + L.head = n -proc prepend*[T](ring: var DoublyLinkedRing[T], value: T) = - ## Prepends (adds to the beginning) a value to `ring`. 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]>`_ @@ -940,11 +918,11 @@ proc prepend*[T](ring: var DoublyLinkedRing[T], value: T) = a.prepend(8) assert a.contains(9) - prepend(ring, newDoublyLinkedNode(value)) + prepend(L, newDoublyLinkedNode(value)) -proc remove*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = - ## Removes `n` from `ring`. Efficiency: O(1). - ## This function assumes, for the sake of efficiency, that `n` is contained in `ring`, +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]() @@ -956,13 +934,13 @@ proc remove*[T](ring: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = n.next.prev = n.prev n.prev.next = n.next - if n == ring.head: - let p = ring.head.prev - if p == ring.head: + if n == L.head: + let p = L.head.prev + if p == L.head: # only one element left: - ring.head = nil + L.head = nil else: - ring.head = p + L.head = p proc append*[T](a: var (SinglyLinkedList[T] | SinglyLinkedRing[T]), b: SinglyLinkedList[T] | SinglyLinkedNode[T] | T) = @@ -991,3 +969,47 @@ proc appendMoved*[T: SomeLinkedList](a, b: var T) {.since: (1, 5, 1).} = ## * `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) |