From: Jesse Guardiani <jesse@wi...>  20040826 23:40:25

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 multinode 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 021111307 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 373202605 423559LINK (v) 4235595145 (f) http://www.wingnet.net 