Release coccinelle-0.2.0

[bpt/coccinelle.git] / commons / ocamlextra / enum.ml

(* \r
 * Enum - Enumeration over abstract collection of elements.\r
 * Copyright (C) 2003 Nicolas Cannasse\r
 * \r
 * This library is free software; you can redistribute it and/or\r
 * modify it under the terms of the GNU Lesser General Public\r
 * License as published by the Free Software Foundation; either\r
 * version 2.1 of the License, or (at your option) any later version,\r
 * with the special exception on linking described in file LICENSE.\r
 *\r
 * This library is distributed in the hope that it will be useful,\r
 * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\r
 * Lesser General Public License for more details.\r
 *\r
 * You should have received a copy of the GNU Lesser General Public\r
 * License along with this library; if not, write to the Free Software\r
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\r
 *)\r
\r
type 'a t = {\r
	mutable count : unit -> int;\r
	mutable next : unit -> 'a;\r
	mutable clone : unit -> 'a t;\r
	mutable fast : bool;\r
}\r
\r
(* raised by 'next' functions, should NOT go outside the API *)\r
exception No_more_elements\r
\r
let _dummy () = assert false\r
\r
let make ~next ~count ~clone =\r
	{\r
		count = count;\r
		next = next;\r
		clone = clone;\r
		fast = true;\r
	}\r
\r
let rec init n f =\r
	if n < 0 then invalid_arg "Enum.init";\r
	let count = ref n in\r
	{\r
		count = (fun () -> !count);\r
		next = (fun () ->\r
			match !count with\r
			| 0 -> raise No_more_elements\r
			| _ ->\r
				decr count;\r
				f (n - 1 - !count));\r
		clone = (fun () -> init !count f);\r
		fast = true;\r
	}			\r
\r
let rec empty () =\r
	{\r
		count = (fun () -> 0);\r
		next = (fun () -> raise No_more_elements);\r
		clone = (fun () -> empty());\r
		fast = true;\r
	}\r
\r
type 'a _mut_list = {\r
	hd : 'a;\r
	mutable tl : 'a _mut_list;\r
}\r
\r
let force t =\r
	let rec clone enum count =\r
		let enum = ref !enum\r
		and	count = ref !count in\r
		{\r
			count = (fun () -> !count);\r
			next = (fun () ->\r
				match !enum with\r
				| [] -> raise No_more_elements\r
				| h :: t -> decr count; enum := t; h);\r
			clone = (fun () ->\r
				let enum = ref !enum\r
				and count = ref !count in\r
				clone enum count);\r
			fast = true;\r
		}\r
	in\r
	let count = ref 0 in\r
	let _empty = Obj.magic [] in\r
	let rec loop dst =\r
		let x = { hd = t.next(); tl = _empty } in\r
		incr count;\r
		dst.tl <- x;\r
		loop x\r
	in\r
	let enum = ref _empty  in \r
	(try\r
		enum := { hd = t.next(); tl = _empty };\r
		incr count;\r
		loop !enum;\r
	with No_more_elements -> ());\r
	let tc = clone (Obj.magic enum) count in\r
	t.clone <- tc.clone;\r
	t.next <- tc.next;\r
	t.count <- tc.count;\r
	t.fast <- true\r
\r
let from f =\r
	let e = {\r
		next = f;\r
		count = _dummy;\r
		clone = _dummy;\r
		fast = false;\r
	} in\r
	e.count <- (fun () -> force e; e.count());\r
	e.clone <- (fun () -> force e; e.clone());\r
	e\r
\r
let from2 next clone =\r
	let e = {\r
		next = next;\r
		count = _dummy;\r
		clone = clone;\r
		fast = false;\r
	} in\r
	e.count <- (fun () -> force e; e.count());\r
	e\r
\r
let get t =\r
	try\r
		Some (t.next())\r
	with\r
		No_more_elements -> None\r
\r
let push t e =\r
	let rec make t =\r
		let fnext = t.next in\r
		let fcount = t.count in\r
		let fclone = t.clone in\r
		let next_called = ref false in\r
		t.next <- (fun () ->\r
			next_called := true;\r
			t.next <- fnext;\r
			t.count <- fcount;\r
			t.clone <- fclone;\r
			e);\r
		t.count <- (fun () ->\r
			let n = fcount() in\r
			if !next_called then n else n+1);\r
		t.clone <- (fun () ->\r
			let tc = fclone() in\r
			if not !next_called then make tc;\r
			tc);\r
	in\r
	make t\r
\r
let peek t =\r
	match get t with\r
	| None -> None\r
	| Some x ->\r
		push t x;\r
		Some x\r
\r
let junk t =\r
	try\r
		ignore(t.next())\r
	with\r
		No_more_elements -> ()\r
\r
let is_empty t =\r
	if t.fast then\r
		t.count() = 0\r
	else\r
		peek t = None\r
\r
let count t =\r
	t.count()\r
\r
let fast_count t =\r
	t.fast\r
\r
let clone t =\r
	t.clone()\r
