%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  coll.msk                    GAP documentation            Alexander Hulpke
%%
%A  @(#)$Id: coll.msk,v 1.23.2.2 2006/09/16 19:02:49 jjm Exp $
%%
%Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
%Y  Copyright (C) 2002 The GAP Group
%%
\Chapter{Collections}

\FileHeader{coll}[1]

\Declaration{IsCollection}


Some of the functions for lists and collections have been described in the
chapter about lists, mainly in Section~"Operations for Lists".
In this chapter, we describe those functions for which the
``collection aspect'' seems to be more important than the ``list aspect''.
As in Chapter~"Lists", an argument that is a list will be denoted by <list>,
and an argument that is a collection will be denoted by <C>.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Collection Families}

\Declaration{CollectionsFamily}
\Declaration{IsCollectionFamily}
\Declaration{ElementsFamily}

\beginexample
gap> fam:= FamilyObj( (1,2) );;
gap> collfam:= CollectionsFamily( fam );;
gap> fam = collfam;  fam = ElementsFamily( collfam );
false
true
gap> collfam = FamilyObj( [ (1,2,3) ] );  collfam = FamilyObj( Group( () ) );
true
true
gap> collfam = CollectionsFamily( collfam );
false
\endexample

\Declaration{CategoryCollections}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Lists and Collections}

\index{Sorted Lists as Collections}

\Declaration{IsListOrCollection}


The following functions take a *list or collection* as argument,
and return a corresponding *list*.
They differ in whether or not the result is
mutable or immutable (see~"Mutability and Copyability"),
guaranteed to be sorted,
or guaranteed to admit list access in constant time
(see~"IsConstantTimeAccessList").

\Declaration{Enumerator}
\Declaration{EnumeratorSorted}
\beginexample
gap> Enumerator( [ 1, 3,, 2 ] );
[ 1, 3,, 2 ]
gap> enum:= Enumerator( Rationals );;  elm:= enum[ 10^6 ];
-69/907
gap> Position( enum, elm );
1000000
gap> IsMutable( enum );  IsSortedList( enum );
false
false
gap> IsConstantTimeAccessList( enum );
false
gap> EnumeratorSorted( [ 1, 3,, 2 ] );
[ 1, 2, 3 ]
\endexample

\Declaration{EnumeratorByFunctions}

\){\fmark List( <C> )}
\){\fmark List( <list> )}

This function is described in~"List",
together with the probably more frequently used version
which takes a function as second argument and returns the list of function
values of the list elements.
\beginexample
gap> l:= List( Group( (1,2,3) ) );
[ (), (1,3,2), (1,2,3) ]
gap> IsMutable( l );  IsSortedList( l );  IsConstantTimeAccessList( l );
true
false
true
\endexample

\Declaration{SortedList}
\beginexample
gap> l:= SortedList( Group( (1,2,3) ) );
[ (), (1,2,3), (1,3,2) ]
gap> IsMutable( l );  IsSortedList( l );  IsConstantTimeAccessList( l );
true
true
true
gap> SortedList( [ 1, 2, 1,, 3, 2 ] );
[ 1, 1, 2, 2, 3 ]
\endexample

\Declaration{SSortedList}
\beginexample
gap> l:= SSortedList( Group( (1,2,3) ) );
[ (), (1,2,3), (1,3,2) ]
gap> IsMutable( l );  IsSSortedList( l );  IsConstantTimeAccessList( l );
true
true
true
gap> SSortedList( [ 1, 2, 1,, 3, 2 ] );
[ 1, 2, 3 ]
\endexample

\Declaration{AsList}
\beginexample
gap> l:= AsList( [ 1, 3, 3,, 2 ] );
[ 1, 3, 3,, 2 ]
gap> IsMutable( l );  IsSortedList( l );  IsConstantTimeAccessList( l );
false
false
true
gap> AsList( Group( (1,2,3), (1,2) ) );
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
\endexample

