deques

nimony/lib/std/deques.nim

An implementation of a deque:idx: (double-ended queue). The underlying implementation uses a seq.

This is the Nimony port. The container is a growable, power-of-two ring buffer: elements are appended/prepended in amortized O(1) and indexed in O(1). Since exceptions are not yet wired up, accessing an element of an empty Deque (or an out-of-range index) is a broken precondition, expressed as a .requires contract, rather than raising IndexDefect.

type Deque = object
  data: seq[T]
  head: int64
  tail: int64
  count: int64
  mask: int64

func initDeque(initialSize: int64): Deque[T]
Creates a new empty Deque.
initialSize is rounded up to the next power of two and used as the initial capacity, avoiding reallocations when the final size is known.
func len(d: Deque[T]): int64
Returns the number of elements of d.
func addLast(d: var Deque[T]; item: sink T)
Adds an item to the end of d.
func addFirst(d: var Deque[T]; item: sink T)
Adds an item to the beginning of d.
func peekFirst(d: Deque[T]): var T
Returns the first element of d. Requires d to be non-empty.
func peekLast(d: Deque[T]): var T
Returns the last element of d. Requires d to be non-empty.
func popFirst(d: var Deque[T]): T
Removes and returns the first element of d. Requires d to be non-empty.
func popLast(d: var Deque[T]): T
Removes and returns the last element of d. Requires d to be non-empty.
func [](d: Deque[T]; i: int64): var T
Accesses the i-th element of d (0-based, counting from the front). Requires i to be in range.
func []=(d: var Deque[T]; i: int64; val: sink T)
Sets the i-th element of d (0-based, counting from the front). Requires i to be in range.
func clear(d: var Deque[T])
Resets d to an empty state, destroying its elements.
func contains(d: Deque[T]; item: T): bool
Returns true if item is in d. Used by the in operator.
iterator items(d: Deque[T]): var T
Yields every element of d, from first to last.
iterator mitems(d: var Deque[T]): var T
Yields every element of d by reference, allowing modification in place.
iterator pairs(d: Deque[T]): tuple[int64, var T]
Yields every (index, element) pair of d, from first to last.
func $(d: Deque[T]): string
Returns the string representation of d, e.g. "[1, 2, 3]".
func toDeque(xs: openArray[T]): Deque[T]
Creates a new Deque containing the elements of xs, in order.