Download

The latest release is December 2012. The header file reducible_queue.h is the whole library. The source file reducible_queue.cc is a test program. Both are MIT-licensed.

Synopsis

reduq provides a C++ template class reduq::reducible_queue<Reducer> with the following operations. All of them run in worst-case constant time assuming that Reducer and the memory allocator are well-behaved.

• reducible_queue(): constructs a reducible_queue
• bool empty(): returns true if and only if there are no elements in the queue
• size_t size(): returns the number of elements in the queue
• const Reducer::Type& front(): returns a const reference to the element in the queue least recently inserted
• const Reducer::Type& back(): returns a const reference to the element in the queue most recently inserted
• void push(const Reducer::Type& x): inserts x into the queue
• void pop(): removes from the queue the element least recently inserted
• Reducer::Type reduce(): returns the “product” by Reducer::reduce of the elements in the queue from least to most recently inserted

The template parameter Reducer must have three members.

• Type: the element type
• Type reduce(const Type& x, const Type& y): returns the “product” of x and y; must be associative
• Type id(): returns a right identity for reduce

reduq defines the following reducer templates, whose element types are all T.

• reduq::BitwiseAnd<T>
• reduq::BitwiseOr<T>
• reduq::BitwiseXor<T>
• reduq::IntegerMax<T>
• reduq::IntegerMin<T>
• reduq::Product<T>
• reduq::RealMax<T>
• reduq::RealMin<T>
• reduq::Sum<T>

Algorithm

Although the implementation uses linked lists, I describe the algorithm using two infinite arrays. At a high level, it interleaves continual back-to-front suffix scans with pushes and pops.

## public ##

f = empty():
    f = begin >= end

push(x):
    A[end] = x
    end = end + 1
    current_batch = reduce(current_batch, x)
    step()

# precondition: not empty()
x = pop():
    x = A[begin]
    begin = begin + 1
    step()

y = reduce():
    if empty():
        y = id
    else if begin >= j:
        y = reduce(B[begin], current_batch)
    else:
        y = reduce(B[begin], previous_batch, current_batch)

## private ##

step():
    if j <= begin:
        j = end - 1
        B[j] = A[j]
        {previous_k = current_k}
        previous_batch = current_batch
        {current_k = end}
        current_batch = id
    else:
        j = j - 1
        B[j] = reduce(A[j], B[j + 1])

begin = 0
end = 0
j = -1
A = [...]
B = [...]
{previous_k = 0}
{current_k = 0}
previous_batch = id
current_batch = id

Statements necessary only for the analysis are surrounded by {braces}. It is clear that empty and push and pop are correct and that all operations run in constant time. The following invariant implies the correctness of reduce.

 (0) 0 <= begin <= end
 (1) previous_k <= current_k <= end
 (2) for all i in {begin, ..., min(previous_k, j) - 1},
         B[i] == reduce(A[i ... previous_k - 1])
 (3) for all i in {    j, ...,      current_k     - 1},
         B[i] == reduce(A[i ...  current_k - 1])
 (4) previous_batch == reduce(A[previous_k ... current_k - 1])
 (5)  current_batch == reduce(A[ current_k ...       end - 1])
 (6) (j - begin) + (end -  current_k) <   current_k - begin
 (7)                  j - previous_k  <= previous_k - begin
 (8) min(begin, end - 1) <= j

The intuition for clauses (6-7) is that there are two intervals, previous_k ... j - 1 and current_k ... end - 1, that begin must not reach if reduce() is to be correct. Clause (7) ensures that begin does not reach the first, and clause (6) ensures that begin does not reach the second. Accordingly, reduce is correct.

Now we establish the invariant. empty and reduce have no side effects and thus maintain the invariant. push, just prior to calling step, ensures clauses (0-5); (6'), a weakening of (6); (7); (8'), a weakening of (8) given (0); and a new clause, (9).

(6') (j - begin) + (end - 1 - current_k) < current_k - begin
(8') begin - 1 <= j
 (9) 0 <= end - 1

In turn, step ensures (0-8) by starting the next scan or subtracting one from j.

pop, just prior to calling step, ensures clauses (0-6); (7'), a weakening of (7); (8'); and (9).

(7') j - previous_k <= previous_k - (begin - 1)

In turn, step again ensures (0-8).

Comments

A classic data structures interview question asks for a queue with an efficient find-min operation. One commonly proposed solution achieves amortized time bounds via two stacks. reduq achieves worst-case time bounds without resorting to the complexity of purely functional data structures.

© 2012–2013 David Eisenstat