std/lists (original) (raw)

Source Edit

Implementation of:

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

Example:

import std/lists var list = initDoublyLinkedListint let a = newDoublyLinkedNodeint b = newDoublyLinkedNodeint c = newDoublyLinkedNodeint

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

Example:

import std/lists var ring = initSinglyLinkedRingint let a = newSinglyLinkedNodeint b = newSinglyLinkedNodeint c = newSinglyLinkedNodeint

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

Procs

proc $[T](L: SomeLinkedCollection[T]): string

Turns a list into its string representation for logging and printing.

Example:

let a = [1, 2, 3, 4].toSinglyLinkedList assert $a == "[1, 2, 3, 4]"

Source Edit

proc add[T: SomeLinkedList](a: var T; b: T)

Appends a shallow copy of b to the end of a.

See also:

Example:

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]

Source Edit

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:

Example:

var a = initDoublyLinkedListint let n = newDoublyLinkedNodeint a.add(n) assert a.contains(9)

Source Edit

proc add[T](L: var DoublyLinkedList[T]; value: T)

Appends (adds to the end) a value to L. Efficiency: O(1).

See also:

Example:

var a = initDoublyLinkedListint a.add(9) a.add(8) assert a.contains(9)

Source Edit

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:

Example:

var a = initDoublyLinkedRingint let n = newDoublyLinkedNodeint a.add(n) assert a.contains(9)

Source Edit

proc add[T](L: var DoublyLinkedRing[T]; value: T)

Appends (adds to the end) a value to L. Efficiency: O(1).

See also:

Example:

var a = initDoublyLinkedRingint a.add(9) a.add(8) assert a.contains(9)

Source Edit

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:

Example:

var a = initSinglyLinkedListint let n = newSinglyLinkedNodeint a.add(n) assert a.contains(9)

Source Edit

proc add[T](L: var SinglyLinkedList[T]; value: T) {.inline.}

Appends (adds to the end) a value to L. Efficiency: O(1).

See also:

Example:

var a = initSinglyLinkedListint a.add(9) a.add(8) assert a.contains(9)

Source Edit

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:

Example:

var a = initSinglyLinkedRingint let n = newSinglyLinkedNodeint a.add(n) assert a.contains(9)

Source Edit

proc add[T](L: var SinglyLinkedRing[T]; value: T)

Appends (adds to the end) a value to L. Efficiency: O(1).

See also:

Example:

var a = initSinglyLinkedRingint a.add(9) a.add(8) assert a.contains(9)

Source Edit

proc addMoved[T](a, b: var DoublyLinkedList[T])

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:

Example:

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]

Source Edit

proc addMoved[T](a, b: var SinglyLinkedList[T])

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:

Example:

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]

Source Edit

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:

Example:

let a = [9, 8].toSinglyLinkedList assert a.contains(9) assert 8 in a assert(not a.contains(1)) assert 2 notin a

Source Edit

func copy[T](a: DoublyLinkedList[T]): DoublyLinkedList[T]

Creates a shallow copy of a.

Example:

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] f.x = 42 assert a.head.value.x == 42 assert b.head.value.x == 42

let c = [1, 2, 3].toDoublyLinkedList assert c==c == c==c.copy

Source Edit

func copy[T](a: SinglyLinkedList[T]): SinglyLinkedList[T]

Creates a shallow copy of a.

Example:

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] f.x = 42 assert a.head.value.x == 42 assert b.head.value.x == 42

let c = [1, 2, 3].toSinglyLinkedList assert c==c == c==c.copy

Source Edit

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.

See also:

Example:

let a = [9, 8].toSinglyLinkedList assert a.find(9).value == 9 assert a.find(1) == nil

Source Edit

proc initDoublyLinkedListT: DoublyLinkedList[T]

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.

Example:

let a = initDoublyLinkedListint

Source Edit

proc initDoublyLinkedRingT: DoublyLinkedRing[T]

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.

Example:

let a = initDoublyLinkedRingint

Source Edit

proc initSinglyLinkedListT: SinglyLinkedList[T]

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.

Example:

let a = initSinglyLinkedListint

Source Edit

proc initSinglyLinkedRingT: SinglyLinkedRing[T]

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.

Example:

let a = initSinglyLinkedRingint

Source Edit

proc newDoublyLinkedNode[T](value: T): DoublyLinkedNode[T]

Creates a new doubly linked node with the given value.

Example:

let n = newDoublyLinkedNodeint assert n.value == 5

Source Edit

proc newSinglyLinkedNode[T](value: T): SinglyLinkedNode[T]

Creates a new singly linked node with the given value.

Example:

let n = newSinglyLinkedNodeint assert n.value == 5

Source Edit

proc prepend[T: SomeLinkedList](a: var T; b: T)

