#############################################################################
##
#F  List( <obj> ) . . . . . . . . . . . . . . . . . . . . . convert to a list
##  Attention, the overloader handles this
##
## documentation see lib/init-methods.g
_List_func_list:=
  function(fun,lis)
    local res, i;

    Print("\n");
    Print("## WARNING! List(func, list) is soon to be renamed to Apply(...)\n");
    Print("## To use `List' prefer functional Apply!\n");
    Print("## Transisition time ends 2005-Feb-06!\n");

    res:=[];
    for i in lis do
      _Add__list_any(res, fun(i));
    od;
    return res;
end;
_List_list_func:=
  function(lis,fun)
    return _List_func_list(fun,lis);
end;
_List_any:=
  function(lis)
    return List(lis);
end;


#############################################################################
##
#F  GetEntry( <record>, <string> [, optarg] )
##
## documentation see lib/init-methods.g
_GetEntry_rec_string:=
  function(arg)
    local re,spec,optarg;
    CheckArgs(arg,["re","spec","optarg"],[,,rec(Fail:=FAILURE)]);
    re:=__ARGREC.("re");
    spec:=__ARGREC.("spec");
    optarg:=__ARGREC.("optarg");
    if IsRec(re) and IsBound(re.(spec)) then
      return re.(spec);
    fi;
    ## overall-else
    if IsBound(optarg.("Fail")) then
      return optarg.Fail;
    else
      return FAILURE;
    fi;
  end;
_GetFailEntry:=re->_GetEntry_rec_string(re,"Fail",rec(Fail:=FAILURE));
_GetSuccessEntry:=re->_GetEntry_rec_string(re,"Success",rec(Fail:=SUCCESS));
#############################################################################
##
#F  GetEntry( <list>, <elt-ord^rat> [, optarg] )
##
## documentation see lib/init-methods.g
_GetEntry_list_eor:=
  function(arg)
    local lis,pos,optarg;
    CheckArgs(arg,["lis","pos","optarg"],[,,rec(Fail:=FAILURE)]);
    lis:=__ARGREC.("lis");
    pos:=__ARGREC.("pos");
    optarg:=__ARGREC.("optarg");
    if IsInt(pos) and pos>0 and IsBound(lis[pos]) then
      return lis[pos];
    fi;
    return _GetEntry_rec_string(optarg,"Fail",rec(Fail:=FAILURE));
  end;



#############################################################################
##
#F  Butfirst( <list> ) (a.k.a. Rest)
##
## documentation see lib/init-methods.g
Butfirst:=
  lis->_Remove_list_eor(lis,1);
Butfirst_:=
  lis->_Remove__list_eor(lis,1);
Rest:=Butfirst;
Rest_:=Butfirst_;

#############################################################################
##
#F  First( <list> )
##
## documentation see lib/init-methods.g
First:=
  lis->_GetEntry_list_eor(lis,1);

#############################################################################
##
#F  Butlast( <list> )
##
Butlast:=
  lis->_Remove_list_eor(lis,_Size_list(lis));
Butlast_:=
  lis->_Remove__list_eor(lis,_Size_list(lis));

#############################################################################
##
#F  Last( <list> )
##
## documentation see lib/init-methods.g
Last:=
  lis->_GetEntry_list_eor(lis,_Size_list(lis));



#############################################################################
##
#F  Apply_( <list>, <func> ) . apply a function to list entries destructively
##
## documentation see lib/init-methods.g
_Apply__func_list:=
  function(fun,lis)
    local i, a;

    for i in [1.._Size_list(lis)] do
      a := lis[i];
      lis[i] := fun(a);
    od;
  end;
_Apply__list_func:=
  function(lis,fun)
    local i, a;

    for i in [1.._Size_list(lis)] do
      a := lis[i];
      lis[i] := fun(a);
    od;
  end;

#############################################################################
##
#F  Apply( <list>, <func> ) . . . . . . . .  apply a function to list entries
##
## documentation see lib/init-methods.g
_Apply_func_list:=
  function(fun,lis)
    local res, i;

#    Print("\n");
#    Print("## WARNING! Apply(...) now has same functionality as List(...)\n");
#    Print("## To use applicative Apply prefer Apply_\n");
#    Print("## Transisition time ends 2005-Feb-06!\n");
    
    res:=[];
    for i in lis do
      _Add__list_any(res, fun(i));
    od;
    return res;
