Editing Double-ended queue (section)

==== Real-time deques via lazy rebuilding and scheduling ====
A double-ended queue is represented as a sextuple <code>(len_front, front, tail_front, len_rear, rear, tail_rear)</code> where <code>front</code> is a [[linked list]] which contains the front of the queue of length <code>len_front</code>. Similarly, <code>rear</code> is a linked list which represents the reverse of the rear of the queue, of length <code>len_rear</code>. Furthermore, it is assured that <code>|front| ≤ 2|rear|+1</code> and <code>|rear| ≤ 2|front|+1</code> - intuitively, it means that both the front and the rear contains between a third minus one and two thirds plus one of the elements. Finally, <code>tail_front</code> and <code>tail_rear</code> are tails of <code>front</code> and of <code>rear</code>, they allow scheduling the moment where some lazy operations are forced. Note that, when a double-ended queue contains <code>n</code> elements in the front list and <code>n</code> elements in the rear list, then the inequality invariant remains satisfied after <code>i</code> insertions and <code>d</code> deletions when <code>(i+d) &leq; n/2</code>. That is, at most <code>n/2</code> operations can happen between each rebalancing.

Let us first give an implementation of the various operations that affect the front of the deque - cons, head and tail. Those implementations do not necessarily respect the invariant. In a second time we'll explain how to modify a deque which does not satisfy the invariant into one which satisfies it. However, they use the invariant, in that if the front is empty then the rear has at most one element. The operations affecting the rear of the list are defined similarly by symmetry. 

<syntaxhighlight lang="sml">
empty = (0, NIL, NIL, 0, NIL, NIL)
fun insert'(x, (len_front, front, tail_front, len_rear, rear, tail_rear)) =
  (len_front+1, CONS(x, front), drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun head((_, CONS(h, _), _, _, _, _)) = h
fun head((_, NIL, _, _, CONS(h, NIL), _)) = h
fun tail'((len_front, CONS(head_front, front), tail_front, len_rear, rear, tail_rear)) =
  (len_front - 1, front, drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty  
</syntaxhighlight>

It remains to explain how to define a method <code>balance</code> that rebalance the deque if <code>insert'</code> or <code>tail</code> broke the invariant. The method <code>insert</code> and <code>tail</code> can be defined by first applying <code>insert'</code> and <code>tail'</code> and then applying <code>balance</code>.

<syntaxhighlight lang="sml">
fun balance(q as (len_front, front, tail_front, len_rear, rear, tail_rear)) =
  let floor_half_len = (len_front + len_rear) / 2 in
  let ceil_half_len = len_front + len_rear - floor_half_len in
  if len_front > 2*len_rear+1 then
    let val front' = take(ceil_half_len, front)
        val rear' = rotateDrop(rear, floor_half_len, front)
    in (ceil_half_len, front', front', floor_half_len, rear', rear')
  else if len_front > 2*len_rear+1 then
    let val rear' = take(floor_half_len, rear)
        val front' = rotateDrop(front, ceil_half_len, rear)
    in (ceil_half_len, front', front', floor_half_len, rear', rear')
  else q
</syntaxhighlight>
where <code>rotateDrop(front, i, rear))</code> return the concatenation of <code>front</code> and of <code>drop(i, rear)</code>. That is<code>front' = rotateDrop(front, ceil_half_len, rear)</code> put into <code>front'</code> the content of <code>front</code> and the  content of <code>rear</code> that is not already in <code>rear'</code>. Since dropping <code>n</code> elements takes <math>O(n)</math> time, we use laziness to ensure that elements are dropped two by two, with two drops being done during each <code>tail'</code> and each <code>insert'</code> operation. 

<syntaxhighlight lang="sml">
fun rotateDrop(front, i, rear) =
  if i < 2 then rotateRev(front, drop(i, rear), NIL)
  else let CONS(x, front') = front in
    CONS(x, rotateDrop(front', j-2, drop(2, rear)))
</syntaxhighlight>
where <code>rotateRev(front, middle, rear)</code> is a function that returns the front, followed by the middle reversed, followed by the rear. This function is also defined using laziness to ensure that it can be computed step by step, with one step executed during each <code>insert'</code> and <code>tail'</code> and taking a constant time. This function uses the invariant that <code>|rear|-2|front|</code> is 2 or 3. 

<syntaxhighlight lang="sml">
fun rotateRev(NIL, rear, a) =
  reverse(rear)++a
fun rotateRev(CONS(x, front), rear, a) =
  CONS(x, rotateRev(front, drop(2, rear), reverse(take(2, rear))++a))
</syntaxhighlight>
where <code>++</code> is the function concatenating two lists.