Re: [Caml-list] Doubly-linked list

[Max Kirillov <max630@mail.ru>]

[-- Attachment #1: Type: text/plain, Size: 477 bytes --]

On Tue, Aug 13, 2002 at 12:12:45PM -0400, Oleg wrote:
> type 'a dlist = {mutable prev : 'a dlist option; 
>                      mutable next : 'a dlist option; 
>                      info : 'a}


> Maybe I'll write it in the next few days. What kind of bothers me is the need 
> to have iterators (a la STL) as helper types.

Unless you need thread-safe behavior, that could be just
"'a dlist ref". I tried to do some fast things. See
attachment.  That's just an idea.

Max.

[-- Attachment #2: dlist.ml --]
[-- Type: text/plain, Size: 1047 bytes --]


type 'a t = {mutable prev : 'a t option;
            mutable next : 'a t option;
            info : 'a}

type 'a dlist = {mutable front: 'a t;
		mutable back: 'a t}

exception Bound

next = function {next=Some obj1} -> obj1 | _ -> raise Bound
prev = function {prev=Some obj1} -> obj1 | _ -> raise Bound

takeNext objR = objR:=(next !objR)
takePrev objR = objR:=(prev !objR)

add_before v obj =
	let newObj = {prev=None;next=obj;info=v} in
	(match obj
	    with {prev=Some obj1} -> (newObj.prev<-obj1;
				    obj1.next<-newObj)
		| {prev=None} -> ());
	obj.prev=newObj
	    
add_after v obj =
	let newObj = {next=None;prev=obj;info=v} in
	(match obj
	    with {next=Some obj1} -> (newObj.next<-obj1;
				    obj1.prev<-newObj)
		| {next=None} -> ());
	obj.next=newObj

(* Hmm... I'm not clear whether front is after back or before it.
    Depends on moving direction:) Let's suppose before *)

push_back v ({back=obj} as data) = add_after v obj; data.back <- next obj
push_front v ({front=obj} as data) = add_before v obj; data.front <- prev obj