% This file was created automatically from coll.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%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}

A *collection* in {\GAP} consists of elements in the same family
(see~"Families").
The most important kinds of collections are *homogeneous lists*
(see~"Lists") and *domains* (see~"Domains").
Note that a list is never a domain, and a domain is never a list.
A list is a collection if and only if it is nonempty and homogeneous.

Basic operations for collections are `Size' (see~"Size")
and `Enumerator' (see~"Enumerator");
for *finite* collections, `Enumerator' admits to delegate the other
operations for collections
(see~"Attributes and Properties for Collections"
and~"Operations for Collections")
to functions for lists (see~"Lists").
Obviously, special methods depending on the arguments are needed for
the computation of e.g.~the intersection of two *infinite* domains.



\>IsCollection( <obj> ) C

tests whether an object is a collection.




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}

\>CollectionsFamily( <Fam> ) A

For a family <Fam>, `CollectionsFamily' returns the family of all
collections that consist of elements in <Fam>.

Note that families (see~"Families") are used to describe relations
between objects.
Important such relations are that between an element <elm> and each
collection of elements that lie in the same family as <elm>,
and that between two collections whose elements lie in the same family.
Therefore, all collections of elements in the family <Fam> form the new
family `CollectionsFamily( <Fam> )'.


\>IsCollectionFamily( <Fam> ) C

is `true' if <Fam> is a family of collections, and `false' otherwise.


\>ElementsFamily( <Fam> ) A

returns the family from which the collections family <Fam> was created
by `CollectionsFamily'.
The way a collections family is created, it always has its elements
family stored.
If <Fam> is not a collections family (see~"IsCollectionFamily")
then an error is signalled.



\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

\>CategoryCollections( <filter> ) F

Let <filter> be a filter that is `true' for all elements of a family
<Fam>, by construction of <Fam>.
Then `CategoryCollections' returns a category that is `true' for all
elements in `CollectionsFamily( <Fam> )'.

For example, the construction of `PermutationsFamily' guarantees that
each of its elements lies in the filter `IsPerm',
and each collection of permutations lies in the category
`CategoryCollections( IsPerm )'.

Note that this works only if the collections category is created *before*
the collections family.
So it is necessary to construct interesting collections categories
immediately after the underlying category has been created.




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

\index{Sorted Lists as Collections}

\>IsListOrCollection( <obj> ) C

Several functions are defined for both lists and collections,
for example `Intersection' (see~"Intersection"), `Iterator'
(see~"Iterator"), and `Random' (see~"Random").
`IsListOrCollection' is a supercategory of `IsList' and `IsCollection'
(that is, all lists and collections lie in this category),
which is used to describe the arguments of functions such as the ones
listed above.




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").

\>Enumerator( <C> ) A
\>Enumerator( <list> ) A

`Enumerator' returns an immutable list <enum>.
If the argument is a list <list> (which may contain holes),
then `Length( <enum> )' is `Length( <list> )',
and <enum> contains the elements (and holes) of <list> in the same order.
If the argument is a collection <C> that is not a list,
then `Length( <enum> )' is the number of different elements of <C>,
and <enum> contains the different elements of <C> in an unspecified
order, which may change for repeated calls of `Enumerator'.
`<enum>[<pos>]' may not execute in constant time
(see~"IsConstantTimeAccessList"),
and the size of <enum> in memory is as small as is feasible.

For lists <list>, the default method is `Immutable'.
For collections <C> that are not lists, there is no default method.


\>EnumeratorSorted( <C> ) A
\>EnumeratorSorted( <list> ) A

`EnumeratorSorted' returns an immutable list <enum>.
The argument must be a collection <C> or a list <list> which may contain
holes but whose elements lie in the same family (see~"Families").
`Length( <enum> )' is the number of different elements of
<C> resp.~<list>,
and <enum> contains the different elements in sorted order, w.r.t.~`\<'.
`<enum>[<pos>]' may not execute in constant time
(see~"IsConstantTimeAccessList"),
and the size of <enum> in memory is as small as is feasible.


\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

\>EnumeratorByFunctions( <D>, <record> ) F
\>EnumeratorByFunctions( <Fam>, <record> ) F

