#Deque
A double-ended queue backed by a growable ring buffer. Supports O(1) amortized push/pop at both ends and O(1) random access, similar to C++ std::deque and Rust VecDeque.
#Layout
Following the Rust VecDeque design, only head and len are stored; the
back position is computed as (head + len - 1) % cap. When the logical
sequence reaches the end of the buffer it simply wraps around, so neither
push_front nor push_back ever shifts elements:
flowchart LR
subgraph buf["buf, cap = 8 — logical order 1·2·3·4·5, head = 5, len = 5"]
direction LR
c0["0: 4"] --- c1["1: 5 ⟵ back"] --- c2["2: ·"] --- c3["3: ·"] --- c4["4: ·"] --- c5["5: 1 ⟵ head"] --- c6["6: 2"] --- c7["7: 3"]
end
c7 -. wraps to index 0 .-> c0Growing allocates a larger buffer and re-linearizes the elements; iteration
and indexing translate logical positions through head the same way.
#Usage
#Create
Create an empty deque with Deque([]), or construct one from an array or iterator.
///|
test {
let dv : @deque.Deque[Int] = Deque([])
@test.assert_eq(dv.is_empty(), true)
let dv2 = @deque.from_array([1, 2, 3, 4, 5])
@test.assert_eq(dv2.length(), 5)
let dv3 = @deque.from_iter(1, 2, 3)
@test.assert_eq(dv3.length(), 3)
}Pre-allocate capacity to avoid resizing:
///|
test {
let dv : @deque.Deque[Int] = Deque([], capacity=1024)
@test.assert_eq(dv.capacity(), 1024)
}#Length & Capacity
///|
test {
let dv = @deque.from_array([1, 2, 3])
@test.assert_eq(dv.length(), 3)
@test.assert_eq(dv.is_empty(), false)
// reserve additional capacity
dv.reserve_capacity(100)
inspect(dv.capacity() >= 100, content="true")
// shrink to fit actual contents
dv.shrink_to_fit()
@test.assert_eq(dv.capacity(), 3)
}#Access
Use index syntax dv[i] or at() for direct access. Use get() for a safe lookup. front() and back() return the first and last element.
///|
test {
let dv = @deque.from_array([10, 20, 30, 40, 50])
@test.assert_eq(dv[0], 10)
@test.assert_eq(dv[4], 50)
@test.assert_eq(dv.get(2), Some(30))
@test.assert_eq(dv.get(99), None)
@test.assert_eq(dv.front(), Some(10))
@test.assert_eq(dv.back(), Some(50))
}#Push & Pop
Push and pop at both ends in O(1) amortized time:
///|
test {
let dv = @deque.from_array([2, 3])
dv.push_front(1)
dv.push_back(4)
debug_inspect(
dv,
content=(
#|<Deque: [1, 2, 3, 4]>
),
)
@test.assert_eq(dv.pop_front(), Some(1))
@test.assert_eq(dv.pop_back(), Some(4))
debug_inspect(
dv,
content=(
#|<Deque: [2, 3]>
),
)
}unsafe_pop_front() and unsafe_pop_back() discard the return value and panic on an empty deque.
#Set
Mutate elements by index:
///|
test {
let dv = @deque.from_array([1, 2, 3])
dv[1] = 20
@test.assert_eq(dv[1], 20)
}#Insert & Remove
Insert or remove elements at arbitrary positions (O(n)):
///|
test {
let dv = @deque.from_array([1, 2, 4])
dv.insert(2, 3) // insert 3 at index 2
debug_inspect(
dv,
content=(
#|<Deque: [1, 2, 3, 4]>
),
)
let removed = dv.remove(0)
@test.assert_eq(removed, 1)
debug_inspect(
dv,
content=(
#|<Deque: [2, 3, 4]>
),
)
}#Concatenation & Append
Use + or append() to combine deques. append mutates the receiver in place.
///|
test {
let a = @deque.from_array([1, 2])
let b = @deque.from_array([3, 4])
debug_inspect(
a + b,
content=(
#|<Deque: [1, 2, 3, 4]>
),
)
a.append(b)
debug_inspect(
a,
content=(
#|<Deque: [1, 2, 3, 4]>
),
)
}#Search
Linear search with contains() and search(). Binary search on sorted deques with binary_search() and binary_search_by().
///|
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
@test.assert_eq(dv.contains(3), true)
@test.assert_eq(dv.search(3), Some(2))
// binary_search returns Ok(index) if found, Err(insertion_point) if not
@test.assert_eq(dv.binary_search(3), Ok(2))
@test.assert_eq(dv.binary_search(6), Err(5))
// binary_search_by takes a comparison function
@test.assert_eq(dv.binary_search_by(fn(x) { x.compare(3) }), Ok(2))
}#Iteration
Forward and reverse iteration via each, eachi, iter, and their rev_* counterparts:
///|
test {
let dv = @deque.from_array([1, 2, 3])
// each / eachi
let buf = []
dv.each(fn(x) { buf.push(x) })
@test.assert_eq(buf, [1, 2, 3])
let pairs = []
dv.eachi(fn(i, x) { pairs.push((i, x)) })
@test.assert_eq(pairs, [(0, 1), (1, 2), (2, 3)])
// reverse iteration
let rev = []
dv.rev_each(fn(x) { rev.push(x) })
@test.assert_eq(rev, [3, 2, 1])
// iterators
debug_inspect(dv.iter().to_array(), content="[1, 2, 3]")
debug_inspect(dv.rev_iter().to_array(), content="[3, 2, 1]")
}#Map & Filter
map() and mapi() produce a new deque. filter() keeps elements matching a predicate. retain() filters in place. retain_map() filters and transforms in place.
///|
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
debug_inspect(
dv.map(fn(x) { x * 2 }),
content=(
#|<Deque: [2, 4, 6, 8, 10]>
),
)
debug_inspect(
dv.mapi(fn(i, x) { i + x }),
content=(
#|<Deque: [1, 3, 5, 7, 9]>
),
)
debug_inspect(
dv.filter(fn(x) { x % 2 == 0 }),
content=(
#|<Deque: [2, 4]>
),
)
// retain modifies in place
let dv2 = @deque.from_array([1, 2, 3, 4, 5])
dv2.retain(fn(x) { x > 3 })
debug_inspect(
dv2,
content=(
#|<Deque: [4, 5]>
),
)
// retain_map: keep Some values, drop None
let dv3 = @deque.from_array([1, 2, 3, 4])
dv3.retain_map(fn(x) { if x % 2 == 0 { Some(x * 10) } else { None } })
debug_inspect(
dv3,
content=(
#|<Deque: [20, 40]>
),
)
}#Extract & Drain
extract_if() removes and returns elements matching a predicate. drain() removes a range of elements.
///|
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
let extracted = dv.extract_if(fn(x) { x % 2 == 0 })
debug_inspect(
extracted,
content=(
#|<Deque: [2, 4]>
),
)
debug_inspect(
dv,
content=(
#|<Deque: [1, 3, 5]>
),
)
let dv2 = @deque.from_array([1, 2, 3, 4, 5])
let drained = dv2.drain(start=1, len=2)
debug_inspect(
drained,
content=(
#|<Deque: [2, 3]>
),
)
debug_inspect(
dv2,
content=(
#|<Deque: [1, 4, 5]>
),
)
}#Chunks
chunks(n) splits the deque into groups of n elements. chunk_by(f) groups consecutive elements where f(a, b) returns true.
///|
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
let cs = dv.chunks(2)
debug_inspect(
cs,
content=(
#|<Deque: [<Deque: [1, 2]>, <Deque: [3, 4]>, <Deque: [5]>]>
),
)
// chunk_by groups consecutive elements that satisfy a predicate
let dv2 = @deque.from_array([1, 1, 2, 2, 3])
let grouped = dv2.chunk_by(fn(a, b) { a == b })
debug_inspect(
grouped,
content=(
#|<Deque: [<Deque: [1, 1]>, <Deque: [2, 2]>, <Deque: [3]>]>
),
)
}#Reverse & Shuffle
///|
test {
let dv = @deque.from_array([1, 2, 3])
// rev returns a new reversed deque
debug_inspect(
dv.rev(),
content=(
#|<Deque: [3, 2, 1]>
),
)
// rev_in_place reverses in place
dv.rev_in_place()
debug_inspect(
dv,
content=(
#|<Deque: [3, 2, 1]>
),
)
}shuffle() returns a new shuffled deque; shuffle_in_place() mutates in place. Both take a rand function that returns a random int in [0, n).
///|
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
let shuffled = dv.shuffle(rand=fn(_n) { 0 }) // deterministic for test
@test.assert_eq(shuffled.length(), 5)
}#Truncate & Clear
truncate(n) keeps only the first n elements. clear() removes all elements but retains allocated memory.
///|
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
dv.truncate(3)
debug_inspect(
dv,
content=(
#|<Deque: [1, 2, 3]>
),
)
dv.clear()
@test.assert_eq(dv.is_empty(), true)
}#Copy & Blit
copy() creates a shallow clone. blit_to() copies a range of elements from one deque to another.
///|
test {
let src = @deque.from_array([1, 2, 3, 4, 5])
let dst = @deque.from_array([0, 0, 0, 0, 0])
src.blit_to(dst, len=3, src_offset=1, dst_offset=2)
debug_inspect(
dst,
content=(
#|<Deque: [0, 0, 2, 3, 4]>
),
)
}#Flatten & Join
flatten() merges a deque of deques into a single deque. join() concatenates a deque of strings with a separator.
///|
test {
let nested : @deque.Deque[@deque.Deque[Int]] = @deque.from_array([
@deque.from_array([1, 2]),
@deque.from_array([3, 4]),
])
debug_inspect(
nested.flatten(),
content=(
#|<Deque: [1, 2, 3, 4]>
),
)
let words = @deque.from_array(["hello", "world"])
inspect(words.join(", "), content="hello, world")
}#Views
as_views() exposes the underlying ring buffer as two contiguous ArrayView slices.
///|
test {
let dv = @deque.from_array([1, 2, 3])
let (v1, v2) = dv.as_views()
// for a non-wrapped deque, all elements are in the first view
@test.assert_eq(v1.length() + v2.length(), 3)
}#Conversion
///|
test {
let dv = @deque.from_array([1, 2, 3])
@test.assert_eq(dv.to_array(), [1, 2, 3])
}#Comparison & Equality
Deques support == (element-wise equality) and compare() (shortlex order).
///|
test {
let a = @deque.from_array([1, 2, 3])
let b = @deque.from_array([1, 2, 3])
@test.assert_eq(a == b, true)
@test.assert_eq(a.compare(@deque.from_array([1, 2, 4])) < 0, true)
}Deque
type Deque[A]A double-ended queue (deque) backed by a growable circular buffer.
This implementation follows the Rust VecDeque design: only head and len
are stored, with tail computed on demand as (head + len - 1) % cap.
Layout:
Wrapped case (head + len > cap):
buf: [4, 5, _, _, _, 1, 2, 3]
^ ^
(tail) head
head = 5, len = 5, tail = (5 + 5 - 1) % 8 = 1
Logical order: [1, 2, 3, 4, 5]
Contiguous case (head + len <= cap):
buf: [_, 1, 2, 3, 4, 5, _, _]
^ ^
head (tail)
head = 1, len = 5, tail = (1 + 5 - 1) % 8 = 5
Logical order: [1, 2, 3, 4, 5]
Empty case (len == 0):
buf: [_, _, _, _]
^
head (tail is undefined, not accessed)Invariants:
- 0 <= len <= buf.length()
- 0 <= head < buf.length()
- Element at index i is at buf[(head + i) % buf.length()]
- When len > 0: front is buf[head], back is buf[(head + len - 1) % cap]
- When len == 0: no valid element, head can be any valid index
Concatenates two deques into a new deque. The resulting deque contains all
elements from the first deque followed by all elements from the second deque.
Parameters:
- self : The first deque to concatenate.
- other : The second deque to concatenate.
Returns a new deque containing all elements from both deques in order.
Example:
test {
let dq1 = @deque.from_array([1, 2, 3])
let dq2 = @deque.from_array([4, 5, 6])
debug_inspect((dq1 + dq2).to_array(), content="[1, 2, 3, 4, 5, 6]")
let mut dq3 = dq2.copy()
dq3 @deque.from_array([7])
@debug.debug_inspect(dq3.to_array(), content="[4, 5, 6, 7]")
}Compares two deques based on shortlex order.
First compares the lengths of the deques. If they differ, returns -1 if the
first deque is shorter, 1 if it's longer. If the lengths are equal, compares
elements pairwise until a difference is found or all elements have been
compared.
Parameters:
- self : The first deque to compare.
- other : The second deque to compare.
Returns an integer that indicates the relative order:
- A negative value if self is less than other
- Zero if self equals other
- A positive value if self is greater than other
Example:
test {
let dq1 = @deque.from_array([1, 2, 3])
let dq2 = @deque.from_array([1, 2, 4])
let dq3 = @deque.from_array([1, 2])
inspect(dq1.compare(dq2), content="-1") // dq1 < dq2
inspect(dq2.compare(dq1), content="1") // dq2 > dq1
inspect(dq1.compare(dq3), content="1") // dq1 > dq3 (longer)
inspect(dq1.compare(dq1), content="0") // dq1 = dq1
}Compares two deques for equality. Returns true if both deques contain the
same elements in the same order.
Parameters:
- self : The first deque to compare.
- other : The second deque to compare with.
Returns true if both deques are equal, false otherwise.
Example:
test {
let dq1 = @deque.from_array([1, 2, 3])
let dq2 = @deque.from_array([1, 2, 3])
let dq3 = @deque.from_array([3, 2, 1])
inspect(dq1 == dq2, content="true")
inspect(dq1 == dq3, content="false")
}Implements the Hash trait for Deque, allowing deques to be used in
hash-based data structures such as hash tables and sets.
The hash value of a deque is computed by sequentially combining the hashes
of all its elements, in order. This ensures that two deques with the same
elements in the same order will always produce the same hash value.
Parameters:
- self : The deque to be hashed.
- hasher : The hasher used to accumulate the hash value.
Example:
test {
let dq1 = @deque.from_array([1, 2, 3])
let dq2 = @deque.from_array([1, 2, 3])
let dq3 = @deque.from_array([1, 2, 3, 4])
@test.assert_eq(Hash::hash(dq1), Hash::hash(dq2)) // same elements → same hash
@test.assert_not_eq(Hash::hash(dq1), Hash::hash(dq3)) // different elements → different hash
}Note:
- The order of elements matters. Deques with the same elements but in different orders will produce different hash values.
Converts a deque to its JSON representation as an array.
Parameters:
- self : The deque to be converted to JSON.
Returns a JSON array containing all elements from the deque converted to
their JSON representations.
Example:
test {
let dq = @deque.from_array([1, 2, 3])
let json = @json.to_json(dq)
@debug.debug_inspect(json, content="Array([Number(1), Number(2), Number(3)])")
}Implements JSON deserialization for deque, converting a JSON array into a
deque containing elements of type A.
Parameters:
- json : The JSON value to be converted to a deque.
- path : The JSON path used for error reporting during deserialization.
Returns a new deque containing all elements from the JSON array converted to
type A.
Throws an error of type @json.JsonDecodeError if the JSON value is not an
array or if any element in the array cannot be converted to type A.
Example:
test {
let json = @json.parse("[1, 2, 3]")
let dq : @deque.Deque[Int] = @json.from_json(json)
@debug.debug_inspect(
dq,
content=(
#|<Deque: [1, 2, 3]>
),
)
}Deque::Deque
Creates a new deque with elements copied from an array.
The optional capacity is treated as a minimum initial capacity.
Parameters:
- array : The array to initialize the deque with. All elements from the array will be copied into the new deque in the same order.
Returns a new deque containing all elements from the input array.
Example:
test {
let arr : ReadOnlyArray[Int] = [1, 2, 3, 4, 5]
let dq = @deque.Deque(arr)
@debug.debug_inspect(
dq,
content=(
#|<Deque: [1, 2, 3, 4, 5]>
),
)
}Deque::append
Appends all elements from one deque to the end of another deque. The elements
are added in-place, modifying the original deque.
Parameters:
- self : The deque to append to.
- other : The deque whose elements will be appended.
Example:
test {
let v1 = @deque.from_array([1, 2, 3])
let v2 = @deque.from_array([4, 5, 6])
v1.append(v2)
debug_inspect(
v1,
content=(
#|<Deque: [1, 2, 3, 4, 5, 6]>
),
)
let v1 = @deque.from_array([1, 2, 3])
let v2 = @deque.from_array([])
v1.append(v2)
@debug.debug_inspect(
v1,
content=(
#|<Deque: [1, 2, 3]>
),
)
}Deque::as_views
Returns two array views that together represent all elements in the deque in
their correct order. The first view contains elements from the head to the
end of the internal buffer, and the second view contains any remaining
elements from the start of the buffer.
If the deque is empty, returns a pair of empty views. If all elements are
contiguous in memory, the second view will be empty.
Parameters:
- self : The deque to be viewed.
Returns a tuple of two array views that together contain all elements of the
deque in order.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 4, 5])
let (v1, v2) = dq.as_views()
inspect(v1.length(), content="5")
inspect(v2.length(), content="0")
}Deque::at
Retrieves the element at the specified index from the deque.
If you try to access an index which isn't in the Deque, it will panic.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
inspect(dv[2], content="3")
}Deque::back
Return the back element from a deque, or None if it is empty.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
@test.assert_eq(dv.back(), Some(5))
}Deque::binary_search
Performs a binary search on a sorted deque for the given value.
Returns the position of the value if found, or the position where
the value could be inserted while maintaining the sorted order.
Parameters:
- value : The value to search for in the deque
Returns a Result containing either:
- Ok(index) if the value is found at position index
- Err(index) if the value is not found, where index is the position where the value could be inserted
Example:
test {
let dq = @deque.from_array([1, 3, 5, 7, 9])
let result = dq.binary_search(5)
@debug.debug_inspect(result, content="Ok(2)")
}Notes:
- Assumes the deque is sorted in ascending order
- For multiple matches, returns the leftmost matching position
- Returns an insertion point that maintains the sort order when no match is found
Deque::binary_search_by
Performs a binary search on a sorted deque using a custom comparison function.
Returns the position of the matching element if found, or the position where
the element could be inserted while maintaining the sorted order.
Parameters:
- cmp : A function that compares each element with the target value, returning:
- A negative integer if the element is less than the target
- Zero if the element equals the target
- A positive integer if the element is greater than the target
Returns a Result containing either:
- Ok(index) if a matching element is found at position index
- Err(index) if no match is found, where index is the position where the element could be inserted
Example:
test {
let dq = @deque.from_array([1, 3, 5, 7, 9])
let find_3 = dq.binary_search_by(x => x.compare(3))
debug_inspect(find_3, content="Ok(1)")
let find_4 = dq.binary_search_by(x => x.compare(4))
@debug.debug_inspect(find_4, content="Err(2)")
}Notes:
- Assumes the deque is sorted according to the ordering implied by the comparison function
- For multiple matches, returns the leftmost matching position
- Returns an insertion point that maintains the sort order when no match is found
- Handles the deque's ring buffer structure internally
- For empty deques, returns Err(0)
Deque::blit_to
Copies elements from one deque to another deque, with support for growing the
destination deque if needed. The copy respects the circular buffer layout
and correctly handles wrap-around in both source and destination.
Parameters:
- self : The deque to copy elements from.
- dst : The deque to copy elements to. Will be automatically grown if needed to accommodate the copied elements.
- len : The number of elements to copy.
- src_offset : Starting index in the source deque (relative to its front). Defaults to 0.
- dst_offset : Starting index in the destination deque (relative to its front). Defaults to 0.
Example:
test {
let d1 = @deque.from_array([1, 2, 3, 4, 5])
let d2 = @deque.from_array([0, 0])
d1.blit_to(d2, len=3, dst_offset=1)
@debug.debug_inspect(d2.to_array(), content="[0, 1, 2, 3]")
}Panics if:
- len is negative
- src_offset is negative
- dst_offset is negative
- dst_offset exceeds the length of the destination deque
- src_offset + len exceeds the length of the source deque
Deque::capacity
Returns the total number of elements the deque can hold in its internal
buffer before requiring reallocation.
Parameters:
- deque : The deque whose capacity is being queried.
Returns the current capacity of the deque's internal buffer.
Example:
test {
let dq = @deque.Deque([], capacity=10)
dq.push_back(1)
dq.push_back(2)
inspect(dq.capacity(), content="10")
}Deque::chunk_by
Groups consecutive elements of the deque into chunks where adjacent elements
satisfy the given predicate function.
Parameters:
- self : The source deque to be chunked.
- pred : A function that takes two adjacent elements and returns true if they should be in the same chunk, false otherwise.
Returns a Deque of Deques, where each inner Deque is a chunk of
consecutive elements that satisfy the predicate with their adjacent elements.
Notes:
- The relative order of elements is preserved.
- The number of chunks is at least 1 if the deque is non-empty.
- Returns an empty deque if the input is empty.
Example:
test {
let d = @deque.from_array([1, 1, 2, 3, 2, 3, 2, 3, 4])
let chunks = d.chunk_by((x, y) => x <= y)
@debug.debug_inspect(
chunks.to_array().map(c => c.to_array()),
content="[[1, 1, 2, 3], [2, 3], [2, 3, 4]]",
)
let empty : @deque.Deque[Int] = @deque.from_array([])
@debug.debug_inspect(
empty.chunk_by((x, y) => x <= y).to_array(),
content="[]",
)
}Deque::chunks
Divides a deque into smaller deques (chunks) of the specified size.
Parameters:
- self : The deque to be divided into chunks.
- size : The size of each chunk. Must be a positive integer, otherwise it will panic.
Returns a deque of deques, where each inner deque is a chunk containing
elements from the original deque. If the length of the original deque is not
divisible by the chunk size, the last chunk will contain fewer elements.
Example:
test {
let d = @deque.from_array([1, 2, 3, 4, 5])
let chunks = d.chunks(2)
@debug.debug_inspect(
chunks.to_array().map(c => c.to_array()),
content="[[1, 2], [3, 4], [5]]",
)
let d : @deque.Deque[Int] = @deque.from_array([])
inspect(d.chunks(3).length(), content="0")
}Panics if:
- size is not positive
Deque::clear
Clears the deque, removing all values.
This method has no effect on the allocated capacity of the deque, only
setting the length to 0.
Emptying a deque is a removal like any other: the buffer keeps referring to
the elements that were in it, and they are released once later pushes reuse
those slots, the buffer grows, or the deque is dropped. Call
Deque::release_unused to overwrite them at once, or Deque::shrink_to_fit
to hand the buffer back entirely.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
dv.clear()
inspect(dv.length(), content="0")
}Deque::contains
Tests whether a deque contains a specific element.
Parameters:
- self : The deque to search in.
- value : The element to search for.
Returns true if the deque contains the specified element, false
otherwise.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 4, 5])
inspect(dq.contains(3), content="true")
inspect(dq.contains(6), content="false")
}Deque::copy
Creates a new deque with the same elements as the original deque. The new
deque will have a capacity equal to its length, and its elements will be
stored contiguously starting from index 0.
Parameters:
- self : The deque to be copied.
Returns a new deque containing all elements from the original deque in the
same order.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 4, 5])
let copied = dq.copy()
@debug.debug_inspect(
copied,
content=(
#|<Deque: [1, 2, 3, 4, 5]>
),
)
}Deque::drain
Removes and returns elements in the specified range [start, start + len) from the deque.
Parameters:
- self : The target deque (modified in-place).
- start : Start index of the range (inclusive). Must be >= 0 and <= self.length().
- len : Length of the range to drain. If not provided, drains from start to end. If provided, must be >= 0 and start + len must be <= self.length().
Returns a new deque containing the drained elements. The original deque retains
elements outside [start, start + len) in their original order.
Panics if:
- start < 0
- start > self.length()
- len < 0 (when provided)
- start + len > self.length() (when len is provided)
Example:
test {
let deque = @deque.from_array([1, 2, 3, 4, 5, 6, 7, 8, 9])
let deque_test = deque.drain(start=2, len=4)
debug_inspect(
deque_test,
content=(
#|<Deque: [3, 4, 5, 6]>
),
)
@debug.debug_inspect(
deque,
content=(
#|<Deque: [1, 2, 7, 8, 9]>
),
)
}The slots the drain vacates are not cleared: each keeps whatever it held
before the survivors were shifted, so a drained element or a duplicate
reference to a survivor stays reachable there until the slot is reused, the
buffer grows, or the deque is dropped. Call Deque::release_unused to
overwrite them at once, or Deque::shrink_to_fit to move the survivors
into an exact-size buffer.
Deque::each
Iterates over the elements of the deque.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
let mut sum = 0
dv.each(x => sum x)
inspect(sum, content="15")
}Deque::eachi
Iterates over the elements of the deque with index.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
let mut idx_sum = 0
dv.eachi((i, _x) => idx_sum i)
inspect(idx_sum, content="10")
}Deque::extract_if
Extracts elements from a deque that satisfy a given predicate function. The
extracted elements are removed from the original deque and returned as a new
deque. The relative order of the extracted elements is preserved.
Parameters:
- self : The deque to extract elements from.
- f : A function that takes an element and returns true if the element should be extracted, false otherwise.
Returns a new deque containing all elements that satisfy the predicate
function, in the order they appeared in the original deque.
Example:
test {
let d = @deque.from_array([1, 2, 3, 4, 5])
let extracted = d.extract_if(x => x % 2 == 0)
debug_inspect(extracted.to_array(), content="[2, 4]")
@debug.debug_inspect(d.to_array(), content="[1, 3, 5]")
}Deque::filter
Creates a new deque containing all elements from the input deque that satisfy
the given predicate function.
Parameters:
- self : The deque to filter.
- f : A function that takes an element and returns a boolean indicating whether the element should be included in the result.
Returns a new deque containing only the elements for which the predicate
function returns true. The relative order of the elements is preserved.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 4, 5])
let evens = dq.filter(x => x % 2 == 0)
@debug.debug_inspect(
evens,
content=(
#|<Deque: [2, 4]>
),
)
}Deque::flatten
Flattens a high-dimensional deque into a lower-dimensional deque
by concatenating all inner deques in order.
Parameters:
- self : The high-dimensional deque to flatten.
Returns a new lower-dimensional deque containing all elements
from inner deques in sequence.
Note:
- Allocates a new buffer of the combined length and copies every inner deque into it; none of the input deques are modified.
- Efficiently preserves element order across all inner deques.
Example:
test {
let deque = @deque.from_array([
@deque.from_array([1, 2, 3]),
@deque.from_array([4, 5, 6]),
@deque.from_array([7, 8]),
])
let deque_test = deque.flatten()
@debug.debug_inspect(
deque_test,
content=(
#|<Deque: [1, 2, 3, 4, 5, 6, 7, 8]>
),
)
}Deque::from_iter
Creates a new deque containing the elements from the given iterator.
Parameters:
- iter : An iterator containing the elements to be added to the deque.
Returns a new deque containing all elements from the iterator in the same
order.
Example:
test {
let arr = [1, 2, 3, 4, 5]
let dq = @deque.from_iter(arr.iter())
@debug.debug_inspect(
dq,
content=(
#|<Deque: [1, 2, 3, 4, 5]>
),
)
}Deque::front
Return the front element from a deque, or None if it is empty.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
@test.assert_eq(dv.front(), Some(1))
}Deque::get
Safe element access with bounds checking
Deque::insert
Inserts an element at the specified position in the deque. The elements are
shifted in-place to make room for the new element, modifying the original deque.
Parameters:
- self : The deque in which the element will be inserted.
- index : The position at which to insert the element. Must satisfy 0 <= index <= self.length().
- value : The element to insert.
Panics:
- If index is out of bounds, the function will abort with an error message.
Example:
test {
let v1 = @deque.from_array([1, 2, 3])
v1.insert(0, 0) // insert at the front
debug_inspect(
v1,
content=(
#|<Deque: [0, 1, 2, 3]>
),
)
let v2 = @deque.from_array([1, 2, 4])
v2.insert(2, 3) // insert in the middle
debug_inspect(
v2,
content=(
#|<Deque: [1, 2, 3, 4]>
),
)
let v3 = @deque.from_array([2, 3, 4])
v3.insert(3, 5) // insert at the end
@debug.debug_inspect(
v3,
content=(
#|<Deque: [2, 3, 4, 5]>
),
)
}Deque::is_empty
Test if the deque is empty.
Example
test {
let dv = @deque.Deque([])
inspect(dv.is_empty(), content="true")
dv.push_back(1)
inspect(dv.is_empty(), content="false")
}Deque::iter
Creates an iterator over the elements of the deque, allowing sequential
access to its elements in order from front to back.
Parameters:
- deque : The deque to iterate over.
Returns an iterator that yields each element in the deque in order.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 4, 5])
let mut sum = 0
dq.iter().each(x => sum x)
inspect(sum, content="15")
}Deque::iter2
Returns an iterator that yields pairs of indices and elements from the deque
in order, starting from the front.
Parameters:
- self : The deque to iterate over.
Returns an iterator of type Iter2[Int, A] that produces tuples of (index,element), where index starts from 0 and increments by 1 for each element,
and element is the corresponding element from the deque.
Example:
test {
let dq = @deque.from_array([10, 20, 30])
let mut sum = 0
let it = dq.iter2()
while it.next() is Some((i, x)) {
sum i * x
}
inspect(sum, content="80") // 0*10 + 1*20 + 2*30 = 80
}Deque::join
Joins the elements of a string deque into a single string,
separated by the specified separator.
Parameters:
- self : The deque of strings to join.
- separator : The separator to insert between elements (as a string view).
Returns the concatenated string.
- If the deque is empty, returns an empty string.
- Efficiently pre-allocates memory based on calculated size hint.
- Handles empty separators efficiently by direct concatenation.
Example:
test {
let deque = @deque.from_array(["a", "b", "c"])
let s1 = deque.join("")
inspect(s1, content="abc")
let s2 = deque.join(",")
inspect(s2, content="a,b,c")
}Deque::length
Returns the number of elements in the deque.
Parameters:
- deque : The deque to get the length of.
Returns the current number of elements in the deque.
Example:
test {
let dq = @deque.from_array([1, 2, 3])
inspect(dq.length(), content="3")
dq.push_back(4)
inspect(dq.length(), content="4")
}Deque::map
Maps a function over the elements of the deque.
Example
test {
let dv = @deque.from_array([3, 4, 5])
let dv2 = dv.map(x => x + 1)
@test.assert_eq(dv2, @deque.from_array([4, 5, 6]))
}Deque::mapi
Maps a function over the elements of the deque with index.
Example
test {
let dv = @deque.from_array([3, 4, 5])
let dv2 = dv.mapi((i, x) => x + i) // @deque.from_array([3, 5, 7])
@test.assert_eq(dv2, @deque.from_array([3, 5, 7]))
}Deque::new
Creates a new empty deque with an optional initial capacity.
Deprecated: use Deque([], capacity=...) instead.
Deque::pop_back
Removes a back element from a deque and returns it, or None if it is empty.
The vacated slot goes on referring to the removed element, so an
ArrayView obtained from Deque::as_views beforehand keeps observing it,
and it is released only once a later push reuses the slot, the buffer
grows, or the buffer is dropped. Call Deque::release_unused to release it at
once.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
@test.assert_eq(dv.pop_back(), Some(5))
}Deque::pop_front
Removes a front element from a deque and returns it, or None if it is empty.
The vacated slot goes on referring to the removed element, so an
ArrayView obtained from Deque::as_views beforehand keeps observing it,
and it is released only once a later push reuses the slot, the buffer
grows, or the buffer is dropped. Call Deque::release_unused to release it at
once.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
@test.assert_eq(dv.pop_front(), Some(1))
}Deque::push_back
Adds an element to the back of the deque.
If the deque is at capacity, it will be reallocated.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
dv.push_back(6)
@test.assert_eq(dv.back(), Some(6))
}Deque::push_front
Adds an element to the front of the deque.
If the deque is at capacity, it will be reallocated.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
dv.push_front(0)
@test.assert_eq(dv.front(), Some(0))
}Deque::release_unused
Overwrites the deque's unused capacity -- every slot not currently holding
an element -- with placeholder, releasing whatever those slots held.
Shrinking a deque never clears the slots it vacates, so whatever they held
-- a removed element, or a duplicate reference to a survivor that was
shifted over it -- stays reachable from the buffer and unreleased until
later pushes reuse those slots, the buffer grows, or the deque is dropped.
This releases them on demand without reallocating, which is what
Deque::pop_front, Deque::pop_back, Deque::remove, Deque::retain
and the other operations that take no placeholder leave outstanding.
Deque::shrink_to_fit releases them too, but by allocating an exact-size
buffer and copying every survivor into it; this costs one pass over the
unused region and no allocation.
This only matters for element types holding references -- for types such as
Int there is nothing to release and the call merely costs a pass over the
buffer.
Example
test {
let dq = @deque.from_array(["a", "b", "c"])
let _ = dq.pop_back()
dq.release_unused(placeholder="")
@debug.debug_inspect(
dq,
content=(
#|<Deque: ["a", "b"]>
),
)
}Deque::remove
Removes and returns the element at the specified position in the deque. The
remaining elements are shifted in-place to fill the gap, modifying the original deque.
Parameters:
- self : The deque from which the element will be removed.
- index : The position of the element to remove. Must satisfy 0 <= index < self.length().
Returns:
- The element that was removed from the deque.
Panics:
- If index is out of bounds, the function will abort with an error message.
Example:
test {
let v1 = @deque.from_array([0, 1, 2, 3])
let x = v1.remove(0) // remove from the front
debug_inspect(
(x, v1),
content=(
#|(0, <Deque: [1, 2, 3]>)
),
)
let v2 = @deque.from_array([1, 2, 3, 4])
let y = v2.remove(2) // remove from the middle
debug_inspect(
(y, v2),
content=(
#|(3, <Deque: [1, 2, 4]>)
),
)
let v3 = @deque.from_array([2, 3, 4, 5])
let z = v3.remove(3) // remove from the end
@debug.debug_inspect(
(z, v3),
content=(
#|(5, <Deque: [2, 3, 4]>)
),
)
}Deque::reserve_capacity
Reserves capacity to ensure that it can hold at least the number of elements
specified by the capacity argument.
Example
test {
let dv = @deque.from_array([1])
dv.reserve_capacity(10)
inspect(dv.capacity(), content="10")
}Deque::retain
Filters elements in-place by retaining only the elements that satisfy the
given predicate. Modifies the deque to keep only the elements for which the
predicate function returns true.
Parameters:
- self : The deque to be filtered.
- f : A function that takes an element and returns true if the element should be kept, false if it should be removed.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 4, 5])
dq.retain(x => x % 2 == 0)
@debug.debug_inspect(
dq,
content=(
#|<Deque: [2, 4]>
),
)
}Deque::retain_map
Filters and maps elements in-place using a provided function. Modifies the
deque to retain only elements for which the provided function returns Some,
and updates those elements with the values inside the Some variant.
Parameters:
- self : The deque to be filtered and mapped.
- f : A function that takes an element and returns either Some with a new value to replace the element, or None to remove the element.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 4, 5])
dq.retain_map(x => if x % 2 == 0 { Some(x * 2) } else { None })
@debug.debug_inspect(
dq,
content=(
#|<Deque: [4, 8]>
),
)
}Deque::rev
Creates a new deque with elements in reversed order.
Parameters:
- self : The deque to be reversed.
Returns a new deque containing the same elements as the input deque but in
reverse order. The original deque remains unchanged.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 4, 5])
debug_inspect(
dq.rev(),
content=(
#|<Deque: [5, 4, 3, 2, 1]>
),
)
@debug.debug_inspect(
dq,
content=(
#|<Deque: [1, 2, 3, 4, 5]>
),
) // original deque unchanged
}Deque::rev_each
Iterates over the elements of the deque in reversed turn.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
let mut sum = 0
dv.rev_each(x => sum x)
inspect(sum, content="15")
}Deque::rev_eachi
Iterates over the elements of the deque in reversed turn with index.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
let mut idx_sum = 0
dv.rev_eachi((i, _x) => idx_sum i)
inspect(idx_sum, content="10")
}Deque::rev_in_place
Reverses the order of elements in the deque in place, modifying the original
deque.
Parameters:
- self : The deque to be reversed.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 4, 5])
dq.rev_in_place()
debug_inspect(
dq,
content=(
#|<Deque: [5, 4, 3, 2, 1]>
),
)
let dq : @deque.Deque[Int] = Deque([])
dq.rev_in_place()
@debug.debug_inspect(
dq,
content=(
#|<Deque: []>
),
)
}Deque::rev_iter
Creates an iterator that yields elements in reverse order.
Parameters:
- self : The deque to iterate over.
Returns an iterator that yields elements from the deque in reverse order,
starting from the last element.
Example:
test {
let dq = @deque.from_array([1, 2, 3])
let mut sum = 0
dq.rev_iter().each(x => sum = sum * 10 + x)
inspect(sum, content="321")
}Deque::rev_iter2
Creates an iterator that yields index-value pairs of elements in the deque in
reverse order.
Parameters:
- self : The deque to iterate over.
Returns an iterator that yields tuples of (index, value) pairs, where the
index starts from 0 and increments by 1, while values are taken from the
deque in reverse order.
Example:
test {
let dq = @deque.from_array([1, 2, 3])
let mut s = ""
let it = dq.rev_iter2()
while it.next() is Some((i, x)) {
s "\{i}:\{x} "
}
inspect(s, content="0:3 1:2 2:1 ")
}Deque::search
Searches for a value in the deque and returns its position.
Parameters:
- self : The deque to search in.
- value : The value to search for.
Returns the index of the first occurrence of the value in the deque, or
None if the value is not found.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 2, 1])
@debug.debug_inspect(dq.search(2), content="Some(1)")
@debug.debug_inspect(dq.search(4), content="None")
}Deque::set
Sets the value of the element at the specified index.
If you try to access an index which isn't in the Deque, it will panic.
Example
test {
let dv = @deque.from_array([1, 2, 3, 4, 5])
dv[2] = 1
inspect(dv[2], content="1")
}Deque::shrink_to_fit
Shrinks the capacity of the deque as much as possible.
Example
test {
let dv = @deque.Deque([], capacity=10)
dv.push_back(1)
dv.push_back(2)
dv.push_back(3)
inspect(dv.capacity(), content="10")
dv.shrink_to_fit()
inspect(dv.capacity(), content="3")
}The survivors are copied into the new buffer and the old one is released
with them, so this also releases whatever earlier removals left in the
unused capacity. It pays an allocation plus a copy of every survivor to do
so; Deque::release_unused releases the same elements in one pass over the
unused region and no allocation, at the cost of leaving the capacity alone.
Deque::shuffle
Shuffle the deque using Knuth shuffle (Fisher-Yates algorithm)
Returns a new shuffled deque without modifying the original deque.
To use this function, you need to provide a rand function, which takes an integer as its upper bound
and returns an integer.
rand n is expected to return a uniformly distributed integer between 0 and n - 1
Deque::shuffle_in_place
Shuffle the deque in place using Knuth shuffle (Fisher-Yates algorithm)
To use this function, you need to provide a rand function, which takes an integer as its upper bound
and returns an integer.
rand n is expected to return a uniformly distributed integer between 0 and n - 1
Note
This function handles the circular buffer nature of the deque internally.
Deque::to_array
Converts the deque to a new array containing all elements in the same order.
Parameters:
- self : The deque to be converted to an array.
Returns a new array containing all elements from the deque. If the deque is
empty, returns an empty array.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 4, 5])
let arr = dq.to_array()
@debug.debug_inspect(arr, content="[1, 2, 3, 4, 5]")
}Deque::truncate
Shortens the deque in-place, keeping the first len elements and dropping
the rest.
If len is greater than or equal to the deque's current length or negative,
this has no effect
Parameters:
- self : The deque to be truncated.
- len : The new length of the deque.
Example:
test {
let dq = @deque.from_array([1, 2, 3, 4, 5])
dq.truncate(3)
@debug.debug_inspect(
dq,
content=(
#|<Deque: [1, 2, 3]>
),
)
}Elements beyond len are removed from the deque, but the backing buffer
keeps referring to them: they are released once those slots are reused,
once the buffer grows, or once the deque is dropped. Call
Deque::release_unused to overwrite them at once, or Deque::shrink_to_fit
to move the survivors into an exact-size buffer.
Install
Installed by default
corestandard library
Apache-2.0
Updated 13 days ago