Short: New array efuns (with code)
Date: Fri, 16 Jul 1999 19:43:46 +0200
From: croft@UNItopia.rus.uni-stuttgart.de (Croft)
Type: Feature
State: Unclassified


Hi!
Ich habe schon vor laengerem ein Inherit mit Funktionen fuer Arrays
geschrieben und es nach und nach um mehr oder weniger nuetzlichen
Funktionen erweitert.  Ein Teil davon erfreut sich auch mittlerweile
reger Benutzung.  Zwar gehen einige der Funktionen von gutmuetigen
Arrays aus (keine Schleifen, keine Typchecks noetig,...) aber vielleicht
findest du ja die ein oder andere brauchbare Vorlage fuer eine
Efun.

Warnung: werden falsche Daten an die sefuns gegeben, gibt es gnadenlos
laufzeitfehler.

Gruss Croft

----------------------------------------------------------------------
/* Inherit fuer Arrayhilfsfunktionen.

   varargs mixed construct_array(int size, closure constructor,
                                 mixed first, mixed args);
       Konstruiert einen Array der Groesse size mit Hilfe der Closure
       constructor.  first ist das erste Element des Arrays.  Die
       Closure wird mit vorherigen Element und args aufgerufen.

       Beispiel:
           construct_array(5, #'+, 1, 1) -> ({ 1,2,3,4,5 })


   varargs mixed init_array(int size, mixed val);
       Erzeugt einen Array der Groesse size und initialisiert alle
       Elemente mit val.  Allerdings ergeben sich bei komplizierten
       Strukturen von val Probleme.  Falls val z.b. ein mehrfach
       verschachtelter Array ist, so haben spaetere Aenderungen an
       einem Element Auswirkungen auf die anderen Elemente.

       Beispiel:
           init_array(5, 42) -> ({ 42, 42, 42, 42, 42 })


   varargs mixed fill_array(mixed arr, int size, mixed val);
       Fuellt den Array arr auf Groesse size auf.  Falls val angegeben
       wird so werden neue Elemente mit val initialisiert, ansonsten
       0.  Falls arr schon groesser als size ist passiert nichts.

       Beispiel:
           fill_array(({ 1, 2, 3 }), 5, -1) -> ({ 1, 2, 3, -1, -1 })


   mixed reduce_array(mixed arr, closure operator);
       Reduziert den Array arr mit Hilfe des Operators operator auf ein
       Element. Einige Operatoren sind vordefiniert (Summe, Produkt,
       Minimum, Maximum, And, Or).

       Beispiele:
           reduce_array(({ 1,2,3,4 }), #'reduce_fun_max) -> 4
           reduce_array(({ 1,2,3,4 }), #'reduce_fun_min) -> 1
           reduce_array(({ 1,2,3,4 }), #'reduce_fun_pro) -> 24
           reduce_array(({ 1,2,3,4 }), #'reduce_fun_sum) -> 10
           reduce_array(({ 0,0,0,4 }), #'reduce_fun_or)  -> 4
           reduce_array(({ 1,2,3,0 }), #'reduce_fun_and) -> 0


    mixed operate_arrays(mixed arr1, mixed arr2, closure operator);
        Verknuepft die Arrays arr1 und arr2 elementweise ueber den
        Operator operator.

        Beispiele:
            operate_arrays(({1,2,3}), ({1,2,3}), #'*) -> ({ 1,4,9 })
            operate_arrays(({1,2,3}), ({1,2,3}), #'+) -> ({ 2,4,6 })

        Mit reduce_array kann somit ein Skalarprodukt ausgerechnet werden:
            reduce_array(operate_arrays(({1,2,3}),({1,2,3}),#'*),
                #'reduce_fun_sum) -> 14


    varargs mixed shuffle_array(mixed arr, closure rand);
        Mischt das Array arr und gibt das gemischte Array zurueck.
        rand ist die Randomfunktion die verwendet wird (default random).

        Beispiel:
            shuffle_array(({ 1,2,3,4,5 })) -> ({ 4,2,3,1,5 })


    mixed reverse_array(mixed arr);
        Dreht den Array arr herum.

        Beispiel:
            reverse_array(({ 1,2,3 })) -> ({ 3,2,1 })


    varargs int equal_arrays(mixed arr1, mixed arr2, closure not_equal);
        Vergleicht zwei Arrays elementweise auf Gleichheit.  Falls
        not_equal nicht angegeben ist, wird != verwendet.
        Aufwand O(sizeof(arr1))

        Beispiel:
            equal_arrays(({ 1,2,3,4,5 }), ({ 1,2,3,4,6 })) -> 0

            int neq(mixed a, mixed b) {
                return a[1] != b[1];
            }
            equal_arrays(({ ({1,1}),({1,2}),({2,1}),({2,2}) }),
                         ({ ({2,1}),({2,2}),({1,1}),({1,2}) }),
                         #'neq) -> 1


    varargs mixed unify_array(mixed arr, closure not_equal);
        Entfernt aus einem Array mehrfach vorkommende Werte.  Wenn
        eine Closure angeben ist, so wird diese bemueht um gleiche
        Elemente herauszufiltern, ansonsten ist es einfach !=.  Bei
        gleichen Elementen wird das "weiter vorne stehende" Element
        (kleinerer Index) behalten.

        Beispiel:
            unify_array(({1,1,2,1,4,2,3,3,3,2,0})) -> ({ 1,2,4,3,0 })

            int neq(mixed a, mixed b) {
                return a[1] != b[1];
            }
            unify_array(({({1,1}),({1,2}),({2,1}),({2,2})}), #'neq)
                -> ({ ({ 1,1 }), ({ 1,2 }) })


    varargs mapping classify_array(mixed arr, closure not_equal);
        Prinzipiell aehnlich zu unify_array nur werden hier die Anzahl
        der einzelnen Werte in ein Mapping eingetragen.

        Beispiel:
            classify_array(({ 1, 2, 3, 4, 5, 1, 2, 4, 8 }))
                -> ([ 2:2, 5:1, 1:2, 8:1, 4:2, 3:1 ])


    varargs mixed split_array(mixed arr, int amount, int flag);
        Teilt einen Array gleichmaessig auf.  Amount ist, wenn das
        Flag nicht gesetzt, die Anzahl der Teilstuecke (Defaultwert 2)
        (Anzahl < sizeof(arr)/2 sollte hier erfuellt sein, sonst wird
        ein kleineres Array zurueckgeliefert mit lauter Teilstuecken
        der Groesse 2 und evtl. einem mit Groesse 1) und wenn das Flag
        gesetzt ist die Groesse der Teilstuecke (Defaultwert 1).
        Zurueckgeliefert wird dann ({ Teil1, Teil2, ... }).  Alle
        Teilstuecke ausser dem Letzten haben dieselbe Groesse.

        Beispiel:
            split_array(({1,2,3,4,5}))
                -> ({({1,2,3}),({4,5})})
            split_array(({1,2,3,4,5,6,7}),3)
                -> ({({1,2,3}),({4,5,6}),({7})})
            split_array(({1,2,3,4,5}),2,1)
                -> ({({1,2}),({3,4}),({5,6}),({7})})


    mixed flatten_array(mixed arr);
        Ein verschachtelter Array wird verflacht.
        Hat allerdings Probleme bei Arrays mit Schleifen.

        Beispiel:
            flatten_array(({({ 1, 2, ({ 3, 4 }), 5 }), 6, ({ 7, 8 }) }))
                -> ({ 1, 2, 3, 4, 5, 6, 7, 8 })


    varargs mixed max_of_array(mixed arr, closure greater);
        Liefert das Maximum des Arrays zurueck.  Die Closure ist
        optional, default ist >.

        Beispiel:
            max_of_array(({ 1, 2, 3, 4, 5, 1, 2, 4, 8 })) -> 8
            max_of_array(({ 1, 2, 3, 4, 5, 1, 2, 4, 8 }), #'<) -> 1


    varargs mixed i_max_of_array(mixed arr, closure greater);
        Wie max_of_array, nur das der Index zurueckgeliefert wird und
        nicht das Element.


    varargs int choose_from_array(mixed arr, mixed pool, closure rand);
        Waehlt aus arr zufaellig (mit Hilfe der Closure rand oder
        Default einfach mit random) ein Element aus und returned einen
        "unbenutzen" INDEX.  Aus pool wird das Element entfernt.
        Falls pool leer ist, wird es anhand der Groesse von arr
        neuinitialisiert. pool ist also nur Variable zum Speichern der
        bereits benutzen Indices.  Arr kann auch ein Integer mit der
        Groesse des Arrays sein, da im Falle pointerp(arr) nur die
        Groesse verwendet wird.
        WICHTIG: pool muss als REFERENZ uebergeben werden!!!
        Damit kann man z.B. aus mehreren Probleme eins auswaehlen ohne
        das die Probleme sich all zu schnell wiederholen.
        (Urnenmodel ohne Zuruecklegen)

        Beispiel:
            problem = choose_from_array(problems, &unused);

        unused = 0;
        choose_from_array(({ 1, 2, 3, 4, 5}), &unused) -> 2
            unused waer dann ({ 0, 1, 3, 4 })
        choose_from_array(({ 1, 2, 3, 4, 5}), &unused) -> 4
            unused waer dann ({ 0, 1, 3 })

        choose_from_array(5, &unused) waer genau dasselbe


    varargs mixed select_from_array(mixed arr, int m, closure rand);
        Waehlt m Elemente zufaellig aus arr aus (mit Hilfe der Closure
        rand oder Default einfach mit random).  Die Elemente bleiben
        in der selben Reihenfolge wie in arr.
        Aufwand O(sizeof(arr)) falls m > 1
        Aufwand O(1) falls m <= 1

        Beispiel:
            select_from_array(({1,2,3,4,5,6,7,8}), 3) -> ({ 2, 3, 7 })


    varargs mixed members_of_array(mixed key, mixed arr, closure equal);
        Returned alle Indices des key's in arr.  Falls equal angeben
        ist wird die Closure bemueht die Gleichheit zu testen,
        ansonsten wird == benutzt.

        Beispiel:
            members_of_array(1, ({ 1, 2, 3, 4, 1 })) ->
                ({ 0, 4 })

            int eq(mixed a, mixed b) {
                return a[1] == b[1];
            }
            members_of_array(({0,1}),({({0,1}),({2,2}),({2,1})}), #'eq) ->
                ({ 0, 2 })


    int in_array(mixed key, mixed arr);
        Liefert 1 wenn key in arr sonst 0. Man spart sich den Test auf
        != -1 im Vergleich zu member_array und kann so die Funktion
        besser als Parameter fuer filter_array einsetzen. Somit ist es
        recht einfach moeglich Arrays (Mengen) miteinander schneiden.

        Beispiel:
            filter_array(({ 2,3,4,5 }) , #'in_array, ({ 1,2,5,8 }))
                -> ({ 2,5 })

        Schneller ist es allerdings ({ 2,3,4,5 }) & ({ 1,2,5,8 })
        zu verwenden.
*/