end;
_Apply_list_func:=
  function(lis,fun)
    return _Apply_func_list(fun,lis);
end;



#############################################################################
##
#F  Mapc(<func>, <list>)
##
Mapc:=
  function(fun,lis)
    local i;
    for i in lis do
      fun(i);
    od;
  end;


#############################################################################
##
#F  Maprec(<func>, <record>)
##
Maprec:=
  function(fun,re)
    local i;
    for i in RecFields(re) do
      fun(re.(i));
    od;
  end;


#############################################################################
##
#F  RunHookWithArg( <list>, <any> )  . . . . . . . . 
##
RunHookWithArg:=
  function(hook,arg)
    local i,gather,tmp;
    gather:=[];
    for i in hook do
      tmp:=i(arg);
      if not(tmp=VOID) then
        _Add__list_any(gather,tmp);
      fi;
    od;
    if gather=[] then
      return VOID;
    else
      return gather;
    fi;
  end;


#############################################################################
##
#F  Mapconcat(<func>, <list>, <sep>)  . . . . . . . . concatentation of lists
#F  Mapconcat(<func>, <list>) . . . . . . . . . . . . concatentation of lists
##
_Mapconcat_func_list_string:=
  function(fun,lis,sep)
    local i,gather;

    gather:="";
    if lis=false then
      return false;
    elif _Size_list(lis)=0 then
      return gather;
    else
      for i in Butlast(lis) do
        gather:=gather+fun(i)+sep;
      od;
      gather:=gather+fun(Last(lis));
      return gather;
    fi;
  end;
_Mapconcat_func_list:=
  function(fun,lis)
    return(_Mapconcat_func_list_string(fun,lis," "));
  end;



#############################################################################
##
#F  Concatenation( <list>, <list> ) . . . . . . . . . concatentation of lists
##
Concatenation:= function(arg)
  local  cat, lst, len, i;
  
  if _Size_list(arg)=0 then
    return [];
  elif _Size_list(arg)=1 and IsList(arg[1]) then
    cat := [];
    for lst  in arg[1]  do
      Append_(cat, lst);
    od;
  else
    cat := Copy(arg[1]);
    len := _Size_list(arg);
    for i in [2..len] do
      Append_(cat, arg[i]);
    od;

  fi;
  return cat;
end;


#############################################################################
##
#F  Flat( <list> )  . . . . . . . list of elements of a nested list structure
##
Flat:=function(lis)
  local flt, elm;

  # make the flattened list
  flt := [];
  for elm  in lis  do
    if not IsList(elm)  then
      _Add__list_any(flt, elm);
    else
      Append_( flt, Flat(elm) );
    fi;
  od;

  # and return it
  return flt;
end;


#############################################################################
##
#F  Reversed( <list> )  . . . . . . . . . . .  reverse the elements in a list
##
Reversed:=function(lis)
  local rev, len, i;
  
  rev := [];
  len := _Size_list(lis);
  for i in [0..len-1] do
    _Add__list_any(rev, lis[len-i]);
  od;
  
  return rev;
end;


#############################################################################
##
#F  Sublist( <list>, <list> ) . . . . . . . . . . .  extract a part of a list
##
Sublist := function ( list1, list2 )
    local  sub,  i;

    sub := [];
    for i  in list2  do
        _Add__list_any( sub, list1[i] );
    od;

    return sub;
end;


#############################################################################
##
#F  Filtered( <list>, <func> )  . . . . extract elements that have a property
##
_Filtered_func_list:=
  function(fun,lis)
    local flt, elm;

    flt := [];
    for elm in lis do
      if fun(elm)  then
        _Add__list_any(flt, elm);
      fi;
    od;
    
    return flt;
  end;
_Filtered_list_func:=
  function(lis,fun)
    return _Filtered_func_list(fun,lis);
  end;


