/** -*-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.
*/
"<summary>Array manipulation</summary>
<prose>This module contains functions for manipulating and inspecting arrays. All of the functions will work on arrays of any type.</prose>
<prose>It is automatically imported (via the Prelude module) unless
the <code>-noprelude</code> compiler option is used. Almost all programs
and modules will need to import this module.</prose>"
module Array;

import Builtins;
import Tuples;

foreign "stdfuns.o" {
    [a] doReverse([a] xs) = reverseArray;
    "<argument name='xs'>The array to resize</argument>
     <argument name='i'>The new length</argument>
     <summary>Resize an array.</summary>
     <prose>Change the size of the array to <variable>i</variable>. If the array is longer than <variable>i</variable>, later items are dropped. If it is shorter, uninitialised values are pushed onto the array.</prose>"
    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;
    Void unshiftArray(a val, [a] array) = unshiftArray;
    [a] docreateArray(Ptr vm, Int size) = createArray;
}

"<argument name='size'>The initial size of the array</argument>
<summary>Create an array</summary>
<prose>Create an array with an initial size of <variable>size</variable>. While arrays are automatically resized as necessary, it is more memory-efficient to only make arrays as large as necessary, if the final size of the array is known.</prose>
<prose><code>[]</code> is equivalent to <code>createArray(1024)</code>. Generally this is adequate - save the use of this function for the optimisation stage.</prose>
<related><functionref>Builtins::createString</functionref></related>"
public [a] createArray(Int size) {
  return docreateArray(getVM,size);
}


"<summary>Attempt to access an out-of-bounds element.</summary>
<prose>This Exception is thrown by various array functions when an attempt is made to read an illegal array index.</prose>"
Exception OutOfBounds();
"<summary>The step in a range may not be zero</summary>
<prose>If the step in a range is zero, as in the following examples, the range would have infinite size, and so this Exception is thrown.</prose>
<example>r = range(1,5,0);
r = [1,1..5];</example>"
Exception ZeroStep();

"<argument name='xs'>The array to reverse</argument>
<summary>Reverse an array in-place.</summary>
<prose>This function reverses an array in-place.</prose>
<example>xs = [1,2,3,4,5];
reverse(xs);
// xs = [5,4,3,2,1]</example>"
public Void reverse(var [a] xs)
{
    xs = doReverse(xs);
}

"<argument name='first'>The first value in the returned array</argument>
<argument name='last'>The limit of the last value in the returned array</argument>
<argument name='step'>The difference between adjacent values (cannot be zero!). This argument is optional and defaults to 1.</argument>
<summary>Get a range of integers</summary>
<prose>Return an array of values from [<variable>first</variable>..<variable>last</variable>], incrementing by <variable>step</variable>.</prose>
<example>xs = range(1,5); // [1,2,3,4,5]
xs = range(1,5,2); // [1,3,5]
xs = range(1,5,3); // [1,4]
xs = range(8,4,-1); // [8,7,6,5,4]</example>
<prose>The usual way of calling the <code>range</code> function is using the <code>[first..last]</code> or <code>[first,second..last]</code> syntax.</prose>
<example>xs = [1..5]; // [1,2,3,4,5]
xs = [1,3..5]; // [1,3,5]
xs = [1,4..5]; // [1,4]
xs = [8,7..4]; // [8,7,6,5,4]</example>"
public [Int] range(Int first, Int last, Int step = 1)
{
//    print "Running range\n";
    if (step == 0) {
      throw(ZeroStep);
    }
    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;
}

"<argument name='xs'>The array to sort</argument>
<argument name='sortfn'>Optionally, a user-defined comparison function.</argument>
<summary>Sort an array.</summary>
<prose>Sort an array in-place using the quicksort algorithm.
By default this uses the <functionref>Builtins::compare</functionref> function and sorts in
ascending order, but it can instead use a user supplied compare function.</prose>
<example>xs = [3,5,1,2,6,1];
sort(xs); // [1,1,2,3,5,6]</example>
<prose>Comparison functions should return 0 if the values are identical, less than zero if the first value passed to the function is 'smaller', and more than zero if the second value is 'bigger'. In this context, 'smaller' values are moved to the start of the array, and 'bigger' values to the end. The following example has a simple function to sort an array of <code>Int</code>s into descending order.</prose>
<example>Int rsort(Int a, Int b) {
    return b-a;
}

