(***********************************************************************)
(*                                                                     *)
(*                               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.                                                        *)
(*                                                                     *)
(***********************************************************************)


type node = Naive_tree.node
type cell = { node : node;
              mutable next : cell }

type iterator = cell

type t = { mutable length : int;
           mutable head : cell;
           mutable last : cell; }

let rec nil = { node = Naive_tree.nil;
                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)