Double-ended queue implemented with two backing arrays.

Deque

Construct with an element schema in front of the module name, for example Int32 Deque.

Deque

(Item -- deque) Creates an empty deque using the schema of Item.
  • The element schema must be a non-Meta In-place schema supported by Array and permit default initialization for insertion. For an existing prototype, supply a mutable view; an immutable prototype makes insertion fail. Direct Text and Code elements are unsupported; wrap them in an In-place Struct when needed.
  • The container owns its backing arrays. Copying copies the backing arrays' items when their schema is copyable. Moving transfers the arrays and leaves the source empty. Destruction destroys remaining items and releases the allocations.

Fields

Public methods

References returned by front, back, at, and iter are mutable through a mutable deque view and immutable through an immutable view.

iter

(-- iter) Returns a forward iterator over items in logical deque order.
  • next returns item valid, with an item reference and TRUE on success and a NIL element reference with FALSE at exhaustion. This iterator has no size method.
  • The iterator borrows the deque; keep it alive and keep its membership/order unchanged during traversal. Rebalancing can move surviving items in both arrays, so a pop may invalidate references to items other than the removed one.
  • It is not a snapshot, and an append can make a previously exhausted iterator produce more items.

size

(-- count) Returns the number of stored items.

pushBack

(item --) Appends one item at the logical back.
  • Adds an item, or items from a source accepted by Array.append, at the logical back. A matching element schema is inserted as one item; bulk items retain source traversal order.
  • An immutable item view is copied; a mutable item view is moved. The item schema must support the selected transfer.
  • If insertion can grow the backing allocation referenced by the input, copy or move the item to a separate object before insertion. See the Array.append known-issue note.

pushFront

(item --) Prepends one item at the logical front.
  • Adds an item, or items from a source accepted by Array.append, at the logical front. A matching element schema is inserted as one item; bulk items appear in reverse source traversal order.
  • If insertion can grow the backing allocation referenced by the input, copy or move the item to a separate object before insertion. See the Array.append known-issue note.

popBack

(--) Removes the logical last item.
  • If the back-side array is empty, moves the first half of the front-side array, rounded up, into it in reverse order before removing the last logical item.
  • Destroys the removed item and returns no item.

popFront

(--) Removes the logical first item.
  • If the front-side array is empty, moves the first half of the back-side items, rounded up, into it in reverse order before removing the first logical item.
  • Destroys the removed item and returns no item.

back

(-- ref) Returns a reference to the logical last item.
  • Backing-array growth or rebalancing can invalidate the reference.

front

(-- ref) Returns a reference to the logical first item.

at

(ordinal -- ref) Returns a reference to the item at a zero-based logical ordinal.
  • Ordinals are Int32 values. Item access requires 0 <= ordinal < size; out-of-range access reports Index is out of range! when checked.

clear

(--) Removes all items while retaining backing-array allocations.
  • Destroys all items and leaves size zero while retaining backing-array allocations.

release

(--) Releases both backing arrays.
  • Destroys all items, releases both allocations, and leaves an empty deque that can be reused.

swapBuffers

(from to --) Moves the first half of from, rounded up, to empty to in reverse order, then compacts the remainder of from.
  • Supply distinct mutable backing arrays of the same item schema. to must be empty; when checked, the diagnostic is Destination must be empty!.
  • The transferred count is (from.size + 1) / 2 with integer division. Items remaining in from retain their order.
  • Both arrays' item references can be invalidated. This is the low-level operation used to rebalance a deque.

Order and returned references

Invalid operations

Examples

Runtime example: front, back, and ordinal access

"Deque"   use
"String"  use
"control" use

{} Int32 {} [
  d: Int32 Deque;
  10 @d.pushBack
  20 @d.pushFront
  30 @d.pushBack
  ("front=" @d.front new LF
    "back=" @d.back new LF
    "at1=" 1 @d.at new LF) printList
  @d.popFront
  ("size=" d.size LF
    "front2=" @d.front new LF) printList
  0
] "main" exportFunction

Expected Output

front=20
back=30
at1=10
size=2
front2=10

Runtime example: iteration order

"Deque"   use
"String"  use
"control" use

{} Int32 {} [
  d: Int32 Deque;
  10 @d.pushBack
  20 @d.pushFront
  30 @d.pushBack
  it: @d.iter;
  item0: ok0: @it.next;;
  item1: ok1: @it.next;;
  item2: ok2: @it.next;;
  item3: ok3: @it.next;;
  ("ok0=" ok0 LF
    "v0=" item0 new LF
    "ok1=" ok1 LF
    "v1=" item1 new LF
    "ok2=" ok2 LF
    "v2=" item2 new LF
    "ok3=" ok3 LF) printList
  0
] "main" exportFunction

Expected Output

ok0=TRUE
v0=20
ok1=TRUE
v1=10
ok2=TRUE
v2=30
ok3=FALSE

See also