// 12. 6.98  Croft  flatten_array eingebaut
// 13. 6.98  Croft  Doku fuer Enzy eingebaut
// 14. 6.98  Croft  select_from_array eingebaut
// 18. 6.98  Croft  Tuning von construct_array und max_of_array
//                  init_array eingebaut
//  1. 7.98  Croft  init_array modifiziert
// 15. 9.98  Croft  reverse_array eingebaut
// 12. 1.99  Croft  shuffle_array optimiert
// 18. 1.99  Croft  equal_arrays eingebaut
// 17. 2.99  Croft  fill_array eingebaut

#pragma save_types
#pragma strict_types
#pragma verbose_errors

#include <error.h>
#include "../sys/math.h"

private mixed construct_element(mixed item, closure constructor, mixed val, mixed args);
varargs mixed construct_array(int size, closure constructor, mixed first, mixed args);
private mixed init_element(mixed a, mixed b);
private mixed init_pointer_element(mixed a, mixed b);
private mixed init_mapping_element(mixed a, mixed b);
varargs mixed init_array(int size, mixed val);
varargs mixed fill_array(mixed arr, int size, mixed val);
mixed reduce_array(mixed arr, closure operator);
void reduce_fun_max(mixed a, mixed erg);
void reduce_fun_min(mixed a, mixed erg);
void reduce_fun_pro(mixed a, mixed erg);
void reduce_fun_sum(mixed a, mixed erg);
void reduce_fun_or(mixed a, mixed erg);
void reduce_fun_and(mixed a, mixed erg);
private mixed operate_elements(mixed element, closure operator);
mixed operate_arrays(mixed arr1, mixed arr2, closure operator);
varargs mixed shuffle_array(mixed arr, closure rand);
mixed reverse_array(mixed arr);
varargs int equal_arrays(mixed arr1, mixed arr2, closure not_equal);
varargs mixed unify_array(mixed arr, closure not_equal);
varargs mapping classify_array(mixed arr, closure not_equal);
varargs mixed split_array(mixed arr, int amount, int flag);
mixed flatten_array(mixed arr);
private mixed max_of(mixed a, mixed b);
private mixed closure_max_of(mixed a, mixed b, closure greater);
varargs mixed max_of_array(mixed arr, closure greater);
varargs mixed i_max_of_array(mixed arr, closure greater);
varargs int choose_from_array(mixed arr, mixed pool, closure rand);
varargs mixed select_from_array(mixed arr, int m, closure rand);
varargs mixed members_of_array(mixed key, mixed arr, closure equal);
int in_array(mixed key, mixed arr);