#############################################################################
##
#F  Filter( <func> ) . . . . . . . . .  extract elements that have a property
##
Filter:=
  function(arg)
    local fun;
    fun := arg[1];
    return
      function(arg)
	if IsBound(arg[1]) then
          if IsString(arg[1]) then
	    return _Filtered_func_list(fun,arg);
          elif IsList(arg[1]) then
            return _Filtered_func_list(fun,arg[1]);
          else
            return _Filtered_func_list(fun,arg);
          fi;
        else
          return VOID;
        fi;
      end;
  end;


#############################################################################
##
#F  Number( <list> [, <func>] ) . . . . . count elements that have a property
##
_Number_list:=
  function(lis)
    local nr, elm;
    
    nr := 0;
    for elm in lis  do
      nr := nr + 1;
    od;
    return nr;
  end;
_Number_func_list:=
  function(fun,lis)
    local nr, elm;
    
    nr := 0;
    for elm in lis do
      if fun(elm)  then
        nr:=nr+1;
      fi;
    od;
    return nr;
  end;
_Number_list_func:=
  function(lis,fun)
    return _Number_func_list(fun,lis);
  end;
_Number_func:=
  function(arg)
    local fun;
    fun := arg[1];
    return
      function(arg)
        if IsBound(arg[1]) then
          if IsString(arg[1]) then
            return _Number_func_list(fun,arg);
          elif IsList(arg[1]) then
            return _Number_func_list(fun,arg[1]);
          else
            return _Number_func_list(fun,arg);
          fi;
        else
          return VOID;
        fi;
      end;
  end;


#############################################################################
##
#F  Compacted( <list> ) . . . . .
##
Compacted :=
  function(lis)
    local    res,       # compacted of <list>, result
             elm;       # element of <list>
    res := [];
    for elm in lis do
      _Add__list_any(res, elm);
    od;
    return res;
  end;


#############################################################################
##
#F  Collected( <list> ) . . . . .
##
Collected := function ( list )
    local   col,        # collected of <list>, result
            elm,        # element of <list>
            nr,         # number of elements of <list> equal to <elm>
            i;          # loop variable

    col := [];
    for elm  in Set( list )  do
        nr := 0;
        for i  in list  do
            if i = elm  then
                nr := nr + 1;
            fi;
        od;
        _Add__list_any( col, [ elm, nr ] );
    od;
    return col;
end;


#############################################################################
##
#F  Equivalenceclasses( <list>, <function> )  . calculate equivalence classes
##
##
##  returns
##
##      rec(
##          classes := <list>,
##          indices := <list>
##      )
##
Equivalenceclasses := function( list, isequal )
    local ecl, idx, len, new, i, j;

    if not IsList( list ) or not IsFunc( isequal ) then
        Error( "usage: Equivalenceclasses( <list>, <function> )" );
    fi;

    len := 0;
    ecl := [];
    idx := [];
    for i in [1.._Size_list( list )] do
        new := true;
        j   := 1;
        while new and j <= len do
            if isequal( list[i], ecl[j][1] ) then
                _Add__list_any( ecl[j], list[i] );
                _Add__list_any( idx[j], i );
                new := false;
            fi;
            j := j + 1;
        od;
        if new then
            len := len + 1;
            ecl[len] := [ list[i] ];
            idx[len] := [ i ];
        fi;
    od;
    return rec( classes := ecl, indices := idx );
end;


#############################################################################
##
#F  ForAll( <list>, <func> )  . .  test a property for all elements of a list
##
_ForAll_func_list:=
  function(fun,lis)
    local l;
    for l in lis do
      if not fun(l) then
        return false;
      fi;
    od;
    return true;
  end;
_ForAll_list_func:=
  function(lis,fun)
    return _ForAll_func_list(fun,lis);
  end;
_ForAll_func:=
  function(arg)
    local fun;
    fun := arg[1];
    return
      function(arg)
        if IsBound(arg[1]) then
          if IsString(arg[1]) then
            return _ForAll_func_list(fun,arg);
          elif IsList(arg[1]) then
            return _ForAll_func_list(fun,arg[1]);
          else
            return _ForAll_func_list(fun,arg);
          fi;
        else
          return VOID;
        fi;
      end;
  end;


#############################################################################
##
#F  ForAny( <list>, <func> )  . . . test a property for any element of a list
##
_ForAny_func_list:=
  function(fun,lis)
    local l;
    
    for l in lis do
      if fun(l) then
        return true;
      fi;
    od;
    return false;
  end;