Prepends a shallow copy of b to the beginning of a.

See also:

Example:

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]

Source Edit

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:

Example:

var a = initDoublyLinkedListint let n = newDoublyLinkedNodeint a.prepend(n) assert a.contains(9)

Source Edit

proc prepend[T](L: var DoublyLinkedList[T]; value: T)

Prepends (adds to the beginning) a value to L. Efficiency: O(1).

See also:

Example:

var a = initDoublyLinkedListint a.prepend(9) a.prepend(8) assert a.contains(9)

Source Edit

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:

Example:

var a = initDoublyLinkedRingint let n = newDoublyLinkedNodeint a.prepend(n) assert a.contains(9)

Source Edit

proc prepend[T](L: var DoublyLinkedRing[T]; value: T)

Prepends (adds to the beginning) a value to L. Efficiency: O(1).

See also:

Example:

var a = initDoublyLinkedRingint a.prepend(9) a.prepend(8) assert a.contains(9)

Source Edit

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:

Example:

var a = initSinglyLinkedListint let n = newSinglyLinkedNodeint a.prepend(n) assert a.contains(9)

Source Edit

proc prepend[T](L: var SinglyLinkedList[T]; value: T) {.inline.}

Prepends (adds to the beginning) a node to L. Efficiency: O(1).

See also:

Example:

var a = initSinglyLinkedListint a.prepend(9) a.prepend(8) assert a.contains(9)

Source Edit

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:

Example:

var a = initSinglyLinkedRingint let n = newSinglyLinkedNodeint a.prepend(n) assert a.contains(9)

Source Edit

proc prepend[T](L: var SinglyLinkedRing[T]; value: T)

Prepends (adds to the beginning) a value to L. Efficiency: O(1).

See also:

Example:

var a = initSinglyLinkedRingint a.prepend(9) a.prepend(8) assert a.contains(9)

Source Edit

proc prependMoved[T: SomeLinkedList](a, b: var T)

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:

Example:

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]

Source Edit

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.

Example:

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) a.remove(a.head) let s = collect: for i, ai in enumerate(a): if i == 4: break ai assert s == [2, 2, 2, 2]

Source Edit

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.

Example:

var a = initDoublyLinkedRingint let n = newDoublyLinkedNodeint a.add(n) assert 5 in a a.remove(n) assert 5 notin a

Source Edit

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.

Example:

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) a.remove(a.head) let s = collect: for i, ai in enumerate(a): if i == 4: break ai assert s == [2, 2, 2, 2]

Source Edit

func toDoublyLinkedList[T](elems: openArray[T]): DoublyLinkedList[T]

Creates a new DoublyLinkedList from the members of elems.

Example:

from std/sequtils import toSeq let a = [1, 2, 3, 4, 5].toDoublyLinkedList assert a.toSeq == [1, 2, 3, 4, 5]

Source Edit

func toDoublyLinkedRing[T](elems: openArray[T]): DoublyLinkedRing[T]

Creates a new DoublyLinkedRing from the members of elems.

Example:

from std/sequtils import toSeq let a = [1, 2, 3, 4, 5].toDoublyLinkedRing assert a.toSeq == [1, 2, 3, 4, 5]

Source Edit

func toSinglyLinkedList[T](elems: openArray[T]): SinglyLinkedList[T]

Creates a new SinglyLinkedList from the members of elems.

Example:

from std/sequtils import toSeq let a = [1, 2, 3, 4, 5].toSinglyLinkedList assert a.toSeq == [1, 2, 3, 4, 5]

Source Edit

func toSinglyLinkedRing[T](elems: openArray[T]): SinglyLinkedRing[T]

Creates a new SinglyLinkedRing from the members of elems.

Example:

from std/sequtils import toSeq let a = [1, 2, 3, 4, 5].toSinglyLinkedRing assert a.toSeq == [1, 2, 3, 4, 5]

Source Edit

Iterators

iterator items[T](L: SomeLinkedList[T]): T

Yields every value of L.

See also:

Example:

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]

Source Edit

iterator items[T](L: SomeLinkedRing[T]): T

Yields every value of L.

See also:

Example:

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]

Source Edit

iterator mitems[T](L: var SomeLinkedList[T]): var T

Yields every value of L so that you can modify it.

See also:

Example:

var a = initSinglyLinkedListint 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]"

Source Edit

iterator mitems[T](L: var SomeLinkedRing[T]): var T

Yields every value of L so that you can modify it.

See also:

Example:

var a = initSinglyLinkedRingint 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]"

Source Edit

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.

See also:

Example:

var a = initDoublyLinkedListint 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]"

Source Edit

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.

See also:

Example:

var a = initDoublyLinkedRingint 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]"

Source Edit