iyi

Standard library, 0.18.0

std/deque

Deque, a double-ended queue over a ring buffer.

import std/deque to use it. Source: src/std/deque.iyi at v0.18.0.

A Deque(T) adds and removes at both ends in amortised O(1) (push, pop, shift, unshift), is indexable ([], []=, negative indices count from the end), rotates in O(min(n, size - n)), and inserts or deletes in the middle by moving the shorter side.

How it is built:

* One contiguous `Pointer(T)` of `@capacity` slots; `@start` is the slot
  of logical element 0, and the elements wrap around the end of the
  buffer when they reach it.
* A push into a full buffer doubles it; if the elements were wrapped at
  that moment, the shorter of the two runs is moved so the logical order
  is contiguous again.
* A slot vacated by `pop`, `shift`, `delete_at` or `clear` is zeroed, so
  an object the deque no longer holds is not kept alive by it.

What comes from the traits: impl Indexable supplies [], []?, first, first?, last, last?, each, to_a, index, join and the rest; impl IndexableMutable supplies swap, fill, update and reverse_in_place; impl Enumerable supplies map, select, sum and the rest. Only what a ring buffer can do better is written here, and the names match Array's: rotate_in_place moves this deque, rotated answers a copy.

What is refused, in the prelude's words: pop/shift/first/last of an empty deque (pop of an empty deque; the ? forms answer nil), an index past the end (index 5 out of range for 3 elements), a negative count (negative count: -1), a negative size or capacity.

Deque(T)class

std/dequeiyi doc src/std/deque.iyi
pub class Deque(T)
  # A new deque: this one's elements, then other's.
  def +(other : Deque(T)) : Deque(T)
  def <<(value : T) : Deque(T)
  # The same elements in the same order, where one element type holds the
  # other, as tuples compare (src/iyi/object.iyi). Restricted to
  # `Deque(T)`, a `Deque(Int32)` was taken for a `Deque(Int32?)` and not
  # back: the one equality answered true one way and false the other.
  def ==(other : Deque(U)) : Bool forall U
  def []=(index : Int32, value : T) : T
  # Slots allocated, live or not.
  def capacity : Int32
  # Forgets every element; the capacity stays.
  def clear : Deque(T)
  # Appends every element of other; answers the deque. The count is read
  # once: walking `other.size` while pushing grew it along with this deque
  # when the two were one, so `d.concat(d)` never ended.
  def concat(other : Deque(T)) : Deque(T)
  def concat(items : Array(T)) : Deque(T)
  # Removes and answers the element at index; the shorter side closes
  # the gap.
  def delete_at(index : Int32) : T
  # A copy with the same elements, contiguous from slot 0.
  def dup : Deque(T)
  # size copies of value.
  def initialize(size : Int32, value : T)
  # An empty deque with room for initial_capacity elements before it grows.
  def initialize(initial_capacity : Int32)
  # An empty deque; the first push allocates.
  def initialize
  # Inserts value before index; `size` appends, `-1` appends too (the
  # position after the last). The shorter side moves.
  def insert(index : Int32, value : T) : Deque(T)
  def inspect : String
  # The array's elements, in its order.
  def self.new(items : Array(T)) : Deque(T)
  # size elements, each what the block answers for its index.
  def self.new(size : Int32, & : (Int32 -> T)) : Deque(T)
  # Removes the last n elements, or all of them when there are fewer.
  def pop(n : Int32) : Nil
  # Removes and answers the last element.
  def pop : T
  def pop? : T | ::Nil
  # Appends value; answers the deque.
  def push(value : T) : Deque(T)
  # Rotates in place so that the element at position n comes first; a
  # negative n rotates the other way. A full buffer only moves `@start`;
  # otherwise the shorter end is walked around.
  def rotate_in_place(n : Int32 = 1) : Deque(T)
  # A copy rotated by n, this deque untouched.
  def rotated(n : Int32 = 1) : Deque(T)
  # Removes the first n elements, or all of them when there are fewer.
  def shift(n : Int32) : Nil
  # Removes and answers the first element.
  def shift : T
  def shift? : T | ::Nil
  def size : Int32
  # `Deque{1, 2, 3}`, elements inspected.
  def to_s : String
  # The element at a logical index, no bounds check; `Indexable#[]` does
  # the checking.
  def unsafe_fetch(index : Int32) : T
  # Prepends value; answers the deque.
  def unshift(value : T) : Deque(T)
end

Std::Indexable::Indexable for Deque(T) forall Timpl

std/dequeiyi doc src/std/deque.iyi
impl Std::Indexable::Indexable for Deque(T) forall T
end

Std::Indexable::IndexableMutable for Deque(T) forall Timpl

std/dequeiyi doc src/std/deque.iyi
impl Std::Indexable::IndexableMutable for Deque(T) forall T
  def unsafe_put(index : Int32, value : T) : T
end

Std::Enumerable::Enumerable for Deque(T) forall Timpl

std/dequeiyi doc src/std/deque.iyi
impl Std::Enumerable::Enumerable for Deque(T) forall T
end