\Declaration{AsSortedList}
\beginexample
gap> l:= AsSortedList( [ 1, 3, 3,, 2 ] );
[ 1, 2, 3, 3 ]
gap> IsMutable( l );  IsSortedList( l );  IsConstantTimeAccessList( l );
false
true
true
gap> IsSSortedList( l );
false
\endexample

\Declaration{AsSSortedList}
\index{elements!of a list or collection}
\beginexample
gap> l:= AsSSortedList( l );
[ 1, 2, 3 ]
gap> IsMutable( l );  IsSSortedList( l );  IsConstantTimeAccessList( l );
false
true
true
gap> AsSSortedList( Group( (1,2,3), (1,2) ) );
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
\endexample

\Declaration{Elements}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Attributes and Properties for Collections}

\Declaration{IsEmpty}
\Declaration{IsFinite}
\index{finiteness test!for a list or collection}
\Declaration{IsTrivial}
\Declaration{IsNonTrivial}
\beginexample
gap> IsEmpty( [] );  IsEmpty( [ 1 .. 100 ] );  IsEmpty( Group( (1,2,3) ) );
true
false
false
gap> IsFinite( [ 1 .. 100 ] );  IsFinite( Integers );
true
false
gap> IsTrivial( Integers );  IsTrivial( Group( () ) );
false
true
gap> IsNonTrivial( Integers );  IsNonTrivial( Group( () ) );
true
false
\endexample

\Declaration{IsWholeFamily}
\beginexample
gap> IsWholeFamily( Integers )
>    ;  # all rationals and cyclotomics lie in the family
false
gap> IsWholeFamily( Integers mod 3 )
>    ;  # all finite field elements in char. 3 lie in this family
false
gap> IsWholeFamily( Integers mod 4 );
true
gap> IsWholeFamily( FreeGroup( 2 ) );
true
\endexample

\Declaration{Size}
\index{size!of a list or collection}
\index{order!of a list, collection or domain}
\beginexample
gap> Size( [1,2,3] );  Size( Group( () ) );  Size( Integers );
3
1
infinity
\endexample

\Declaration{Representative}
\index{representative!of a list or collection}
\Declaration{RepresentativeSmallest}
\beginexample
gap> Representative( Rationals );
1
gap> Representative( [ -1, -2 .. -100 ] );
-1
gap> RepresentativeSmallest( [ -1, -2 .. -100 ] );
-100
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Operations for Collections}

\Declaration{IsSubset}
\index{subset test!for collections}
\beginexample
gap> IsSubset( Rationals, Integers );
true
gap> IsSubset( Integers, [ 1, 2, 3 ] );
true
gap> IsSubset( Group( (1,2,3,4) ), [ (1,2,3) ] );
false
\endexample

\Declaration{Intersection}
\index{intersection!of collections}
\beginexample
gap> Intersection( CyclotomicField(9), CyclotomicField(12) )
>       # this is one of the rare cases where the intersection of two infinite
>    ;  # domains works (`CF' is a shorthand for `CyclotomicField')
CF(3)
gap> D12 := Group( (2,6)(3,5), (1,2)(3,6)(4,5) );;
gap> Intersection( D12, Group( (1,2), (1,2,3,4,5) ) );
Group([ (1,5)(2,4) ])
gap> Intersection( D12, [ (1,3)(4,6), (1,2)(3,4) ] )
>    ;  # note that the second argument is not a proper set
[ (1,3)(4,6) ]
gap> Intersection( D12, [ (), (1,2)(3,4), (1,3)(4,6), (1,4)(5,6) ] )
>       # although the result is mathematically a group it is returned as a
>    ;  # proper set because the second argument is not regarded as a group
[ (), (1,3)(4,6) ]
gap> Intersection( Group( () ), [1,2,3] );
[  ]
gap> Intersection( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] )
>    ;  # two or more lists or collections as arguments are legal
[  ]
gap> Intersection( [ [1,2,4], [2,3,4], [1,3,4] ] )
>    ;  # or one list of lists or collections
[ 4 ]
\endexample

