/*..

==============
Some Utilities
==============

:Source: http://pure-lang.googlecode.com/svn/trunk/pure/examples/libor/myutils.pure
:Author: Libor Spacek (C) <libors@gmail.com\>
:License: GPL V3
:Date: June 2009


General mathematical iterators over one and two indices
=======================================================
*/
//>>>
iter1d op i1 i2 f = foldl1 op (map f (i1..i2));

iter2d op i1 i2 j1 j2 f = 
	foldl1 op (map (uncurry f) [x,y | x = i1..i2; y = j1..j2]);

//Examples using the mathematical iterators (sums and products)
Sigma i1 i2 f = iter1d (+) i1 i2 f;
Sigma2 i1 i2 j1 j2 = iter2d (+) i1 i2 j1 j2 f;
Pi i1 i2 f = iter1d (*) i1 i2 f;
Pi2 i1 i2 j1 j2 f = iter2d (*) i1 i2 j1 j2 f;
fac n = Pi 1L n id;

//Binomial using (k, n-k) symmetry, Pi, and bignum division
binomial n k = (Pi (k+1L) n id) div (Pi 2L (n-k) id) if n-k < k;
   = (Pi (n-k+1L) n id) div (Pi 2L k id);

// Euclid's recursive greatest common factor algorithm for ints and bignums
gcf x 0 | gcf x 0L = x;
gcf x y = gcf y (x mod y);
//<<<
/*..

List Processing
===============
*/
//>>>

// ecat puts h at the end of list l 
ecat h [] = [h];
ecat h (h2:t) = h2:(ecat h t);

// take off the head of a list and put it at the end	
rotate (h:t) = ecat h t;

// list of all rotations using recursion and the size of the list
rotations l = rot (#l) l with
	rot 1 l = [l];
	rot i::int l = l:(rot (pred i)(rotate l)) end;

// list of all rotations using iteraten and the size of the list
lazyrotations l = iteraten (#l) rotate l;

// generate a reducing branching factor tree of all permutations of a list. 
// nodes are head items for their branches
permtree [i] = [i];
permtree l =  map (\(h:t) -> h:(permtree t)) (rotations l);

// take n items from the front and put them at the end (n positive 0<=n<=#n)
protate 0 l = l;
protate n::int l = (drop n l)+(take n l);

// rotate n items, cf. "rotate n bits instruction" (n can now also be -ve) 
// example applied to clocks: >head (nrotate (-33) (0..23)); 
// what time is 33 hrs before midnight? Answer: 15 hrs.
nrotate  n::int l 
   = if n<0  then (protate (ll + (n mod ll)) l)
             else	(protate (n mod ll) l) when ll=#l end;

// removal of the first ordered list from the second. (<) must be defined
orem _ [] = [];
orem [] l = l;
orem (h1:t1) l2@(h2:_) = orem t1 l2 if h1 < h2; // h1 not found in l2
orem l1@(h1:t1) (h2:t2) = if (h1 === h2) then orem t1 t2 else h2:(orem l1 t2);
//<<<
/*..

**## operator**

	returns the total (deep) size of a heterogeneous list-like binary 
	structure using arbitrary constructors and the terminators, [] () nil,
	in any combination. */

//>>>
nonfix nil;
prefix (#) ##;
## [] | ## () | ## nil = 0;
## (f@_ x xs) = accum (accum 0 x) xs with
	accum n::int [] | accum n::int () | accum n::int nil = n;
	accum n::int (f@_ x xs)  = accum (accum n x) xs;
	accum n::int x = n+1 end;
//<<<
