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.
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
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)
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]
Deque.len
fn len(self) -> IntNumber of elements currently in the deque.
- cost: O(1)
- traps: never
Examples:
Deque.of([4, 5]).len == 2
Deque.is_empty
fn is_empty(self) -> BoolWhether the deque is empty.
- cost: O(1)
- traps: never
Examples:
Deque.of([7]).is_empty == false
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
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]
Deque.grow_to
fn grow_to(mut self, cap: Int, fill: T)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]
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]
Deque.pop
fn pop(mut self) -> ?TRemove 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]
Deque.pop_front
fn pop_front(mut self) -> ?TRemove 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]
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
kremoved - 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]
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
kremoved - 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]
Deque.first
fn first(self) -> ?TThe 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)
Deque.last
fn last(self, k: Int = 0) -> ?TThe 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:
Nonefor everyk - ties: none: each
knames 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
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)]
Deque.get
fn get(self, i: Int) -> TThe 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
iis not in0..len
Examples:
Deque.of([7, 8]).get(1) == 8var q = Deque.of([1]); q.push_front(0); q[0] == 0
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
iis not in0..len
Examples:
var q = Deque.of([7, 8]); q[0] = 9; q.to_list() == [9, 8]
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]
Deque.each
fn each(self) -> yields TYield 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]
Deque.each_rev
fn each_rev(self) -> yields TYield 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]
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
kmodn - 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]
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
kmodn - 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]
LinkedList
pub struct LinkedList<T>Doubly-linked list supporting O(1) end pushes/pops and O(1) splicing (splice_back, splice_front).
LinkedList.fwd
fn fwd(self, i: Int) -> IntLinkedList.bwd
fn bwd(self, i: Int) -> IntLinkedList.set_fwd
fn set_fwd(mut self, i: Int, j: Int)LinkedList.set_bwd
fn set_bwd(mut self, i: Int, j: Int)LinkedList.node
fn node(mut self, x: T) -> IntLinkedList.new
fn new() -> LinkedList<T>Create an empty LinkedList<T>.
- cost: O(1)
- traps: never
Examples:
var l: LinkedList<Int> = LinkedList(); l.len == 0
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]
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]
LinkedList.len
fn len(self) -> IntNumber of elements currently in the list.
- cost: O(1)
- traps: never
Examples:
LinkedList.from_list([1, 2, 3]).len == 3
LinkedList.is_empty
fn is_empty(self) -> BoolWhether the list is empty.
- cost: O(1)
- traps: never
Examples:
LinkedList.of(1).is_empty == false
LinkedList.first
fn first(self) -> ?TThe 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)
LinkedList.last
fn last(self) -> ?TThe 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)
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]
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]
LinkedList.pop
fn pop(mut self) -> ?TRemove 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
LinkedList.pop_front
fn pop_front(mut self) -> ?TRemove 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
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]
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]
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]
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
LinkedList.each
fn each(self) -> yields TYield 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]
LinkedList.each_rev
fn each_rev(self) -> yields TYield 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]