Void main() {
    xs =  [3,5,1,2,6,1];
    sort(xs,rsort); // [6,5,3,2,1,1]
}</example>
<prose>Values that are identical for the purposes of the sorting function will be placed in an undefined order relative to each other.</prose>
<related>The <functionref>sorted</functionref> function returns a sorted copy of the array, rather than sorting in place.</related>"
public Void sort(var [a] xs, Int(a,a) sortfn = compare)
{
    quicksort(getVM(),xs,sortfn);
//    quicksort(xs, 0, size(xs)-1, sortfn);
}

"<argument name='xs'>The array to sort</argument>
<argument name='sortfn'>Optionally, a user-defined comparison function.</argument>
<summary>Return a sorted array.</summary>
<prose>Sorts an array, but unlike <functionref>sort</functionref> returns a new array and leaves the original unmodified.</prose>
<related>See the <functionref>sort</functionref> function documentation for usage examples.</related>"
public [a] sorted([a] xs, Int(a,a) sortfn = compare)
{
    newxs = createArray(size(xs));
    // Do a shallow copy.
    for x in xs {
	push(newxs,x);
    }
    sort(newxs,sortfn);
    return newxs;
}

"<argument name='xs'>The array to shuffle</argument>
<summary>Randomly reorder an array.</summary>
<prose>Randomly reorder an array in-place. Because this function uses <functionref>Builtins::rand</functionref> to determine the order, you must have called <functionref>Builtins::srand</functionref> before you use it.</prose>"
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)]);
    }
}


"<argument name='xs'>The first array</argument>
<argument name='ys'>The second array</argument>
<summary>Concatenate two arrays.</summary>
<prose>Append the elements of the second array onto the first array.</prose>
<example>xs = [1,2,3];
ys = [4,5];
concat(xs,ys);
// xs = [1,2,3,4,5]
// ys = [4,5]</example>"
public Void concat(var [a] xs, [a] ys)
{
    for y in ys {
	push(xs,y);
    }
}

"<argument name='lists'>A list of lists</argument>
<summary>Concatentate a list of lists</summary>
<prose>Concatentate a list of lists into a single list.</prose>
<example>lists = [[1,2,3],[4,5],[6,7,8,9,10]];
joined = join(lists);
// joined = [1,2,3,4,5,6,7,8,9,10]</example>"
public [a] join ([[a]] lists)
{
    new = [];
    for xs in lists {
	for x in xs {
	    push(new,x);
	}
    }
    return new;
}

"<argument name='sep'>The separator</argument>
<argument name='sep'>The elements</argument>
<summary>Place a separator between each element of an array</summary>
<prose>Place the separator <variable>sep</variable> between each element of <variable>xs</variable> and return the resulting array.</prose>
<example>xs = [1,2,3,4];
ys = intersperse(0,xs);
// ys = [1,0,2,0,3,0,4]</example>"
public [a] intersperse(a sep, [a] xs)
{
    new = createArray(size(xs)*2);
    for x@i in xs {
	push(new,x);
	if (i+1!=size(xs))
	    push(new,sep);
    }
    return new;
}

"<argument name='pred'>The predicate to test with</argument>
<argument name='xs'>The array to test</argument>
<summary>Check if any elements satisfy a predicate</summary>
<prose>Return true if any of the elements of <variable>xs</variable> satsify the predicate <variable>p</variable>.</prose>
<related><functionref>all</functionref></related>"
public Bool any(Bool(a) pred, [a] xs)
{
    for x in xs {
	if (pred(x)) {
	    return true;
	}
    }
    return false;
}

