Date: Wed, 15 Sep 1999 14:35:24 +0200
From: Jerome Vouillon <Jerome.Vouillon@inria.fr>
To: Steve Stevenson <steve@cs.clemson.edu>, caml-list@inria.fr
Subject: Re: Imperative list operations
In-Reply-To: <14302.41638.913957.615588@merlin.cs.clemson.edu>; from Steve Stevenson on Tue, Sep 14, 1999 at 03:36:18PM -0400
On Tue, Sep 14, 1999 at 03:36:18PM -0400, Steve Stevenson wrote:
> I need a double-ended queue implementation. The lists
> can get very long, so I would like to use imperative operations to
> change the links.
There are some very nice and quite efficient purely functional
implementations of double-ended queues. I suggest you to have a look
at Chris Okasaki's work on http://www.cs.columbia.edu/~cdo/papers.html
(in particular, "Simple Confluently Persistent Catenable Lists",
"Catenable Double-Ended Queues" and "Simple and Efficient Purely
Functional Queues and Deques").
> I've tried all the naïve type declarations --- all of which
> don't seem to work. I've tried the age old tricks. What am I not
> understanding? or doing right?
It is hard to guess without knowing what you have done...
You can use the following type definition :
type 'a node =
{ mutable prev : 'a list; mutable next : 'a list; value : 'a }
and 'a list = 'a node option;;
type 'a dequeue = { mutable head : 'a list; mutable tail : 'a list}
A double-ended queue has a pointer to the head of the list and a
pointer to its tail. A list can either be empty (None) or contain a
sequence of nodes. A node holds a pointer to the nodes that precedes
it and a pointer to the nodes that follows it.
Ther is some space overhead in using option types. So, you could also
use a circular list. The type definition would be :
type 'a node =
{ mutable prev : 'a node; mutable next : 'a node; val : 'a }
type 'a dequeue = 'a node option ref
A double-ended queue is either empty (None) or point to the head of
the circular list. Each node has a pointer to the previous node and
the next node in the circular list.
Insertion and removal looks something like that :
let insert_front d v =
match !d with
None ->
let rec node = { prev = node; next = node; value = v } in
d := Some node
| Some n' ->
let n = { prev = n'.prev; next = n'; value = v } in
n'.prev.next <- n; n'.prev <- n;
d := Some n;;
let remove_front d =
match !d with
None ->
raise Not_found
| Some n when n.next == n ->
d := None;
n.value
| Some n ->
n.next.prev <- n.prev; n.prev.next <- n.next;
d := Some n.next;
n.value;;
Regards,
-- Jérôme
This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:25 MET