Tern

deque

The deque module is a double-ended queue: push and pop at either end in O(1). Use it as a queue (breadth-first search), a sliding window, or a bounded history.

import deque

fn main():
    d = deque.new[str]()
    d.push_back("b")
    d.push_back("c")
    d.push_front("a")
    print(d.len(), d.front(), d.back(), d.at(1), d.to_array())
    print(d.pop_front(), d.pop_back(), d.to_array())
    w = deque.of([1, 2, 3])
    for i in 4..8:
        w.push_back(i)
        if w.len() > 3:
            w.pop_front()
    print(w.to_array())
Output
3 Some("a") Some("c") b ["a", "b", "c"]
Some("a") Some("c") ["b"]
[5, 6, 7]

Functions

fn new[T]() Deque[T]                         empty
fn of[T](xs: [T]) Deque[T]                   xs, front to back
fn push_back[T](d: mut Deque[T], x: T)       fn push_front[T](d: mut Deque[T], x: T)
fn pop_back[T](d: mut Deque[T]) Option[T]    fn pop_front[T](d: mut Deque[T]) Option[T]
fn front[T](d: Deque[T]) Option[T]           fn back[T](d: Deque[T]) Option[T]
fn at[T](d: Deque[T], i: int) T              0 is the front; out of range is a runtime error
fn put[T](d: mut Deque[T], i: int, x: T)
fn len[T](d: Deque[T]) int                   fn is_empty[T](d: Deque[T]) bool
fn to_array[T](d: Deque[T]) [T]              front to back
fn clear[T](d: mut Deque[T])

How it works, and speed

A ring buffer whose size is a power of two. Growing doubles it by appending a copy of itself (Tern has no empty slots), which also puts the values that had wrapped around to the front right after the old end: nothing moves, and the array grows in place when it can. A popped slot keeps its old value until it's written again; clear() lets go of everything. bench/std keeps a window of 1000 over 20 million values with a push at the front every 16th: Tern 59.3 ms, Rust's VecDeque 54.7 ms, Go (gammazero/deque; Go's standard library has none) 92 ms. The difference with Rust is the copy-on-write check on every write.