private mixed construct_element(mixed item, closure constructor, mixed val, mixed args) {
    val =  funcall(constructor, val, args);
    return val;
}


/*
FUNKTION: construct_array
DEKLARATION: mixed construct_array(int size, closure constructor, [mixed first, [mixed args]]);
BESCHREIBUNG:
Konstruiert einen Array der Groesse size mit Hilfe der Closure constructor.
first ist das erste Element des Arrays.  Die Closure wird mit vorherigen
Element und args aufgerufen.
Aufwand O(size) falls der constructor nicht allzu wild ist ;-)

Beispiel:
    construct_array(5, #'+, 1, 1) -> ({ 1,2,3,4,5 })
VERWEISE: allocate, init_array
GRUPPEN: array
*/
varargs mixed construct_array(int size, closure constructor, mixed first, mixed args) {
    mixed erg, tmp;

    if ((size < 0) || (size > 3000)) {
        do_error("construct_array: Illegal array size: "+size+".\n");
        return 0;
    }

    if (!size) {
        return ({});
    }

    if (!closurep(constructor)) {
        do_error("construct_array: Parameter 2 muss eine Closure sein.\n");
        return 0;
    }

    erg = allocate(size);
    erg[0] = (tmp = first);
    erg[1..<1] = map_array(erg[1..<1], #'construct_element, //'
                     constructor, &tmp, args);
    return erg;
}


private mixed init_element(mixed a, mixed b) {
    return b;
}


private mixed init_pointer_element(mixed a, mixed b) {
    return ({})+b;
}


private mixed init_mapping_element(mixed a, mixed b) {
    return copy_mapping(b);
}


/*
FUNKTION: init_array
DEKLARATION: mixed init_array(int size, [mixed val]);
BESCHREIBUNG:
Erzeugt einen Array der Groesse size und initialisiert alle Elemente
mit val.  Allerdings ergeben sich bei komplizierten Strukturen von val
Probleme.  Falls val z.b. ein mehrfach verschachtelter Array ist, so
haben spaetere Aenderungen an einem Element Auswirkungen auf die
anderen Elemente.

Beispiel:
    init_array(5, 42) -> ({ 42, 42, 42, 42, 42 })
VERWEISE: allocate, construct_array, fill_array
GRUPPEN: array
*/
varargs mixed init_array(int size, mixed val) {
    if ((size < 0) || (size > 3000)) {
        do_error("init_array: Illegal array size: "+size+".\n");
        return 0;
    }

    if (val) {
        if (pointerp(val)) {
            return map_array(allocate(size), #'init_pointer_element, //'
                   val);
        } else
        if (mappingp(val)) {
            return map_array(allocate(size), #'init_mapping_element, //'
                   val);
        } else {
            return map_array(allocate(size), #'init_element, //'
                   val);
        }
    } else {
        return allocate(size);
    }
}


/*
FUNKTION: fill_array
DEKLARATION: mixed fill_array(mixed arr, int size, [mixed val]) {
BESCHREIBUNG:
Fuellt den Array arr auf Groesse size auf.  Falls val angegeben wird
so werden neue Elemente mit val initialisiert, ansonsten 0.  Falls arr
schon groesser als size ist passiert nichts.

Beispiel:
    fill_array(({1,2,3,4}), 5, -1) -> ({ 1, 2, 3, 4, -1 })
VERWEISE: init_array
GRUPPEN: array
*/
varargs mixed fill_array(mixed arr, int size, mixed val) {
    if (!pointerp(arr)) {
        do_error("fill_array: Parameter 1 muss ein Array sein.\n");
        return 0;
    }
    if (size < 0) {
        do_error("fill_array: Parameter 2 muss ein Integer >= 0 sein.\n");
        return 0;
    }
    if (sizeof(arr) >= size) {
        return ({}) + arr;
    }
    return ({}) + arr + init_array(size-sizeof(arr), val);
}


/*
FUNKTION: reduce_array
DEKLARATION: mixed reduce_array(mixed arr, closure operator);
BESCHREIBUNG:
Reduziert den Array arr mit Hilfe des Operators operator auf ein
Element. Einige Operatoren sind vordefiniert (Summe, Produkt, Minimum,
Maximum, And, Or).
Aufwand O(sizeof(arr))

Beispiele:
    reduce_array(({ 1,2,3,4 }), #'reduce_fun_max) -> 4
    reduce_array(({ 1,2,3,4 }), #'reduce_fun_min) -> 1
    reduce_array(({ 1,2,3,4 }), #'reduce_fun_pro) -> 24
    reduce_array(({ 1,2,3,4 }), #'reduce_fun_sum) -> 10
    reduce_array(({ 0,0,0,4 }), #'reduce_fun_or)  -> 4
    reduce_array(({ 1,2,3,0 }), #'reduce_fun_and) -> 0
GRUPPEN: array
*/
mixed reduce_array(mixed arr, closure operator) {
    mixed erg;

    if (!pointerp(arr)) {
        do_error("reduce_array: Parameter 1 muss ein Array sein.\n");
        return 0;
    }
    switch (sizeof(arr)) {
    case 0: return 0;
    case 1: return arr[0];
    default:
        erg = arr[0];
        map_array(arr[1..<1], operator, &erg);
    }
    return erg;
}


/*
FUNKTION: reduce_fun_max
DEKLARATION: void reduce_fun_max(mixed a, mixed erg);
BESCHREIBUNG:
Reduce-Operator zur Maximumfindung fuer reduce_array.
Aufwand O(1)
VERWEISE: reduce_array
GRUPPEN: array
*/
void reduce_fun_max(mixed a, mixed erg) {
    erg = (erg > a ? erg : a);
}


/*
FUNKTION: reduce_fun_min
DEKLARATION: void reduce_fun_min(mixed a, mixed erg);
BESCHREIBUNG:
Reduce-Operator zur Minimumfindung fuer reduce_array.
Aufwand O(1)
VERWEISE: reduce_array
GRUPPEN: array
*/
void reduce_fun_min(mixed a, mixed erg) {
    erg = (erg < a ? erg : a);
}


/*
FUNKTION: reduce_fun_pro
DEKLARATION: void reduce_fun_pro(mixed a, mixed erg);
BESCHREIBUNG:
Reduce-Operator zur Produktbildung fuer reduce_array.
Aufwand O(1)
VERWEISE: reduce_array
GRUPPEN: array
*/
void reduce_fun_pro(mixed a, mixed erg) {
    erg *= a;
}


/*
FUNKTION: reduce_fun_sum
DEKLARATION: void reduce_fun_sum(mixed a, mixed erg);
BESCHREIBUNG:
Reduce-Operator zur Summenbildung fuer reduce_array.
Aufwand O(1)
VERWEISE: reduce_array
GRUPPEN: array
*/
void reduce_fun_sum(mixed a, mixed erg) {
    erg += a;
}


/*
FUNKTION: reduce_fun_or
DEKLARATION: void reduce_fun_or(mixed a, mixed erg);
BESCHREIBUNG:
Reduce-Operator um das erste Element != 0 zu finden bzw. 0 falls Array nur
aus 0en besteht fuer reduce_array.
Aufwand O(1)
VERWEISE: reduce_array
GRUPPEN: array
*/
void reduce_fun_or(mixed a, mixed erg) {
    erg = erg || a;
}


