#
#
# Nimrod's Runtime Library
# (c) Copyright 2011 Andreas Rumpf
#
# See the file "copying.txt", included in this
# 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.
type
TDoublyLinkedNode*[T] {.pure,
final.} = object ## a node a doubly linked list consists of
next*, prev*: ref TDoublyLinkedNode[T]
value*: T
PDoublyLinkedNode*[T] = ref TDoublyLinkedNode[T]
TSinglyLinkedNode*[T] {.pure,
final.} = object ## a node a singly linked list consists of
next*: ref TSinglyLinkedNode[T]
value*: T
PSinglyLinkedNode*[T] = ref TSinglyLinkedNode[T]
TRingNode[T] {.pure,
final.} = object ## a node a ring list consists of
next*, prev*: ref TRingNode[T]
value*: T
PRingNode*[T] = ref TRingNode[T]
proc newDoublyLinkedNode*[T](value: T): PDoublyLinkedNode[T] =
## creates a new doubly linked node with the given `value`.
new(result)
result.value = value
proc newSinglyLinkedNode*[T](value: T): PSinglyLinkedNode[T] =
## creates a new singly linked node with the given `value`.
new(result)
result.value = value
iterator items*[T](n: PDoublyLinkedNode[T]): T =
## yields every value of `x`.
var it = n
while it != nil:
yield it.value
it = it.next
iterator items*[T](n: PSinglyLinkedNode[T]): T =
## yields every value of `x`.
var it = n
while it != nil:
yield it.value
it = it.next
iterator nodes*[T](n: PSinglyLinkedNode[T]): PSinglyLinkedNode[T] =
## iterates over every node of `x`. Removing the current node from the
## list during traversal is supported.
var it = n
while it != nil:
var nxt = it.next
yield it
it = nxt
iterator nodes*[T](n: PDoublyLinkedNode[T]): PDoublyLinkedNode[T] =
## iterates over every node of `x`. Removing the current node from the
## list during traversal is supported.
var it = n
while it != nil:
var nxt = it.next
yield it
it = nxt
proc `$`*[list: PSinglyLinkedNode|PDoublyLinkedNode](n: list): string =
## turns a list into its string representation.
result = "["
for x in nodes(n):
if result.len > 1: result.add(", ")
result.add($x.value)
result.add("]")
proc find*[list: PSinglyLinkedNode|PDoublyLinkedNode, T](
n: list, value: T): list =
## searches in the list for a value. Returns nil if the value does not
## exist.
for x in nodes(n):
if x.value == value: return x
proc contains*[list: PSinglyLinkedNode|PDoublyLinkedNode, T](
n: list, value: T): list =
## searches in the list for a value. Returns false if the value does not
## exist, true otherwise.
for x in nodes(n):
if x.value == value: return true
proc prepend*[T](head: var PSinglyLinkedNode[T],
toAdd: PSinglyLinkedNode[T]) {.inline.} =
## prepends a node to `head`. Efficiency: O(1).
toAdd.next = head
head = toAdd
proc prepend*[T](head: var PSinglyLinkedNode[T], x: T) {.inline.} =
## creates a new node with the value `x` and prepends that node to `head`.
## Efficiency: O(1).
preprend(head, newSinglyLinkedNode(x))
proc append*[T](head: var PSinglyLinkedNode[T],
toAdd: PSinglyLinkedNode[T]) =
## appends a node to `head`. Efficiency: O(n).
if head == nil:
head = toAdd
else:
var it = head
while it.next != nil: it = it.next
it.next = toAdd
proc append*[T](head: var PSinglyLinkedNode[T], x: T) {.inline.} =
## creates a new node with the value `x` and appends that node to `head`.
## Efficiency: O(n).
append(head, newSinglyLinkedNode(x))
proc prepend*[T](head: var PDoublyLinkedNode[T],
toAdd: PDoublyLinkedNode[T]) {.inline.} =
## prepends a node to `head`. Efficiency: O(1).
if head == nil:
head = toAdd
# head.prev stores the last node:
head.prev = toAdd
else:
toAdd.next = head
toAdd.prev = head.prev # copy pointer to last element
head.prev = toAdd
head = toAdd
proc prepend*[T](head: var PDoublyLinkedNode[T], x: T) {.inline.} =
## creates a new node with the value `x` and prepends that node to `head`.
## Efficiency: O(1).
preprend(head, newDoublyLinkedNode(x))
proc append*[T](head: var PDoublyLinkedNode[T],
toAdd: PDoublyLinkedNode[T]) {.inline.} =
## appends a node to `head`. Efficiency: O(1).
if head == nil:
head = toAdd
# head.prev stores the last node:
head.prev = toAdd
else:
var last = head.prev
assert last.next == nil
last.next = toAdd
toAdd.prev = last
head.prev = toAdd # new last element
proc append*[T](head: var PDoublyLinkedNode[T], x: T) {.inline.} =
## creates a new node with the value `x` and appends that node to `head`.
## Efficiency: O(1).
append(head, newDoublyLinkedNode(x))