Add a generic deque module.

[tatoo.git] / src / deque.ml

diff --git a/src/deque.ml b/src/deque.ml
new file mode 100644 (file)
index 0000000..64e7188
--- /dev/null
+++ b/src/deque.ml
@@ -0,0 +1,114 @@
+(***********************************************************************)
+(*                                                                     *)
+(*                               TAToo                                 *)
+(*                                                                     *)
+(*                     Kim Nguyen, LRI UMR8623                         *)
+(*                   Université Paris-Sud & CNRS                       *)
+(*                                                                     *)
+(*  Copyright 2010-2013 Université Paris-Sud and Centre National de la *)
+(*  Recherche Scientifique. All rights reserved.  This file is         *)
+(*  distributed under the terms of the GNU Lesser General Public       *)
+(*  License, with the special exception on linking described in file   *)
+(*  ../LICENSE.                                                        *)
+(*                                                                     *)
+(***********************************************************************)
+
+
+module type S =
+  sig
+    type elem
+    type t
+    type iterator
+
+    val create : unit -> t
+    val add : elem -> t -> unit
+    val push_front : elem -> t -> unit
+    val push_back : elem -> t -> unit
+    val iter : (elem -> unit) -> t -> unit
+    val length : t -> int
+    val is_empty : t -> bool
+    val head : t -> iterator
+    val last : t -> iterator
+    val next : iterator -> iterator
+    val value : iterator -> elem
+    val finished : iterator -> bool
+    val copy : t -> t
+  end
+
+module Make (E : sig type t end) =
+struct
+
+
+  type elem = E.t
+  type cell = { node : elem;
+                mutable next : cell }
+
+  type iterator = cell
+
+  type t = { mutable length : int;
+             mutable head : cell;
+             mutable last : cell; }
+
+  let rec nil = { node = Obj.magic ();
+                  next = nil }
+
+  let create () = { length = 0;
+                    head = nil;
+                    last = nil }
+
+  let iter f l =
+    let rec loop c =
+      if c != nil then begin
+        f c.node;
+        loop c.next
+      end
+    in
+    loop l.head
+
+
+  let length l = l.length
+  let is_empty l = l.head == nil
+
+  let add n l =
+    let ncell = { node = n;
+                  next = nil }
+    in
+    if l.head == nil then begin
+      l.head <- ncell;
+      l.last <- ncell;
+      l.length <- 1
+    end else begin
+      l.last.next <- ncell;
+      l.last <- ncell;
+      l.length <- l.length + 1
+    end
+
+  let push_back n l = add n l
+  let push_front n l =
+    let ncell = { node = n;
+                  next = l.head }
+    in
+    if l.head == nil then begin
+      l.head <- ncell;
+      l.last <- ncell;
+      l.length <- 1;
+    end else begin
+      l.head <- ncell;
+      l.length <- l.length + 1;
+    end
+
+  let head l = l.head
+  let last l = l.last
+  let next i = i.next
+  let value i = i.node
+  let finished i = i == nil
+
+  let copy l =
+    let rec loop l2 i =
+      if finished i then l2 else begin
+        add (value i) l2;
+        loop l2 (next i)
+      end
+    in
+    loop (create ()) (head l)
+end