/** -*-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>Sets: collections of unique values</summary>
<prose>This module contains two implementations for collections of unique values. <dataref>Set</dataref> stores the values in order, whereas <dataref>HashSet</dataref> is unordered but has faster insertion and lookup. The <moduleref>Dict</moduleref> module may also be useful.</prose>"
module Set;

import Prelude;

"<summary>Collection of unique values.</summary>
<prose>A collection of unique values stored as a hash table, which is usually faster than a <dataref>Set</dataref> but loses ordering.</prose>"
abstract data HashSet<a>([[a]] entries, Int buckets, Int(a) hashfn);

// TODO: If it seems worth it, replace this with a balanced binary tree.
// The current version will be too slow for big sets where elements are 
// inserted in some kind of order.
data STree<a> = leaf | node(STree<a> left, a val, STree<a> right);

"<summary>Ordered collection of unique values.</summary>
<prose>An ordered collection of unique values stored as a binary tree. If ordering is not crucial, then <dataref>HashSet</dataref> is likely to be faster. Sets may be iterated over using a <code>for</code> loop.</prose>"
abstract data Set<a>(STree<a> entries, Int(a,a) cmp);

"<argument name='cmp'>The comparison function to use for ordering. It must take two parameters, returning a negative number if the first parameter is smaller (whatever 'smaller' means in this context), positive if it is bigger, and zero if the two parameters are equal. For Ints, for example, the function <code>Int icmp(Int a, Int b) = a-b;</code> could be used. This argument may be omitted and defaults to <functionref>Builtins::compare</functionref>.</argument>
<summary>Create a new empty set.</summary>
<prose>Create a new empty set.</prose>
<related><dataref>Set</dataref></related>
<related><functionref index='1'>add</functionref></related>
<related><functionref index='1'>array</functionref></related>
<related><functionref index='1'>delete</functionref></related>
<related><functionref index='1'>elem</functionref></related>
<related><functionref index='1'>empty</functionref></related>"
public Set<a> newSet(Int(a,a) cmp = compare) = Set(leaf, cmp);

"<argument name='set'>The set to add to</argument>
<argument name='val'>The value to add</argument>
<summary>Add an element into a Set.</summary>
<prose>Add a new element to a Set. If the value is already in the set, does nothing.</prose>
<related><dataref>Set</dataref></related>
<related><functionref index='1'>array</functionref></related>
<related><functionref index='1'>delete</functionref></related>
<related><functionref index='1'>elem</functionref></related>
<related><functionref index='1'>empty</functionref></related>
<related><functionref>newSet</functionref></related>"
public Void add(var Set<a> set, a val)
{
    add(set.entries,set.cmp,val);
}

Void add(var STree<a> t, Int(a,a) cmp, a val)
{
    case t of {
	leaf -> 
	    t = node(leaf, val, leaf);
            return;
      | node(l,v,r) ->
	    cv = cmp(val,v);
	    if (cv<0) {
		add(l, cmp, val); 
		t.left = l;
	    }
	    else if (cv==0) return;
	    else {
		add(r, cmp, val);
		t.right = r;
	    }
    }
}

"<argument name='val'>The value to check for</argument>
<argument name='set'>The set to check</argument>
<summary>Check for an element in a Set.</summary>
<prose>Returns true if the value exists in the set, and false otherwise.</prose>
<related><dataref>Set</dataref></related>
<related><functionref index='1'>add</functionref></related>
<related><functionref index='1'>array</functionref></related>
<related><functionref index='1'>delete</functionref></related>
<related><functionref index='1'>empty</functionref></related>
<related><functionref>newSet</functionref></related>"
public Bool elem(a val, Set<a> set)
{
    t = set.entries;
    repeat case t of {
	leaf -> return false;
      | node(l,v,r) ->
	    cv = set.cmp(val,v);
            if (cv<0) t = l;
	    else if (cv==0) return true;
	    else t = r;
    }
    return false;
}

"<argument name='set'>The set to delete from</argument>
<argument name='val'>The value to delete</argument>
<summary>Remove an element from a Set.</summary>
<prose>Remove an element from a Set. If the value is not in the set, does nothing.</prose>
<related><dataref>Set</dataref></related>
<related><functionref index='1'>add</functionref></related>
<related><functionref index='1'>array</functionref></related>
<related><functionref index='1'>elem</functionref></related>
<related><functionref index='1'>empty</functionref></related>
<related><functionref>newSet</functionref></related>"
public Void delete(var Set<a> set, a val)
{
    delete(set.entries, val, set.cmp);
}

"<argument name='block'>The block of code to execute for each set element.</argument>
<argument name='set'>The set to traverse</argument>
<summary>Iteration over Sets</summary>
<prose>Used by <code>for</code> loops to traverse <dataref>Set</dataref> data structure. It is unlikely that you will need to call this function directly.</prose>"
public Void traverse(Bool(a, Int) block, Set<a> set) {
    traverseAux(0, block, set.entries);
}

Void traverseAux(var Int i, Bool(a,Int) block, STree<a> t) {
    case t of {
	leaf -> return;
	| node(l,v,r) -> 
	      traverseAux(i, block, l);
              if (!block(v, i)) return;
	      i=i+1;
	      traverseAux(i, block, r);
    }
}

Void delete(var STree<a> t, a val, Int(a,a) cmp)
{
    // First find the node
    case t of {
	leaf -> return; // phew, easy
      | node(l,v,r) ->
	    cv = cmp(val,v);
	    if (cv<0) {
		delete(l, val, cmp);
		t.left = l;
	    } else if (cv == 0) {
		// Found it
		deleteRoot(t);
	    } else {
		delete(r, val, cmp);
		t.right = r;
	    }
    }
}

Void deleteRoot(var STree<a> t)
{
    // No left child, replace with right child.
    // (Obviously works if no child at all, since t then becomes a leaf)
    if (t.left==leaf) {
//	putStrLn("in case 1");
	t = t.right;
	return;
    }
    // No right child, replace node with left child.
    if (t.right==leaf) {
//	putStrLn("in case 2");
	t = t.left;
	return;
    }
    // Now we definitely have two children
    // Find the leftmost value in the right tree and use that as the
    // value of the node.
    val = deleteLeftmost(t.right);
    t.val = val;
}

a deleteLeftmost(var STree<a> t)
{
//    putStrLn("in deleteLeftmost");
    if (t.left == leaf) {
	val = t.val;
	t = t.right;
	return val;
    } else {
	return deleteLeftmost(t.left);
    }
}


"<argument name='set'>The set to check</argument>
<summary>Check whether a Set is empty</summary>
<prose>Returns true if the Set is empty, false otherwise.</prose>
<related><dataref>Set</dataref></related>
<related><functionref index='1'>add</functionref></related>
<related><functionref index='1'>array</functionref></related>
<related><functionref index='1'>delete</functionref></related>
<related><functionref index='1'>elem</functionref></related>
<related><functionref>newSet</functionref></related>"
public Bool empty(Set<a> set) = set.entries == leaf;

"<argument name='set'>The set to coerce</argument>
<summary>Return all elements of a Set</summary>
<prose>Return all the elements of a Set as an array, ordered according to the set's ordering predicate.</prose>
<related><dataref>Set</dataref></related>
<related><functionref index='1'>add</functionref></related>
<related><functionref index='1'>delete</functionref></related>
<related><functionref index='1'>elem</functionref></related>
<related><functionref index='1'>empty</functionref></related>
<related><functionref>newSet</functionref></related>"
public [a] array(Set<a> set)
{
    arr = [];
    arrAux(set.entries, arr);
    return arr;
}

Void arrAux(STree<a> t, var [a] arr)
{
    case t of {
	leaf -> ;
      | node(l,v,r) ->
	    arrAux(l, arr);
  	    push(arr,v);
	    arrAux(r, arr);
    }
}

"<argument name='buckets'>The number of hashing buckets to use. A larger number of buckets increases the speed of the dictionary (up to a limit) but uses more memory. A good choice is the nearest prime number to <code>1.5*(<variable>expected number of entries</variable>)</code>, with the default being 157.</argument>
<argument name='hashfn'>The hashing function to use. This function must take a key, and return an integer. A good hashing function will return different values for similar keys (but must of course always return the same value for the same key!). A default built-in hashing function is provided, though if the keys are of type <code>String</code>, the <functionref>Builtins::strHash</functionref> function should be used instead, and if the keys are of type <code>Int</code> you may use <functionref>Builtins::identity</functionref> (though an array may provide faster insertion and lookup if the keys are positive and either small or largely sequential). If the keys are an especially complex data type, it may again be best to write your own hashing function. This argument may be omitted and defaults to <functionref>Builtins::hash</functionref>.</argument>
<summary>Create a new empty HashSet.</summary>
<prose>Create a new empty HashSet.</prose>
<related><dataref>HashSet</dataref></related>
<related><functionref>add</functionref></related>
<related><functionref>array</functionref></related>
<related><functionref>delete</functionref></related>
<related><functionref>elem</functionref></related>
<related><functionref>empty</functionref></related>"
public HashSet<a> newHashSet(Int buckets = 157, Int(a) hashfn = hash) 
    = HashSet(createArray(buckets),buckets,hashfn);

"<argument name='block'>The block of code to execute for each set element.</argument>
<argument name='set'>The HashSet to traverse</argument>
<summary>Iteration over HashSets</summary>
<prose>Used by <code>for</code> loops to traverse <dataref>HashSet</dataref> data structure. It is unlikely that you will need to call this function directly.</prose>
<prose>The order in which a HashSet is traversed is undefined.</prose>"
public Void traverse(Bool(a, Int) block, HashSet<a> set) {
  i = 0;
  for ps in set.entries {
    if (isInitialised(ps)) {
      for p in ps {
	if (!block(p,i)) { return; } i++;
      }
    }
  }
}


"<argument name='set'>The set to add to</argument>
<argument name='val'>The value to add</argument>
<summary>Add an element into a HashSet.</summary>
<prose>Add a new element to a HashSet. If the value is already in the set, does nothing.</prose>
<related><dataref>HashSet</dataref></related>
<related><functionref>array</functionref></related>
<related><functionref>delete</functionref></related>
<related><functionref>elem</functionref></related>
<related><functionref>empty</functionref></related>
<related><functionref>newHashSet</functionref></related>"
public Void add(var HashSet<a> set, a key) {
    // Find the right bucket
    bucket = abs(set.hashfn(key)) % set.buckets;
    if (!isInitialised(set.entries[bucket])) {
      // shouldn't need to be very large 
      set.entries[bucket] = createArray(5);
    }
    // If a is already a key, no-op.
    for p in set.entries[bucket] {
	if (p==key) {
	    return;
	}
    }
    push(set.entries[bucket],key);
}

"<argument name='val'>The value to check for</argument>
<argument name='set'>The set to check</argument>
<summary>Check for an element in a HashSet.</summary>
<prose>Returns true if the value exists in the HashSet, and false otherwise.</prose>
<related><dataref>HashSet</dataref></related>
<related><functionref>add</functionref></related>
<related><functionref>array</functionref></related>
<related><functionref>delete</functionref></related>
<related><functionref>empty</functionref></related>
<related><functionref>newHashSet</functionref></related>"
public Bool elem(a val, HashSet<a> set) {
    // Find the right bucket
    bucket = abs(set.hashfn(val)) % set.buckets;
    d = set.entries[bucket];
    if (!isInitialised(d)) {
      // can't be here
      return false;
    }
    for p in d {
	if (p==val) {
	    return true;
	}
    }
    return false;
}

"<argument name='set'>The set to delete from</argument>
<argument name='val'>The value to delete</argument>
<summary>Remove an element from a HashSet.</summary>
<prose>Remove an element from a HashSet. If the value is not in the set, does nothing.</prose>
<related><dataref>HashSet</dataref></related>
<related><functionref>add</functionref></related>
<related><functionref>array</functionref></related>
<related><functionref>elem</functionref></related>
<related><functionref>empty</functionref></related>
<related><functionref>newHashSet</functionref></related>"
public Void delete(HashSet<a> set, a key) {
    // Find the right bucket
    bucket = abs(set.hashfn(key)) % set.buckets;
    if (!isInitialised(set.entries[bucket])) {
      return; //can't be in here
    }
    ps = set.entries[bucket];
    // If a is a key in ps, remove it.
    for z in [0..(size(ps)-1)] {
	if (ps[z]==key) {
	  removeAt(ps,z);
	  return;
	}
    }
}

"<argument name='set'>The set to check</argument>
<summary>Check whether a HashSet is empty</summary>
<prose>Returns true if the HashSet is empty, false otherwise.</prose>
<related><dataref>HashSet</dataref></related>
<related><functionref>add</functionref></related>
<related><functionref>array</functionref></related>
<related><functionref>delete</functionref></related>
<related><functionref>elem</functionref></related>
<related><functionref>newHashSet</functionref></related>"
public Bool empty(HashSet<a> set) {
    for ps in set.entries {
	for p in ps {
	  return false;
	}
    }
    return true;
}

"<argument name='set'>The set to coerce</argument>
<summary>Return all elements of a HashSet</summary>
<prose>Return all the elements of a HashSet as an array. The elements will be returned in an arbitrary order.</prose>
<related><dataref>HashSet</dataref></related>
<related><functionref>add</functionref></related>
<related><functionref>delete</functionref></related>
<related><functionref>elem</functionref></related>
<related><functionref>empty</functionref></related>
<related><functionref>newHashSet</functionref></related>"
public [a] array(HashSet<a> set) {
    keys = [];
    for ps in set.entries {
      if (isInitialised(ps)) {
	for p in ps {
	    push(keys,p);
	}
      }
    }
    return keys;
}