(*
 * RefList - List reference
 * Copyright (C) 2003 Nicolas Cannasse
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version,
 * with the special exception on linking described in file LICENSE.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *)
open ExtList

exception Empty_list
exception Invalid_index of int

type 'a t = 'a list ref

let empty () = ref []

let is_empty x =
	match !x with
	| [] -> true
	| _ -> false

let of_list l = ref l
let to_list rl = !rl
let copy ~dst ~src = dst := !src
let copy_list ~dst ~src = dst := src

let add rl item = rl := List.append !rl [item]
let push rl item = rl := item::!rl

let clear rl = rl := []

let length rl = List.length !rl
let hd rl = try List.hd !rl with _ -> raise Empty_list
let tl rl = try ref (List.tl !rl) with _ -> raise Empty_list
let iter f rl = List.iter f !rl
let for_all f rl = List.for_all f !rl
let map f rl = ref (List.map f !rl)
let transform f rl = rl := List.map f !rl
let map_list f rl = List.map f !rl
let find f rl = List.find f !rl
let rev rl = rl := List.rev !rl
let find_exc f exn rl = try List.find f !rl with _ -> raise exn
let exists f rl = List.exists f !rl
let sort ?(cmp=compare) rl = rl := List.sort ~cmp !rl

let rfind f rl = List.rfind f !rl

let first = hd

let last rl = 
	let rec loop = function
		| x :: [] -> x
		| x :: l -> loop l
		| [] -> assert false
	in
	match !rl with
	| [] -> raise Empty_list
	| l -> loop l

let remove rl item = rl := List.remove !rl item
let remove_if pred rl = rl := List.remove_if pred !rl
let remove_all rl item = rl := List.remove_all !rl item
let filter pred rl = rl := List.filter pred !rl

let add_sort ?(cmp=compare) rl item =
	let rec add_aux = function
		| x::lnext as l ->
			let r = cmp x item in
			if r < 0 then item::l else x::(add_aux lnext)
		| [] -> [item]
	in
	rl := add_aux !rl

let pop rl =
	match !rl with
	| [] -> raise Empty_list
	| e::l -> rl := l; e

let npop rl n =		
	let rec pop_aux l n =
		if n = 0 then begin
			rl := l;
			[]
		end else
			match l with
			| [] -> raise Empty_list
			| x::l -> x::(pop_aux l (n-1))
	in
	pop_aux !rl n

let copy_enum ~dst ~src = dst := List.of_enum src
let enum rl = List.enum !rl
let of_enum e = ref (List.of_enum e)

module Index = struct

	let remove_at rl pos =
		let p = ref (-1) in
		let rec del_aux = function			
			| x::l -> incr p; if !p = pos then l else x::(del_aux l)
			| [] -> raise (Invalid_index pos)
		in
		rl := del_aux !rl

	let index pred rl =
		let index = ref (-1) in
		List.find (fun it -> incr index; pred it; ) !rl;
		!index

	let index_of rl item =
		let index = ref (-1) in
		List.find (fun it -> incr index; it = item; ) !rl;
		!index

	let at_index rl pos =
		try
			List.nth !rl pos
		with
			_ -> raise (Invalid_index pos)

	let set rl pos newitem =
		let p = ref (-1) in
		rl := List.map (fun item -> incr p; if !p = pos then newitem else item) !rl;
		if !p < pos || pos < 0 then raise (Invalid_index pos)


end