src/containers/deque.bend checks

raw source on the hub · import 0xe4067e0d858024083f36a7abe7281e89/src/containers/deque.bend as Deque

2 imports

import Base
import ./types/deque.bend as E

Types

type Deque source · line 8 · raw

@-T:Data -> Type

Two-list deque: logical order is front ++ reverse(back). Rebalance only when the requested side is empty, moving half the other side. End operations are amortized O(1) along a consumed state history; a rebalance is O(n). to_list is O(n). No arrays, handles or DLL storage.

DE

@-T:Data -> @front:List<&2, T> -> @back:List<&2, T> -> @nf:Nat -> @nb:Nat -> Deque<T>

Templates

template new source · line 11 · raw

@-T:Data -> Deque<T>

template length source · line 14 · raw

@-T:Data -> @d:Deque<T> -> Pair(Deque<T>, Nat)

template push_front source · line 18 · raw

@-T:Data -> @d:Deque<T> -> @x:T -> Deque<T>

template push_back source · line 22 · raw

@-T:Data -> @d:Deque<T> -> @x:T -> Deque<T>

template split_cons source · line 27 · raw

@-T:Data -> @x:T -> @r:Pair(List<&2, T>, List<&2, T>) -> Pair(List<&2, T>, List<&2, T>)

One split traversal; keep the near half, reverse the far half.

template split source · line 31 · raw

@-T:Data -> @n:Nat -> @xs:List<&2, T> -> Pair(List<&2, T>, List<&2, T>)

template front_split source · line 40 · raw

@-T:Data -> @+n:Nat -> @+half:Nat -> @r:Pair(List<&2, T>, List<&2, T>) -> Deque<T>

template back_split source · line 44 · raw

@-T:Data -> @+n:Nat -> @+half:Nat -> @r:Pair(List<&2, T>, List<&2, T>) -> Deque<T>

template move_front source · line 48 · raw

@-T:Data -> @b:List<&2, T> -> @+n:Nat -> @+half:Nat -> Deque<T>

template move_back source · line 51 · raw

@-T:Data -> @f:List<&2, T> -> @+n:Nat -> @+half:Nat -> Deque<T>

template ready_front source · line 54 · raw

@-T:Data -> @d:Deque<T> -> Deque<T>

template ready_back source · line 61 · raw

@-T:Data -> @d:Deque<T> -> Deque<T>

template pop_front_ready source · line 68 · raw

@-T:Data -> @d:Deque<T> -> Pair(Deque<T>, Result<&2, &2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Error, T>)

template pop_back_ready source · line 75 · raw

@-T:Data -> @d:Deque<T> -> Pair(Deque<T>, Result<&2, &2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Error, T>)

template peek_front_ready source · line 82 · raw

@-T:Data -> @d:Deque<T> -> Pair(Deque<T>, Result<&2, &2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Error, T>)

template peek_back_ready source · line 89 · raw

@-T:Data -> @d:Deque<T> -> Pair(Deque<T>, Result<&2, &2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Error, T>)

template pop_front source · line 96 · raw

@-T:Data -> @d:Deque<T> -> Pair(Deque<T>, Result<&2, &2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Error, T>)

template pop_back source · line 99 · raw

@-T:Data -> @d:Deque<T> -> Pair(Deque<T>, Result<&2, &2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Error, T>)

template peek_front source · line 102 · raw

@-T:Data -> @d:Deque<T> -> Pair(Deque<T>, Result<&2, &2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Error, T>)

template peek_back source · line 105 · raw

@-T:Data -> @d:Deque<T> -> Pair(Deque<T>, Result<&2, &2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Error, T>)

template to_list source · line 108 · raw

@-T:Data -> @d:Deque<T> -> Pair(Deque<T>, List<&2, T>)

template obs_nat source · line 114 · raw

@-T:Data -> @r:Pair(Deque<T>, Nat) -> Pair(Deque<T>, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>)

template obs_item source · line 118 · raw

@-T:Data -> @r:Pair(Deque<T>, Result<&2, &2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Error, T>) -> Pair(Deque<T>, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>)

template obs_list source · line 122 · raw

@-T:Data -> @r:Pair(Deque<T>, List<&2, T>) -> Pair(Deque<T>, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>)

template step source · line 126 · raw

@-T:Data -> @d:Deque<T> -> @op:0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Op<T> -> Pair(Deque<T>, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>)

template record source · line 145 · raw

@-T:Data -> @acc:List<&2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>> -> @r:Pair(Deque<T>, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>) -> Pair(Deque<T>, List<&2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>>)

template step_acc source · line 149 · raw

@-T:Data -> @op:0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Op<T> -> @st:Pair(Deque<T>, List<&2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>>) -> Pair(Deque<T>, List<&2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>>)

template run_acc source · line 154 · raw

@-T:Data -> @ops:List<&2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Op<T>> -> @st:Pair(Deque<T>, List<&2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>>) -> Pair(Deque<T>, List<&2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>>)

Runs ops left to right; observations are accumulated newest-first.

template finish source · line 161 · raw

@-T:Data -> @st:Pair(Deque<T>, List<&2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>>) -> Pair(Deque<T>, List<&2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>>)

template run source · line 166 · raw

@-T:Data -> @ops:List<&2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Op<T>> -> @d:Deque<T> -> Pair(Deque<T>, List<&2, 0xe4067e0d858024083f36a7abe7281e89/src/containers/types/deque.Obs<T>>)

Final state and the observation of every operation, in order.