_ForAny_list_func:=
  function(lis,fun)
    return _ForAny_func_list(fun,lis);
  end;
_ForAny_func:=
  function(arg)
    local fun;
    fun := arg[1];
    return
      function(arg)
        if IsBound(arg[1]) then
          if IsString(arg[1]) then
            return _ForAny_func_list(fun,arg);
          elif IsList(arg[1]) then
            return _ForAny_func_list(fun,arg[1]);
          else
            return _ForAny_func_list(fun,arg);
          fi;
        else
          return VOID;
        fi;
      end;
  end;


#############################################################################
##
#F  First( <list>, <func> ) . .  find first element in a list with a property
##
_First_func_list:=
  function(arg)
    local fun,lis,optarg,l;

    ## first of all, check the args
    CheckArgs(arg,["fun","lis","optarg"],[,,__FAILUREREC]);
    fun:=__ARGREC.("fun");
    lis:=__ARGREC.("lis");
    optarg:=__ARGREC.("optarg");

    for l in lis do
      if fun(l) then
        return l;
      fi;
    od;
    return _GetFailEntry(optarg);
  end;
_First_list_func:=
  function(arg)
    local fun,lis,optarg;

    ## first of all, check the args
    CheckArgs(arg,["lis","fun","optarg"],[,,__FAILUREREC]);
    fun:=__ARGREC.("fun");
    lis:=__ARGREC.("lis");
    optarg:=__ARGREC.("optarg");

    return _First_func_list(fun,lis,optarg);
  end;
_First_func:=
  function(arg)
    local fun,optarg;

    ## first of all, check the args
    CheckArgs(arg,["fun","optarg"],[,__FAILUREREC]);
    fun:=__ARGREC.("fun");
    optarg:=__ARGREC.("optarg");

    return
      function(arg)
        if IsBound(arg[1]) then
          if IsString(arg[1]) then
            return _First_func_list(fun,arg,optarg);
          elif IsList(arg[1]) then
            return _First_func_list(fun,arg[1],optarg);
          else
            return _First_func_list(fun,arg,optarg);
          fi;
        else
          return _GetFailEntry(optarg);
        fi;
      end;
  end;


#############################################################################
##
#F  Last( <list>, <func> ) . . .  find last element in a list with a property
##
_Last_func_list:=
  function(arg)
    local fun,lis,optarg,l;

    ## first of all, check the args
    CheckArgs(arg,["fun","lis","optarg"],[,,__FAILUREREC]);
    fun:=__ARGREC.("fun");
    lis:=__ARGREC.("lis");
    optarg:=__ARGREC.("optarg");

    return _First_func_list(fun,Reversed(lis),optarg);
  end;
_Last_list_func:=
  function(arg)
    local fun,lis,optarg;

    ## first of all, check the args
    CheckArgs(arg,["lis","fun","optarg"],[,,__FAILUREREC]);
    fun:=__ARGREC.("fun");
    lis:=__ARGREC.("lis");
    optarg:=__ARGREC.("optarg");

    return _Last_func_list(fun,lis,optarg);
  end;
_Last_func:=
  function(arg)
    local fun,optarg;

    ## first of all, check the args
    CheckArgs(arg,["fun","optarg"],[,__FAILUREREC]);
    fun:=__ARGREC.("fun");
    optarg:=__ARGREC.("optarg");

    return
      function(arg)
        if IsBound(arg[1]) then
          if IsString(arg[1]) then
            return _Last_func_list(fun,arg,optarg);
          elif IsList(arg[1]) then
            return _Last_func_list(fun,arg[1],optarg);
          else
            return _Last_func_list(fun,arg,optarg);
          fi;
        else
          return _GetFailEntry(optarg);
        fi;
      end;
  end;



#############################################################################
##
#F  PositionProperty( <list>, <func> ) position of an element with a property
##
_PositionProperty_func_list:=
  function(arg)
    local fun,lis,i,optarg,elm;

    ## now check the args
    CheckArgs(arg,["fun","lis","optarg"],[,,__FAILUREREC]);
    fun:=__ARGREC.("fun");
    lis:=__ARGREC.("lis");
    optarg:=__ARGREC.("optarg");

    for i in [1.._Size_list(lis)] do
      elm := _GetEntry_list_eor(lis,i,__FAILUREREC);
      if IsSuccess(elm) then
        if fun(elm) then
          return i;
        fi;
      fi;
    od;
    return _GetFailEntry(optarg);
  end;
