Skip to Content
ReferenceLibrary

deque

A queue with both ends open: var q = Deque<Int>().

Generated from spec/std/deque.cp by cpl doc --format json.

Deque

pub struct Deque<T>

A queue with both ends open: var q = Deque<Int>(). push / pop work at the back, push_front / pop_front at the front, all amortized O(1); q[i] is the i-th element from the front in O(1). Memory is a ring of at most twice the largest length.

Source

Deque.new

fn new() -> Deque<T>

Create an empty Deque<T>.

  • cost: O(1); nothing is allocated until the first push
  • traps: never

Examples:

  • var q: Deque<Int> = Deque(); q.len == 0

Source

Deque.of

fn of(xs: List<T>) -> Deque<T>

A deque holding xs, front to back: the queue of a search, var q = Deque.of(sources), then while let u = q.pop_front(): .... O(n).

The first element of xs is the front, so pop_front returns the elements in the order xs lists them.

  • cost: O(n)
  • empty: an empty deque
  • traps: never

Examples:

  • Deque.of([1, 2, 3]).to_list() == [1, 2, 3]
  • var q = Deque.of([1, 2]); q.pop_front() == Some(1)

Source

Deque.reserve

fn reserve(mut self, cap: Int)

Reserve capacity for at least cap elements without reallocating. O(1) when empty, O(cap) otherwise.

The contents and their order do not change; a cap no larger than the current capacity (including any cap <= 0) does nothing.

  • cost: O(1) when empty, O(cap) otherwise
  • traps: never

Examples:

  • var q = Deque.of([1, 2]); q.reserve(100); q.to_list() == [1, 2]

Source

Deque.len

fn len(self) -> Int

Number of elements currently in the deque.

  • cost: O(1)
  • traps: never

Examples:

  • Deque.of([4, 5]).len == 2

Source

Deque.is_empty

fn is_empty(self) -> Bool

Whether the deque is empty.

  • cost: O(1)
  • traps: never

Examples:

  • Deque.of([7]).is_empty == false

Source

Deque.clear

fn clear(mut self)

Remove all elements from the deque.

The capacity is kept, so refilling does not reallocate.

  • cost: O(1)
  • traps: never

Examples:

  • var q = Deque.of([1, 2]); q.clear(); q.len == 0

Source

Deque.take

fn take(mut self) -> Deque<T>

Move the deque's contents out in O(1), leaving self empty.

  • cost: O(1)
  • traps: never

Examples:

  • var q = Deque.of([1, 2]); let r = q.take(); q.len == 0 and r.to_list() == [1, 2]

Source

Deque.grow_to

fn grow_to(mut self, cap: Int, fill: T)

Source

Deque.push

fn push(mut self, x: T)

Append x to the back of the deque.

  • cost: O(1) amortized; a full ring doubles
  • traps: never

Examples:

  • var q = Deque.of([1]); q.push(2); q.to_list() == [1, 2]

Source

Deque.push_front

fn push_front(mut self, x: T)

Prepend x to the front of the deque.

Every existing element moves one place back: q[0] is now x.

  • cost: O(1) amortized; a full ring doubles
  • traps: never

Examples:

  • var q = Deque.of([1]); q.push_front(0); q.to_list() == [0, 1]

Source

Deque.pop

fn pop(mut self) -> ?T

Remove and return the back, or None when empty.

  • cost: O(1)
  • empty: None, and the deque stays empty
  • traps: never

Examples:

  • var q = Deque.of([1, 2]); q.pop() == Some(2) and q.to_list() == [1]

Source

Deque.pop_front

fn pop_front(mut self) -> ?T

Remove and return the front, or None when empty.

  • cost: O(1)
  • empty: None, and the deque stays empty
  • traps: never

Examples:

  • var q = Deque.of([1, 2]); q.pop_front() == Some(1) and q.to_list() == [2]

Source

Deque.pop_front_while

fn pop_front_while(mut self, ok: T -> Bool) -> List<T>

O(k) for k removed. Remove and return the longest front run on which ok holds, in order: a queue sorted by key releases everything below a rising threshold.

ok is called front to back and the run stops at the first element where it is false; that element and everything behind it stay. ok is called at most k + 1 times.

  • cost: O(k) for k removed
  • empty: []
  • order: front first, the order the elements sat in; a new List, keyed from 0
  • traps: never

Examples:

  • var q = Deque.of([1, 2, 5, 3]); q.pop_front_while(x => x < 4) == [1, 2] and q.to_list() == [5, 3]

Source

Deque.pop_while

fn pop_while(mut self, ok: T -> Bool) -> List<T>

Pop from the back while ok holds; the popped values, back first. O(popped).

The mirror of pop_front_while: ok is called back to front and the run stops at the first element where it is false.

  • cost: O(k) for k removed
  • empty: []
  • order: back first, the order they were popped; a new List, keyed from 0
  • traps: never

Examples:

  • var q = Deque.of([5, 1, 2]); q.pop_while(x => x < 4) == [2, 1] and q.to_list() == [5]

Source

Deque.first

fn first(self) -> ?T

The front, or None when empty.

  • cost: O(1)
  • empty: None
  • ties: none: there is one front
  • traps: never

Examples:

  • Deque.of([4, 5]).first == Some(4)

Source

Deque.last

fn last(self, k: Int = 0) -> ?T

The back, or None when empty. dq.last(k) is the element k back from it, so dq.last(1) is the one before the back.

dq.last(k) is dq[dq.len - 1 - k] when k < dq.len, and None otherwise.

  • cost: O(1)
  • empty: None for every k
  • ties: none: each k names one place
  • traps: when k < 0

Examples:

  • Deque.of([4, 5, 6]).last == Some(6)
  • Deque.of([4, 5, 6]).last(1) == Some(5)
  • Deque.of([4]).last(1) == None

Source

Deque.items

fn items(self) -> yields (Int, T)

Each element with its place from the front: for (i, x) in dq.items. O(1) to make, O(n) to walk.

  • cost: O(1) to make, O(1) per step
  • empty: yields nothing
  • order: front to back; the places are 0..len
  • traps: never

Examples:

  • Deque.of([7, 8]).items.collect() == [(0, 7), (1, 8)]

Source

Deque.get

fn get(self, i: Int) -> T

The i-th element from the front.

q[i] calls this; place 0 is the front and len - 1 the back.

  • cost: O(1)
  • traps: when i is not in 0..len

Examples:

  • Deque.of([7, 8]).get(1) == 8
  • var q = Deque.of([1]); q.push_front(0); q[0] == 0

Source

Deque.set

fn set(mut self, i: Int, x: T)

Overwrite the i-th element from the front (W8 IndexSet backing dq[i] = x).

  • cost: O(1)
  • traps: when i is not in 0..len

Examples:

  • var q = Deque.of([7, 8]); q[0] = 9; q.to_list() == [9, 8]

Source

Deque.to_list

fn to_list(self) -> List<T>

Materialize the elements front to back as a List<T>.

  • cost: O(n), one new List
  • empty: []
  • order: front to back; a new List, keyed from 0
  • traps: never

Examples:

  • var q = Deque.of([2]); q.push_front(1); q.to_list() == [1, 2]

Source

Deque.each

fn each(self) -> yields T

Yield elements front to back without allocating.

for x in q uses this.

  • cost: O(1) per step
  • empty: yields nothing
  • order: front to back
  • traps: never

Examples:

  • Deque.of([1, 2]).each().collect() == [1, 2]

Source

Deque.each_rev

fn each_rev(self) -> yields T

Yield elements back to front without allocating.

  • cost: O(1) per step
  • empty: yields nothing
  • order: back to front
  • traps: never

Examples:

  • Deque.of([1, 2]).each_rev().collect() == [2, 1]

Source

Deque.rotate_left

fn rotate_left(mut self, k: Int)

Rotate elements left by k positions (k mod len).

The element at place k becomes the front. k is reduced with Euclidean %, so a negative k rotates right: rotate_left(-1) is rotate_right(1).

  • cost: O(min(k, n - k)) after reducing k mod n
  • empty: does nothing, for every k
  • traps: never

Examples:

  • var q = Deque.of([1, 2, 3, 4]); q.rotate_left(1); q.to_list() == [2, 3, 4, 1]
  • var q = Deque.of([1, 2, 3, 4]); q.rotate_left(-1); q.to_list() == [4, 1, 2, 3]

Source

Deque.rotate_right

fn rotate_right(mut self, k: Int)

Rotate elements right by k positions (k mod len).

The back k elements move to the front, in order. rotate_right(k) is rotate_left(-k).

  • cost: O(min(k, n - k)) after reducing k mod n
  • empty: does nothing, for every k
  • traps: never

Examples:

  • var q = Deque.of([1, 2, 3, 4]); q.rotate_right(1); q.to_list() == [4, 1, 2, 3]
  • var q = Deque.of([1, 2, 3]); q.rotate_right(4); q.to_list() == [3, 1, 2]

Source

LinkedList

pub struct LinkedList<T>

Doubly-linked list supporting O(1) end pushes/pops and O(1) splicing (splice_back, splice_front).

Source

LinkedList.fwd

fn fwd(self, i: Int) -> Int

Source

LinkedList.bwd

fn bwd(self, i: Int) -> Int

Source

LinkedList.set_fwd

fn set_fwd(mut self, i: Int, j: Int)

Source

LinkedList.set_bwd

fn set_bwd(mut self, i: Int, j: Int)

Source