`EnumeratorByFunctions' returns an immutable, dense, and duplicate-free
list <enum> for which `IsBound', element access, `Length', and `Position'
are computed via prescribed functions.

Let <record> be a record with at least the following components.
\beginitems
`ElementNumber' &
    a function taking two arguments <enum> and <pos>,
    which returns `<enum>[ <pos> ]' (see~"Basic Operations for Lists");
    it can be assumed that the argument <pos> is a positive integer,
    but <pos> may be larger than the length of <enum> (in which case
    an error must be signalled);
    note that the result must be immutable since <enum> itself is
    immutable,

`NumberElement' &
    a function taking two arguments <enum> and <elm>,
    which returns `Position( <enum>, <elm> )' (see~"Position");
    it cannot be assumed that <elm> is really contained in <enum>
    (and `fail' must be returned if not);
    note that for the three argument version of `Position', the
    method that is available for duplicate-free lists suffices.
\enditems
Further (data) components may be contained in <record> which can be used
by these function.

If the first argument is a domain <D> then <enum> lists the elements of
<D> (in general <enum> is *not* sorted),
and methods for `Length', `IsBound', and `PrintObj' may use <D>.

If one wants to describe the result without creating a domain then the
elements are given implicitly by the functions in <record>,
and the first argument must be a family <Fam> which will become the
family of <enum>;
if <enum> is not homogeneous then <Fam> must be `ListsFamily',
otherwise it must be the collections family of any element in <enum>.
In this case, additionally the following component in <record> is
needed.
\beginitems
`Length' &
    a function taking the argument <enum>,
    which returns the length of <enum> (see~"Length").
\enditems

The following components are optional; they are used if they are present
but default methods are installed for the case that they are missing.
\beginitems
`IsBound\\[\\]' &
    a function taking two arguments <enum> and <k>,
    which returns `IsBound( <enum>[ <k> ] )'
    (see~"Basic Operations for Lists");
    if this component is missing then `Length' is used for computing the
    result,

`Membership' &
    a function taking two arguments <elm> and <enum>,
    which returns `true' is <elm> is an element of <enum>,
    and `false' otherwise (see~"Basic Operations for Lists");
    if this component is missing then `NumberElement' is used
    for computing the result,

`AsList' &
    a function taking one argument <enum>, which returns a list with the
    property that the access to each of its elements will take roughly
    the same time (see~"IsConstantTimeAccessList");
    if this component is missing then `ConstantTimeAccessList' is used
    for computing the result,

`ViewObj' and `PrintObj' &
    two functions that print what one wants to be printed when
    `View( <enum> )' or `Print( <enum> )' is called
    (see~"View and Print"),
    if the `ViewObj' component is missing then the `PrintObj' method is
    used as a default.
\enditems

If the result is known to have additional properties such as being
strictly sorted (see~"IsSSortedList") then it can be useful to set
these properties after the construction of the enumerator,
before it is used for the first time.
And in the case that a new sorted enumerator of a domain is implemented
via `EnumeratorByFunctions', and this construction is installed as a
method for the operation `Enumerator' (see~"Enumerator"),
then it should be installed also as a method for `EnumeratorSorted'
(see~"EnumeratorSorted").

Note that it is *not* checked that `EnumeratorByFunctions' really returns
a dense and duplicate-free list.
`EnumeratorByFunctions' does *not* make a shallow copy of <record>,
this record is changed in place
(see~"prg:Creating Objects" in ``Programming in {\GAP}'').

It would be easy to implement a slightly generalized setup for
enumerators that need not be duplicate-free (where the three argument
version of `Position' is supported),
but the resulting overhead for the methods seems not to be justified.



