diff options
Diffstat (limited to 'lib/pure/collections/lists.nim')
| -rw-r--r-- | lib/pure/collections/lists.nim | 533 |
1 files changed, 490 insertions, 43 deletions
diff --git a/lib/pure/collections/lists.nim b/lib/pure/collections/lists.nim index 15ce5d074..182eb8442 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -7,34 +7,112 @@ # 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. +## 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 +## ----- +## +## .. code-block:: +## import lists +## +## var +## l = initDoublyLinkedList[int]() +## a = newDoublyLinkedNode[int](3) +## b = newDoublyLinkedNode[int](7) +## c = newDoublyLinkedNode[int](9) +## +## l.append(a) +## l.append(b) +## l.prepend(c) +## +## assert a.next == b +## assert a.prev == c +## assert c.next == a +## assert c.next.next == b +## assert c.prev == nil +## assert b.next == nil +## +## +## Rings +## ----- +## +## .. code-block:: +## import lists +## +## var +## l = initSinglyLinkedRing[int]() +## a = newSinglyLinkedNode[int](3) +## b = newSinglyLinkedNode[int](7) +## c = newSinglyLinkedNode[int](9) +## +## l.append(a) +## l.append(b) +## l.prepend(c) +## +## assert c.next == a +## assert a.next == b +## assert c.next.next == b +## assert b.next == c +## assert c.next.next.next == c +## +## See also +## ======== +## +## * `deques module <#deques.html>`_ for double-ended queues +## * `sharedlist module <#sharedlist.html>`_ for shared singly-linked lists + when not defined(nimhygiene): {.pragma: dirty.} type - DoublyLinkedNodeObj*[T] = object ## a node a doubly linked list consists of + DoublyLinkedNodeObj*[T] = object ## A node a doubly linked list consists of. + ## + ## It consists of a `value` field, and pointers to `next` and `prev`. next*, prev*: ref DoublyLinkedNodeObj[T] value*: T DoublyLinkedNode*[T] = ref DoublyLinkedNodeObj[T] - SinglyLinkedNodeObj*[T] = object ## a node a singly linked list consists of + SinglyLinkedNodeObj*[T] = object ## A node a singly linked list consists of. + ## + ## It consists of a `value` field, and a pointer to `next`. next*: ref SinglyLinkedNodeObj[T] value*: T SinglyLinkedNode*[T] = ref SinglyLinkedNodeObj[T] - SinglyLinkedList*[T] = object ## a singly linked list + SinglyLinkedList*[T] = object ## A singly linked list. + ## + ## Use `initSinglyLinkedList proc <#initSinglyLinkedList,>`_ to create + ## a new empty list. head*, tail*: SinglyLinkedNode[T] - DoublyLinkedList*[T] = object ## a doubly linked list + DoublyLinkedList*[T] = object ## A doubly linked list. + ## + ## Use `initDoublyLinkedList proc <#initDoublyLinkedList,>`_ to create + ## a new empty list. head*, tail*: DoublyLinkedNode[T] - SinglyLinkedRing*[T] = object ## a singly linked ring + SinglyLinkedRing*[T] = object ## A singly linked ring. + ## + ## Use `initSinglyLinkedRing proc <#initSinglyLinkedRing,>`_ to create + ## a new empty ring. head*, tail*: SinglyLinkedNode[T] - DoublyLinkedRing*[T] = object ## a doubly linked ring + DoublyLinkedRing*[T] = object ## A doubly linked ring. + ## + ## Use `initDoublyLinkedRing proc <#initDoublyLinkedRing,>`_ to create + ## a new empty ring. head*: DoublyLinkedNode[T] SomeLinkedList*[T] = SinglyLinkedList[T] | DoublyLinkedList[T] @@ -46,28 +124,44 @@ type 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. + runnableExamples: + var 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. + runnableExamples: + var 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. + runnableExamples: + var 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. + runnableExamples: + var 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: + var 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: + var n = newSinglyLinkedNode[int](5) + assert n.value == 5 + new(result) result.value = value @@ -86,24 +180,100 @@ template itemsRingImpl() {.dirty.} = if it == L.head: break iterator items*[T](L: SomeLinkedList[T]): T = - ## yields every value of `L`. + ## Yields every value of `L`. + ## + ## 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 itemsListImpl() iterator items*[T](L: SomeLinkedRing[T]): T = - ## yields every value of `L`. + ## Yields every value of `L`. + ## + ## 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 itemsRingImpl() iterator mitems*[T](L: var SomeLinkedList[T]): var T = - ## yields every value of `L` so that you can modify it. + ## 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.append(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]" itemsListImpl() iterator mitems*[T](L: var SomeLinkedRing[T]): var T = - ## yields every value of `L` so that you can modify it. + ## 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.append(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]" itemsRingImpl() iterator nodes*[T](L: SomeLinkedList[T]): SomeLinkedNode[T] = - ## iterates over every node of `x`. Removing the current node from the + ## Iterates over every node of `x`. Removing the current node from the ## list during traversal is supported. + ## + ## See also: + ## * `items iterator <#items.i,SomeLinkedList[T]>`_ + ## * `mitems iterator <#mitems.i,SomeLinkedList[T]>`_ + runnableExamples: + var a = initDoublyLinkedList[int]() + for i in 1 .. 5: + a.append(10*i) + 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 = L.head while it != nil: var nxt = it.next @@ -111,8 +281,24 @@ iterator nodes*[T](L: SomeLinkedList[T]): SomeLinkedNode[T] = it = nxt iterator nodes*[T](L: SomeLinkedRing[T]): SomeLinkedNode[T] = - ## iterates over every node of `x`. Removing the current node from the + ## Iterates over every node of `x`. Removing the current node from the ## list during traversal is supported. + ## + ## See also: + ## * `items iterator <#items.i,SomeLinkedRing[T]>`_ + ## * `mitems iterator <#mitems.i,SomeLinkedRing[T]>`_ + runnableExamples: + var a = initDoublyLinkedRing[int]() + for i in 1 .. 5: + a.append(10*i) + 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 = L.head if it != nil: while true: @@ -122,7 +308,7 @@ iterator nodes*[T](L: SomeLinkedRing[T]): SomeLinkedNode[T] = if it == L.head: break proc `$`*[T](L: SomeLinkedCollection[T]): string = - ## turns a list into its string representation. + ## Turns a list into its string representation for logging and printing. result = "[" for x in nodes(L): if result.len > 1: result.add(", ") @@ -130,19 +316,54 @@ proc `$`*[T](L: SomeLinkedCollection[T]): string = result.add("]") proc find*[T](L: SomeLinkedCollection[T], value: T): SomeLinkedNode[T] = - ## searches in the list for a value. Returns nil if the value does not + ## Searches in the list for a value. Returns `nil` if the value does not ## exist. + ## + ## See also: + ## * `contains proc <#contains,SomeLinkedCollection[T],T>`_ + runnableExamples: + var a = initSinglyLinkedList[int]() + a.append(9) + a.append(8) + assert a.find(9).value == 9 + assert a.find(1) == nil + for x in nodes(L): if x.value == value: return x 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. + ## Searches in the list for a value. Returns `false` if the value does not + ## exist, `true` otherwise. + ## + ## See also: + ## * `find proc <#find,SomeLinkedCollection[T],T>`_ + runnableExamples: + var a = initSinglyLinkedList[int]() + a.append(9) + a.append(8) + assert a.contains(9) + assert 8 in a + assert(not a.contains(1)) + assert 2 notin a + result = find(L, value) != nil proc append*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = - ## appends a node `n` to `L`. Efficiency: O(1). + ## 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 + ## * `prepend proc <#prepend,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## for prepending a node + ## * `prepend proc <#prepend,SinglyLinkedList[T],T>`_ for prepending a value + runnableExamples: + var + a = initSinglyLinkedList[int]() + n = newSinglyLinkedNode[int](9) + a.append(n) + assert a.contains(9) + n.next = nil if L.tail != nil: assert(L.tail.next == nil) @@ -151,22 +372,75 @@ proc append*[T](L: var SinglyLinkedList[T], if L.head == nil: L.head = n proc append*[T](L: var SinglyLinkedList[T], value: T) {.inline.} = - ## appends a value to `L`. Efficiency: O(1). + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,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) + assert a.contains(9) append(L, newSinglyLinkedNode(value)) proc prepend*[T](L: var SinglyLinkedList[T], n: SinglyLinkedNode[T]) {.inline.} = - ## prepends a node to `L`. Efficiency: O(1). + ## Prepends (adds to the beginning) a node to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## for appending a node + ## * `append proc <#append,SinglyLinkedList[T],T>`_ for appending a value + ## * `prepend proc <#prepend,SinglyLinkedList[T],T>`_ for prepending a value + runnableExamples: + var + a = initSinglyLinkedList[int]() + n = newSinglyLinkedNode[int](9) + a.prepend(n) + assert a.contains(9) + 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 a node to `L`. Efficiency: O(1). + ## Prepends (adds to the beginning) a node to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,SinglyLinkedList[T],SinglyLinkedNode[T]>`_ + ## for appending a node + ## * `append proc <#append,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) prepend(L, newSinglyLinkedNode(value)) + + proc append*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = - ## appends a node `n` to `L`. Efficiency: O(1). + ## 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 + ## * `prepend proc <#prepend,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## for prepending a node + ## * `prepend proc <#prepend,DoublyLinkedList[T],T>`_ for prepending a value + ## * `remove proc <#remove,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## for removing a node + runnableExamples: + var + a = initDoublyLinkedList[int]() + n = newDoublyLinkedNode[int](9) + a.append(n) + assert a.contains(9) + n.next = nil n.prev = L.tail if L.tail != nil: @@ -176,11 +450,40 @@ proc append*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = if L.head == nil: L.head = n proc append*[T](L: var DoublyLinkedList[T], value: T) = - ## appends a value to `L`. Efficiency: O(1). + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,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.append(9) + a.append(8) + assert a.contains(9) append(L, newDoublyLinkedNode(value)) proc prepend*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = - ## prepends a node `n` to `L`. Efficiency: O(1). + ## Prepends (adds to the beginning) a node `n` to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## for appending a node + ## * `append proc <#append,DoublyLinkedList[T],T>`_ for appending a value + ## * `prepend proc <#prepend,DoublyLinkedList[T],T>`_ for prepending a value + ## * `remove proc <#remove,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## for removing a node + runnableExamples: + var + a = initDoublyLinkedList[int]() + n = newDoublyLinkedNode[int](9) + a.prepend(n) + assert a.contains(9) + n.prev = nil n.next = L.head if L.head != nil: @@ -190,18 +493,56 @@ proc prepend*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = if L.tail == nil: L.tail = n proc prepend*[T](L: var DoublyLinkedList[T], value: T) = - ## prepends a value to `L`. Efficiency: O(1). + ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,DoublyLinkedList[T],DoublyLinkedNode[T]>`_ + ## for appending a node + ## * `append proc <#append,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). + ## 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 + 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). + ## 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 + ## * `prepend proc <#prepend,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## for prepending a node + ## * `prepend proc <#prepend,SinglyLinkedRing[T],T>`_ for prepending a value + runnableExamples: + var + a = initSinglyLinkedRing[int]() + n = newSinglyLinkedNode[int](9) + a.append(n) + assert a.contains(9) + if L.head != nil: n.next = L.head assert(L.tail != nil) @@ -213,11 +554,36 @@ proc append*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = L.tail = n proc append*[T](L: var SinglyLinkedRing[T], value: T) = - ## appends a value to `L`. Efficiency: O(1). + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,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) + assert a.contains(9) append(L, newSinglyLinkedNode(value)) proc prepend*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = - ## prepends a node `n` to `L`. Efficiency: O(1). + ## Prepends (adds to the beginning) a node `n` to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## for appending a node + ## * `append proc <#append,SinglyLinkedRing[T],T>`_ for appending a value + ## * `prepend proc <#prepend,SinglyLinkedRing[T],T>`_ for prepending a value + runnableExamples: + var + a = initSinglyLinkedRing[int]() + n = newSinglyLinkedNode[int](9) + a.prepend(n) + assert a.contains(9) + if L.head != nil: n.next = L.head assert(L.tail != nil) @@ -228,11 +594,40 @@ proc prepend*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = L.head = n proc prepend*[T](L: var SinglyLinkedRing[T], value: T) = - ## prepends a value to `L`. Efficiency: O(1). + ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,SinglyLinkedRing[T],SinglyLinkedNode[T]>`_ + ## for appending a node + ## * `append proc <#append,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). + ## 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 + ## * `prepend proc <#prepend,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## for prepending a node + ## * `prepend proc <#prepend,DoublyLinkedRing[T],T>`_ for prepending a value + ## * `remove proc <#remove,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## for removing a node + runnableExamples: + var + a = initDoublyLinkedRing[int]() + n = newDoublyLinkedNode[int](9) + a.append(n) + assert a.contains(9) + if L.head != nil: n.next = L.head n.prev = L.head.prev @@ -244,11 +639,40 @@ proc append*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = L.head = n proc append*[T](L: var DoublyLinkedRing[T], value: T) = - ## appends a value to `L`. Efficiency: O(1). + ## Appends (adds to the end) a value to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,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.append(9) + a.append(8) + assert a.contains(9) append(L, newDoublyLinkedNode(value)) proc prepend*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = - ## prepends a node `n` to `L`. Efficiency: O(1). + ## Prepends (adds to the beginning) a node `n` to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## for appending a node + ## * `append proc <#append,DoublyLinkedRing[T],T>`_ for appending a value + ## * `prepend proc <#prepend,DoublyLinkedRing[T],T>`_ for prepending a value + ## * `remove proc <#remove,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## for removing a node + runnableExamples: + var + a = initDoublyLinkedRing[int]() + n = newDoublyLinkedNode[int](9) + a.prepend(n) + assert a.contains(9) + if L.head != nil: n.next = L.head n.prev = L.head.prev @@ -260,11 +684,34 @@ proc prepend*[T](L: var DoublyLinkedRing[T], n: DoublyLinkedNode[T]) = L.head = n proc prepend*[T](L: var DoublyLinkedRing[T], value: T) = - ## prepends a value to `L`. Efficiency: O(1). + ## Prepends (adds to the beginning) a value to `L`. Efficiency: O(1). + ## + ## See also: + ## * `append proc <#append,DoublyLinkedRing[T],DoublyLinkedNode[T]>`_ + ## for appending a node + ## * `append proc <#append,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). + ## Removes `n` from `L`. Efficiency: O(1). + runnableExamples: + var + a = initDoublyLinkedRing[int]() + n = newDoublyLinkedNode[int](5) + a.append(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: |