(*
   Wojciech Muła, $Id: mylist.ml,v 1.5 2006-06-03 20:56:12 wojtek Exp $
 *)

(* converts string to list of chars

   explode "Ocaml" = ['O'; 'c'; 'a'; 'm'; 'l']
 *)
let explode s =
	let rec worker = function
	    | (l, -1) -> l
	    | (l,  i) -> worker (s.[i]::l, (i-1))
	in
		worker ([], String.length s - 1)


(* convert char to string *)
let string_of_char c =
	String.make 1 c


(* convert list of chars to string

   implode ['O'; 'c'; 'a'; 'm'; 'l'] = "Ocaml"
 *)
let rec implode l = 
	List.fold_left (fun s c -> s ^ (string_of_char c)) "" l


(* returns last element of list

   last [1; 2; 3; 4; 5] = 5
 *)
let rec last = function
	| []    -> failwith "last"
	| [x]   -> x
	| _::xs -> last xs

(* returns all but one elements of list

   allbutone [1; 2; 3; 4; 5] = [1; 2; 3; 4]
 *)
let rec allbutone = function
	| []    -> raise (Failure "allbutone: empty string")
	| [x]   -> []
	| x::xs -> x::allbutone xs


(* returns first n element of list l

   take [1; 2; 3; 4; 5] 2 = [1; 2]
 *)
let take l n =
	let rec worker l' l i =
		if i = 0 then
			l'
		else
			match l with
			  []    -> l'
			| x::xs -> worker (l' @ [x]) xs (i-1)
	in
		worker [] l n


let allbut l n =
	let n' = (List.length l - n) in
	if n' < 0 then [] else take l n'


(* returns all but first n-elements of list l

   drop [1; 2; 3; 4; 5] 2 = [3; 4; 5]

   (take l n) @ (drop l n) = l
 *)
let rec drop l i =
	match l with
	  []		-> []
	| _::xs as l	-> if i > 0 then
				drop xs (i-1)
			   else
			        l


(* returns sublist of list l

   cut [1; 2; 3; 4; 5] 1 4 = [2; 3; 4]
 *)
let cut l f t =
	assert (f >= 0);
	assert (f < t);
	take (drop l f) (t-f)


(* splits list l into two list at n-th element

   splitat [1; 2; 3; 4; 5] 0 = ([], [1; 2; 3; 4; 5])
   splitat [1; 2; 3; 4; 5] 1 = ([1], [2; 3; 4; 5])
   splitat [1; 2; 3; 4; 5] 2 = ([1; 2], [3; 4; 5])
   splitat [1; 2; 3; 4; 5] 3 = ([1; 2; 3], [4; 5])
   splitat [1; 2; 3; 4; 5] 4 = ([1; 2; 3; 4], [5])
   splitat [1; 2; 3; 4; 5] 5 = ([1; 2; 3; 4; 5], [])
 *)
let splitat l n =
	let rec worker before after i =
		if i = 0 then
			(before, after)
		else
			match after with
			  []	    -> (before, after)
			| x::after' -> worker (before @ [x]) after' (i-1)
	in
		worker [] l n

(* returns copy of list l with changed i-th element

   change [1; 2; 3; 4; 5] 0 100 = [100; 2; 3; 4; 5]
   change [1; 2; 3; 4; 5] 3 100 = [1; 2; 3; 100; 5]
 *)
let rec change l i n =
	match l with
	  []	-> []
	| x::xs	-> if i > 0 then
			x::(change xs (i-1) n)
		   else
		   	n::xs


(* inset element n into list l at position i

   insert [1; 2; 3; 4; 5] 0 100 = [100; 1; 2; 3; 4; 5]
   insert [1; 2; 3; 4; 5] 1 100 = [1; 100; 2; 3; 4; 5]
   insert [1; 2; 3; 4; 5] 2 100 = [1; 2; 100; 3; 4; 5]
   insert [1; 2; 3; 4; 5] 3 100 = [1; 2; 3; 100; 4; 5]
   insert [1; 2; 3; 4; 5] 4 100 = [1; 2; 3; 4; 100; 5]
   insert [1; 2; 3; 4; 5] 5 100 = [1; 2; 3; 4; 5; 100]
 *)
let insertat l i n =
	let rec worker before after i =
		if i = 0 then
			before @ [n] @ after
		else
			match after with
			  []	    -> before @ after @ [n]
			| x::after' -> worker (before @ [x]) after' (i-1)
	in	
		worker [] l i


(* returns index of first occurence of y,
   or -1 if y is not member of list
   
   index [11; 44; 33; 44; 55] 44 = 1
 *)
let index l y =
	let rec worker l i =
		match l with
		  []    -> -1
		| x::xs -> if x=y then i else worker xs (i+1)
	in
		worker l 0


(* returns index of last occurence of y,
   or -1 if y is not member of list

   rindex [11; 44; 33; 44; 55] 44 = 3
 *)
let rindex l y =
	let rec worker l i found =
		match l with
		  []    -> found
		| x::xs -> if x=y then
		              worker xs (i+1) i
			   else
		              worker xs (i+1) found
	in
		worker l 0 (-1)


(* returns list of integeres [lo..hi)

   range -5 10 = [-5; -4; -3; -2; -1; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
 *)
let range lo hi =
	assert (lo < hi);
	let rec worker l i =
		if i >= lo then
			worker (i::l) (i-1)
		else
			l
	in
		worker [] (hi-1)


(* List.map f (range lo hi)

   irange 0 10 (fun x -> x*x) = [0; 1; 4; 9; 16; 25; 36; 49; 64; 81]
 *)
let tabulate lo hi f =
	assert (lo < hi);
	let rec worker l i =
		if i >= lo then
			worker ((f i)::l) (i-1)
		else
			l
	in
		worker [] (hi-1)

let imap fn l =
	let rec aux l i =
		match l with
		  []    -> []
		| x::xs -> (fn i x)::aux xs (i+1)
	in
		aux l 0

let ifilter fn l =
	let rec aux l i =
		match l with
		  []    -> []
		| x::xs -> if fn i x then
				x::aux xs (i+1)
		           else
				aux xs (i+1)
	in
		aux l 0

(*
let take' l n  = ifilter (fun i _ -> i < n) l

let drop' l n  = ifilter (fun i _ -> i >= n) l

let cut' l k n = ifilter (fun i _ -> i >= k && i < n) l
*)

let count pred l =
	List.fold_left (fun i x -> (if pred x then i+1 else i)) 0 l