Re: [Ocaml-lib-devel] Re: Dllist ? IndexTree ?

[Brian H. <bh...@sp...>]

On Fri, 10 Sep 2004, Jesse Guardiani wrote:

> Actually, I tried this before I submitted the current implementation and I
> couldn't get it to work. The problem seemed to be that Dllist has no
> concept of Empty, so the length function becomes really difficult to
> implement.

I moved the concept of "empty" one level up in my implementation.  This is 
because I didn't want to deal with options on the next/prev links.  

> 
> Brian, do you think it's possible to implement enums without the "valid"
> test? If everyone thinks it's possible then I'll give it another shot. I just
> didn't have much luck the first time around.

Actually, changing things so that x.next == x is the sign of the end of 
the list should make enums easier.

let rec enum_done = { data = Obj.magic (); next = enum_done;
                      prev = enum_done };;

let enum dlst =
    match dlst.head with
        | None -> Enum.empty ()
        | Some(hd) ->
            let next r () =
                if (!r) == enum_done then
                    raise Enum.no_more_elements
                else
                    begin
                        let rval = (!r).data in
                        if (!r).next == (!r) then
                            r := enum_done
                        else
                            r := (!r).next;
                        rval
                    end
            and count r () =
                let rec loop cnt node =
                    if node.next == node then
                        cnt + 1
                    else
                        loop (cnt + 1) node.next
                in
                if (!r) == enum_done then
                    0
                else
                    loop 0 node
            in
            let rec clone r () =
                let r = ref (!r) in
                Enum.make ~next:(next r) ~count:(count r)
                          ~clone:(clone r)
            in
            let r = ref hd in
            Enum.make ~next:(next r) ~count:(count r)
                      ~clone:(clone r)
;;

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian