cannam@127: (*
cannam@127:  * Copyright (c) 1997-1999 Massachusetts Institute of Technology
cannam@127:  * Copyright (c) 2003, 2007-14 Matteo Frigo
cannam@127:  * Copyright (c) 2003, 2007-14 Massachusetts Institute of Technology
cannam@127:  *
cannam@127:  * This program is free software; you can redistribute it and/or modify
cannam@127:  * it under the terms of the GNU General Public License as published by
cannam@127:  * the Free Software Foundation; either version 2 of the License, or
cannam@127:  * (at your option) any later version.
cannam@127:  *
cannam@127:  * This program is distributed in the hope that it will be useful,
cannam@127:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
cannam@127:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
cannam@127:  * GNU General Public License for more details.
cannam@127:  *
cannam@127:  * You should have received a copy of the GNU General Public License
cannam@127:  * along with this program; if not, write to the Free Software
cannam@127:  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
cannam@127:  *
cannam@127:  *)
cannam@127: 
cannam@127: (* various utility functions *)
cannam@127: open List
cannam@127: open Unix 
cannam@127: 
cannam@127: (*****************************************
cannam@127:  * Integer operations
cannam@127:  *****************************************)
cannam@127: (* fint the inverse of n modulo m *)
cannam@127: let invmod n m =
cannam@127:     let rec loop i =
cannam@127: 	if ((i * n) mod m == 1) then i
cannam@127: 	else loop (i + 1)
cannam@127:     in
cannam@127: 	loop 1
cannam@127: 
cannam@127: (* Yooklid's algorithm *)
cannam@127: let rec gcd n m =
cannam@127:     if (n > m)
cannam@127:       then gcd m n
cannam@127:     else
cannam@127:       let r = m mod n
cannam@127:       in
cannam@127: 	  if (r == 0) then n
cannam@127: 	  else gcd r n
cannam@127: 
cannam@127: (* reduce the fraction m/n to lowest terms, modulo factors of n/n *)
cannam@127: let lowest_terms n m =
cannam@127:     if (m mod n == 0) then
cannam@127:       (1,0)
cannam@127:     else
cannam@127:       let nn = (abs n) in let mm = m * (n / nn)
cannam@127:       in let mpos = 
cannam@127: 	  if (mm > 0) then (mm mod nn)
cannam@127: 	  else (mm + (1 + (abs mm) / nn) * nn) mod nn
cannam@127:       and d = gcd nn (abs mm)
cannam@127:       in (nn / d, mpos / d)
cannam@127: 
cannam@127: (* find a generator for the multiplicative group mod p
cannam@127:    (where p must be prime for a generator to exist!!) *)
cannam@127: 
cannam@127: exception No_Generator
cannam@127: 
cannam@127: let find_generator p =
cannam@127:     let rec period x prod =
cannam@127:  	if (prod == 1) then 1
cannam@127: 	else 1 + (period x (prod * x mod p))
cannam@127:     in let rec findgen x =
cannam@127: 	if (x == 0) then raise No_Generator
cannam@127: 	else if ((period x x) == (p - 1)) then x
cannam@127: 	else findgen ((x + 1) mod p)
cannam@127:     in findgen 1
cannam@127: 
cannam@127: (* raise x to a power n modulo p (requires n > 0) (in principle,
cannam@127:    negative powers would be fine, provided that x and p are relatively
cannam@127:    prime...we don't need this functionality, though) *)
cannam@127: 
cannam@127: exception Negative_Power
cannam@127: 
cannam@127: let rec pow_mod x n p =
cannam@127:     if (n == 0) then 1
cannam@127:     else if (n < 0) then raise Negative_Power
cannam@127:     else if (n mod 2 == 0) then pow_mod (x * x mod p) (n / 2) p
cannam@127:     else x * (pow_mod x (n - 1) p) mod p
cannam@127: 
cannam@127: (******************************************
cannam@127:  * auxiliary functions 
cannam@127:  ******************************************)
cannam@127: let rec forall id combiner a b f =
cannam@127:     if (a >= b) then id
cannam@127:     else combiner (f a) (forall id combiner (a + 1) b f)
cannam@127: 
cannam@127: let sum_list l = fold_right (+) l 0
cannam@127: let max_list l = fold_right (max) l (-999999)
cannam@127: let min_list l = fold_right (min) l 999999
cannam@127: let count pred = fold_left 
cannam@127:     (fun a elem -> if (pred elem) then 1 + a else a) 0
cannam@127: let remove elem = List.filter (fun e -> (e != elem))
cannam@127: let cons a b = a :: b
cannam@127: let null = function 
cannam@127:     [] -> true
cannam@127:   | _ -> false
cannam@127: let for_list l f = List.iter f l
cannam@127: let rmap l f = List.map f l
cannam@127: 
cannam@127: (* functional composition *)
cannam@127: let (@@) f g x = f (g x)
cannam@127: 
cannam@127: let forall_flat a b = forall [] (@) a b
cannam@127: 
cannam@127: let identity x = x
cannam@127: 
cannam@127: let rec minimize f = function
cannam@127:     [] -> None
cannam@127:   | elem :: rest ->
cannam@127:       match minimize f rest with
cannam@127: 	None -> Some elem
cannam@127:       |	Some x -> if (f x) >= (f elem) then Some elem else Some x
cannam@127: 
cannam@127: 
cannam@127: let rec find_elem condition = function
cannam@127:     [] -> None
cannam@127:   | elem :: rest ->
cannam@127:       if condition elem then
cannam@127: 	Some elem
cannam@127:       else
cannam@127: 	find_elem condition rest
cannam@127: 
cannam@127: 
cannam@127: (* find x, x >= a, such that (p x) is true *)
cannam@127: let rec suchthat a pred =
cannam@127:   if (pred a) then a else suchthat (a + 1) pred
cannam@127: 
cannam@127: (* print an information message *)
cannam@127: let info string =
cannam@127:   if !Magic.verbose then begin
cannam@127:     let now = Unix.times () 
cannam@127:     and pid = Unix.getpid () in
cannam@127:     prerr_string ((string_of_int pid) ^ ": " ^
cannam@127: 		  "at t = " ^  (string_of_float now.tms_utime) ^ " : ");
cannam@127:     prerr_string (string ^ "\n");
cannam@127:     flush Pervasives.stderr;
cannam@127:   end
cannam@127: 
cannam@127: (* iota n produces the list [0; 1; ...; n - 1] *)
cannam@127: let iota n = forall [] cons 0 n identity
cannam@127: 
cannam@127: (* interval a b produces the list [a; 1; ...; b - 1] *)
cannam@127: let interval a b = List.map ((+) a) (iota (b - a))
cannam@127: 
cannam@127: (*
cannam@127:  * freeze a function, i.e., compute it only once on demand, and
cannam@127:  * cache it into an array.
cannam@127:  *)
cannam@127: let array n f =
cannam@127:   let a = Array.init n (fun i -> lazy (f i))
cannam@127:   in fun i -> Lazy.force a.(i)
cannam@127: 
cannam@127: 
cannam@127: let rec take n l =
cannam@127:   match (n, l) with
cannam@127:     (0, _) -> []
cannam@127:   | (n, (a :: b)) -> a :: (take (n - 1) b)
cannam@127:   | _ -> failwith "take"
cannam@127: 
cannam@127: let rec drop n l =
cannam@127:   match (n, l) with
cannam@127:     (0, _) -> l
cannam@127:   | (n, (_ :: b)) -> drop (n - 1) b
cannam@127:   | _ -> failwith "drop"
cannam@127: 
cannam@127: 
cannam@127: let either a b =
cannam@127:   match a with
cannam@127:     Some x -> x
cannam@127:   | _ -> b