[Ocaml-lib-devel] new dllist (yet again)

[Jesse G. <je...@wi...>]

This time it's purely node based. I haven't implemented
enums yet, as I don't know what they do. :)

Most of the code has been tested, but there might be a
few bugs left. Feature requests are welcome, as long as
the feature can be implemented safely (i.e. forget about
a multi-node O(1) cut function. There's no way to guarantee
that the two nodes given as arguments are part of the same
list)

Here's what I've got so far:

(*
 * Dllist- a mutable, circular, doubly linked list library
 * Copyright (C) 2004 Brian Hurt
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version,
 * with the special exception on linking described in file LICENSE.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *)

type 'a node_t = {
        mutable data : 'a;
        mutable next : 'a node_t;
        mutable prev : 'a node_t;
};;

exception Empty;;

let create x = let rec nn = { data = x; next = nn; prev = nn} in nn;;

let length node =
        let rec loop cnt n =
                if n = node then
                        cnt
                else
                        loop (cnt + 1) n.next
        in
        loop 1 node.next
;;

let append node elem =
        let nn = { data = elem; next = node.next; prev = node } in
        node.next.prev <- nn;
        node.next <- nn;
        nn
;;

let prepend node elem =
        let nn = { data = elem; next = node; prev = node.prev } in
        node.prev.next <- nn;
        node.prev <- nn;
        nn
;;

let remove node =
        let next = node.next in
        node.prev.next <- next;
        next.prev <- node.prev;
        node.prev <- node;
        node.next <- node;
;;

let drop node =
        let next = node.next in
        node.prev.next <- next;
        next.prev <- node.prev;
        node.prev <- node;
        node.next <- node;
        next
;;

let rev_drop node =
        let prev = node.prev in
        prev.next <- node.next;
        node.next.prev <- prev;
        node.prev <- node;
        node.next <- node;
        prev
;;

let merge node1 node2 =
        let next = node1.next in
        let prev = node2.prev in
        node1.next <- node2;
        node2.prev <- node1;
        next.prev <- prev;
        prev.next <- next;
;;

let set node data = node.data <- data;;

let get node = node.data;;

let next node = node.next;;

let prev node = node.prev;;

let jump node idx =
        let m = if idx > 0 then -1 else 1 in
        let rec loop idx n =
                if idx == 0 then
                        n
                else
                        loop (idx + m) n.next
        in
        loop idx node
;;

let iter f node =
        let () = f node.data in
        let rec loop n =
                if n <> node then
                        let () = f n.data in
                        loop n.next
        in
        loop node.next
;;

let fold_left f init node =
        let rec loop accu n =
                if n = node then
                        accu
                else
                        loop (f accu n.data) n.next
        in
        loop (f init node.data) node.next
;;

let fold_right f node init =
        let rec loop accu n =
                if n = node then
                        f n.data accu
                else
                        loop (f n.data accu) n.prev
        in
        loop init node.prev
;;

let map f node =
        let first = create (f node.data) in
        let rec loop last n =
                if n = node then
                        begin
                                first.prev <- last;
                                first
                        end
                else
                        begin
                                let nn = { data = f n.data; next = first; prev = last } in
                                last.next <- nn;
                                loop nn n.next
                        end
        in
        loop first node.next
;;

let copy node = map (fun x -> x) node;;

let to_list node = fold_right (fun d l -> d::l) node [];;

let of_list lst =
        match lst with
                | [] -> raise Empty
                | h :: t ->
                        let first = create h in
                        let rec loop last = function
                                | [] ->
                                        last.next <- first;
                                        first.prev <- last;
                                        first
                                | h :: t ->
                                        let nn = { data = h; next = first; prev = last } in
                                        last.next <- nn;
                                        loop nn t
                        in
                        loop first t;
;;


-- 
Jesse Guardiani, Systems Administrator
WingNET Internet Services,
P.O. Box 2605 // Cleveland, TN 37320-2605
423-559-LINK (v)  423-559-5145 (f)
http://www.wingnet.net