LinkedList.node

fn node(mut self, x: T) -> Int

Source

LinkedList.new

fn new() -> LinkedList<T>

Create an empty LinkedList<T>.

  • cost: O(1)
  • traps: never

Examples:

  • var l: LinkedList<Int> = LinkedList(); l.len == 0

Source

LinkedList.of

fn of(x: T) -> LinkedList<T>

Create a singleton LinkedList<T> containing x.

  • cost: O(1)
  • traps: never

Examples:

  • LinkedList.of(5).each().collect() == [5]

Source

LinkedList.from_list

fn from_list(xs: List<T>) -> LinkedList<T>

Build a LinkedList<T> from xs, front to back.

  • cost: O(n)
  • empty: an empty list
  • traps: never

Examples:

  • LinkedList.from_list([1, 2]).each().collect() == [1, 2]

Source

LinkedList.len

fn len(self) -> Int

Number of elements currently in the list.

  • cost: O(1)
  • traps: never

Examples:

  • LinkedList.from_list([1, 2, 3]).len == 3

Source

LinkedList.is_empty

fn is_empty(self) -> Bool

Whether the list is empty.

  • cost: O(1)
  • traps: never

Examples:

  • LinkedList.of(1).is_empty == false

Source

LinkedList.first

fn first(self) -> ?T

The front element, or None when the list is empty (as Deque.first).

  • cost: O(1)
  • empty: None
  • ties: none: there is one front
  • traps: never

Examples:

  • LinkedList.from_list([1, 2]).first == Some(1)

Source

LinkedList.last

fn last(self) -> ?T

The back element, or None when the list is empty (as Deque.last).

  • cost: O(1)
  • empty: None
  • ties: none: there is one back
  • traps: never

Examples:

  • LinkedList.from_list([1, 2]).last == Some(2)

Source

LinkedList.push

fn push(mut self, x: T)

Append x to the back.

  • cost: O(1)
  • traps: never

Examples:

  • var l = LinkedList.of(1); l.push(2); l.each().collect() == [1, 2]

Source

LinkedList.push_front

fn push_front(mut self, x: T)

Prepend x to the front.

  • cost: O(1)
  • traps: never

Examples:

  • var l = LinkedList.of(1); l.push_front(0); l.each().collect() == [0, 1]

Source

LinkedList.pop

fn pop(mut self) -> ?T

Remove and return the back element, or None if empty.

  • cost: O(1)
  • empty: None
  • traps: never

Examples:

  • var l = LinkedList.from_list([1, 2]); l.pop() == Some(2) and l.len == 1

Source

LinkedList.pop_front

fn pop_front(mut self) -> ?T

Remove and return the front element, or None if empty.

  • cost: O(1)
  • empty: None
  • traps: never

Examples:

  • var l = LinkedList.from_list([1, 2]); l.pop_front() == Some(1) and l.first == 2

Source

LinkedList.splice_back

fn splice_back(mut self, other: LinkedList<T>)

Splice all elements of other onto the back of self, consuming other.

The elements keep their order: self's first, then other's. No element is copied.

  • cost: O(1)
  • traps: never

Examples:

  • var a = LinkedList.from_list([1, 2]); a.splice_back(LinkedList.from_list([3, 4])); a.each().collect() == [1, 2, 3, 4]

Source

LinkedList.splice_front

fn splice_front(mut self, other: LinkedList<T>)

Splice all elements of other onto the front of self, consuming other.

The elements keep their order: other's first, then self's.

  • cost: O(1)
  • traps: never

Examples:

  • var a = LinkedList.from_list([1, 2]); a.splice_front(LinkedList.from_list([3, 4])); a.each().collect() == [3, 4, 1, 2]

Source

LinkedList.reverse

fn reverse(mut self)

Reverse the list in place. O(1) via reversible links.

  • cost: O(1)
  • empty: does nothing
  • traps: never

Examples:

  • var a = LinkedList.from_list([1, 2, 3]); a.reverse(); a.each().collect() == [3, 2, 1]

Source

LinkedList.clear

fn clear(mut self)

Remove all elements.

  • cost: O(1)
  • traps: never

Examples:

  • var a = LinkedList.from_list([1, 2]); a.clear(); a.is_empty

Source

LinkedList.each

fn each(self) -> yields T

Yield elements front to back.

  • cost: O(1) per step
  • empty: yields nothing
  • order: front to back
  • traps: never

Examples:

  • LinkedList.from_list([1, 2]).each().collect() == [1, 2]

Source

LinkedList.each_rev

fn each_rev(self) -> yields T

Yield elements back to front.

  • cost: O(1) per step
  • empty: yields nothing
  • order: back to front
  • traps: never

Examples:

  • LinkedList.from_list([1, 2]).each_rev().collect() == [2, 1]

Source

On this page