IntrusiveDeque

Intrusive doubly linked deque over external items. The deque does not own the items.

`IntrusiveDeque`

(Item -- deque) Constructs an empty intrusive doubly linked deque for external items.

The Item schema must provide prev and next fields of schema [Item] Mref.
Returns a new empty container object; Item supplies the item schema and the supplied object is not inserted.
The deque stores references to items and does not own or destroy them.

Fields

SCHEMA_NAME: static Text naming the generated schema as IntrusiveDeque<ItemSchemaName>.
Item: static NIL reference supplying the item-reference schema.
first: reference to the first item, or NIL when empty; ordinary reads are immutable, while mutable access through a mutable container returns a mutable item reference.
last: reference to the last item, or NIL when empty; ordinary reads are immutable, while mutable access through a mutable container returns a mutable item reference.

Lifetime

INIT clears the endpoint references and does not touch item links. DIE does nothing; destroying the container does not destroy items or rewrite their links.

Ownership and link updates

Insertion and cut require mutable access to a live, non-NIL Item object.
Provide prev and next as [Item] Mref links. The links must refer to the same Item schema and yield mutable references through mutable item access.
Keep linked items and items an iterator may still visit alive at the same storage address. Duplicate insertion can create a cycle; reuse in another chain can corrupt the old chain. There is no membership check.
A deque uses both prev and next; sharing either link set with another deque or stack prevents independent mutation. The container is movable but not copyable; moving transfers endpoint references and leaves the source empty without relocating items.
Removal repairs retained links but does not clear the removed item's own links. An existing iterator keeps its position and follows current item links; clearing the container does not reset it.

Caller requirements

Use an in-place Item object or mutable Item reference as the schema representative. An immutable representative changes generated item-reference schemas and is not interchangeable with this form.
Predicate has stack effect (item -- cond), receives a mutable Item reference, and must not change intrusive links, membership, move items, or end their lifetimes.
cutFirst, cutLast, popFirst, and popLast require a nonempty deque; checked violations report deque is empty. Removal does not destroy the caller-owned item. popFirst and popLast return a mutable Item reference, not a copy.
Nonempty and link-validity requirements are preconditions. Assertion checking reports violations; the removal checks run at run time and are disabled by -ndebug.
Known violations of these assertions are rejected at compile time even with DEBUG disabled.

Known issue: removal from a valid container of named local items can fail at compile time with invalid linked list state, even with -ndebug. Affected methods: cut, cutAllIf, cutFirst, cutIf, cutLast, cutLastIf, popFirst, and popLast; apply @d dynamic drop immediately before each removal.

`empty?`

(-- cond) Reports whether the deque has no first item.

Returns TRUE when first is NIL and FALSE otherwise.

`append`

(item --) Links item at the back of the deque.

item.next is NIL and item.prev is the former last. The former last links forward to item; an initially empty deque also has first refer to item.

`appendAll`

(other --) Moves every item from other to the back of this deque.

other is a mutable reference to a distinct deque with the same Item reference schema; the chains must not share items. An empty other deque changes nothing. A nonempty other deque is appended without copying or moving items, then other is emptied.
After the move, other.first and other.last are NIL; items are not copied or destroyed.

`clear`

(--) Forgets the deque's first and last endpoints.

It does not rewrite any item's prev or next fields and does not destroy items.

`cut`

(item --) Unlinks one item from its current deque position.

Neighbor links and first/last are updated according to the item's prev and next links.
Inconsistent links fail with invalid linked list state. The removed item's own links are not cleared.

`cutAllIf`

(predicate -- count) Removes every item for which predicate returns TRUE and returns the removal count.

The predicate returns Cond. The method returns an Int32 removal count: it calls the predicate once per item from front to back, the retained items preserve order, and an empty deque returns 0 without calling it.

`cutFirst`

(--) Removes the first item from a nonempty deque.

`cutIf`

(predicate -- count) Removes the first item accepted by predicate and returns 0 or 1.

The predicate returns Cond. The method returns an Int32 removal count: it stops after the first TRUE result and returns 1, or returns 0 if none matches; an empty deque does not call it.

`cutLast`

(--) Removes the last item from a nonempty deque.

`cutLastIf`

(predicate -- count) Removes the first item accepted by predicate when scanning from the back and returns 0 or 1.

The predicate returns Cond. The method returns an Int32 removal count: it stops after the first TRUE result and returns 1, or returns 0 if none matches; an empty deque does not call it.

`iter`

(-- iter) Returns a forward iterator over the linked items.

next has stack effect (-- item cond). On success, item is a reference to the caller's object, not a copy. Advance the iterator through a mutable view; an immutable container view returns immutable references. Exhaustion returns a NIL item reference and FALSE; do not dereference that result.
The iterator does not own the items; callers must not destroy them while iterating.
An iterator created through a mutable container view permits mutable item access when advanced through a mutable iterator view.

item.prev is NIL and item.next is the former first. The former first links back to item; an initially empty deque also has last refer to item.

`reverse`

(--) Reverses the deque's links and swaps first and last.

An empty deque is unchanged. Items remain external; their prev and next links are exchanged in place.

`reverseIter`