"<argument name='pred'>The predicate to test with</argument>
<argument name='xs'>The array to test</argument>
<summary>Check if all elements satisfy a predicate</summary>
<prose>Return true if all of the elements of <variable>xs</variable> satsify the predicate <variable>p</variable>.</prose>
<related><functionref>any</functionref></related>"
public Bool all(Bool(a) pred, [a] xs)
{
    for x in xs {
	if (!pred(x)) {
	    return false;
	}
    }
    return true;
}

"<argument name='f'>The function to apply</argument>
<argument name='xs'>The array</argument>
<summary>Map a function across an array.</summary>
<prose>Returns the array created by applying function <variable>f</variable> to every element of <variable>xs</variable>.</prose>
<example>xs = [\"abc\",\"d\",\"efghij\"];
ys = map(length,xs);
// ys = [3,1,6]</example>
<prose>or</prose>
<example>xs = [1,-5,2,-7,-4];
ys = map(abs,xs);
// ys = [1,5,2,7,4]</example>
<related><functionref>zipWith</functionref></related>
<related><functionref>fold</functionref></related>"
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!

"<argument name='f'>The function to use</argument>
<argument name='xs'>The first array</argument>
<argument name='ys'>The second array</argument>
<summary>Map a function across two arrays.</summary>
<prose>Returns the array created by applying function <variable>f</variable> to every pairwise elements of <variable>xs</variable> and <variable>ys</variable>. If the arrays are of different lengths, then the resulting array will be the same size as the shorter of the two input arrays.</prose>
<prose>The function must take <code>xs[0]</code> and <code>ys[0]</code> to give <code>zs[0]</code> and so on.</prose>
<example>Int sum(Int a, Int b) {
    return a+b;
}

Void main() {
    xs = [1,2,3,4,5];
    ys = [7,8,9];
    zs = zipWith(sum,xs,ys);
// zs = [8,10,12];
}</example>
<related><functionref>map</functionref></related>
<related><functionref>zip</functionref></related>"
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;
}

"<argument name='xs'>The first list</argument>
<argument name='xs'>The second list</argument>
<summary>Turn a pair of lists into a list of pairs.</summary>
<prose>Turn a pair of lists into a list of pairs. This is equivalent to using <functionref>zipWith</functionref> with this function:</prose>
<example>(a,b) zipfn(a fst, b snd) {
    return (a,b);
}</example>
<related><functionref>zipWith</functionref></related>"
public [(a,b)] zip([a] xs, [b] ys) {
    return zipWith(\(a,b) -> (a,b), xs, ys);
}


"<argument name='f'>The function to use</argument>
<argument name='xs'>The array</argument>
<argument name='acc'>The initial value for folding.</argument>
<summary>Fold an array.</summary>
<prose>Applies a function across an array. For example, given a function <code>sum</code> which adds two integers:</prose>
<example>total = fold(sum,[1,2,3,4,5],0);
putStrLn(String(total));</example>
<prose>This prints the sum of the values in the array <code>[1,2,3,4,5]</code>. The following example uses <code>fold</code> to calculate the final direction.</prose>
<example>data Direction = North | East | South | West;
data Turn = Left | Right;
Direction doTurn(Turn turn, Direction current) {
    case turn of {
        Left -> case current of {
            North -> new = West;
            | West -> new = South;
            | South -> new = East;
            | East -> new = North;
        }
        | Right -> case current of {
            North -> new = East;
            | West -> new = North;
            | South -> new = West;
            | East -> new = South;
        } 
    }
    return new;
}

Void main() {
    turns = [Left,Left,Left,Right,Right,Left,Right,Left,Left];
    original = West;
    final = fold(doTurn,turns,original);
    // final = North
}</example>
<related><functionref>map</functionref></related>"
public b fold (b(a,b) f, [a] xs, b acc) {
    for x in xs {
	acc = f(x,acc);
    }
    return acc;
}

