From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA21145 for caml-redistribution; Fri, 17 Sep 1999 13:06:47 +0200 (MET DST)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA23705 for <caml-list@pauillac.inria.fr>; Wed, 15 Sep 1999 14:35:29 +0200 (MET DST)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.8.7/8.8.7) with ESMTP id OAA24769;
	Wed, 15 Sep 1999 14:35:24 +0200 (MET DST)
Received: (from vouillon@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA23728; Wed, 15 Sep 1999 14:35:24 +0200 (MET DST)
Message-ID: <19990915143524.40888@pauillac.inria.fr>
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
References: <14302.41638.913957.615588@merlin.cs.clemson.edu>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Mailer: Mutt 0.89.1
In-Reply-To: <14302.41638.913957.615588@merlin.cs.clemson.edu>; from Steve Stevenson on Tue, Sep 14, 1999 at 03:36:18PM -0400
Sender: weis

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