Skip to content
Double ended queue implemented with DoublyLinkedRing
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src
tests
.gitignore
changeLog.md
readme.md
ringDeque.nimble

readme.md

Deque implemented with DoublyLinkedRing

This package is trying to mimic some functionalities of Python's deque from collections. Since there's already a deques implemented with seq, I had to call this RingDeque.

Example Usage

import ringDeque

var dq = newDeque("ghi")

echo dq                       # ['g', 'h', 'i']

dq.append('j')
dq.prepend('f')

echo dq.len                   # 5
echo dq                       # ['f', 'g', 'h', 'i', 'j']

echo dq.pop()                 # j
echo dq.popLeft()             # f

echo dq                       # ['g', 'h', 'i']

var n = dq.headNode # Gets the head node (of type DoublyLinkedNode) of the deque
echo n.value                  # g
echo n.next.value             # h
echo n.prev.value             # i

echo dq[0]                    # g
echo dq.head                  # g
echo dq[^1]                   # i
echo dq.tail                  # i

dq[1] = 'z'
echo dq                       # ['g', 'z', 'i']
dq[1] = 'h'

# dq[x] justs goes down the headNode.next chain x mod dq.len times
# Access the two ends will be fast.
# Access the middle of a long deque will be really slow.

# However, we only go at most dq.len steps
# These are the same as doing dq[0]
echo dq[9]                    # g
echo dq[^9]                   # g

let rdq = reversed(dq)        # Makes a reversed copy of dq
echo rdq                      # ['i', 'h', 'g']

echo 'h' in dq                # true
echo '@' in dq                # false

dq.extend("jkl")
echo dq                       # ['g', 'h', 'i', 'j', 'k', 'l']

dq.rotate(1)
echo dq                       # ['l', 'g', 'h', 'i', 'j', 'k']

dq.rotate(-1)
echo dq                       # ['g', 'h', 'i', 'j', 'k', 'l']

dq.reverse()                  # reverses dq in-place
echo dq                       # ['l', 'k', 'j', 'i', 'h', 'g']

dq.clear()                    # Empty the deque
try:
  discard dq.pop()
except ValueError:
  echo "raises ValueError if popping empty deque"

dq.extendLeft("abc")          # extendLeft() reverses the input order
echo dq                       # ['c', 'b', 'a']

# Utility proc step(node: var DoublyLinkedNode; n = 1)
# Helps with manipulating multiple cursors from a single deque.
var nodeA = dq.headNode
var nodeB = dq.headNode
nodeA.step(2)                 # step(n) to moves nodeA forward n times
echo nodeA.value              # a
nodeB.step(-2)                # step(-n) to moves nodeB backward n times
echo nodeA.value              # b

Please take a look at theTest.nim for more supported usages.

You can’t perform that action at this time.