/** -*-C-*-ish
    Kaya standard library
    Copyright (C) 2004, 2005 Edwin Brady

    This file is distributed under the terms of the GNU Lesser General
    Public Licence. See COPYING for licence.
*/

module Array;

import Builtins;
import Tuples;

foreign "stdfuns.o" {
    [a] doReverse([a] xs) = reverseArray;
    "Resize an array.
    Change the size of the array to <em>i</em>. If the array is longer
    than <em>i</em>, later items are dropper. If shorter, uninitialised
    values are pushed onto the array."
    public Void resize([a] xs, Int i) = resizeArray;

    Void quicksort(Ptr vm, [a] xs, Int(a,a) sortfn) = quicksort;
    Void shortenArray([a] array) = shortenArray;
    a shiftArray([a] array) = shiftArray;

    "Create an array with an initial size of <em>size</em>."
    public [a] createArray(Int size) = createArray;
}

public Exception OutOfBounds = Exception("Out of bounds error",20);

"Reverse an array in-place."
public Void reverse(var [a] xs)
{
    xs = doReverse(xs);
}

"Return an array of values from [first..last], incrementing by step."
public [Int] range(Int first, Int last, Int step = 1)
{
//    print "Running range\n";
    size = (last+1-first)/step;
    if (size<0) { size=-size; }
    xs = createArray(size);
    j=0;
    val = first;
    if (step>0) {
	while (val<=last) {
	    xs[j]=val;
	    j=j+1;
	    val = val + step;
	}
    } else if (step<0) {
	while (val>=last) {
	    xs[j]=val;
	    j=j+1;
	    val = val + step;
	}
    }
    return xs;
}

"Sort an array.
Uses quicksort algorithm.
By default uses built in compare function and sorts in
ascending order, but can also use a user supplied compare function."
public Void sort(var [a] xs, Int(a,a) sortfn = compare)
{
    quicksort(getVM(),xs,sortfn);
//    quicksort(xs, 0, size(xs)-1, sortfn);
}

"Return a sorted array.
Sorts an array, but unlike <em>sort</em> returns a new array and leaves
the original intact."
public [a] sorted([a] xs)
{
    newxs = createArray(size(xs));
    // Do a shallow copy.
    for x in xs {
	push(newxs,x);
    }
    sort(newxs);
    return newxs;
}

"Randomly reorder an array."
public Void shuffle(var [a] xs)
{
    // Swap each element with a random other element
    xsize = size(xs);
    for i in [0..xsize-1] {
	swap(xs[i],xs[abs(rand()%xsize)]);
    }
}

/*
Void quicksort([a] xs, Int left, Int right, Int(a,a) sortfn)
{
    if (right>left) {
	// Get the pivot from about the middle.
	pi = partition(xs, left, right, (left+right)/2, sortfn);
	quicksort(xs, left, pi-1, sortfn);
	quicksort(xs, pi+1, right, sortfn);
    }
}

Int partition(var [a] xs, var Int left, var Int right, var Int pivotIndex, var Int(a,a) sortfn)
{
    pivotval = xs[pivotIndex];
    swap(xs[pivotIndex], xs[right]); // Put pivot on the end
    si = left;
    for(i=left;i<right;i++) { // More efficient than "for x in xs"
	if (sortfn(xs[i],pivotval)<0) {
	    swap(xs[si],xs[i]);
	    si++;
	}
    }
    swap(xs[right],xs[si]); // Put pivot where it should be.
    return si;
}
*/

"Concatenate two arrays."
public Void concat(var [a] xs, [a] ys)
{
    for y in ys {
	push(xs,y);
    }
}

"DEPRECATED synonym for concat"
public Void append(var [a] xs, var [a] ys) = concat(xs,ys);

"Concatentate a list of lists into a single list."
public [a] join ([[a]] lists)
{
    new = [];
    for xs in lists {
	for x in xs {
	    push(new,x);
	}
    }
    return new;
}

"Place the separator <em>sep</em> between each element of <em>xs</em>."
public [a] intersperse(a sep, [a] xs)
{
    new = createArray(size(xs)*2);
    for x@i in xs {
	push(new,x);
	if (i!=size(xs))
	    push(new,sep);
    }
    return new;
}

"Return whether any of <em>xs</em> satsify predicate <em>p</em>."
public Bool any(Bool(a) pred, var [a] xs)
{
    for x in xs {
	if (pred(x)) {
	    return true;
	}
    }
    return false;
}

"Return whether all of <em>xs</em> satsify predicate <em>p</em>."
public Bool all(Bool(a) pred, [a] xs)
{
    for x in xs {
	if (!pred(x)) {
	    return false;
	}
    }
    return true;
}

"Map a function across an array.
Returns the array created by applying function <em>f</em> to every 
element of <em>xs</em>."
public [b] map (b(a) f, [a] xs) {
    newxs = createArray(size(xs));
    for x in xs {
	push(newxs, f(x));
    }
    return newxs;
}

// If we have map, we might as well have zipWith!