\Declaration{Union}
\index{union!of collections}
\beginexample
gap> Union( [ (1,2,3), (1,2,3,4) ], Group( (1,2,3), (1,2) ) );
[ (), (2,3), (1,2), (1,2,3), (1,2,3,4), (1,3,2), (1,3) ]
gap> Union( [2,4,6,8,10], [3,6,9,12,15], [5,10,15,20,25] )
>    ;  # two or more lists or collections as arguments are legal
[ 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 20, 25 ]
gap> Union( [ [1,2,4], [2,3,4], [1,3,4] ] )
>    ;  # or one list of lists or collections
[ 1, 2, 3, 4 ]
gap> Union( [ ] );
[  ]
\endexample

\Declaration{Difference}
\index{set difference!of collections}
\beginexample
gap> Difference( [ (1,2,3), (1,2,3,4) ], Group( (1,2,3), (1,2) ) );
[ (1,2,3,4) ]
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Membership Test for Collections}

\indextt{\\in!operation for testing membership}
\>`<obj> in <C>'{in!for collections}@{`in'!for collections}
\>`\\in( <obj>, <C> )'{in!operation for}@{`in'!operation for} O

returns `true' if the object <obj> lies in the collection <C>,
and `false' otherwise.

The infix version of the command calls the operation `\\in',
for which methods can be installed.

\beginexample
gap> 13 in Integers;  [ 1, 2 ] in Integers;
true
false
gap> g:= Group( (1,2) );;  (1,2) in g;  (1,2,3) in g;
true
false
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Random Elements}

\index{random element!of a list or collection}
\Declaration{Random}[coll]
\beginexample
gap> Random(Rationals);
4
gap> g:= Group( (1,2,3) );;  Random( g );  Random( g );
(1,3,2)
()
\endexample

\Declaration{StateRandom}
\beginexample
gap> seed:=StateRandom();;
gap> List([1..10],i->Random(Integers));
[ -2, 1, -2, -1, 0, 1, 0, 1, -1, 0 ]
gap> List([1..10],i->Random(Integers));
[ 2, 0, 4, -1, -3, 1, -4, -1, 5, -2 ]
gap> RestoreStateRandom(seed);
gap> List([1..10],i->Random(Integers));
[ -5, -2, 0, 1, -2, -1, -3, -2, 0, 0 ]
\endexample

\Declaration{PseudoRandom}

\medskip
\FileHeader{coll}[2]
\Declaration{RandomList}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Iterators}

\Declaration{Iterator}
\beginexample
gap> iter:= Iterator( GF(5) );
<iterator>
gap> l:= [];;
gap> for i in iter do Add( l, i ); od; l;
[ 0*Z(5), Z(5)^0, Z(5), Z(5)^2, Z(5)^3 ]
gap> iter:= Iterator( [ 1, 2, 3, 4 ] );;  l:= [];;
gap> for i in iter do
>      new:= ShallowCopy( iter );
>      for j in new do Add( l, j ); od;
>    od; l;
[ 2, 3, 4, 3, 4, 4 ]
\endexample

\Declaration{IteratorSorted}
\Declaration{IsIterator}
\Declaration{IsDoneIterator}
\Declaration{NextIterator}
\Declaration{IteratorList}
\Declaration{TrivialIterator}

\beginexample
gap> iter:= Iterator( [ 1, 2, 3, 4 ] );
<iterator>
gap> sum:= 0;;
gap> while not IsDoneIterator( iter ) do
>      sum:= sum + NextIterator( iter );
>    od;
gap> IsDoneIterator( iter ); sum;
true
10
gap> ir:= Iterator( Rationals );;
gap> l:= [];; for i in [1..20] do Add( l, NextIterator( ir ) ); od; l;
[ 0, 1, -1, 1/2, 2, -1/2, -2, 1/3, 2/3, 3/2, 3, -1/3, -2/3, -3/2, -3, 1/4, 
  3/4, 4/3, 4, -1/4 ]
gap> for i in ir do
>      if DenominatorRat( i ) > 10 then break; fi;
>    od;
gap> i;
1/11
\endexample

\Declaration{IteratorByFunctions}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E