\){\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

\>SortedList( <C> ) O
\>SortedList( <list> ) O

`SortedList' returns a new mutable and dense list <new>.
The argument must be a collection <C> or a list <list> which may contain
holes but whose elements lie in the same family (see~"Families").
`Length( <new> )' is the number of elements of <C> resp.~<list>,
and <new> contains the elements in sorted order, w.r.t.~`\<='.
`<new>[<pos>]' executes in constant time
(see~"IsConstantTimeAccessList"),
and the size of <new> in memory is proportional to its length.


\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

\>SSortedList( <C> ) O
\>SSortedList( <list> ) O
\>Set( <C> ) O

`SSortedList' (``strictly sorted list'') returns a new dense, mutable,
and duplicate free list <new>.
The argument must be a collection <C> or a list <list> which may contain
holes but whose elements lie in the same family (see~"Families").
`Length( <new> )' is the number of different elements of <C>
resp.~<list>,
and <new> contains the different elements in strictly sorted order,
w.r.t.~`\<'.
`<new>[<pos>]' executes in constant time
(see~"IsConstantTimeAccessList"),
and the size of <new> in memory is proportional to its length.

`Set' is simply a synonym for `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

\>AsList( <C> ) A
\>AsList( <list> ) A

`AsList' returns a immutable list <imm>.
If the argument is a list <list> (which may contain holes),
then `Length( <imm> )' is `Length( <list> )',
and <imm> contains the elements (and holes) of <list> in the same order.
If the argument is a collection <C> that is not a list,
then `Length( <imm> )' is the number of different elements of <C>,
and <imm> contains the different elements of <C> in an unspecified
order, which may change for repeated calls of `AsList'.
`<imm>[<pos>]' executes in constant time
(see~"IsConstantTimeAccessList"),
and the size of <imm> in memory is proportional to its length.

If you expect to do many element tests in the resulting list, it might
be worth to use a sorted list instead, using `AsSSortedList'.



\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

\>AsSortedList( <C> ) A
\>AsSortedList( <list> ) A

`AsSortedList' returns a dense and immutable list <imm>.
The argument must be a collection <C> or a list <list> which may contain
holes but whose elements lie in the same family (see~"Families").
`Length( <imm> )' is the number of elements of <C> resp.~<list>,
and <imm> contains the elements in sorted order, w.r.t.~`\<='.
`<new>[<pos>]' executes in constant time
(see~"IsConstantTimeAccessList"),
and the size of <imm> in memory is proportional to its length.

The only difference to the operation `SortedList' (see~"SortedList")
is that `AsSortedList' returns an *immutable* list.


\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

\>AsSSortedList( <C> ) A
\>AsSSortedList( <list> ) A
\>AsSet( <C> ) A

`AsSSortedList' (``as strictly sorted list'') returns a dense, immutable,
and duplicate free list <imm>.
The argument must be a collection <C> or a list <list> which may contain
holes but whose elements lie in the same family (see~"Families").
`Length( <imm> )' is the number of different elements of <C>
resp.~<list>,
and <imm> contains the different elements in strictly sorted order,
w.r.t.~`\<'.
`<imm>[<pos>]' executes in constant time
(see~"IsConstantTimeAccessList"),
and the size of <imm> in memory is proportional to its length.

Because the comparisons required for sorting can be very expensive for
some kinds of objects, you should use `AsList' instead if you do not
require the result to be sorted.

The only difference to the operation `SSortedList' (see~"SSortedList")
is that `AsSSortedList' returns an *immutable* list.

`AsSet' is simply a synonym for `AsSSortedList'.

In general a function that returns a set of elements is free, in fact
encouraged, to return a domain instead of the proper set of its elements.
This allows one to keep a given structure, and moreover the
representation by a domain object is usually more space efficient.
`AsSSortedList' must of course *not* do this,
its only purpose is to create the proper set of elements.



\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

\>Elements( <C> ) F

`Elements' does the same as `AsSSortedList' (see~"AsSSortedList"),
that is, the return value is a strictly sorted list of the elements in
the list or collection <C>.

`Elements' is only supported for backwards compatibility.
In many situations, the sortedness of the ``element list'' for a
collection is in fact not needed, and one can save a lot of time by
asking for a list that is *not* necessarily sorted, using `AsList'
(see~"AsList").
If one is really interested in the strictly sorted list of elements in
<C> then one should use `AsSet' or `AsSSortedList' instead.




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

\>IsEmpty( <C> ) P
\>IsEmpty( <list> ) P

`IsEmpty' returns `true' if the collection <C> resp.~the list <list> is
*empty* (that is it contains no elements), and `false' otherwise.


\>IsFinite( <C> ) P

`IsFinite' returns `true' if the collection <C> is finite, and `false'
otherwise.

The default method for `IsFinite' checks the size (see~"Size") of <C>.

Methods for `IsFinite' may call `Size',
but methods for `Size' must *not* call `IsFinite'.


\index{finiteness test!for a list or collection}
\>IsTrivial( <C> ) P

`IsTrivial' returns `true' if the collection <C>  consists of exactly one
element.



\>IsNonTrivial( <C> ) P

`IsNonTrivial' returns `true' if the collection <C> is empty or consists
of at least two elements (see~"IsTrivial").



\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

\>IsWholeFamily( <C> ) P

`IsWholeFamily' returns `true' if the collection <C> contains the whole
family (see~"Families") of its elements.


\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

\>Size( <C> ) A
\>Size( <list> ) A

`Size' returns the size of the collection <C>, which is either an integer
or `infinity'.
The argument may also be a list <list>, in which case the result is the
length of <list> (see~"Length").

The default method for `Size' checks the length of an enumerator of <C>.

Methods for `IsFinite' may call `Size',
but methods for `Size' must not call `IsFinite'.


\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

\>Representative( <C> ) A

`Representative' returns a *representative* of the collection <C>.

Note that `Representative' is free in choosing a representative if
there are several elements in <C>.
It is not even guaranteed that `Representative' returns the same
representative if it is called several times for one collection.
The main difference between `Representative' and `Random'
(see~"Random") is that `Representative' is free to choose a value that is
cheap to compute,
while `Random' must make an effort to randomly distribute its answers.

If <C> is a domain then there are methods for `Representative' that try
to fetch an element from any known generator list of <C>,
see~"Domains and their Elements".
Note that `Representative' does not try to *compute* generators of <C>,
thus `Representative' may give up and signal an error if <C> has no
generators stored at all.


\index{representative!of a list or collection}
\>RepresentativeSmallest( <C> ) A

returns the smallest element in the collection <C>, w.r.t.~the ordering
`\<'.
While the operation defaults to comparing all elements,
better methods are installed for some collections.


\beginexample
gap> Representative( Rationals );
1
gap> Representative( [ -1, -2 .. -100 ] );
-1
gap> RepresentativeSmallest( [ -1, -2 .. -100 ] );
-100
\endexample


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

\>IsSubset( <C1>, <C2> ) O

`IsSubset' returns `true' if <C2>, which must be a collection, is a
*subset* of <C1>, which also must be a collection, and `false' otherwise.

<C2> is considered a subset of <C1> if and only if each element of <C2>
is also an element of <C1>.
That is `IsSubset' behaves as if implemented as
`IsSubsetSet( AsSSortedList( <C1> ), AsSSortedList( <C2> ) )',
except that it will also sometimes, but not always,
work for infinite collections,
and that it will usually work much faster than the above definition.
Either argument may also be a proper set (see~"Sorted Lists and Sets").


\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

\>Intersection( <C1>, <C2> ... ) F
\>Intersection( <list> ) F
\>Intersection2( <C1>, <C2> ) O

In the first form `Intersection' returns the intersection of the
collections <C1>, <C2>, etc.
In the second form <list> must be a *nonempty* list of collections
and `Intersection' returns the intersection of those collections.
Each argument or element of <list> respectively may also be a
homogeneous list that is not a proper set,
in which case `Intersection' silently applies `Set' (see~"Set") to it
first.

The result of `Intersection' is the set of elements that lie in every of
the collections <C1>, <C2>, etc.
If the result is a list then it is mutable and new, i.e., not identical
to any of <C1>, <C2>, etc.

Methods can be installed for the operation `Intersection2' that takes
only two arguments.
`Intersection' calls `Intersection2'.

Methods for `Intersection2' should try to maintain as much structure as
possible, for example the intersection of two permutation groups is
again a permutation group.


\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

\>Union( <C1>, <C2> ... ) F
\>Union( <list> ) F
\>Union2( <C1>, <C2> ) O

In the first form `Union' returns the union of the
collections <C1>, <C2>, etc.
In the second form <list> must be a list of collections
and `Union' returns the union of those collections.
Each argument or element of <list> respectively may also be a
homogeneous list that is not a proper set,
in which case `Union' silently applies `Set' (see~"Set") to it first.

The result of `Union' is the set of elements that lie in any of the
collections <C1>, <C2>, etc.
If the result is a list then it is mutable and new, i.e., not identical
to any of <C1>, <C2>, etc.

Methods can be installed for the operation `Union2' that takes only two
arguments.
`Union' calls `Union2'.


\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

\>Difference( <C1>, <C2> ) O

`Difference' returns the set difference of the collections <C1> and <C2>.
Either argument may also be a homogeneous list that is not a proper set,
in which case `Difference' silently applies `Set' (see~"Set") to it
first.

The result of `Difference' is the set of elements that lie in <C1> but
not in <C2>.
Note that <C2> need not be a subset of <C1>.
The elements of <C2>, however, that are not elements of <C1> play no role
for the result.
If the result is a list then it is mutable and new, i.e., not identical
to <C1> or <C2>.


\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}
\>`Random( <C> )'{Random![coll]}@{`Random'!`[coll]'} O
\>`Random( <list> )'{Random![coll]}@{`Random'!`[coll]'} O

`Random' returns a (pseudo-)random element of the collection <C>
respectively the list <list>.

The distribution of elements returned by `Random' depends on the
argument.  For a list <list>, all elements are equally likely.  The same
holds usually for finite collections <C> that are not lists.  For
infinite collections <C> some reasonable distribution is used.

See the chapters of the various collections to find out
which distribution is being used.

For some collections ensuring a reasonable distribution can be
difficult and require substantial runtime.
If speed at the cost of equal distribution is desired,
the operation `PseudoRandom' should be used instead.

Note that `Random' is of course *not* an attribute.


\beginexample
gap> Random(Rationals);
4
gap> g:= Group( (1,2,3) );;  Random( g );  Random( g );
(1,3,2)
()
\endexample

\>StateRandom( ) F
\>RestoreStateRandom( <obj> ) F

[This interface to the global random generator is kept for compatibility 
with older versions of {\GAP}. Use now `State(GlobalRandomSource)'
and `Reset(GlobalRandomSource, <obj>)' instead.]

For debugging purposes, it can be desirable to reset the random number
generator to a state it had before. `StateRandom' returns a {\GAP}
object that represents the current state of the random number generator
used by `RandomList'.

By calling `RestoreStateRandom' with this object as argument, the
random number is reset to this same state.

(The same result can be obtained by accessing the two global variables
`R_N' and `R_X'.)

(The format of the object used to represent the random generator seed
is not guaranteed to be stable between different machines or versions
of {\GAP}.


\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

\>PseudoRandom( <C> ) O
\>PseudoRandom( <list> ) O

`PseudoRandom' returns a pseudo random element of the collection <C>
respectively the list <list>, which can be roughly described as follows.
For a list <list>, `PseudoRandom' returns the same as `Random'.
For collections <C> that are not lists,
the elements returned by `PseudoRandom' are *not* necessarily equally
distributed, even for finite collections <C>;
the idea is that `Random' (see~"Random") returns elements according to
a reasonable distribution, `PseudoRandom' returns elements that are
cheap to compute but need not satisfy this strong condition, and
`Representative' (see~"Representative") returns arbitrary elements,
probably the same element for each call.



\medskip
The method used by {\GAP} to obtain random elements may depend on the
type object.

Many random methods in the library are eventually based on the function
`RandomList'. As `RandomList' is restricted to lists of up to $2^{28}$
elements, this may create problems for very large collections. Also note
that the method used by `RandomList' is intended to provide a fast
algorithm rather than to produce high quality randomness for
statistical purposes.

If you implement your own `Random' methods we recommend
that they initialize their seed to a defined value when they are loaded
to permit to reproduce calculations even if they involved random
elements.

\>RandomList( <list> ) F

\index{random seed}
For a dense list <list> of up to $2^{28}$ elements,
`RandomList' returns a (pseudo-)random element with equal distribution.

The algorithm used is an additive number generator (Algorithm A in
section~3.2.2 of \cite{TACP2} with lag 30)

This random number generator is (deliberately) initialized to the same
values when {\GAP} is started, so different runs of {\GAP} with the same
input will always produce the same result, even if random calculations
are involved.

See `StateRandom' for a description on how to reset the random number
generator to a previous state.




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

\>Iterator( <C> ) O
\>Iterator( <list> ) O

Iterators provide a possibility to loop over the elements of a
(countable) collection <C> or a list <list>, without repetition.
For many collections <C>,
an iterator of <C> need not store all elements of <C>,
for example it is possible to construct an iterator of some infinite
domains, such as the field of rational numbers.

`Iterator' returns a mutable *iterator* <iter> for its argument.
If this is a list <list> (which may contain holes),
then <iter> iterates over the elements (but not the holes) of <list> in
the same order (see~"IteratorList" for details).
If this is a collection <C> but not a list then <iter> iterates over the
elements of <C> in an unspecified order,
which may change for repeated calls of `Iterator'.
Because iterators returned by `Iterator' are mutable
(see~"Mutability and Copyability"),
each call of `Iterator' for the same argument returns a *new* iterator.
Therefore `Iterator' is not an attribute (see~"Attributes").

The only operations for iterators are `IsDoneIterator',
`NextIterator', and `ShallowCopy'.
In particular, it is only possible to access the next element of the
iterator with `NextIterator' if there is one, and this can be checked
with `IsDoneIterator' (see~"NextIterator").
For an iterator <iter>, `ShallowCopy( <iter> )' is a mutable iterator
<new> that iterates over the remaining elements independent of <iter>;
the results of `IsDoneIterator' for <iter> and <new> are equal,
and if <iter> is mutable then also the results of `NextIterator' for
<iter> and <new> are equal;
note that `=' is not defined for iterators,
so the equality of two iterators cannot be checked with `='.

When `Iterator' is called for a *mutable* collection <C> then it is not
defined whether <iter> respects changes to <C> occurring after the
construction of <iter>, except if the documentation explicitly promises
a certain behaviour.  The latter is the case if the argument is a mutable
list <list> (see~"IteratorList" for subtleties in this case).

It is possible to have `for'-loops run over mutable iterators instead of
lists.

In some situations, one can construct iterators with a special
succession of elements,
see~"IteratorByBasis" for the possibility to loop over the elements
of a vector space w.r.t.~a given basis.

For lists, `Iterator' is implemented by `IteratorList( <list> )'.
For collections that are not lists, the default method is
`IteratorList( Enumerator( <C> ) )'.
Better methods depending on <C> should be provided if possible.

For random access to the elements of a (possibly infinite) collection,
*enumerators* are used.
See~"Enumerators" for the facility to compute a list from <C>,
which provides a (partial) mapping from <C> to the positive integers.



\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

\>IteratorSorted( <C> ) O
\>IteratorSorted( <list> ) O

`IteratorSorted' returns a mutable iterator.
The argument must be a collection <C> or a list <list> that is not
necessarily dense but whose elements lie in the same family
(see~"Families").
It loops over the different elements in sorted order.

For collections <C> that are not lists, the generic method is
`IteratorList( EnumeratorSorted( <C> ) )'.


\>IsIterator( <obj> ) C

Every iterator lies in the category `IsIterator'.


\>IsDoneIterator( <iter> ) O

If <iter> is an iterator for the list or collection $C$ then
`IsDoneIterator( <iter> )' is `true' if all elements of $C$ have been
returned already by `NextIterator( <iter> )', and `false' otherwise.


\>NextIterator( <iter> ) O

Let <iter> be a mutable iterator for the list or collection $C$.
If `IsDoneIterator( <iter> )' is `false' then `NextIterator' is
applicable to <iter>, and the result is the next element of $C$,
according to the succession defined by <iter>.

If `IsDoneIterator( <iter> )' is `true' then it is not defined what
happens if `NextIterator' is called for <iter>;
that is, it may happen that an error is signalled or that something
meaningless is returned, or even that {\GAP} crashes.


\>IteratorList( <list> ) F

`IteratorList' returns a new iterator that allows iteration over the
elements of the list <list> (which may have holes) in the same order.

If <list> is mutable then it is in principle possible to change <list>
after the call of `IteratorList'.
In this case all changes concerning positions that have not yet been
reached in the iteration will also affect the iterator.
For example, if <list> is enlarged then the iterator will iterate also
over the new elements at the end of the changed list.

*Note* that changes of <list> will also affect all shallow copies of
<list>.


\>TrivialIterator( <elm> ) F

is a mutable iterator for the collection `[ <elm> ]' that consists of
exactly one element <elm> (see~"IsTrivial").



\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

\>IteratorByFunctions( <record> ) F

`IteratorByFunctions' returns a (mutable) iterator <iter> for which
`NextIterator', `IsDoneIterator', and `ShallowCopy'
are computed via prescribed functions.

Let <record> be a record with at least the following components.
\beginitems
`NextIterator' &
    a function taking one argument <iter>,
    which returns the next element of <iter> (see~"NextIterator");
    for that, the components of <iter> are changed,

`IsDoneIterator' &
    a function taking one argument <iter>,
    which returns `IsDoneIterator( <iter> )' (see~"IsDoneIterator");

`ShallowCopy' &
    a function taking one argument <iter>,
    which returns a record for which `IteratorByFunctions' can be called
    in order to create a new iterator that is independent of <iter> but
    behaves like <iter> w.r.t. the operations `NextIterator' and
    `IsDoneIterator'.
\enditems
Further (data) components may be contained in <record> which can be used
by these function.

`IteratorByFunctions' does *not* make a shallow copy of <record>,
this record is changed in place
(see~"prg:Creating Objects" in ``Programming in {\GAP}'').




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