"<argument name='p'>The predicate to test against</argument>
<argument name='xs'>The array to filter</argument>
<summary>Filter a list according to a predicate.</summary>
<prose>Each element of <variable>xs</variable> is tested against the predicate <variable>p</variable>.
The returned list contains those elements of <variable>xs</variable> for which the predicate is true. The predicate function may of course be partially applied for ease of programming.</prose>
<example>Bool isDiv(Int d,Int a) {
    return (a%d==0);
}

Void main() {
    ints = [1,2,3,4,5,6,7,8];
    odds = filter(isDiv@(3),ints);
    // odds = [3,6];
}</example>
<prose>Naturally, <code>all(p,filter(p,xs)) == any(p,xs)</code>.</prose>
<related><functionref>any</functionref></related>
<related><functionref>all</functionref></related>"
public [a] filter(Bool(a) p, [a] xs) {
    newxs = createArray(size(xs));
    for x in xs {
	if (p(x)) push(newxs,x);
    }
    return newxs;
}

"<argument name='array'>The array</argument>
<argument name='v'>The value to push</argument>
<summary>Push a value onto the end of an array.</summary>
<prose>Push a value onto the end of an array.</prose>
<example>array = [1,2,3];
push(array,4);
// array = [1,2,3,4]</example>
<related><functionref>addAt</functionref></related>
<related><functionref>pop</functionref></related>
<related><functionref>shift</functionref></related>
<related><functionref>unshift</functionref></related>"
public Void push(var [a] array, a v)
{
    array[size(array)]=v;
}

"<argument name='array'>The array</argument>
<summary>Return the last value in an array</summary>
<prose>Return the last value in an array</prose>
<related><functionref>pop</functionref></related>"
public a top([a] array) 
{
    if (size(array)<=0) {
	throw(OutOfBounds);
    }
    return array[size(array)-1];
}

"<argument name='array'>The array</argument>
<summary>Remove a value from the end of an array</summary>
<prose>Remove a value from the end of an array</prose>
<example>array = [1,2,3];
pop(array);
// array = [1,2]</example>
<related><functionref>push</functionref></related>
<related><functionref>removeAt</functionref></related>
<related><functionref>shift</functionref></related>
<related><functionref>top</functionref></related>
<related><functionref>unshift</functionref></related>"
public Void pop(var [a] array) {
    if (size(array)<=0) {
	throw(OutOfBounds);
    }
    shortenArray(array);    
}

"<argument name='array'>The array</argument>
<summary>Get the first item off an array, and remove it from the array.</summary>
<prose>Get the first item off an array, and remove it from the array.</prose>
<example>array = [1,2,3];
v = shift(array);
// array = [2,3]; v = 1;</example>
<related><functionref>push</functionref></related>
<related><functionref>pop</functionref></related>
<related><functionref>removeAt</functionref></related>
<related><functionref>unshift</functionref></related>"
public a shift(var [a] array)
{
    if (size(array)==0) {
	throw(OutOfBounds);
    }
    return shiftArray(array);
}

"<argument name='val'>The value to unshift</argument>
<argument name='array'>The array</argument>
<summary>Add a value onto the start of an array.</summary>
<prose>Add a value onto the start of an array.</prose>
<example>array = [1,2,3];
unshift(array,4);
// array = [4,1,2,3]</example>
<related><functionref>addAt</functionref></related>
<related><functionref>push</functionref></related>
<related><functionref>pop</functionref></related>
<related><functionref>shift</functionref></related>"
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; */
  unshiftArray(val,array);
}

"<argument name='array'>The array to act on</argument>
<argument name='pos'>The starting index</argument>
<argument name='n'>The number of elements to retrieve</argument>
<summary>Return a subarray</summary>
<prose>Return the subarray starting at position <variable>pos</variable>, <variable>n</variable> elements long. An Exception is thrown if the subarray will not fit entirely within the array.</prose>
<example>array = [1,2,3,4,5,6,7];
sub = subarray(array,3,2);
// sub = [4,5]</example>
<related><functionref>remove</functionref></related>
<related><functionref>Prelude::substr</functionref></related>"
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;
}

