util.ml

(*
 * Copyright (c) 1997-1999 Massachusetts Institute of Technology
 * Copyright (c) 2003, 2006 Matteo Frigo
 * Copyright (c) 2003, 2006 Massachusetts Institute of Technology
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *)

(* various utility functions *)
open List
open Unix 

(*****************************************
 * Integer operations
 *****************************************)
(* fint the inverse of n modulo m *)
let invmod n m =
    let rec loop i =
	if ((i * n) mod m == 1) then i
	else loop (i + 1)
    in
	loop 1

(* Yooklid's algorithm *)
let rec gcd n m =
    if (n > m)
      then gcd m n
    else
      let r = m mod n
      in
	  if (r == 0) then n
	  else gcd r n

(* reduce the fraction m/n to lowest terms, modulo factors of n/n *)
let lowest_terms n m =
    if (m mod n == 0) then
      (1,0)
    else
      let nn = (abs n) in let mm = m * (n / nn)
      in let mpos = 
	  if (mm > 0) then (mm mod nn)
	  else (mm + (1 + (abs mm) / nn) * nn) mod nn
      and d = gcd nn (abs mm)
      in (nn / d, mpos / d)

(* find a generator for the multiplicative group mod p
   (where p must be prime for a generator to exist!!) *)

exception No_Generator

let find_generator p =
    let rec period x prod =
 	if (prod == 1) then 1
	else 1 + (period x (prod * x mod p))
    in let rec findgen x =
	if (x == 0) then raise No_Generator
	else if ((period x x) == (p - 1)) then x
	else findgen ((x + 1) mod p)
    in findgen 1

(* raise x to a power n modulo p (requires n > 0) (in principle,
   negative powers would be fine, provided that x and p are relatively
   prime...we don't need this functionality, though) *)

exception Negative_Power

let rec pow_mod x n p =
    if (n == 0) then 1
    else if (n < 0) then raise Negative_Power
    else if (n mod 2 == 0) then pow_mod (x * x mod p) (n / 2) p
    else x * (pow_mod x (n - 1) p) mod p

(******************************************
 * auxiliary functions 
 ******************************************)
let rec forall id combiner a b f =
    if (a >= b) then id
    else combiner (f a) (forall id combiner (a + 1) b f)

let sum_list l = fold_right (+) l 0
let max_list l = fold_right (max) l (-999999)
let min_list l = fold_right (min) l 999999
let count pred = fold_left 
    (fun a elem -> if (pred elem) then 1 + a else a) 0
let remove elem = List.filter (fun e -> (e != elem))
let cons a b = a :: b
let null = function 
    [] -> true
  | _ -> false
let for_list l f = List.iter f l
let rmap l f = List.map f l

(* functional composition *)
let (@@) f g x = f (g x)

let forall_flat a b = forall [] (@) a b

let identity x = x

let rec minimize f = function
    [] -> None
  | elem :: rest ->
      match minimize f rest with
	None -> Some elem
      |	Some x -> if (f x) >= (f elem) then Some elem else Some x


let rec find_elem condition = function
    [] -> None
  | elem :: rest ->
      if condition elem then
	Some elem
      else
	find_elem condition rest


(* find x, x >= a, such that (p x) is true *)
let rec suchthat a pred =
  if (pred a) then a else suchthat (a + 1) pred

(* print an information message *)
let info string =
  if !Magic.verbose then begin
    let now = Unix.times () 
    and pid = Unix.getpid () in
    prerr_string ((string_of_int pid) ^ ": " ^
		  "at t = " ^  (string_of_float now.tms_utime) ^ " : ");
    prerr_string (string ^ "\n");
    flush Pervasives.stderr;
  end

(* iota n produces the list [0; 1; ...; n - 1] *)
let iota n = forall [] cons 0 n identity

(* interval a b produces the list [a; 1; ...; b - 1] *)
let interval a b = List.map ((+) a) (iota (b - a))

(*
 * freeze a function, i.e., compute it only once on demand, and
 * cache it into an array.
 *)
let array n f =
  let a = Array.init n (fun i -> lazy (f i))
  in fun i -> Lazy.force a.(i)


let rec take n l =
  match (n, l) with
    (0, _) -> []
  | (n, (a :: b)) -> a :: (take (n - 1) b)
  | _ -> failwith "take"

let rec drop n l =
  match (n, l) with
    (0, _) -> l
  | (n, (_ :: b)) -> drop (n - 1) b
  | _ -> failwith "drop"


let either a b =
  match a with
    Some x -> x
  | _ -> b