IntrusiveDeque

Fields

• Item: stored item schema.
• first: first item or NIL when empty.
• last: last item or NIL when empty.

Requirements

• Each item schema must provide prev and next of schema [Item] Mref.

Ownership and link updates

• The deque stores external items and never destroys them.
• append, prepend, cut, cutFirst, cutLast, reverse, and appendAll update the participating prev and next fields.
• appendAll moves all items from the source deque to the back of the target deque and clears the source endpoints.
• clear forgets the deque endpoints without rewriting stored item links.

Methods

• INIT (--): clears the deque.
• DIE (--): no-op destructor.
• empty? (-- valid): reports whether the deque is empty.
• append (item --): appends one item at the back.
• appendAll (other --): moves all items from another deque to the back and clears the source deque.
• clear (--): forgets the current first and last items.
• cut (item --): removes one item currently linked in the deque.
• cutAllIf (predicate -- count): removes all items for which predicate reports TRUE.
• cutFirst (--): removes the first item.
• cutIf (predicate -- count): removes the first matching item.
• cutLast (--): removes the last item.
• cutLastIf (predicate -- count): removes the last matching item.
• iter (-- iter): returns forward iteration from first to last.
• popFirst (-- item): returns the first item and removes it.
• popLast (-- item): returns the last item and removes it.
• prepend (item --): prepends one item at the front.
• reverse (--): reverses the linked order in place.
• reverseIter (-- iter): returns reverse iteration from last to first.
• validate (--): debug-only structure check.

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=" @[email protected] new LF
   "last=" @[email protected] new LF) printList
  @d.reverse
  ("first2=" @[email protected] new LF
   "last2=" @[email protected] new LF
   "popFirst=" @d.popFirst.value new LF
   "first3=" @[email protected] 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=" @[email protected] new LF
   "last=" @[email protected] 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

Traversal and validity rules

• iter traverses items from first to last.
• reverseIter traverses items from last to first.
• cutIf scans from the front.
• cutLastIf scans from the back.
• cut requires one item that is currently linked in that deque.
• popFirst, popLast, cutFirst, and cutLast require one non-empty deque.

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

See also

• IntrusiveQueue: Intrusive singly linked queue over external items.
• IntrusiveStack: Intrusive singly linked LIFO stack over external items.
• Mref: Minimal Ref type with custom semantics.
• Deque: Double-ended queue data structure.