Simple Confluently Persistent Catenable Lists.
We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends.  Updates to a persistent data structure are nondestructive---each operation produces a new list incorporating the change, while keeping intact the list or lists to which it applies. Although general techniques exist for making data structures persistent, these techniques fail for structures that are subject to operations, such as catenation, that combine two or more versions.  In this paper we develop a simple implementation of persistent double-ended queues (deques) with catenation that supports all deque operations in constant amortized time. Our implementation is functional if we allow memoization.
Introduction
. Over the last fteen years, there has been considerable development
of persistent data structures, those in which not only the current version,
but also older ones, are available for access (partial persistence) or updating (full per-
sistence). In particular, Driscoll, Sarnak, Sleator, and Tarjan [5] developed e-cient
general methods to make pointer-based data structures partially or fully persistent,
and Dietz [3] developed an e-cient general method to make array-based structures
fully persistent.
These general methods support updates that apply to a single version of a structure
at a time, but they do not accommodate operations that combine two dierent
versions of a structure, such as set union or list catenation. Driscoll, Sleator, and
Tarjan [4] coined the term con
uently persistent for fully persistent structures that
support such combining operations. An alternative way to obtain persistence is to
use purely functional programming. We take here an extremely strict view of pure
functionality: we disallow lazy evaluation, memoization, and other such techniques.
For list-based data structure design, purely functional programming amounts to using
only the LISP functions cons, car, cdr. Purely functional data structures are
automatically persistent, and indeed con
uently persistent.
A simple but important problem in data structure design that makes the issue of
con
uent persistence concrete is that of implementing persistent double-ended queues
(deques) with catenation. A series of papers [2, 4] culminated in the work of Kaplan
and Tarjan [11, 10], who developed a con
uently persistent implementation of deques
with catenation that has a worst-case constant time and space bound for any deque
operation, including catenation. The Kaplan-Tarjan data structure and its precursors
obtain con
uent persistence by being purely functional.
Department of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel.
haimk@math.tau.ac.il.
y Department of Computer Science, Columbia University, New York, NY 10027. Research at
Carnegie Mellon University supported by the Advanced Research Projects Agency CSTO under the
title \The Fox Project: Advanced Languages for Systems Software", ARPA Order No. C533, issued
by ESC/ENS under Contract No. F19628-95-C-0050. cokasaki@cs.columbia.edu.
z Department of Computer Science, Princeton University, Princeton, NJ 08544 and InterTrust
Technologies Corporation, Sunnyvale, CA 94086. Research at Princeton University partially supported
by NSF Grant No. CCR-9626862. ret@cs.princeton.edu.
If all one cares about is persistence, purely functional programming is unnecessarily
restrictive. In particular, Okasaki [14, 15, 16] observed that the use of lazy evaluation
in combination with memoization can lead to e-cient functional (but not purely
functional in our sense) data structures that are con
uently persistent. In order to
analyze such structures, Okasaki developed a novel kind of debit-based amortization.
Using these techniques and weakening the time bound from worst-case to amortized,
he was able to considerably simplify the Kaplan-Tarjan data structure, in particular
to eliminate its complicated skeleton that encodes a tree extension of a redundant
digital numbering system.
In this paper we explore the problem of further simplifying the Kaplan-Tarjan
result. We obtain a con
uently persistent implementation of deques with catenation
that has a constant amortized time bound per operation. Our structure is
substantially simpler than the original Kaplan-Tarjan structure, and even simpler
than Okasaki's catenable deques: whereas Okasaki requires e-cient persistent deques
without catenation as building blocks, our structure is entirely self-contained. Furthermore
our analysis uses a standard credit-based approach. We give two alternative,
but closely related implementations of our method. The rst uses memoization. The
second, which saves a small constant factor in time and space, uses an extension of
memoization in which any expression can replace an equivalent expression.
The remainder of the paper consists of ve sections. In Section 2, we introduce
terminology and concepts. In Section 3, we illustrate our approach by developing
a persistent implementation of deques without catenation. In Section 4, we extend
our approach to handle stacks with catenation. In Section 5, we develop our solution
for deques with catenation. We conclude in Section 6 with some remarks and open
problems. An extended abstract of this work appeared in [9].
2. Preliminaries. The objects of our study are lists. As in [11, 10] we allow the
following operations on lists:
return a new list containing the single element x.
return a new list formed by adding element x to the
front of list L.
pop(L): return a pair whose rst component is the rst element
on list L and whose second component is a
list containing the second through last elements of
L.
return a new list formed by adding element x to the
back of list L.
return a pair whose rst component is a list containing
all but the last element of L and whose second
component is the last element of L.
catenate(L; R): return a new list formed by catenating L and R,
with L rst.
We seek implementations of these operations (or specic subsets of them) on
persistent lists: any operation is allowed on any previously constructed list or lists
at any time. For discussions of various forms of persistence see [5]. A stack is a list
on which only push and pop are allowed. A queue is a list on which only inject
and pop are allowed. A steque (stack-ended queue) is a list on which only push,
pop, and inject are allowed. Finally, a deque (double-ended queue) is a list on which
all four operations push, pop, inject, and eject are allowed. For any of these
four structures, we may or may not allow catenation. If catenation is allowed, push
and inject become redundant, since they are special cases of catenation, but it is
sometimes convenient to treat them as separate operations because they are easier to
implement than general catenation.
We say a data structure is purely functional if it can be built and manipulated
using the LISP functions car, cons, cdr. That is, the structure consists of a set
of immutable nodes, each either an atom or a node containing two pointers to other
nodes, with no cycles of pointers. The nodes we use to build our structures actually
contain a xed number of elds; reducing our structures to two elds per node by
adding additional nodes is straightforward. Various nodes in our structure represent
lists.
To obtain our results, we extend pure functionality by allowing memoization,
in which a function is evaluated only once on a node; the second time the same
function is evaluated on the same node, the value is simply retrieved from the previous
computation. In all our constructions, there are only a constant number of memoized
functions (one or two). We can implement memoization by having a node point to
the results of applying each memoized function to it. Initially each such pointer is
undened. The rst function evaluation lls in the appropriate pointer to indicate the
result. Subsequent evaluations merely follow the pointer to the result, which takes
time.
We also consider the use of a more substantial extension of pure functionality,
in which we allow the operation of replacing a node in a structure by another node
representing the same list. Such a replacement can be performed in an imperative
setting by replacing all the elds in the node, for instance in LISP by using replaca
and replacd. Replacement can be viewed as a generalization of memoization. In our
structures, any node is replaced at most twice, which means that all our structures
can be implemented in a write-once memory. (It is easy to convert an algorithm
that overwrites any eld only a xed constant number of times into a write-once
algorithm, with only a constant-factor loss of e-ciency.) The use of overwriting
instead of memoization saves a small constant factor in running time and storage
space and slightly simplies the amortized analysis.
To perform amortized analysis, we use a standard potential-based framework.
We assign to each conguration of the data structure (the totality of nodes currently
existing) a potential. We dene the amortized cost of an operation to be its actual
cost plus the net increase in potential caused by performing the operation. In our
applications, the potential of an empty structure is zero and the potential is always
non-negative. It follows that, for any sequence of operations starting with an empty
structure, the total actual cost of the operations is bounded above by the sum of
their amortized costs. See the survey paper [17] for a more complete discussion of
amortized analysis.
3. Noncatenable Deques. In this section we describe an implementation of
persistent noncatenable deques with a constant amortized time bound per operation.
The structure is based on the analogous Kaplan-Tarjan structure [11, 10] but is much
simpler. The result presented here illustrates our technique for doing amortized analysis
of a persistent data structure. At the end of the section we comment on the
relation between the structure proposed here and previously existing solutions.
3.1. Representation. Here and in subsequent sections we say a data structure
is over a set A if it stores elements from A. Our representation is recursive. It
is built from bounded-size deques called buers, each containing at most three ele-
4 H. KAPLAN, C. OKASAKI, and R. E. TARJEN
ments. Buers are of two kinds: prexes and su-xes. A nonempty deque d over A
is represented by an ordered triple consisting of a prex over A, denoted by pr(d); a
(possibly empty) child deque of ordered pairs over A, denoted by c(d); and a su-x
over A, denoted by sf(d). Each pair consists of two elements from A. The child deque
c(d), if nonempty, is represented in the same way. We dene the set of descendants
of a deque d in the standard way|namely, c 0
exist.
The order of elements in a deque is dened recursively to be the one consistent
with the order of each triple, each buer, each pair, and each child deque. Thus, the
order of elements in a deque d is rst the elements of pr(d), then the elements of each
pair in c(d), and nally the elements of sf(d).
In general the representation of a deque is not unique|the same sequence of
elements may be represented by triples that dier in the sizes of their prexes and
su-xes, as well as in the contents and representations of their descendant deques.
Whenever we refer to a deque d we actually mean a particular representation of d,
one that will be clear from the context.
The pointer representation for this representation is the obvious one: a node
representing a deque d contains pointers to pr(d), c(d), and sf(d). Note that the
pointer structure of d is essentially a linked list of its descendants, since c i (d) contains
a pointer to c i+1 (d), for each i.
3.2. Operations. Implementing the deque operations is straightforward, except
for maintaining the size bounds on buers. Specically, a push on a deque is easy
unless its prex is of size three, a pop on a deque is easy unless its prex is empty,
and symmetric statements hold for inject and eject. We deal with buer over
ow
and under
ow in a proactive fashion, rst xing the buer so that the operation to
be performed cannot violate its size bounds and then actually doing the operation.
The details are as follows.
We dene a buer to be green if it contains one or two elements, and red if it
contains zero or three. We dene two memoized functions on a deque: gp, which
constructs a representation of the same list but with a green prex; and gs, which
constructs a representation of the same list with a green su-x. We only apply gp (gs,
respectively) to a list whose prex (su-x) is red and can be made green. Specically,
for gp, if the prex is empty, the child deque must be nonempty, and symmetrically
for gs. Below we give implementations of push, pop, and gp; the implementations
for inject, eject, and gs are symmetric. We denote a deque with prex p, child
deque c, and su-x s by [p; c; s]. As mentioned in Section 2, we can implement the
memoization of gp and gs by having each node point to the nodes resulting from
applying gp and gs to it; initially, such pointers are undened.
to
If pr(d) is empty and c(d) is not, let
is nonempty, let (x; return the pair (x; [p; c(e); sf(e)]). Otherwise
(c(e) must be empty), let (x; return the pair (x; [;; ;; s]).
y, z be the three elements in pr(d). Let p be a prex
containing only x, and let c
(pr(d) is empty and c(d) is not), let ((x; be a prex
containing x followed by y. Return [p
3.3. Analysis. The amortized analysis of this method relies on the memoization
of gp and gs. We call a node representing a deque secondary if it is returned by a
call to gp or gs and primary otherwise. If a secondary node y is constructed by a call
gp(x) (gs(x), respectively), the only way to access y later is via another call gp(x)
(gs(x), respectively): no secondary node is returned as the result of a push, pop,
inject, or eject operation. This means that gp and gs are called only on primary
nodes.
We devide the nodes representing deques into three states: such a node is rr if
both its buers are red, gr if exactly one of its buers is red, and gg if both its buers
are green. We subdivide the rr and gr states: an rr node is rr0 if neither gp nor gs
has been applied to it, rr1 if exactly one of gp and gs has been applied to it, and
rr2 if both gp and gs have been applied to it; a gr node is gr0 if neither gp nor gs
has been applied to it, and gr1 otherwise. By the discussion above every secondary
node is gr0 or gg. We dene #rr0, #rr1, and #gr0 to be the numbers of primary
nodes in states rr0, rr1, and gr0, respectively. We dene the potential of a collection
of nodes representing deques to be 4#rr0
A call to push is either terminal or results in a call to gp, which in turn calls
push. Similarly, a call to pop is either terminal or results in a call to gp, which in
turn calls pop. We charge the O(1) time spent in a call to gp (exclusive of the inner
call to push or pop) to the push or pop that calls gp. A call to push results in
a sequence of recursive calls to push (via calls to gp), of which the bottommost is
terminal and the rest are nonterminal. A nonterminal push has one of the following
eects: it converts a primary rr0 node to rr1 and creates a new primary gr0 node
(the result of the push) and a new secondary gr0 node (the result of the call to gp);
it converts a primary rr1 node to rr2 and creates a new primary gr0 node and a
new secondary gr0 node; or, it converts a primary gr0 node to gr1 and creates a new
primary gg node and a new secondary gg node. In each case the total potential drops
by one, paying for the time needed for the push (excluding the recursive call). A
terminal push takes O(1) time, creates O(1) new nodes, and increases the potential
by O(1). We conclude that push takes O(1) amortized time. Analogous arguments
apply to pop, inject, and eject, giving us the following theorem:
Theorem 3.1. Each of the operations push, pop, inject, and eject dened
above takes O(1) amortized time.
3.4. Implementation Using Overwriting. With the memoized implementation
described above, a primary rr node can give rise to two secondary gr nodes
representing the same list; a primary gr node can give rise to a secondary gg node
representing the same list. These redundant representations exist simultanously. A
gr representation, however, dominates an rr representation for performing deque op-
erations, and a gg representation dominates a gr representation. This allows us to
improve the e-ciency of the implementation by using overwriting in place of memo-
ization: when gp is called on a node, it overwrites the contents of the node with the
results of the gp computation, and similarly for gs. Then only one representation of
a list exists at any time, and it evolves from rr to gr to gg (via one of two alternative
paths, depending on whether gp or gs is called rst). Each node now needs only
three elds (for prex, child deque, and su-x) instead of ve (two extra for gp and
gs).
Not only does the use of overwriting save a constant factor in running time and
storage space, but it also simplies the amortized analysis, as follows. We dene
#rr and #gr to be the number of nodes in states rr and gr, respectively. (There
are now no secondary nodes.) We dene the potential of a collection of nodes to be
3#rr +#gr. A nonterminal push has one of the following eects: it converts an rr
6 H. KAPLAN, C. OKASAKI, and R. E. TARJEN
node to gr and creates a new gr node, or converts a gr node to gg and creates a
new gg node. In either case it reduces the potential by one, paying for the O(1) time
required by the push (excluding the recursive call). A terminal push takes O(1) time
and can increase the potential by O(1). We conclude that push takes O(1) amortized
time. Similar arguments apply to pop, inject, and eject.
3.5. Related Work. The structure just described is based on the Kaplan-Tarjan
structure of [10, Section 4], but simplies it in three ways. First, the skeleton of our
structure (the sequence of descendants) is a stack; in the Kaplan-Tarjan structure,
this skeleton must be partitioned into a stack of stacks in order to support worst-case
constant-time operations (via a redundant binary counting mechanism). Second, the
recursive changes to the structure to make its nodes green are one-sided, instead of
two-sided: in the original structure, the stack-of-stacks mechanism requires coordination
to keep both sides of the structure in related states. Third, the maximum buer
size is reduced, from ve to three. In the special case of a steque, the maximum size
of the su-x can be further reduced, to two. In the special case of a queue, both the
prex and the su-x can be reduced to maximum size two.
There is an alternative, much older approach that uses incremental recopying
to obtain persistent deques with worst-case constant-time operations. See [7] for a
discussion of this approach. The incremental recopying approach yields an arguably
simpler structure than the one presented here, but our structure generalizes to allow
catenation, which no one knows how to implement e-ciently using incremental
recopying. Also, our structure can be extended to support access, insertion, and deletion
d positions away from the end of a list in O(log d) amortized time, by applying
the ideas in [12].
4. Catenable Steques. In this section we show how to extend our ideas to
support catenation. Specically, we describe a data structure for catenable steques
that achieves an O(1) amortized time bound for push, pop, inject, and catenate.
The data structure is based on the same recursive decomposition of lists as that in
Section 5 of [10]. The pointer structure that we need here is much simpler than that
in [10], and the analysis is amortized, following the framework outlined in Section 2
and used in Section 3.
4.1. Representation. Our structure is similar to the structure of Section 3,
but with slightly dierent denitions of the component parts. As in Section 3, we use
buers of two kinds: prexes and su-xes. Each prex contains two to six elements
and each su-x contains one to three elements. A nonempty steque d over A is
represented either by a su-x sf(d) only, or by an ordered triple consisting of a prex
pr(d) over A, a child steque c(d) of pairs over A, and a su-x sf(d) over A. In contrast
to Section 3, a pair over A is dened to be an ordered pair containing a prex and a
possibly empty steque of pairs over A. Observe that this denition adds an additional
kind of recursion (pairs store steques) to the structure of Section 3. This extra kind
of recursion is what allows e-cient catenation.
The order of elements in a steque is the one consistent with the order of each
triple, each buer, each pair, each steque within a pair, and each child steque. As in
Section 3, there can be many dierent representations of a steque containing a given
list of elements; when speaking of a steque, we mean a particular representation of it.
The pointer structure for this representation is straightforward. Each triple is
represented by a node containing three pointers: to a prex, a child steque, and a
su-x. Each pair is represented by a node containing two pointers: to a prex and a
steque.
4.2. Operations. The implementation of the steque operations is much like the
implementation of the noncatenable deque operations presented in Section 3.2. We
call a prex red if it contains either two or six elements, and green otherwise. We call a
su-x red if it contains three elements and green otherwise. The prex in a su-x-only
steque is considered to have the same color as the su-x. We dene two memoized
functions, gp, and gs, which produce green-prex and green-su-x representations of
a steque, respectively. Each is called only when the corresponding buer is red and
can be made green. We dene push, pop, and inject to call gp or gs when necessary
to obtain a green buer. In the denitions below, we represent a steque with prex
child steque c, and su-x s by [p; c; s].
Case 1: Steque d is represented by a triple. If
Case 2: Steque d is represented by a su-x only. If create a prex p
containing x and the rst two elements of sf(d), create a su-x s containing the last
element of sf(d), and return [p; ;; s]. Otherwise, create a su-x s by pushing x onto
sf(d) and return [;; ;; s].
Case 1: Steque d is represented by a triple. If
Case 2: Steque d is represented by a su-x only. If create a su-x s
containing x, and return [sf(d); ;; s]. Otherwise, create a su-x s by injecting x into
sf(d) and return [;; ;; s].
Case 1: d 1 and d 2 are represented by triples. First, catenate the buers sf(d 1 )
and pr(d 2 ) to obtain p. Now, calculate c 0 as follows: If jpj  5 then let c
9. Create two new prexes p 0 and
containing the rst four elements of p and p 00 containing the remaining
elements. Let c In either case, return
Case 2: d 1 or d 2 is represented by a su-x only. Push or inject the elements of the
su-x-only steque one-by-one into the other steque.
Note that both push and catenate produce valid steques even when their second
arguments are steques with prexes of length one. Although such steques are not
normally allowed, they may exist transiently during a pop. Every such steque is
immediately passed to push or catenate, and then discarded, however. In order to
dene the pop, gp, and gs operations, we dene a n aive-pop operation that simply
pops its steque argument without making sure that the result is a valid steque.
If d is represented by a triple, let (x; return the
consists of a su-x only, let (x;
the pair (x; ;) if
Case 1: Steque d is represented by a su-x only or jpr(d)j > 2. Return n aive-pop(d).
Case 2: Steque d is represented by a triple, x be the
rst element on pr(d) and y the second. If jsf(d)j < 3, push y onto sf(d) to form s and
8 H. KAPLAN, C. OKASAKI, and R. E. TARJEN
return (x; [;; ;; s]). Otherwise (jsf(d)j = 3), form p from y and the rst two elements
on sf(d), form s from the last element on sf(d), and return (x; [p; ;; s]).
Case 3: Steque d is represented by a triple,
create two new prexes p and p 0 by splitting pr(d) equally
in two. Let c
c(d) 6= ;), proceed as follows. Inspect the rst pair (p; d 0 ) in c(d). If jpj  4 or d 0 is
not empty, let ((p; d 0
Now inspect p.
Case 1: p contains at least four elements. Pop the rst two elements from p to form
inject these two elements into pr(d) to obtain p 0 . Let c
Return
Case 2: p contains at most three elements. Push the two elements in pr(d) onto p
to obtain p 0 . Let c is nonempty, or c
Return
(Steque d is represented by a triple with contain the rst
two elements of sf(d) and s the last element on sf(d). Let c
Return
4.3. Analysis. The analysis of this method is similar to the analysis in Section
3.3. We dene primary and secondary nodes, node states, and the potential function
exactly as in Section 3.3: the potential function, as there, is 4#rr0
where #rr0, #rr1, and #gr0 are the numbers of primary nodes in states rr0, rr1,
and gr0, respectively.
As in Section 3.3, we charge the O(1) cost of a call to gp or gs (excluding the cost
of any recursive call to push, pop, or inject) to the push, pop, or inject that calls
gp or gs. The amortized costs of push and inject are O(1) by an argument identical
to that used to analyze push in Section 3.3. Operation catenate calls push and
inject a constant number of times and creates a single new node, so its amortized
cost is also O(1).
To analyze pop, assume that a call to pop recurs to depth k (via intervening calls
to gp). By an argument analogous to that for push, each of the rst k 1 calls pays
for itself by decreasing the potential by one. The terminal call to pop can result in a
call to either push or catenate, each of which has O(1) amortized cost. It follows
that the overall amortized cost of pop is O(1), giving us the following theorem:
Theorem 4.1. Each of the operations push, pop, inject, and catenate dened
above takes O(1) amortized time.
We can improve the time and space e-ciency of the steque data structure by
constant factors by using overwriting in place of memoization, exactly as described in
Section 3.4. If we do this, we can also simplify the amortized analysis, again exactly
as described in Section 3.4.
4.4. Related work. The structure presented in this section is analogous to the
Kaplan-Tarjan structure of [10, Section 5] and the structure of [8, Section 7], but
simplies them as follows. First, the buers are of constant-bounded size, whereas
the structure of [10, Section 5] uses noncatenable steques as buers, and the structure
of [8, Section 7] uses noncatenable stacks as buers. These buers in turn must
be represented as in Section 3 of this paper or by using one of the other methods
mentioned there. In contrast, the structure of the present section is entirely self-
contained. Second, the skeleton of the present structure is just a stack, instead of
a stack of stacks as in [10] and [8]. Third, the changes used to make buers green
are applied in a one-sided, need-driven way; in [10] and [8], repairs must be made
simultaneously to both sides of the structure in carefully chosen locations.
Okasaki [14] has devised a dierent and somewhat simpler implementation of
con
uently persistent catenable steques that also achieves an O(1) amortized bound
per operation. His solution obtains its e-ciency by (implicitly) using a form of path
reversal [18] in addition to lazy evaluation and memoization. Our structure extends to
the double-ended case, as we shall see in the next section; whether Okasaki's structure
extends to this case is an open problem.
5. Catenable Deques. In this section we show how to extend our ideas to
support all ve list operations. Specically, we describe a data structure for catenable
deques that achieves an O(1) amortized time bound for push, pop, inject, eject,
and catenate. Our structure is based upon an analogous structure of Okasaki [16],
but simplied to use constant-size buers.
5.1. Representation. We use three kinds of buers: prexes, middles, and
su-xes. A nonempty deque d over A is represented either by a su-x sf(d) or by a
5-tuple that consists of a prex pr(d), a left deque of triples ld(d), a middle md(d),
a right deque of triples rd(d), and a su-x sf(d). A triple consists of a rst middle
buer , a deque of triples, and a last middle buer. One of the two middle buers
in a triple must be nonempty, and in a triple that contains a nonempty deque both
middles must be nonempty. All buers and triples are over A. A prex or su-x in a
5-tuple contains three to six elements, a su-x in a su-x-only representation contains
one to eight elements, a middle in a 5-tuple contains exactly two elements, and a
nonempty middle buer in a triple contains two or three elements.
The order of elements in a deque is the one consistent with the order of each
5-tuple, each buer, each triple, and each recursive deque. The pointer structure is
again straightforward, with the nodes representing 5-tuples or triples containing one
pointer for each eld.
5.2. Operations. We call a prex or su-x in a 5-tuple red if it contains either
three or six elements and green otherwise. We call a su-x in a su-x-only representation
red if it contains eight elements and green otherwise. The prex of a su-x-only
deque is considered to have the same color as the su-x. We introduce two memoizing
functions functions gp and gs as in Sections 3.2 and 4.2, which produce green-prex
and green-su-x representations of a deque, respectively, and which are called only
when the corresponding buer is red but can be made green. Below we give the implementations
of push, pop, gp, and catenate; the implementations of inject, eject,
and gs are symmetric to those of push, pop, and gp, respectively. We denote a deque
with prex p, left deque l, middle m, right deque r, and su-x s by [p; l; m;
Case 1: Deque d is represented by a 5-tuple. If
otherwise, let
Case 2: Deque d is represented by a su-x only. If sf(d) < 8, return a su-x-only
deque with su-x push(x; sf(d)). Otherwise, push x onto sf(d) to form s, with nine
elements. Create a new prex p with the rst four, a middle with the next two, and
a su-x s with the last three. Return [p; ;; m; ;; s].
As in Section 4.2, the implementation of pop uses n aive-pop.
Case 1: Deque d is represented by a su-x only or jpr(d)j > 3. Return n aive-pop(d).
Case 2:
Case 3: x be the rst element on pr(d). If
create a new su-x s containing all the elements in pr(d), md(d), and sf(d)
except x, and return the pair consisting of x and the deque represented by s only.
Otherwise, form p from pr(d) by popping x and injecting the rst element on md(d),
m 0 from md(d) by popping the rst element and injecting the rst element on
sf(d), form s from sf(d) by popping the rst element, and return (x;
create two new prexes p and p 0 , with p containing the rst four
elements of jpr(d)j and p 0 the last two; return [p; push((p
proceed as follows.
Case 1: ld(d) 6= ;. Inspect the rst triple t on ld(d). If either the rst nonempty
middle buer in t contains 3 elements or t contains a nonempty deque, let (t;
and assume that
x is nonempty if t consists of only one nonempty middle buer. Apply the appropriate
one of the folowing two subcases.
Case 1.1: 3. Form x 0 from x and p from pr(d) by popping
the rst element from x and injecting it into pr(d). Return
Case 1.2: 2. Inject both elements in x into pr(d) to form p. If d 0 and y
are empty, return [p; l; md(d); rd(d); sf(d)]. Otherwise (d 0 and y are nonempty)
let l
Case 2: Inspect the rst triple t in rd(d). If either the rst
nonempty middle buer in t contains 3 elements or t contains a nonempty deque, let
assume that x is nonempty if t consists of only one nonempty middle buer. Apply
the appropriate one of the following two subcases.
Case 2.1: x 0 from pr(d), m, and x by popping an
element from m and injecting it into pr(d) to form p, popping an element from
m and injecting the rst element from x to form m 0 , and popping the rst
element from x to form x 0 . Return
Case 2.2: 2. Inject the two elements in md(d) into pr(d) to form p. Let
are empty or r
Return
Case 1: Both d 1 and d 2 are represented by 5-tuples. Let y be the rst element in
pr(d 2 ), and let x be the last element in sf(d 1 ). Create a new middle m containing x
followed by y. Partition the elements in sf(d 1 ) fxg into at most two buers s 0
1 and
1 , each containing two or three elements in order, with s 00
possibly empty. let ld 0
ld 00
otherwise, let ld 00
ld 0
1 . Similarly, partition the elements in pr(d 1 ) fyg into at
most two prexes
, each containing two or three elements in order, with
possibly empty. Let rd 0
2 . Return [pr(d 1 ); ld 00
Case 2: d 1 or d 2 is represented by a su-x only. Push or inject the elements of the
su-x-only deque one-by-one into the other deque.
5.3. Analysis. To analyze this structure, we use the same denitions and the
same potential function as in Sections 3.3 and 4.3. The amortized costs of push,
inject, catenate, and pop are O(1) by an argument analogous to that in Section
4.3. The amortized cost of eject is O(1) by an argument symmetric to that for pop.
Thus we obtain the following theorem:
Theorem 5.1. Each of the operations push, pop, inject, eject, and catenate
dened above takes O(1) amortized time.
Just as in Sections 3.4 and 4.3, we can improve the time and space constant factors
and simplify the analysis by using overwriting in place of memoization. Overwriting is
the preferred implementation, unless one is using a functional programming language
that supports memoization but does not easily allow overwriting.
5.4. Related Work. The structure presented in this section is analogous to
the structures of [16, Chapter 11] and [8, Section 9] but simplies them as follows.
First, the buers are of constant size, whereas in [16] and [8] they are noncatenable
deques. Second, the skeleton of the present structure is a binary tree, instead of a
tree extension of a redundant digital numbering system as in [8]. Also, our amortized
analysis uses the standard potential function method of [17] rather than the more
complicated debit mechanism used in [16]. Another related structure is that of [10,
Section 5], which represents purely functional, real-time deques as pairs of triples
rather than 5-tuples, but otherwise is similar to (but simpler than) the structure of
[8, Section 9]. It is straightforward to modify the structure presented here to use pairs
of triples rather than 5-tuples.
6. Further Results and Open Questions. If the universe A of elements over
which deques are constructed has a total order, we can extend the structures described
here to support an additional heap order based on the order on A. Specically, we
can support the additional operation of nding the minimum element in a deque (but
not deleting it) while preserving a constant amortized time bound for every operation,
including nding the minimum. We merely have to store with each buer, each deque,
and each pair or triple the minimum element in it. For related work see [1, 2, 6, 13].
We can also support a
ip operation on deques. A
ip operation reverses the
linear order of the elements in the deque: the ith from the front becomes the ith from
the back, and vice-versa. For the noncatenable deques of Section 3, we implement
ip by maintaining a reversal bit that is
ipped by a
ip operation. If the reversal bit
is set, a push becomes an inject, a pop becomes an eject, an inject becomes a push,
and an eject becomes a pop. To support catenation as well as
ip we use reversal
bits at all levels. We must also symmetrize the denition in Section 5 to allow a
deque to be represented by a prex only, and extend the various operations to handle
this possibility. The interpretation of reversal bits is cumulative. That is, if d is a
deque and x is a deque inside of d, x is regarded as being reversed if an odd number
of reversal bits are set to 1 along the path of actual pointers in the structure from
the node for d to the node for x. Before performing catenation, if the reversal bit of
either or both of the two deques is 1, we push such bits down by
ipping such a bit
of a deque x to 0,
ipping the bits of all the deques to which x points, and swapping
the appropriate buers and deques. (The prex and su-x exchange roles, as do the
left deque and right deque; the order of elements in the prex and su-x is reversed
as well.) We do such push-downs of reversal bits by assembling new deques, not by
overwriting the old ones.
We have devised an alternative implementation of catenable deques in which the
sizes of the prexes and su-xes are between 3 and 5 instead of 3 and 6. We do this by
memoizing the pop and eject operations and avoiding creating a new structure with
a green prex (su-x, respectively) representing the original deque when performing
pop (eject, respectively). Using a more complicated potential function than the
ones used in earlier sections, we can show that such an implementation runs in O(1)
amortized time per operation.
One direction for future research is to nd a way to simplify our structures fur-
ther. Specically, consider the following alternative representation of catenable de-
ques, which uses a single recursive subdeque rather than two such subdeques. A
nonempty deque d over A is represented by a triple that consists of a prex pr(d), a
(possibly empty) child deque of triples c(d), and a su-x sf(d). A triple consists of a
nonempty prex , a deque of triples, and a nonempty su-x, or just of a nonempty prex
or su-x. All buers and triples are over A. The operations push, pop, inject, and
eject have implementations similar to their implementations in Section 5. The major
dierence is in the implementation of catenate, which for this structure requires a
call to pop. Specically, let d 1 and d 2 be two deques to be catenated. catenate
pops c(d 1 ) to obtain a triple (p; d and a new deque c, injects (s; c; sf(d 1
to obtain d 00 , and then pushes (p; d 00 ; pr(d 2 . The nal result
has prex pr(d 1 ), child deque c 0 , and su-x sf(d 2 ). It is an open question whether this
algorithm runs in constant amortized time per operation for any constant upper and
lower bounds on the buer sizes.
Another research direction is to design a con
uently persistent representation of
sorted lists such that accesses or updates d positions from either end take O(log d)
time, and catenation takes O(1) time. The best structure so far developed for this
problem has a doubly logarithmic catenation time [12]; it is purely functional, and
the time bounds are worst-case.

Acknowledgment

. We thank Michael Goldwasser for a detailed reading of this
paper, and Jason Hartline for discussions that led to our implementations using memoization



--R

Data structural bootstrapping
Con uently persistant deques via data structural boot- strapping
Fully persistent arrays
Fully persistent lists with catenation
Making data structures persistent
Deques with heap order

lists, PhD thesis
Simple con uently persistent catenable lists (ex- tended abstract)



An optimal RAM implementation of catenable min double-ended queues



Amortized computational complexity
Worst case analysis of set union algorithms
--TR

--CTR
Amos Fiat , Haim Kaplan, Making data structures confluently persistent, Journal of Algorithms, v.48 n.1, p.16-58, August
George Lagogiannis , Yannis Panagis , Spyros Sioutas , Athanasios Tsakalidis, A survey of persistent data structures, Proceedings of the 9th WSEAS International Conference on Computers, p.1-6, July 14-16, 2005, Athens, Greece
queue;memoization;functional programming;data structures;stack;double-ended queue deque;stack-ended queue steque;persistent data structures