\r
let iter f t =\r
	let rec loop () =\r
		f (t.next());\r
		loop();\r
	in\r
	try\r
		loop();\r
	with\r
		No_more_elements -> ()\r
\r
let iteri f t =\r
	let rec loop idx =\r
		f idx (t.next());\r
		loop (idx+1);\r
	in\r
	try\r
		loop 0;\r
	with\r
		No_more_elements -> ()\r
\r
let iter2 f t u =\r
	let push_t = ref None in\r
	let rec loop () =\r
		push_t := None;\r
		let e = t.next() in\r
		push_t := Some e;\r
		f e (u.next());\r
		loop ()\r
	in\r
	try\r
		loop ()\r
	with\r
		No_more_elements ->\r
			match !push_t with\r
			| None -> ()\r
			| Some e ->\r
				push t e\r
\r
let iter2i f t u =\r
	let push_t = ref None in\r
	let rec loop idx =\r
		push_t := None;\r
		let e = t.next() in\r
		push_t := Some e;\r
		f idx e (u.next());\r
		loop (idx + 1)\r
	in\r
	try\r
		loop 0\r
	with\r
		No_more_elements ->\r
			match !push_t with\r
			| None -> ()\r
			| Some e -> push t e\r
\r
let fold f init t =\r
	let acc = ref init in\r
	let rec loop() =\r
		acc := f (t.next()) !acc;\r
		loop()\r
	in\r
	try\r
		loop()\r
	with\r
		No_more_elements -> !acc\r
\r
let foldi f init t =\r
	let acc = ref init in\r
	let rec loop idx =\r
		acc := f idx (t.next()) !acc;\r
		loop (idx + 1)\r
	in\r
	try\r
		loop 0\r
	with\r
		No_more_elements -> !acc\r
\r
let fold2 f init t u =\r
	let acc = ref init in\r
	let push_t = ref None in\r
	let rec loop() =\r
		push_t := None;\r
		let e = t.next() in\r
		push_t := Some e;\r
		acc := f e (u.next()) !acc;\r
		loop()\r
	in\r
	try\r
		loop()\r
	with\r
		No_more_elements ->\r
			match !push_t with\r
			| None -> !acc\r
			| Some e ->\r
				push t e;\r
				!acc\r
\r
let fold2i f init t u =\r
	let acc = ref init in\r
	let push_t = ref None in\r
	let rec loop idx =\r
		push_t := None;\r
		let e = t.next() in\r
		push_t := Some e;\r
		acc := f idx e (u.next()) !acc;\r
		loop (idx + 1)\r
	in\r
	try\r
		loop 0\r
	with\r
		No_more_elements ->\r
			match !push_t with\r
			| None -> !acc\r
			| Some e ->\r
				push t e;\r
				!acc\r
\r
let find f t =\r
	let rec loop () =\r
		let x = t.next() in\r
		if f x then x else loop()\r
	in\r
	try\r
		loop()\r
	with\r
		No_more_elements -> raise Not_found\r
\r
let rec map f t =\r
	{\r
		count = t.count;\r
		next = (fun () -> f (t.next()));\r
		clone = (fun () -> map f (t.clone()));\r
		fast = t.fast;\r
	}\r
\r
let rec mapi f t =\r
	let idx = ref (-1) in\r
	{\r
		count = t.count;\r
		next = (fun () -> incr idx; f !idx (t.next()));\r
		clone = (fun () -> mapi f (t.clone()));\r
		fast = t.fast;\r
	}\r
\r
let rec filter f t =\r
	let rec next() =\r
		let x = t.next() in\r
		if f x then x else next()\r
	in\r
	from2 next (fun () -> filter f (t.clone()))\r
\r
let rec filter_map f t =\r
    let rec next () =\r
        match f (t.next()) with\r
        | None -> next()\r
        | Some x -> x\r
    in\r
	from2 next (fun () -> filter_map f (t.clone()))\r
\r
let rec append ta tb = \r
	let t = {\r
		count = (fun () -> ta.count() + tb.count());\r
		next = _dummy;\r
		clone = (fun () -> append (ta.clone()) (tb.clone()));\r
		fast = ta.fast && tb.fast;\r
	} in\r
	t.next <- (fun () ->\r
		try\r
			ta.next()\r
		with\r
			No_more_elements ->\r
				(* add one indirection because tb can mute *)\r
				t.next <- (fun () -> tb.next());\r
				t.count <- (fun () -> tb.count());\r
				t.clone <- (fun () -> tb.clone());\r
				t.fast <- tb.fast;\r
				t.next()\r
	);\r
	t\r
\r
let rec concat t =\r
	let concat_ref = ref _dummy in\r
	let rec concat_next() =\r
		let tn = t.next() in\r
		concat_ref := (fun () ->\r
			try\r
				tn.next()\r
			with\r
				No_more_elements ->\r
					concat_next());\r
		!concat_ref ()\r
	in\r
	concat_ref := concat_next;\r
	from2 (fun () -> !concat_ref ()) (fun () -> concat (t.clone()))\r