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