"Map a function across two arrays.
Returns the array created by applying function <em>f</em> to every pairwise
elements of <em>xs</em> and <em>ys</em>."
public [c] zipWith(c(a,b) f, [a] xs, [b] ys) {
    if (size(xs)<size(ys)) {
	max = size(xs);
    } else {
	max = size(ys);
    }

    newxs = createArray(max);
    for i in [0..max-1] {
	push(newxs, f(xs[i],ys[i]));
    }
    return newxs;
}

"Turn a pair of lists into a list of pairs."
public [(a,b)] zip([a] xs, [b] ys) {
    return zipWith(lambda(a,b) -> { (a,b) }, xs, ys);
}


"Fold an array.
Applies a function across an array. Example, given a function <code>sum</code>
which adds two numbers:
<pre>
   total = fold(sum,[1,2,3,4,5],0);
   putStrLn(String(total));
</pre>
This prints the sum of the values in the array <code>[1,2,3,4,5]</code>."
public b fold (b(a,b) f, [a] xs, b acc) {
    for x in xs {
	acc = f(x,acc);
    }
    return acc;
}

"Filter a list according to a predicate.
Each element of <em>xs</em> is tested against the predicate <em>p</em>.
The returned list contains those elements of <em>xs</em> for which the
predicate is true."
public [a] filter(Bool(a) p, [a] xs) {
    newxs = createArray(size(xs));
    for x in xs {
	if (p(x)) push(newxs,x);
    }
    return newxs;
}

"Push a value onto the end of an array."
public Void push(var [a] array,var a v)
{
    array[size(array)]=v;
}

public a top([a] array) 
{
    if (size(array)==0) {
	throw(OutOfBounds);
    }
    return array[size(array)-1];
}

"Remove a value from the end of an array"
public Void pop(var [a] array) {
    if (size(array)==0) {
	throw(OutOfBounds);
    }
    shortenArray(array);    
}

"Get the first item off an array, and remove it from the array."
public a shift(var [a] array)
{
    if (size(array)==0) {
	throw(OutOfBounds);
    }
    return shiftArray(array);
/*    x = array[0];
    for(i=0;i<(size(array)-1);i=i+1) {
	array[i]=array[i+1];
    }
    shortenArray(array);
    return x;*/
}

"Opposite of shift; put a value on the front of an array."
public Void unshift(a val, var [a] array)
{
    for(i=size(array)-1;i>=0;i=i-1) {
	array[i+1]=array[i];
    }
    array[0]=val;
}

"Return the subarray starting at position pos, n elements long."
public [a] subarray([a] array, Int pos, Int n)
{
    if (pos < 0 || n < 1 || pos+n > size(array)) {
      throw(OutOfBounds);
    }
    sub = createArray(n);
    for i in [pos..(pos+n-1)] {
	push(sub,array[i]);
    }
    return sub;
}

"Return the array created by removing a subarray.
Subarray starts at position pos, n elements long."
public [a] remove([a] array, Int pos, Int n)
{
  // subarray() does the bounds checking for us here.
    sub = subarray(array,pos,n);
    for i in [pos..(size(array)-n-1)] {
      array[i] = array[i+n];
    }
    for i in [1..n] {
      pop(array);
    }
    return sub;
}

"Remove the element at position <em>idx</em>."
public Void removeAt(var [a] array, Int idx)
{
    if (size(array)<=idx) {
	throw(OutOfBounds);
    }
    for(i=idx;i<(size(array)-1);i=i+1) {
	array[i]=array[i+1];
    }
    shortenArray(array);
}

"DEPRECATED synonym for removeAt()"
public Void removeidx(var [a] array, Int idx) = removeAt(array,idx);

"Add an element at position <em>idx</em>"
// idx = 0 is equivalent to unshift, idx = size(array) is equivalent to push
public Void addAt(var [a] array, a elem, Int idx)
{
    if (size(array)<idx) {
      throw(OutOfBounds);
    } else if (size(array) == idx) {
      push(array,elem);
    } else {
      for(i=size(array);i>=idx;i--) {
	array[i]=array[i-1];
      }
      array[idx] = elem;
    }
}

"DEPRECATED synonym for addAt()"
public Void addidx(var [a] array, a elem, Int idx) = addAt(array,elem,idx);

"Return whether val is in list."
public Bool elem(a val, [a] list, Bool(a,a) eq = equal) {
  // this should probably be optimised at compile time
  // rather than with less neat code here, but it is a 
  // commonly-used function
  for x in [0..size(list)-1] {
    if (eq(list[x],val)) {
      return true;
    }
  }
  return false;
}

"Remove repeated elements from a list (in-place modification).
The name 'nub', incidentally, is borrowed from the Haskell prelude function
of the same name, and suggests 'essence'."
public Void nub(var [a] xs, Bool(a,a) eq = equal) {
    pos = 1;
    while (pos < size(xs)) {
        if (elem(xs[pos],take(pos,xs),@eq)) {
	    removeAt(xs,pos);
	} else {
	    pos++;
	}
    }
}

"Take the first <em>n</em> elements from an array.
Returns a new array, leaving the original unmodified."
public [a] take(Int x, [a] xs) = subarray(xs,0,x);
/*{ // might as well only implement subarray once
    if (size(xs)<x) {
	x = size(xs);
    }

    retxs = [];
    for i in [0..x-1] {
	push(retxs,xs[i]);
    }

    return retxs;
    }*/