Merge pull request #2037 from def-/fix-lists

Fix SinglyLinkedRing in lists module

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