"<argument name='array'>The array to act on</argument>
<argument name='pos'>The starting index</argument>
<argument name='n'>The number of elements to remove</argument>
<summary>Return the array created by removing a subarray.</summary>
<prose>Return the array created by removing a subarray starting at position <variable>pos</variable>, <variable>n</variable> elements long.</prose>
<example>array = [1,2,3,4,5,6,7];
rem = remove(array,3,2);
// array = [1,2,3,6,7]; rem = [4,5]</example>
<related><functionref>subarray</functionref></related>
<related><functionref>removeAt</functionref></related>"
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;
}

"<argument name='array'>The array to act on</argument>
<argument name='idx'>The index of the element to remove</argument>
<summary>Remove an element from an array</summary>
<prose>Remove (in-place) the element at position <variable>idx</variable>.</prose>
<example>array = [1,2,3,4,5,6,7];
removeAt(array,2);
// array = [1,2,4,5,6,7];</example>
<related><functionref>remove</functionref></related>
<related><functionref>addAt</functionref></related>"
public Void removeAt(var [a] array, Int idx)
{
    if (size(array)<=idx || idx < 0) {
	throw(OutOfBounds);
    }
    for(i=idx;i<(size(array)-1);i=i+1) {
	array[i]=array[i+1];
    }
    shortenArray(array);
}

// idx = 0 is equivalent to unshift, idx = size(array) is equivalent to push
"<argument name='array'>The array to act on</argument>
<argument name='elem'>The new element</argument>
<argument name='idx'>The index of the element to add before</argument>
<summary>Add an element to an array</summary>
<prose>Add (in-place) an element before position <variable>idx</variable>.</prose>
<example>array = [1,2,3,4,5,6,7];
addAt(array,5,2);
// array = [1,2,5,3,4,5,6,7];</example>
<related><functionref>push</functionref> is equivalent to <code>idx = size(array)</code></related>
<related><functionref>removeAt</functionref></related>
<related><functionref>unshift</functionref> is equivalent to <code>idx = 0</code></related>"
public Void addAt(var [a] array, a elem, Int idx)
{
    if (size(array)<idx || idx < 0) {
      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;
    }
}

"<argument name='val'>The value to search for (\"needle\")</argument>
<argument name='list'>The list to search (\"haystack\")</argument>
<argument name='eq'>Optionally, the function used to check for presence (the default is <functionref>Builtins::equal</functionref>, obviously, but <functionref>Builtins::identical</functionref> might be used)</argument>
<summary>Check whether a value is in a list.</summary>
<prose>Check whether the \"needle\" occurs at least once in the \"haystack\". This function can be thought of as a specialised version of <functionref>any</functionref></prose>
<related><functionref>any</functionref></related>
<related><functionref>Builtins::equal</functionref></related>
<related><functionref>Builtins::identical</functionref></related>"
public Bool elem(a val, [a] list, Bool(a,a) eq = equal) {
  for x in list {
    if (eq(x,val)) {
      return true;
    }
  }
  return false;
}

"<argument name='xs'>The list</argument>
<argument name='eq'>Optionally, the equality test. Defaults to <functionref>Builtins::equal</functionref>.</argument>
<summary>Remove repeated elements from a list.</summary>
<prose>Remove repeated elements from a list in-place. Repeated elements will be removed whether adjacent or not.</prose>
<example>xs = [1,2,3,3,1,2,4,5,2,2,1];
nub(xs);
// xs = [1,2,3,4,5]</example>
<prose>The name 'nub', incidentally, is borrowed from the Haskell prelude function of the same name, and suggests 'essence'.</prose>"
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++;
	}
    }
}

"<argument name='x'>The number of elements to take</argument>
<argument name='xs'>The array of elements</argument>
<summary>Take the first <variable>x</variable> elements from an array.</summary>
<prose>Take the first <variable>x</variable> elements from an array, and return a new array, leaving the original unmodified. This is equivalent to <code>subarray(xs,0,x)</code>.</prose>
<related><functionref>subarray</functionref></related>"
public [a] take(Int x, [a] xs) = subarray(xs,0,x);