src/deque.ml

   1 (***********************************************************************)
   2 (*                                                                     *)
   3 (*                               TAToo                                 *)
   4 (*                                                                     *)
   5 (*                     Kim Nguyen, LRI UMR8623                         *)
   6 (*                   Université Paris-Sud & CNRS                       *)
   7 (*                                                                     *)
   8 (*  Copyright 2010-2013 Université Paris-Sud and Centre National de la *)
   9 (*  Recherche Scientifique. All rights reserved.  This file is         *)
  10 (*  distributed under the terms of the GNU Lesser General Public       *)
  11 (*  License, with the special exception on linking described in file   *)
  12 (*  ../LICENSE.                                                        *)
  13 (*                                                                     *)
  14 (***********************************************************************)
  15
  16
  17 module type S =
  18   sig
  19     type elem
  20     type t
  21     type iterator
  22
  23     val create : unit -> t
  24     val add : elem -> t -> unit
  25     val push_front : elem -> t -> unit
  26     val push_back : elem -> t -> unit
  27     val iter : (elem -> unit) -> t -> unit
  28     val length : t -> int
  29     val is_empty : t -> bool
  30     val head : t -> iterator
  31     val last : t -> iterator
  32     val next : iterator -> iterator
  33     val value : iterator -> elem
  34     val finished : iterator -> bool
  35     val copy : t -> t
  36   end
  37
  38 module Make (E : sig type t end) =
  39 struct
  40
  41
  42   type elem = E.t
  43   type cell = { node : elem;
  44                 mutable next : cell }
  45
  46   type iterator = cell
  47
  48   type t = { mutable length : int;
  49              mutable head : cell;
  50              mutable last : cell; }
  51
  52   let rec nil = { node = Obj.magic ();
  53                   next = nil }
  54
  55   let create () = { length = 0;
  56                     head = nil;
  57                     last = nil }
  58
  59   let iter f l =
  60     let rec loop c =
  61       if c != nil then begin
  62         f c.node;
  63         loop c.next
  64       end
  65     in
  66     loop l.head
  67
  68
  69   let length l = l.length
  70   let is_empty l = l.head == nil
  71
  72   let add n l =
  73     let ncell = { node = n;
  74                   next = nil }
  75     in
  76     if l.head == nil then begin
  77       l.head <- ncell;
  78       l.last <- ncell;
  79       l.length <- 1
  80     end else begin
  81       l.last.next <- ncell;
  82       l.last <- ncell;
  83       l.length <- l.length + 1
  84     end
  85
  86   let push_back n l = add n l
  87   let push_front n l =
  88     let ncell = { node = n;
  89                   next = l.head }
  90     in
  91     if l.head == nil then begin
  92       l.head <- ncell;
  93       l.last <- ncell;
  94       l.length <- 1;
  95     end else begin
  96       l.head <- ncell;
  97       l.length <- l.length + 1;
  98     end
  99
 100   let head l = l.head
 101   let last l = l.last
 102   let next i = i.next
 103   let value i = i.node
 104   let finished i = i == nil
 105
 106   let copy l =
 107     let rec loop l2 i =
 108       if finished i then l2 else begin
 109         add (value i) l2;
 110         loop l2 (next i)
 111       end
 112     in
 113     loop (create ()) (head l)
 114 end