/*
FUNKTION: reduce_fun_and
DEKLARATION: void reduce_fun_and(mixed a, mixed erg);
BESCHREIBUNG:
Reduce-Operator um zu Testen ob ein Array aus lauter Elementen != 0 besteht,
falls ja dann wird das letzte Element != 0 zurueckgeliefert, sonst 0.  Fuer
reduce_array.
Aufwand O(1)
VERWEISE: reduce_array
GRUPPEN: array
*/
void reduce_fun_and(mixed a, mixed erg) {
    erg = erg && a;
}


private mixed operate_elements(mixed element, closure operator) {
    return funcall(operator, element[0], element[1]);
}


/*
FUNKTION: operate_arrays
DEKLARATION: mixed operate_arrays(mixed arr1, mixed arr2, closure operator);
BESCHREIBUNG:
Verknuepft die Arrays arr1 und arr2 elementweise ueber den Operator
operator.
Aufwand O(max(sizeof(arr1),sizeof(arr2)))

Beispiele:
    operate_arrays(({1,2,3}), ({1,2,3}), #'*) -> ({ 1,4,9 })
    operate_arrays(({1,2,3}), ({1,2,3}), #'+) -> ({ 2,4,6 })

Mit reduce_array kann somit ein Skalarprodukt ausgerechnet werden:
    reduce_array(operate_arrays(({1,2,3}),({1,2,3}),#'*),
        #'reduce_fun_sum) -> 14
VERWEISE: reduce_array
GRUPPEN: array
*/
mixed operate_arrays(mixed arr1, mixed arr2, closure operator) {
    if (!pointerp(arr1)) {
        do_error("operate_arrays: Parameter 1 muss ein Array sein.\n");
        return 0;
    }
    if (!pointerp(arr2)) {
        do_error("operate_arrays: Parameter 2 muss ein Array sein.\n");
        return 0;
    }
    return map_array(transpose_array(({ arr1, arr2 })), #'operate_elements, //'
        operator);
}


/*
FUNKTION: shuffle_array
DEKLARATION: mixed shuffle_array(mixed arr, [closure rand]);
BESCHREIBUNG:
Mischt das Array arr und gibt das gemischte Array zurueck.  rand ist die
Randomfunktion die verwendet wird (default random).
Aufwand O(sizeof(arr))

Beispiel:
    shuffle_array(({ 1,2,3,4,5 })) -> ({ 4,2,3,1,5 })
VERWEISE: reverse_array
GRUPPEN: array
*/
varargs mixed shuffle_array(mixed arr, closure rand) {
    int size, ran;
    mixed tmp, erg;

    if (!pointerp(arr)) {
        do_error("shuffle_array: Parameter 1 muss ein Array sein.\n");
        return 0;
    }
    erg = ({});
    tmp = ({}) + arr;
    if (closurep(rand)) {
        for (size=sizeof(arr); size--; ) {
            ran = funcall(rand, size);
            erg += ({ tmp[ran] });
            tmp -= ({ tmp[ran] = "SHUFFLE_ARRAY_DUMMY" });
        }
    } else {
        for (size=sizeof(arr); size--; ) {
            ran = random(size);
            erg += ({ tmp[ran] });
            tmp -= ({ tmp[ran] = "SHUFFLE_ARRAY_DUMMY" });
        }
    }
    return erg;
}


/*
FUNKTION: reverse_array
DEKLARATION: mixed reverse_array(mixed arr);
BESCHREIBUNG:
Dreht den Array arr herum.
Aufwand O(sizeof(arr))

Beispiel:
    reverse_array(({ 1,2,3 })) -> ({ 3,2,1 })
VERWEISE: shuffle_array
GRUPPEN: array
*/
mixed reverse_array(mixed arr) {
    int i, j;
    mixed erg;

    if (!pointerp(arr)) {
        do_error("reverse_array: Parameter 1 muss ein Array sein.\n");
        return 0;
    }
    j = sizeof(arr);
    erg = allocate(j);
    for (i=0; j--; i++) {
        erg[i] = arr[j];
    }
    return erg;
}


