Re: Enum, doubly linked lists, and thoughts

On Wed, 30 Apr 2003, Nicolas Cannasse wrote:

> > I'm playing (while waiting for compiles) at writting a circular, mutable,
> > doubly linked list data structure.  The advantage of this is that inserts
> > anywhere into the list are O(1), if you have a pointer into the list.
> >
> > Enum is almost a perfect vehicle for this- internal to the enum I'm
> > keeping a reference to the current element.  If I could just 'reach into'
> > the enum and snag this reference, all would be good with the world.  But I
> > can't figure out how to do that (this may be because it's friday afternoon
> > of a long, stressfull week and my brain is mush).
> 
> With circular lists, your next() function will of course never raise
> No_more_elements, and count() should also be something like :
> let rec infinite_count() = infinite_count()
> And doing an *.of_enum with a cicular list will of course run until you kill
> the process or run out of memory, same for Enum.iter... You could hack
> something like waiting for physical equality with the first element to break
> the loop, but if there is a map done before, you will never get it ! 

Sorry, I wasn't clear.  It's internal structure is circular so that I
don't have to define a NULL.  But externally it will be a finite list, and
have a most definate end and begining.  This circularness will be hidden 
internally.

Here's the basic idea I have so far and some example functions:

type 'a dllist_elem_t = { datum : 'a; mutable next : 'a dllist_elem_t;
                          mutable prev : 'a dllist_elem_t }

type 'a dllist_head_t = Empty | NotEmpty of 'a dllist_elem_t

type 'a dllist_t = 'a dllist_head_t ref

let head dllist =
    match !dllist with
        Empty -> assert false (* or something *)
        | NotEmpty head -> head.datum

let prepend dllist x =
    let rec newelem = { datum = x ; next = newelem ; prev = newelem } in
    match !dllist with
        Empty -> dllist := (NotEmpty newelem)
        | NotEmpty head ->
                newelem.next <- head;
                newelem.prev <- head.prev;
                head.prev <- newelem;
                newelem.prev.next <- newelem;
                dllist := NotEmpty(newelem)


let count dllist =
    match !dllist with
        Empty -> 0
        | NotEmpty head ->
            let tail = head.prev in
            let rec loop elem cnt =
                if elem == tail then (cnt + 1) else
                loop (elem.next) (cnt + 1)
            in
            loop head 0


let iter f dllist =
    match !dllist with
        Empty -> ()
        | NotEmpty head ->
            let tail = head.prev in
            let rec loop elem =
                f elem;
                if (elem == tail) then () else loop elem.next
            in
            loop head



Notice in head- I don't return the dllist_elem_t, I return the element in 
it.  This is how I want it to work- dllist_elem_t never "leaks" out of the 
internal representation.  Also note that although I have a double 
dereference to get to the first element (the reference and the enumerated 
type) after that everything else is just 1 reference away.  

But this actually raises problems with doing a pointer type external from 
the linked list.  I suppose what I want is sort of an OO interface, with a 
"protected" inteface seen only inside the module, and a "public" interface 
I can put into the .mli and everyone can use.  But I'm not 100% sure how 
to do this.

Brian




-------------------------------------------------------
This sf.net email is sponsored by:ThinkGeek
Welcome to geek heaven.
http://thinkgeek.com/sf