_PositionProperty_list_func:=
  function(arg)
    local fun,lis,optarg;

    ## now check the args
    CheckArgs(arg,["lis","fun","optarg"],[,,__FAILUREREC]);
    fun:=__ARGREC.("fun");
    lis:=__ARGREC.("lis");
    optarg:=__ARGREC.("optarg");

    return _PositionProperty_func_list(fun,lis,optarg);
  end;
_PositionProperty_func:=
  function(arg)
    local fun;
    fun := arg[1];
    return
      function(arg)
        if IsBound(arg[1]) then
          if IsString(arg[1]) then
            return _PositionProperty_func_list(fun,arg);
          elif IsList(arg[1]) then
            return _PositionProperty_func_list(fun,arg[1]);
          else
            return _PositionProperty_func_list(fun,arg);
          fi;
        else
          return FAILURE;
        fi;
      end;
  end;


#############################################################################
##
#F  PositionBound( <list> ) . . . . . . . . . . position of first bound entry
##
PositionBound :=
  function(lis)
    local i;

    # look for the first bound element
    for i  in [1..Length(lis)]  do
      if IsBound(lis[i])  then
        return i;
      fi;
    od;
    # no bound element found
    return FAILURE;
  end;



#############################################################################
##
#F  Cartesian( <list>, <list>.. ) . . . . . . . .  cartesian product of lists
##
Cartesian2 := function ( list, n, tup, i )
  local  tups,  l;
  if i = n+1  then
    tup := Copy(tup);
    tups := [ tup ];
  else
    tups := [];
    for l  in list[i]  do
      tup[i] := l;
      Append_( tups, Cartesian2( list, n, tup, i+1 ) );
    od;
  fi;
  return tups;
end;

Cartesian:=function(arg)
  if _Size_list(arg) = 1  then
    return Cartesian2( arg[1], _Size_list(arg[1]), [], 1 );
  else
    return Cartesian2( arg, _Size_list(arg), [], 1 );
  fi;
end;


#############################################################################
##
#F  Sort( <list> )  . . . . . . . . . . . . . . . . . . . . . . . sort a list
##
##  Sort() uses Shell's diminishing increment sort, which extends bubblesort.
##  The bubble sort works by  running  through  the  list  again  and  again,
##  each time exchanging pairs of adjacent elements which are out  of  order.
##  Thus large elements "bubble" to the top, hence the name  of  the  method.
##  However elements need many moves to come close to their  final  position.
##  In shellsort the first passes do not compare element j with its  neighbor
##  but with the element j+h, where h is larger than one.  Thus elements that
##  aren't at their final position make large moves towards the  destination.
##  This increment h is diminished, until during the last  pass  it  is  one.
##  A good sequence of incremements is given by Knuth:  (3^k-1)/2,... 13,4,1.
##  For this sequence shellsort uses on average  approximatly  N^1.25  moves.
##
##  Shellsort is the method of choice to  sort  lists  for  various  reasons:
##  Shellsort is quite easy to get right, much easier than,  say,  quicksort.
##  It runs as fast as quicksort for lists with  less  than  ~5000  elements.
##  It handles both  almost  sorted  and  reverse  sorted  lists  very  good.
##  It works well  in  the  presence  of  duplicate  elements  in  the  list.
##  Says Sedgewick: "In short, if you have a sorting problem,  use the  above
##  program, then determine whether the extra effort required to  replace  it
##  with a sophisticated method will be worthwile."
##
##  Donald Knuth, The Art of Computer Programming, Vol.3, AddWes 1973, 84-95
##  Donald Shell, CACM 2, July 1959, 30-32
##  Robert Sedgewick, Algorithms 2nd ed., AddWes 1988, 107-123
##
Sort := function ( arg )
    local   list,  isLess,  i,  k,  h,  v;

    if _Size_list(arg) = 1 and IsList(arg[1])  then
        list := arg[1];
        h := 1;  while 9 * h + 4 < _Size_list(list)  do h := 3 * h + 1;  od;
        while 0 < h  do
            for i  in [ h+1 .. _Size_list(list) ]  do
                v := list[i];  k := i;
                while h < k  and v < list[k-h]  do
                    list[k] := list[k-h];  k := k - h;
                od;
                list[k] := v;
            od;
            h := Div( h, 3 );
        od;

    elif _Size_list(arg) = 2  and IsList(arg[1])  and IsFunc(arg[2])  then
        list := arg[1];  isLess := arg[2];
        h := 1;  while 9 * h + 4 < _Size_list(list)  do h := 3 * h + 1;  od;
        while 0 < h  do
            for i  in [ h+1 .. _Size_list(list) ]  do
                v := list[i];  k := i;
                while h < k  and isLess( v, list[k-h] )  do
                    list[k] := list[k-h];   k := k - h;
                od;
                list[k] := v;
            od;
            h := Div( h, 3 );
        od;

    else
        Error("usage: Sort( <list> ) or Sort( <list>, <func> )");
    fi;