/*
FUNKTION: equal_arrays
DEKLARATION: int equal_arrays(mixed arr1, mixed arr2, [closure not_equal]);
BESCHREIBUNG:
Vergleicht zwei Arrays elementweise auf Gleichheit.  Falls not_equal
nicht angegeben ist, wird != verwendet.
Aufwand O(sizeof(arr1))

Beispiel:
    equal_arrays(({ 1,2,3,4,5 }), ({ 1,2,3,4,6 })) -> 0

    int neq(mixed a, mixed b) {
        return a[1] != b[1];
    }
    equal_arrays(({ ({1,1}),({1,2}),({2,1}),({2,2}) }),
                 ({ ({2,1}),({2,2}),({1,1}),({1,2}) }),
                 #'neq) -> 1
VERWEISE:
GRUPPEN: array
*/
varargs int equal_arrays(mixed arr1, mixed arr2, closure not_equal) {
    int i;

    if (!pointerp(arr1)) {
        do_error("equal_arrays: Parameter 1 muss ein Array sein.\n");
        return 0;
    }
    if (!pointerp(arr2)) {
        do_error("equal_arrays: Parameter 2 muss ein Array sein.\n");
        return 0;
    }
    if (sizeof(arr1) != sizeof(arr2)) {
        return 0;
    }
    if (closurep(not_equal)) {
        for (i = sizeof(arr1); i--; ) {
            if (funcall(not_equal, arr1[i], arr2[i])) {
                return 0;
            }
        }
    } else {
        for (i = sizeof(arr1); i--; ) {
            if (arr1[i] != arr2[i]) {
                return 0;
            }
        }
    }
    return 1;
}
/*
FUNKTION: unify_array
DEKLARATION: mixed unify_array(mixed arr, [closure not_equal]);
BESCHREIBUNG:
Entfernt aus einem Array mehrfach vorkommende Werte.  Wenn eine Closure
angeben ist, so wird diese bemueht um gleiche Elemente herauszufiltern,
ansonsten ist es einfach !=.  Bei gleichen Elementen wird das "weiter vorne
stehende" Element (kleinerer Index) behalten.
Aufwand O(sizeof(arr))

Beispiel:
    unify_array(({1,1,2,1,4,2,3,3,3,2,0})) -> ({ 1,2,4,3,0 })

    int neq(mixed a, mixed b) {
        return a[1] != b[1];
    }
    unify_array(({({1,1}),({1,2}),({2,1}),({2,2})}), #'neq)
        -> ({ ({ 1,1 }), ({ 1,2 }) })
VERWEISE: classify_array, unique_array
GRUPPEN: array
*/
varargs mixed unify_array(mixed arr, closure not_equal) {
    mixed tmp, erg;

    if (!pointerp(arr)) {
        do_error("unify_array: Parameter 1 muss ein Array sein.\n");
        return 0;
    }
    erg = ({});
    tmp = ({}) + arr;
    if (closurep(not_equal)) {
        while (sizeof(tmp)) {
            erg += ({ tmp[0] });
            tmp = filter_array(tmp, not_equal, tmp[0]);
        }
    } else {
        while (sizeof(tmp)) {
            erg += ({ tmp[0] });
            tmp -= ({ tmp[0] });
        }
    }
    return erg;
}


/*
FUNKTION: classify_array
DEKLARATION: mapping classify_array(mixed arr, [closure not_equal]);
BESCHREIBUNG:
Prinzipiell aehnlich zu unify_array nur werden hier die Anzahl der
einzelnen Werte in ein Mapping eingetragen.
Aufwand O(sizeof(arr))

Beispiel:
    classify_array(({ 1, 2, 3, 4, 5, 1, 2, 4, 8 }))
        -> ([ 2:2, 5:1, 1:2, 8:1, 4:2, 3:1 ])
VERWEISE: unify_array, unique_array
GRUPPEN: array
*/
varargs mapping classify_array(mixed arr, closure not_equal) {
    int size;
    mapping erg;
    mixed tmp, item;

    if (!pointerp(arr)) {
        do_error("classify_array: Parameter 1 muss ein Array sein.\n");
        return 0;
    }
    erg = ([]);
    tmp = ({}) + arr;
    if (closurep(not_equal)) {
        while (size = sizeof(tmp)) {
            item = tmp[0];
            tmp = filter_array(tmp, not_equal, tmp[0]);
            erg[item] = size - sizeof(tmp);
        }
    } else {
        while (size = sizeof(tmp)) {
            item = tmp[0];
            tmp -= ({ tmp[0] });
            erg[item] = size - sizeof(tmp);
        }
    }
    return erg;
}


/*
FUNKTION: split_array
DEKLARATION: mixed split_array(mixed arr, [int amount, [int flag]]);
BESCHREIBUNG:
Teilt einen Array gleichmaessig auf.  Amount ist, wenn das Flag nicht
gesetzt, die Anzahl der Teilstuecke (Defaultwert 2) (Anzahl < sizeof(arr)/2
sollte hier erfuellt sein, sonst wird ein kleineres Array zurueckgeliefert
mit lauter Teilstuecken der Groesse 2 und evtl. einem mit Groesse 1) und
wenn das Flag gesetzt ist die Groesse der Teilstuecke (Defaultwert 1).
Zurueckgeliefert wird dann ({ Teil1, Teil2, ... }).  Alle Teilstuecke
ausser dem Letzten haben dieselbe Groesse.
Aufwand O(sizeof(arr))

Beispiel:
    split_array(({1,2,3,4,5}))
        -> ({({1,2,3}),({4,5})})
    split_array(({1,2,3,4,5,6,7}),3)
        -> ({({1,2,3}),({4,5,6}),({7})})
    split_array(({1,2,3,4,5}),2,1)
        -> ({({1,2}),({3,4}),({5,6}),({7})})
VERWEISE: flatten_array
GRUPPEN: array
*/
varargs mixed split_array(mixed arr, int amount, int flag) {
    int i, size, chunk;
    mixed erg;

    if (!pointerp(arr)) {
        do_error("split_array: Parameter 1 muss ein Array sein.\n");
        return 0;
    }

    if (amount < 0) {
        do_error("select_from_array: Parameter 2 muss groesser gleich 0 sein.\n");
        return 0;
    }

    erg = ({});
    size = sizeof(arr);

    if (flag) {
        chunk = (amount || 1);
    } else {
         chunk = size / (amount || 2);
         if (size % (amount || 2)) {
             chunk++;
         }
    }

    if (chunk == 1) {
        return transpose_array( ({ arr }));
    }

    for (i = 0; i < size; i += chunk) {
        if (i+chunk <= size) {
            erg += ({ arr[i..(i+chunk-1)] });
        } else {
            erg += ({ arr[i..<1] });
        }
    }

    return erg;
}


