Deque

public struct Deque[T] { /* private fields */ }

A double-ended queue backed by a ring buffer with copy-on-write storage.

O(1) amortized pushBack/pushFront/popBack/popFront and O(1) random access by index. Storage is shared between copies until one mutates, at which point the COW barrier fires.

Examples

var d = Deque[Int64]();
d.pushBack(1);
d.pushFront(0);
d.pushBack(2);
d.popFront();  // .Some(0)
d.popBack();   // .Some(2)

Representation

Holds a CowBox[DequeStorage[T]]. The storage is a (ptr, len, cap, head) quad over a heap-allocated ring buffer.

Memory Model

Reference-counted storage with copy-on-write value semantics via CowBox. Copying a Deque is O(1); the first mutation on a shared copy triggers a deep clone that linearizes the ring buffer.

Guarantees

pushBack/pushFront are O(1) amortized; growth is geometric.
popBack/popFront are O(1).
Subscript access is O(1).
Iteration order is front-to-back.

Properties

public var capacity: Int64 { get }

Number of elements the buffer can hold without reallocating.

The deque automatically grows when count exceeds capacity, so this is mainly useful for pre-sizing via reserveCapacity().

Examples

var d = Deque[Int64](capacity: 16);
d.capacity;  // 16

public var count: Int64 { get }

Number of elements in the deque.

Examples

let d = Deque[Int64](from: [1, 2, 3]);
d.count;  // 3

public var isEmpty: Bool { get }

True when the deque contains no elements.

Examples

Deque[Int64]().isEmpty;  // true
Deque[Int64](from: [1]).isEmpty;  // false

Initializers

public init()

Creates an empty deque with no allocation.

No heap memory is allocated until the first pushBack or pushFront. Use Deque(capacity:) to pre-allocate when the expected size is known.

Examples

var d = Deque[Int64]();
d.isEmpty;  // true

public init[I](from: I) where I: Iterable, I.Item == T

Creates a deque by collecting every element from an iterable.

Elements are appended via pushBack, so iteration order of the source is preserved as front-to-back order in the deque.

Examples

let d = Deque[Int64](from: 1..<5);
d.count;  // 4
d.first();  // .Some(1)
d.last();   // .Some(4)

public init(capacity: Int64)

Creates an empty deque with at least capacity slots reserved.

Allocates a ring buffer that can hold capacity elements before needing to grow. Passing 0 is equivalent to Deque().

Examples

var d = Deque[Int64](capacity: 100);
d.count;  // 0
d.capacity;  // 100

Methods

public func asSlices() -> (ArraySlice[T], ArraySlice[T])

Returns the two contiguous slices that make up the ring buffer.

If the buffer doesn't wrap, the first slice contains all elements and the second is empty. If it wraps, the first slice covers head-to-end and the second covers start-to-tail. Useful for bulk operations that need pointer-contiguous access without copying.

Examples

var d = Deque[Int64](from: [1, 2, 3]);
let (a, b) = d.asSlices();
// non-wrapping: a contains all 3 elements, b is empty

public mutating func clear()

Removes all elements, retaining allocated capacity.

After calling clear(), count is 0 and head resets to 0, but the buffer stays allocated so subsequent pushes avoid reallocation.

Examples

var d = Deque[Int64](from: [1, 2, 3]);
d.clear();
d.isEmpty;  // true

public func first() -> T?

Returns the front element without removing it, or .None if empty.

O(1). The removing counterpart is popFront().

Examples

let d = Deque[Int64](from: [10, 20, 30]);
d.first();  // .Some(10)
Deque[Int64]().first();  // .None

public func last() -> T?

Returns the back element without removing it, or .None if empty.

O(1). The removing counterpart is popBack().

Examples

let d = Deque[Int64](from: [10, 20, 30]);
d.last();  // .Some(30)
Deque[Int64]().last();  // .None

public mutating func popBack() -> T?

Removes and returns the back element, or .None if empty. O(1).

Retracts the logical tail by one slot. The non-removing mirror is last(). The front-end counterpart is popFront().

Examples

var d = Deque[Int64](from: [1, 2, 3]);
d.popBack();  // .Some(3)
d.popBack();  // .Some(2)
d.popBack();  // .Some(1)
d.popBack();  // .None

public mutating func popFront() -> T?

Removes and returns the front element, or .None if empty. O(1).

Advances the ring-buffer head by one slot. The non-removing mirror is first(). The back-end counterpart is popBack().

Examples

var d = Deque[Int64](from: [1, 2, 3]);
d.popFront();  // .Some(1)
d.popFront();  // .Some(2)
d.popFront();  // .Some(3)
d.popFront();  // .None

public mutating func pushBack(T)

Appends element to the back of the deque. O(1) amortized.

Grows the ring buffer geometrically when full. The counterpart for the front end is pushFront.

Examples

var d = Deque[Int64]();
d.pushBack(1);
d.pushBack(2);
d.popFront();  // .Some(1)

public mutating func pushFront(T)

Prepends element to the front of the deque. O(1) amortized.

Grows the ring buffer geometrically when full. The counterpart for the back end is pushBack.

Examples

var d = Deque[Int64]();
d.pushFront(1);
d.pushFront(0);
d.popFront();  // .Some(0)

public mutating func reserveCapacity(minimumCapacity: Int64)

Ensures the buffer can hold at least capacity elements without reallocating.

If the current capacity already meets or exceeds capacity, this is a no-op. Otherwise the ring buffer is reallocated and linearized. Useful before a burst of pushBack/pushFront calls when the final size is known in advance.

Examples

var d = Deque[Int64]();
d.reserveCapacity(minimumCapacity: 100);

Subscripts

subscript(Int64) -> T { get set }

O(1) random access by logical index.

Logical index 0 is the front element, count - 1 is the back. The ring-buffer offset is computed internally. Both get and set are O(1).

Errors

Panics with "Deque: index out of bounds" when index < 0 or index >= count.

Examples

var d = Deque[Int64](from: [10, 20, 30]);
d(0);  // 10
d(2);  // 30
d(1) = 99;
d(1);  // 99

ImplementsIterable

Associated Types

type Item = T

Iterable element type.

type TargetIterator = DequeIterator[T]

Iterable iterator type.

Methods

public func iter() -> DequeIterator[T]

Returns an iterator that yields elements front-to-back.

The iterator walks the ring buffer from head through count elements, wrapping around the buffer boundary transparently.

Examples

var d = Deque[Int64](from: [10, 20, 30]);
for x in d {
    // yields 10, 20, 30
}

ImplementsCloneable

Methods

public func clone() -> Deque[T]

Returns a shallow copy of this deque. O(1).

The CowBox storage is shared until either copy mutates, at which point the COW barrier fires a deep clone that linearizes the ring buffer.

Examples

let d = Deque[Int64](from: [1, 2, 3]);
var d2 = d.clone();
d2.pushBack(4);
d.count;   // 3 -- original unchanged
d2.count;  // 4

Defined in lang/std/collections/deque.ks