end;


#############################################################################
##
#F  Sortex(<list>) . . . sort a list (stable), return the applied permutation
##
Sortex :=
  function(lis)
    local both, perm, i;

    # make a new list that contains the elements of <list> and their indices
    both := [];
    for i  in [1..Length(lis)]  do
      both[i] := [lis[i], i];
    od;

    # sort the new list according to the first item (stable)
    Sort(both);

    # copy back and remember the permutation
    perm := [];
    for i  in [1..Length(lis)]  do
        lis[i] := both[i][1];
        perm[i] := both[i][2];
    od;

    # return the permutation mapping old <list> onto the sorted list
    return PermList( perm )^(-1);
end;


#############################################################################
##
#F  SortParallel(<list>,<list2>)  . . . . . . . .  sort two lists in parallel
##
SortParallel := function ( arg )
    local   lst,        # list <lst> to be sorted, first argument
            par,        # list <par> to be sorted parallel, second argument
            isLess,     # comparison function, optional third argument
            gap,        # gap width
            l, p,       # elements from <lst> and <par>
            i, k;       # loop variables

    if _Size_list(arg) = 2  and IsList(arg[1])  then
        lst := arg[1];
        par := arg[2];
        gap := 1;  while 9*gap+4 < _Size_list(lst)  do gap := 3*gap+1;  od;
        while 0 < gap  do
            for i  in [ gap+1 .. _Size_list(lst) ]  do
                l := lst[i];  p := par[i];  k := i;
                while gap < k  and l < lst[k-gap]  do
                    lst[k] := lst[k-gap];  par[k] := par[k-gap];  k := k-gap;
                od;
                lst[k] := l;  par[k] := p;
            od;
            gap := Div( gap, 3 );
        od;

    elif _Size_list(arg) = 3  and IsList(arg[1])  and IsFunc(arg[3])  then
        lst := arg[1];
        par := arg[2];
        isLess := arg[3];
        gap := 1;  while 9*gap+4 < _Size_list(lst)  do gap := 3*gap+1;  od;
        while 0 < gap  do
            for i  in [ gap+1 .. _Size_list(lst) ]  do
                l := lst[i];  p := par[i];  k := i;
                while gap < k  and isLess( l, lst[k-gap] )  do
                    lst[k] := lst[k-gap];  par[k] := par[k-gap];  k := k-gap;
                od;
                lst[k] := l;  par[k] := p;
            od;
            gap := Div( gap, 3 );
        od;

    else
        Error("usage: SortParallel(<lst>,<par>[,<func>])");
    fi;

end;



#############################################################################
##
#F  Permuted( <list>, <perm> )  . . . apply permutation <perm> to list <list>
##
Permuted := function ( list, perm )
    local   permuted, i;
    permuted := [];
    for i  in [1.._Size_list(list)]  do
        permuted[i^perm] := list[i];
    od;
    return permuted;
end;


