src/naive_node_list.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 type node = Naive_tree.node
  18 type cell = { node : node;
  19               mutable next : cell }
  20
  21 type iterator = cell
  22
  23 type t = { mutable length : int;
  24            mutable head : cell;
  25            mutable last : cell; }
  26
  27 let rec nil = { node = Naive_tree.nil;
  28                 next = nil }
  29
  30 let create () = { length = 0;
  31                   head = nil;
  32                   last = nil }
  33
  34 let iter f l =
  35   let rec loop c =
  36     if c != nil then begin
  37       f c.node;
  38       loop c.next
  39     end
  40   in
  41   loop l.head
  42
  43
  44
  45
  46 let length l = l.length
  47 let is_empty l = l.head == nil
  48
  49 let pop l =
  50   if is_empty l then failwith "pop"
  51   else
  52     let v = l.head.node in
  53     let nhead = l.head.next in
  54     l.head <- nhead;
  55     if nhead == nil then l.last <- nil;
  56     v
  57
  58
  59
  60 let add n l =
  61   let ncell = { node = n;
  62                 next = nil }
  63   in
  64   if l.head == nil then begin
  65     l.head <- ncell;
  66     l.last <- ncell;
  67     l.length <- 1
  68   end else begin
  69     l.last.next <- ncell;
  70     l.last <- ncell;
  71     l.length <- l.length + 1
  72   end
  73
  74 let push_back n l = add n l
  75 let push_front n l =
  76   let ncell = { node = n;
  77                 next = l.head }
  78   in
  79   if l.head == nil then begin
  80     l.head <- ncell;
  81     l.last <- ncell;
  82     l.length <- 1;
  83   end else begin
  84     l.head <- ncell;
  85     l.length <- l.length + 1;
  86   end
  87
  88 let append l1 l2 =
  89   let len2 = l2.length in
  90   if len2 != 0 then begin
  91     l1.length <- l1.length + len2;
  92     l1.last.next <- l2.head;
  93     l1.last <- l2.last;
  94   end;
  95   l1
  96
  97 let head l = l.head
  98 let last l = l.last
  99 let next i = i.next
 100 let value i = i.node
 101 let finished i = i == nil
 102
 103 let copy l =
 104   let rec loop l2 i =
 105     if finished i then l2 else begin
 106       add (value i) l2;
 107       loop l2 (next i)
 108     end
 109   in
 110   loop (create ()) (head l)