/*
FUNKTION: flatten_array
DEKLARATION: mixed flatten_array(mixed arr);
BESCHREIBUNG:
Ein verschachtelter Array wird verflacht.
Hat allerdings Probleme bei Arrays mit Schleifen.
Aufwand O(sizeof(arr))

Beispiel:
    flatten_array(({({ 1, 2, ({ 3, 4 }), 5 }), 6, ({ 7, 8 }) }))
        -> ({ 1, 2, 3, 4, 5, 6, 7, 8 })
VERWEISE: split_array
GRUPPEN: array
*/
mixed flatten_array(mixed arr) {
    int i;
    mixed erg;

    if (!pointerp(arr)) {
        do_error("flatten_array: Parameter 1 muss ein Array sein.\n");
        return 0;
    }

    i = 0;
    erg = ({}) + arr;
    while (i<sizeof(erg)) {
        if (pointerp(erg[i])) {
            if (i) {
                erg = erg[0..(i-1)] + erg[i] + erg[(i+1)..<1];
            } else {
                erg = erg[0] + erg[1..<1];
            }
        } else {
            i++;
        }
    }
    return erg;
}


private mixed max_of(mixed a, mixed b) {
    b =  a > b ? a : b;
    return b;
}


private mixed closure_max_of(mixed a, mixed b, closure greater) {
    b = funcall(greater, a, b) ? a : b;
    return b;
}


/*
FUNKTION: max_of_array
DEKLARATION: mixed max_of_array(mixed arr, [closure greater]);
BESCHREIBUNG:
Liefert das Maximum des Arrays zurueck.  Die Closure ist optional, default
ist >.
Aufwand O(sizeof(arr))

Beispiel:
    max_of_array(({ 1, 2, 3, 4, 5, 1, 2, 4, 8 })) -> 8
    max_of_array(({ 1, 2, 3, 4, 5, 1, 2, 4, 8 }), #'<) -> 1
VERWEISE: i_max_of_array
GRUPPEN: array
*/
varargs mixed max_of_array(mixed arr, closure greater) {
    mixed erg;

    if (!pointerp(arr)) {
        do_error("max_of_array: Parameter 1 muss ein Array sein.\n");
        return 0;
    }
    if (!sizeof(arr)) {
        return 0;
    }
    erg = arr[0];
    if (closurep(greater)) {
        map_array(arr[1..<1], #'closure_max_of, //'
            &erg, greater);
    } else {
        map_array(arr[1..<1], #'max_of, //'
            &erg);
    }
    return erg;
}


/*
FUNKTION: i_max_of_array
DEKLARATION: mixed i_max_of_array(mixed arr, [closure greater]);
BESCHREIBUNG:
Wie max_of_array, nur das der Index zurueckgeliefert wird und nicht das
Element.
Aufwand O(sizeof(arr))
VERWEISE: max_of_array
GRUPPEN: array
*/
varargs mixed i_max_of_array(mixed arr, closure greater) {
    int i, erg;
    mixed best;

    if (!pointerp(arr)) {
        do_error("i_max_of_array: Parameter 1 muss ein Array sein.\n");
        return 0;
    }
    if (!sizeof(arr)) {
        return 0;
    }
    best = arr[<1];
    erg = sizeof(arr)-1;
    if (closurep(greater)) {
        for (i=erg; i--; ) {
            if (!funcall(greater, best, arr[i])) {
                best = arr[i];
                erg = i;
            }
        }
    } else {
        for (i=erg; i--; ) {
            if (best <= arr[i]) {
                best = arr[i];
                erg = i;
            }
        }
    }
    return erg;
}


/*
FUNKTION:  choose_from_array
DEKLARATION: int choose_from_array(mixed arr, mixed pool, [closure rand]);
BESCHREIBUNG:
Waehlt aus arr zufaellig (mit Hilfe der Closure rand oder Default einfach
mit random) ein Element aus und returned einen "unbenutzen" INDEX.  Aus
pool wird das Element entfernt.  Falls pool leer ist, wird es anhand der
Groesse von arr neuinitialisiert. pool ist also nur Variable zum Speichern
der bereits benutzen Indices.  Arr kann auch ein Integer mit der Groesse
des Arrays sein, da im Falle pointerp(arr) nur die Groesse verwendet wird.
WICHTIG: pool muss als REFERENZ uebergeben werden!!!
Damit kann man z.B. aus mehreren Probleme eins auswaehlen ohne das die
Probleme sich all zu schnell wiederholen.
(Urnenmodel ohne Zuruecklegen)
Aufwand O(1) falls pool bereits initialisiert
Aufwand O(sizeof(arr)) falls pool initialisiert werden muss

Beispiel:
    problem = choose_from_array(problems, &unused);

    unused = 0;
    choose_from_array(({ 1, 2, 3, 4, 5}), &unused) -> 2
        unused waer dann ({ 0, 1, 3, 4 })
    choose_from_array(({ 1, 2, 3, 4, 5}), &unused) -> 4
        unused waer dann ({ 0, 1, 3 })

    choose_from_array(5, &unused) waer genau dasselbe
VERWEISE: select_from_array
GRUPPEN: array
*/
varargs int choose_from_array(mixed arr, mixed pool, closure rand) {
    int erg, size;

    if (!pointerp(arr) && !intp(arr)) {
        do_error("choose_from_array: Parameter 1 muss ein Array oder Integer sein.\n");
        return 0;
    }

    if (pointerp(arr)) {
        size = sizeof(arr);
    } else {
        size = arr;
    }

    if (size <= 1) {
        return -1;
    }

    erg = -1;
    // Die Whileschleife falls sich arr veraendert hat
    while ((erg < 0) || (erg >= size)) {
        if (!pointerp(pool) || (sizeof(pool) == 0)) {
            pool = construct_array(size, #'+, //'
                   0, 1);
        }

        if (closurep(rand)) {
            erg = pool[funcall(rand, sizeof(pool))];
        } else {
            erg = pool[random(sizeof(pool))];
        }
        pool -= ({ erg });
    }
    return erg;
}