#############################################################################
##
#F  PositionSorted( <list>, <elm> ) . . . .  find an element in a sorted list
##
##  'PositionSorted' uses a binary search instead of the linear  search  used
##  'Position'.  This takes log to base 2 of  '_Size_list( <list> )' comparisons.
##  The list <list> must be  sorted  however  for  'PositionSorted'  to work.
##
##  Jon Bentley, Programming Pearls, AddWes 1986, 85-88
##
### REVISE ME!
PositionSorted := function ( arg )
    local   list,  elm,  isLess,  l,  m,  h;

    if _Size_list(arg) = 2  and IsList(arg[1])  then
        list := arg[1];  elm := arg[2];
        l := 0;  h := _Size_list(list)+1;
        while l+1 < h  do               # list[l]<elm & elm<=list[h] & l+1<h
            m := Div( l + h, 2 );    # l < m < h
            if list[m] < elm  then l := m;
            else                   h := m;
            fi;
        od;
        return h;                       # list[l]<elm & elm<=list[h] & l+1=h

    elif _Size_list(arg) = 3  and IsList(arg[1])  and Type(arg[3])=func  then
        list := arg[1];  elm := arg[2];  isLess := arg[3];
        l := 0;  h := _Size_list(list)+1;
        while l+1 < h  do               # list[l]<elm & elm<=list[h] & l+1<h
            m := Div( l + h, 2 );    # l < m < h
            if isLess( list[m], elm )  then l := m;
            else                            h := m;
            fi;
        od;
        return h;                       # list[l]<elm & elm<=list[h] & l+1=h

    else
        Error("usage: PositionSorted( <list>, <elm> [, <func>] )");
    fi;
end;


#############################################################################
##
#F  Product( <list> ) . . . . . . . . . . . product of the elements in a list
##
##  'Product( <list> )' \\
##  'Product( <list>, <func> )'
##
##  When used in the first way 'Product' returns the product of the  elements
##  of the list <list>.  When used in the second way  'Product'  applies  the
##  function <func>, which must  be  a  function  taking  one  argument,  and
##  returns the product of the results.  In either case if  <list>  is  empty
##  'Product' returns 1.
##
_Product_list:=
  function(lis)
    local prod, i;
    
      if not IsList(lis) then
        return _Product(lis);
      fi;
      if _Size_list(lis) = 0  then
        prod := 1;
      else
        prod := lis[1];
        for i  in [ 2 .. _Size_list(lis) ]  do
          prod := prod * lis[i];
        od;
      fi;
    return prod;
  end;
_Product_func_list:=
  function(fun,lis)
    local prod, i;

    if _Size_list(lis) = 0  then
      prod := 1;
    else
      prod := fun( lis[1] );
      for i  in [ 2 .. _Size_list(lis) ]  do
        prod := prod * fun( lis[i] );
      od;
    fi;
    return prod;
  end;
_Product_list_func:=
  function(lis,fun)
    return _Product_func_list(fun,lis);
  end;
_Product_func:=
  function(fun)
    return
      function(arg)
        if IsBound(arg[1]) then
          if IsString(arg[1]) then
            return _Product_func_list(fun,arg);
          elif IsList(arg[1]) then
            return _Product_func_list(fun,arg[1]);
          else
            return _Product_func_list(fun,arg);
          fi;
        else
          return VOID;
        fi;
      end;
  end;


#############################################################################
##
#F  Sum( <list> ) . . . . . . . . . . . . . . . sum of the elements of a list
##
_Sum_list:=
  function(lis)
    local sum, i;
    
    if not IsList(lis) then
      return _Sum(lis);
    fi;
    if _Size_list(lis) = 0  then
      sum := 0;
    else
      sum := lis[1];
      for i in [2.._Size_list(lis)] do
        sum := sum + lis[i];
      od;
    fi;
    return sum;
  end;
_Sum_func_list:=
  function(fun,lis)
    local sum, i;
    
    if _Size_list(lis)=0 then
      sum := 0;
    else
      sum := fun(lis[1]);
      for i in [2.._Size_list(lis)] do
        sum := sum + fun(lis[i]);
      od;
    fi;
    return sum;
  end;
_Sum_list_func:=
  function(lis,fun)
    return _Sum_func_list(fun,lis);
  end;
_Sum_func:=
  function(fun)
    return
      function(arg)
        if IsBound(arg[1]) then
          if IsString(arg[1]) then
            return _Sum_func_list(fun,arg);
          elif IsList(arg[1]) then
            return _Sum_func_list(fun,arg[1]);
          else
            return _Sum_func_list(fun,arg);
          fi;
        else
          return VOID;
        fi;
      end;
  end;