(-- iter) Returns a reverse iterator over the linked items.

next has stack effect (-- item cond). On success, item is a reference to the caller's object, not a copy. Exhaustion returns a NIL item reference and FALSE; do not dereference that result.

`validate`

(--) Checks the forward links and final last item in debug builds.

It is guarded by DEBUG; in a non-debug build it has no effect.
An inconsistent link fails with invalid linked list state.

Append, prepend, reverse, and popFirst

"IntrusiveDeque" use
"Mref"           use
"String"         use
"control"        use

Node: [{
  value: Int32;
  prev: [Node] Mref;
  next: [Node] Mref;
}];

{} Int32 {} [
  d: Node IntrusiveDeque;
  n0: Node;
  n1: Node;
  n2: Node;
  10 @n0.!value
  20 @n1.!value
  30 @n2.!value
  @n1 @d.append
  @n2 @d.append
  @n0 @d.prepend
  ("first=" @d.@first.value new LF
    "last=" @d.@last.value new LF) printList
  @d.reverse
  ("first2=" @d.@first.value new LF
    "last2=" @d.@last.value new LF
    "popFirst=" @d.popFirst.value new LF
    "first3=" @d.@first.value new LF) printList
  0
] "main" exportFunction

Expected Output

first=10
last=30
first2=30
last2=10
popFirst=30
first3=20

appendAll and source clearing

"IntrusiveDeque" use
"Mref"           use
"String"         use
"control"        use

Node: [{
  value: Int32;
  prev: [Node] Mref;
  next: [Node] Mref;
}];

{} Int32 {} [
  d0: Node IntrusiveDeque;
  d1: Node IntrusiveDeque;
  n0: Node;
  n1: Node;
  n2: Node;
  n3: Node;
  10 @n0.!value
  20 @n1.!value
  30 @n2.!value
  40 @n3.!value
  @n0 @d0.append
  @n1 @d0.append
  @n2 @d1.append
  @n3 @d1.append
  @d1 @d0.appendAll
  it: @d0.iter;
  item0: ok0: @it.next;;
  item1: ok1: @it.next;;
  item2: ok2: @it.next;;
  item3: ok3: @it.next;;
  item4: ok4: @it.next;;
  ("empty1=" @d1.empty? LF
    "first=" @d0.@first.value new LF
    "last=" @d0.@last.value new LF
    "v0=" item0.value new LF
    "v1=" item1.value new LF
    "v2=" item2.value new LF
    "v3=" item3.value new LF
    "done=" ok4 LF) printList
  0
] "main" exportFunction

Expected Output

empty1=TRUE
first=10
last=40
v0=10
v1=20
v2=30
v3=40
done=FALSE

Iterator next result schemas

The forward and reverse iterators both return one item and one success condition from next.

Empty iterator results

"IntrusiveDeque" use
"Mref"           use
"control"        use

Node: [{
  value: Int32;
  prev: [Node] Mref;
  next: [Node] Mref;
}];

{} () {} [
  d: Node IntrusiveDeque;
  @d.iter.next printStack swap drop drop
  @d.reverseIter.next printStack swap drop drop
] "main" exportFunction

Expected Output During Compilation

{
  value: Int32;
  prev: Mref;
  next: Mref;
} NIL
FALSE
{
  value: Int32;
  prev: Mref;
  next: Mref;
} NIL
FALSE

Runtime example: forward and reverse iteration

"IntrusiveDeque" use
"Mref"           use
"String"         use
"control"        use

Node: [{
  value: Int32;
  prev: [Node] Mref;
  next: [Node] Mref;
}];

{} Int32 {} [
  d: Node IntrusiveDeque;
  n0: Node;
  n1: Node;
  n2: Node;
  10 @n0.!value
  20 @n1.!value
  30 @n2.!value
  @n0 @d.append
  @n1 @d.append
  @n2 @d.prepend
  forward: @d.iter;
  f0: ok0: @forward.next;;
  f1: ok1: @forward.next;;
  f2: ok2: @forward.next;;
  reverse: @d.reverseIter;
  r0: rok0: @reverse.next;;
  r1: rok1: @reverse.next;;
  r2: rok2: @reverse.next;;
  ("f0=" f0.value new LF
    "f1=" f1.value new LF
    "f2=" f2.value new LF
    "r0=" r0.value new LF
    "r1=" r1.value new LF
    "r2=" r2.value new LF) printList
  0
] "main" exportFunction

Expected Output

f0=30
f1=10
f2=20
r0=20
r1=10
r2=30

IntrusiveDeque

`IntrusiveDeque`

Fields

Lifetime

Ownership and link updates

Caller requirements

`empty?`

`append`

`appendAll`

`clear`

`cut`

`cutAllIf`

`cutFirst`

`cutIf`

`cutLast`

`cutLastIf`

`iter`

`popFirst`

`popLast`

`prepend`

`reverse`

`reverseIter`

`validate`

Append, prepend, reverse, and popFirst

Expected Output

appendAll and source clearing

Expected Output

Iterator next result schemas

Empty iterator results

Expected Output During Compilation

Runtime example: forward and reverse iteration

Expected Output

See also