This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Imperative list operations
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 1999-09-17 (11:06) From: Jerome Vouillon Subject: Re: Imperative list operations
```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

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

```