diff options
author | def <dennis@felsin9.de> | 2015-01-30 02:17:49 +0100 |
---|---|---|
committer | def <dennis@felsin9.de> | 2015-02-01 03:04:18 +0100 |
commit | 11a5a4a9a6a573d5c80c583584323036c72cd691 (patch) | |
tree | 1f24cb41830d4aa21662932dc884f7b1373ab119 | |
parent | 2780e7a54a28ebb87982abbb4a5b0e1ccfe31451 (diff) | |
download | Nim-11a5a4a9a6a573d5c80c583584323036c72cd691.tar.gz |
Fix SinglyLinkedRing in lists module
- SinglyLinkedRing's prepend was broken - needed a tail so that prepend can work properly - now append works as well, so I added it too - simple testcase added as well
-rw-r--r-- | lib/pure/collections/lists.nim | 26 | ||||
-rw-r--r-- | tests/stdlib/tsinglylinkedring.nim | 29 |
2 files changed, 51 insertions, 4 deletions
diff --git a/lib/pure/collections/lists.nim b/lib/pure/collections/lists.nim index 095775cbb..535d5e21d 100644 --- a/lib/pure/collections/lists.nim +++ b/lib/pure/collections/lists.nim @@ -32,7 +32,7 @@ type head*, tail*: DoublyLinkedNode[T] SinglyLinkedRing*[T] = object ## a singly linked ring - head*: SinglyLinkedNode[T] + head*, tail*: SinglyLinkedNode[T] DoublyLinkedRing*[T] = object ## a doubly linked ring head*: DoublyLinkedNode[T] @@ -267,13 +267,31 @@ proc remove*[T](L: var DoublyLinkedList[T], n: DoublyLinkedNode[T]) = 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). + 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 + +proc append*[T](L: var SinglyLinkedRing[T], value: T) = + ## appends a value to `L`. Efficiency: O(1). + append(L, newSinglyLinkedNode(value)) + proc prepend*[T](L: var SinglyLinkedRing[T], n: SinglyLinkedNode[T]) = ## prepends a node `n` to `L`. Efficiency: O(1). - if L.head != nil: + if L.head != nil: n.next = L.head - L.head.next = n - else: + assert(L.tail != nil) + L.tail.next = n + else: n.next = n + L.tail = n L.head = n proc prepend*[T](L: var SinglyLinkedRing[T], value: T) = diff --git a/tests/stdlib/tsinglylinkedring.nim b/tests/stdlib/tsinglylinkedring.nim new file mode 100644 index 000000000..93f0c69cd --- /dev/null +++ b/tests/stdlib/tsinglylinkedring.nim @@ -0,0 +1,29 @@ +discard """ + output: '''[5] +[4, 5] +[3, 4, 5] +[2, 3, 4, 5] +[2, 3, 4, 5, 6] +[2, 3, 4, 5, 6, 7] +[2, 3, 4, 5, 6, 7, 8] +[1, 2, 3, 4, 5, 6, 7, 8]''' +""" +import lists + +var r = initSinglyLinkedRing[int]() +r.prepend(5) +echo r +r.prepend(4) +echo r +r.prepend(3) +echo r +r.prepend(2) +echo r +r.append(6) +echo r +r.append(7) +echo r +r.append(8) +echo r +r.prepend(1) +echo r |