#############################################################################
##
#F  Iterated( <list>, <func> )  . . . . . . .  iterate a function over a list
##
### REVISE ME
Iterated := function ( lis, fun )
    local  res,  i;
    if _Size_list(lis) = 0  then
        Error("Iterated: <list> must contain at least one element");
    fi;
    res := lis[1];
    for i  in [ 2 .. _Size_list(lis) ]  do
        res := fun( res, lis[i] );
    od;
    return res;
end;


#############################################################################
##
#F  Maximum( <obj>, <obj>... )  . . . . . . . . . . . . . maximum of integers
##
### REVISE ME
Maximum := function ( arg )
    local   max, elm;
    if _Size_list(arg) = 1  and IsList(arg[1])  then
        if _Size_list(arg[1]) = 0  then
            Error("Maximum: <list> must contain at least one element");
        fi;
        max := arg[1][_Size_list(arg[1])];
        for elm  in arg[1]  do
            if max < elm  then
                max := elm;
            fi;
        od;
    elif  _Size_list(arg) = 2  then
        if arg[1] > arg[2]  then return arg[1];
        else                     return arg[2];
        fi;
    elif _Size_list(arg) > 2  then
        max := arg[_Size_list(arg)];
        for elm  in arg  do
            if max < elm  then
                max := elm;
            fi;
        od;
    else
        Error("usage: Maximum( <obj>, <obj>... ) or Maximum( <list> )");
    fi;
    return max;
end;


#############################################################################
##
#F  Minimum( <obj>, <obj>... )  . . . . . . . . . . . . . minimum of integers
##
### REVISE ME
Minimum := function ( arg )
    local   min, elm;
    if _Size_list(arg) = 1 then
      if IsList(arg[1])  then
        if _Size_list(arg[1]) = 0  then
            Error("Minimum: <list> must contain at least one element");
        fi;
        min := arg[1][_Size_list(arg[1])];
        for elm  in arg[1]  do
            if min > elm  then
                min := elm;
            fi;
        od;
      else # use KANT function Minimum
        return _Minimum(arg[1]);
      fi;
    elif  _Size_list(arg) = 2  then
        if arg[1] < arg[2]  then return arg[1];
        else                     return arg[2];
        fi;
    elif _Size_list(arg) > 2  then
        min := arg[_Size_list(arg)];
        for elm  in arg  do
            if min > elm  then
                min := elm;
            fi;
        od;
    else     
        Error("usage: Minimum( <nof(any)> ) or Minimum( <any> )");
    fi;
    return min;
end;


#############################################################################
##
#F  RandomList( <list> )  . . . . . . . . return a random element from a list
##
#N  31-May-91 martin 'RandomList' should be internal
##
R_N := 1;  R_X := [];

RandomList := function ( list )
    R_N := R_N mod 55 + 1;
    R_X[R_N] := (R_X[R_N] + R_X[(R_N+30) mod 55+1]) mod 2^28;
    return list[ Div( R_X[R_N] * _Size_list(list), 2^28 ) + 1 ];
end;

RandomSeed := function ( n )
    local  i;
    R_N := 1;  R_X := [ n ];
    for i  in [2..55]  do
        R_X[i] := (1664525 * R_X[i-1] + 1) mod 2^28;
    od;
    for i  in [1..99]  do
        R_N := R_N mod 55 + 1;
        R_X[R_N] := (R_X[R_N] + R_X[(R_N+30) mod 55+1]) mod 2^28;
    od;
end;

if R_X = []  then RandomSeed( 1 );  fi;


#############################################################################
##
#F  ListSplit( <list>, <elt-ord^rat> )
##
##  Split the list <list> in parts of size <elt-ord^rat>
##
ListSplit :=
  function ( L, n )
    local  S, r;
    r := Truncate(Real( Length( L ) / n ));
    S := List( [ 0 .. r - 1 ], function ( i )
            return L{[ i * n + 1 .. (i + 1) * n ]};
        end );
    if Length( L ) > r * n  then
        _Add__list_any( S, L{[ r * n + 1 .. Length( L ) ]} );
    fi;
    return S;
  end;