/*
FUNKTION: select_from_array
DEKLARATION: mixed select_from_array(mixed arr, int m, [closure rand]) {
BESCHREIBUNG:
Waehlt m Elemente zufaellig aus arr aus (mit Hilfe der Closure rand
oder Default einfach mit random).  Die Elemente bleiben in der selben
Reihenfolge wie in arr.
Aufwand O(sizeof(arr)) falls m > 1
Aufwand O(1) falls m <= 1

Beispiel:
    select_from_array(({1,2,3,4,5,6,7,8}), 3) -> ({ 2, 3, 7 })
VERWEISE: choose_from_array
GRUPPEN: array
*/
varargs mixed select_from_array(mixed arr, int m, closure rand) {
    int i, n;
    mixed erg;

    if (!pointerp(arr)) {
        do_error("select_from_array: Parameter 1 muss ein Array sein.\n");
        return 0;
    }

    if (m < 0) {
        do_error("select_from_array: Parameter 2 muss groesser gleich 0 sein.\n");
        return 0;
    }
    n = sizeof(arr);
    if (m > n) {
        do_error("select_from_array: Parameter 2 muss kleiner als die "
            "Groesse des Arrays sein.\n");
        return 0;
    }
    if (!m) {
        return ({});
    }


    erg = ({});
    if (closurep(rand)) {
        if (m == 1) {
            return ({ arr[funcall(rand, n)] });
        }
        for (i=0; i<n; i++) {
            if (to_float(funcall(rand, MAX_INT))/MAX_INT < to_float(m)/(n-i)) {
                erg += ({ arr[i] });
                m--;
                if (!m) {
                    return erg;
                }
            }
        }
    } else {
        if (m == 1) {
            return ({ arr[random(n)] });
        }
        for (i=0; i<n; i++) {
            if (to_float(random(MAX_INT))/MAX_INT < to_float(m)/(n-i)) {
                erg += ({ arr[i] });
                m--;
                if (!m) {
                    return erg;
                }
            }
        }
    }
    return erg;
}


/*
FUNKTION: members_of_array
DEKLARATION: mixed members_of_array(mixed key, mixed arr, [closure equal]);
BESCHREIBUNG:
Returned alle Indices des key's in arr.  Falls equal angeben ist wird die
Closure bemueht die Gleichheit zu testen, ansonsten wird == benutzt.
Aufwand O(sizeof(arr))

Beispiel:
    members_of_array(1, ({ 1, 2, 3, 4, 1 })) ->
        ({ 0, 4 })

    int eq(mixed a, mixed b) {
        return a[1] == b[1];
    }
    members_of_array(({0,1}),({({0,1}),({2,2}),({2,1})}), #'eq) ->
        ({ 0, 2 })
VERWEISE: in_array, member_array
GRUPPEN: array
*/
varargs mixed members_of_array(mixed key, mixed arr, closure equal) {
    int i, size;
    mixed erg;

    if (!pointerp(arr)) {
        do_error("members_of_array: Parameter 2 muss ein Array sein.\n");
        return 0;
    }

    size = sizeof(arr);
    erg = ({});
    if (closurep(equal)) {
        for (i=0; i<size; i++) {
            if (funcall(equal, arr[i], key)) {
                erg += ({ i });
            }
        }
    } else {
        for (i=0; i<size; i++) {
            if (arr[i] == key) {
                erg += ({ i });
            }
        }
    }
    return erg;
}


/*
FUNKTION: in_array
DEKLARATION: int in_array(mixed key, mixed arr);
BESCHREIBUNG:
Liefert 1 wenn key in arr sonst 0. Man spart sich den Test auf != -1 im
Vergleich zu member_array und kann so die Funktion besser als Parameter
fuer filter_array einsetzen. Somit ist es recht einfach moeglich Arrays
(Mengen) miteinander schneiden.

Beispiel:
    filter_array(({ 2,3,4,5 }) , #'in_array, ({ 1,2,5,8 }))
        -> ({ 2,5 })

Schneller ist es allerdings ({ 2,3,4,5 }) & ({ 1,2,5,8 })
zu verwenden.
VERWEISE: members_of_array, member_array, filter_array
GRUPPEN: array
*/
int in_array(mixed key, mixed arr) {
    if (!pointerp(arr)) {
        do_error("in_array: Parameter 2 muss ein Array sein.\n");
        return 0;
    }
    return (member_array(key, arr) != -1);
}