|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Martin Schönert, Thomas Breuer.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains methods for collections in general.
##
#############################################################################
##
#M CollectionsFamily(<F>) . . . . . . . . . . . . . . . . . generic method
##
InstallMethod( CollectionsFamily,
"for a family",
[ IsFamily ], 90,
function ( F )
local colls, coll_req, coll_imp, elms_flags, tmp;
coll_req := IsCollection;
coll_imp := IsObject;
elms_flags := F!.IMP_FLAGS;
atomic readonly CATEGORIES_COLLECTIONS do
for tmp in CATEGORIES_COLLECTIONS do
if IS_SUBSET_FLAGS( elms_flags, FLAGS_FILTER( tmp[1] ) ) then
coll_imp := coll_imp and tmp[2];
fi;
od;
od;
if ( not HasElementsFamily( F ) )
or not IsOddAdditiveNestingDepthFamily( F ) then
colls := NewFamily( "CollectionsFamily(...)", coll_req,
coll_imp and IsOddAdditiveNestingDepthObject );
SetFilterObj( colls, IsOddAdditiveNestingDepthFamily );
else
colls := NewFamily( "CollectionsFamily(...)", coll_req, coll_imp );
fi;
SetElementsFamily( colls, F );
return colls;
end );
#
# Rather nasty cludge follows. We need StringFamily before we read
# this file, so we created it earlier and "force" it to be the CollectionsFamily of
# CharsFamily here.
#
SetElementsFamily( StringFamily, CharsFamily);
SetCollectionsFamily( CharsFamily, StringFamily);
#############################################################################
##
## Iterators
##
#############################################################################
##
#V IteratorsFamily
##
BIND_GLOBAL( "IteratorsFamily", NewFamily( "IteratorsFamily", IsIterator ) );
#############################################################################
##
#M PrintObj( <iter> ) . . . . . . . . . . . . . . . . . . print an iterator
##
## This method is also the default for `ViewObj'.
##
InstallMethod( PrintObj,
"for an iterator",
[ IsIterator ],
function( iter )
local msg;
msg := "<iterator";
if not IsMutable( iter ) then
Append(msg, " (immutable)");
fi;
Append(msg,">");
Print(msg);
end );
#############################################################################
##
#M IsEmpty(<C>) . . . . . . . . . . . . . . . test if a collection is empty
##
InstallImmediateMethod( IsEmpty,
IsCollection and HasSize, 0,
C -> Size( C ) = 0 );
InstallMethod( IsEmpty,
"for a collection",
[ IsCollection ],
C -> Size( C ) = 0 );
InstallMethod( IsEmpty,
"for a list",
[ IsList ],
list -> Length( list ) = 0 );
#############################################################################
##
#M IsTrivial(<C>) . . . . . . . . . . . . . test if a collection is trivial
##
InstallImmediateMethod( IsTrivial,
IsCollection and HasSize, 0,
C -> Size( C ) = 1 );
InstallMethod( IsTrivial,
"for a collection",
[ IsCollection ],
C -> Size( C ) = 1 );
InstallMethod( IsTrivial,
[IsCollection and HasIsNonTrivial], 0,
C -> not IsNonTrivial( C ) );
#############################################################################
##
#M IsNonTrivial( <C> ) . . . . . . . . . test if a collection is nontrivial
##
InstallMethod( IsNonTrivial,
[IsCollection and HasIsTrivial], 0,
C -> not IsTrivial( C ) );
InstallMethod( IsNonTrivial,
"for a collection",
[ IsCollection ],
C -> Size( C ) <> 1 );
#############################################################################
##
#M IsFinite(<C>) . . . . . . . . . . . . . . test if a collection is finite
##
InstallImmediateMethod( IsFinite,
IsCollection and HasSize, 0,
C -> not IsIdenticalObj( Size( C ), infinity ) );
InstallMethod( IsFinite,
"for a collection",
[ IsCollection ],
C -> Size( C ) < infinity );
#############################################################################
##
#M IsWholeFamily( <C> ) . . test if a collection contains the whole family
##
InstallMethod( IsWholeFamily,
"default for a collection, print an error message",
[ IsCollection ],
function ( C )
Error( "cannot test whether <C> contains the family of its elements" );
end );
#############################################################################
##
#M Size( <C> ) . . . . . . . . . . . . . . . . . . . . size of a collection
##
# This used to be an immediate method. It was replaced by an ordinary
# method, as the immediate method would get called for every group that
# knows it is finite but does not know its size -- e.g. permutation, pc.
# The benefit of this is minimal beyond showing off a feature.
InstallMethod( Size,true, [IsCollection and HasIsFinite],
100, # rank above object-specific methods
function ( C )
if IsFinite( C ) then
TryNextMethod();
fi;
return infinity;
end );
InstallImmediateMethod( Size,
IsCollection and HasAsList and IsAttributeStoringRep, 0,
C -> Length( AsList( C ) ) );
InstallMethod( Size,
"for a collection",
[ IsCollection ],
C -> Length( Enumerator( C ) ) );
#############################################################################
##
#M Representative( <C> ) . . . . . . . . . . for a collection that is a list
##
InstallMethod( Representative,
"for a collection that is a list",
[ IsCollection and IsList ],
function ( C )
if IsEmpty( C ) then
Error( "<C> must be nonempty to have a representative" );
else
return C[1];
fi;
end );
InstallImmediateMethod( RepresentativeSmallest,
IsCollection and HasEnumeratorSorted and IsAttributeStoringRep, 1000,
function( C )
C:= EnumeratorSorted( C );
if IsEmpty( C ) then
TryNextMethod();
else
return C[1];
fi;
end );
InstallImmediateMethod( RepresentativeSmallest,
IsCollection and HasAsSSortedList and IsAttributeStoringRep, 1000,
function( C )
C:= AsSSortedList( C );
if IsEmpty( C ) then
TryNextMethod();
else
return C[1];
fi;
end );
InstallMethod( RepresentativeSmallest,
"for a collection",
[ IsCollection ],
function ( C )
local elm;
for elm in EnumeratorSorted( C ) do
return elm;
od;
Error( "<C> must be nonempty to have a representative" );
end );
#############################################################################
##
#M Random( <list> ) . . . . . . . . . . . . . . . . . . . . . . for a list
#M Random( <C> ) . . . . . . . . . . . . . . . . . . . . . for a collection
##
## The default function for random selection in a finite collection computes
## an enumerator of <C> and selects a random element of this list using the
## function `RandomList', which uses a pseudo random number generator.
##
# RandomList is not an operation to avoid the (often expensive) cost of
# dispatch for lists
InstallGlobalFunction( RandomList, function(args...)
local len, source, list;
len := Length(args);
if len = 1 then
source := GlobalMersenneTwister;
list := args[1];
elif len = 2 then
source := args[1];
list := args[2];
else
Error( "usage: RandomList( [<rs>], <list> ) for a dense list <list>" );
fi;
return list[Random(source, 1, Length(list))];
end );
RedispatchOnCondition(Random,true,[IsCollection],[IsFinite],0);
RedispatchOnCondition(Random,true,[IsRandomSource,IsCollection],[,IsFinite],0);
#############################################################################
##
#M PseudoRandom( <list> ) . . . . . . . . . . . . . . for an internal list
##
InstallMethod( PseudoRandom,
"for an internal list",
[ IsList and IsInternalRep ], 100,
RandomList );
#############################################################################
##
#M PseudoRandom( <C> ) . . . . . . . . . . . . . . for a list or collection
##
InstallMethod( PseudoRandom,
"for a list or collection (delegate to `Random')",
[ IsListOrCollection ], Random );
#############################################################################
##
#M AsList( <coll> )
##
InstallMethod( AsList,
"for a collection",
[ IsCollection ],
coll -> ConstantTimeAccessList( Enumerator( coll ) ) );
InstallMethod( AsList,
"for collections that are constant time access lists",
[ IsCollection and IsConstantTimeAccessList ],
Immutable );
#############################################################################
##
#M AsSSortedList( <coll> )
##
InstallMethod( AsSSortedList,
"for a collection",
[ IsCollection ],
coll -> ConstantTimeAccessList( EnumeratorSorted( coll ) ) );
InstallOtherMethod( AsSSortedList,
"for a collection that is a constant time access list",
[ IsCollection and IsConstantTimeAccessList ],
l->AsSSortedListList(AsPlist(l)) );
#############################################################################
##
#M AsSSortedListNonstored( <C> )
##
InstallMethod(AsSSortedListNonstored,"if `AsSSortedList' is known",
[IsListOrCollection and HasAsSSortedList],
# besser geht nicht
SUM_FLAGS,
AsSSortedList);
InstallMethod(AsSSortedListNonstored,"if `AsList' is known:sort",
[IsListOrCollection and HasAsList],
# unless the construction constructs the elements already sorted, this
# method is as good as it gets
QuoInt(SUM_FLAGS,4),
function(l)
local a;
a:=ShallowCopy(AsList(l));
Sort(a);
return a;
end);
#############################################################################
##
#M Enumerator( <C> )
##
InstallImmediateMethod( Enumerator,
IsCollection and HasAsList and IsAttributeStoringRep, 0,
AsList );
InstallMethod( Enumerator,
"for a collection with known `AsList' value",
[ IsCollection and HasAsList ],
SUM_FLAGS, # we don't want to compute anything anew -- this is already a
# known result as good as any.
AsList );
InstallMethod( Enumerator,
"for a collection with known `AsSSortedList' value",
[ IsCollection and HasAsSSortedList ],
SUM_FLAGS, # we don't want to compute anything anew -- this is already a
# known result as good as any.
AsSSortedList );
InstallMethod( Enumerator,
"for a collection that is a list",
[ IsCollection and IsList ],
Immutable );
#############################################################################
##
#M EnumeratorSorted( <C> )
##
## If a collection known already its `AsSSortedList' value then
## `EnumeratorSorted' may fetch this value.
##
InstallImmediateMethod( EnumeratorSorted,
IsCollection and HasAsSSortedList and IsAttributeStoringRep, 0,
AsSSortedList );
InstallMethod( EnumeratorSorted,
"for a collection with known `AsSSortedList' value",
[ IsCollection and HasAsSSortedList ],
SUM_FLAGS, # we don't want to compute anything anew -- this is already a
# known result as good as any.
AsSSortedList );
#############################################################################
##
#M PrintObj( <enum> ) . . . . . . . . . . . . . . . . . print an enumerator
##
## This is also the default method for `ViewObj'.
##
InstallMethod( PrintObj,
"for an enumerator",
[ IsList and IsAttributeStoringRep ],
function( enum )
Print( "<enumerator>" );
end );
#############################################################################
##
#F EnumeratorByFunctions( <D>, <record> )
#F EnumeratorByFunctions( <Fam>, <record> )
##
DeclareRepresentation( "IsEnumeratorByFunctionsRep", IsComponentObjectRep );
DeclareSynonym( "IsEnumeratorByFunctions",
IsEnumeratorByFunctionsRep and IsDenseList and IsDuplicateFreeList );
InstallGlobalFunction( EnumeratorByFunctions, function( D, record )
local filter, Fam, enum;
if not ( IsRecord( record ) and IsBound( record.ElementNumber )
and IsBound( record.NumberElement ) ) then
Error( "<record> must be a record with components `ElementNumber'\n",
"and `NumberElement'" );
fi;
filter:= IsEnumeratorByFunctions and IsAttributeStoringRep;
if IsDomain( D ) then
Fam:= FamilyObj( D );
elif IsFamily( D ) then
if not IsBound( record.Length ) then
Error( "<record> must have the component `Length'" );
fi;
Fam:= D;
else
Error( "<D> must be a record or a family" );
fi;
enum:= Objectify( NewType( Fam, filter ), record );
if IsDomain( D ) then
SetUnderlyingCollection( enum, D );
if HasIsFinite( D ) then
SetIsFinite( enum, IsFinite( D ) );
fi;
fi;
return enum;
end );
InstallOtherMethod( \[\],
"for enumerator by functions",
[ IsEnumeratorByFunctions, IsPosInt ],
function( enum, nr )
return enum!.ElementNumber( enum, nr );
end );
InstallOtherMethod( Position,
"for enumerator by functions",
[ IsEnumeratorByFunctions, IsObject, IsZeroCyc ],
RankFilter( IsSmallList ), # override the generic method for those lists
function( enum, elm, zero )
return enum!.NumberElement( enum, elm );
end );
InstallOtherMethod( PositionCanonical,
"for enumerator by functions",
[ IsEnumeratorByFunctions, IsObject ],
function( enum, elm )
if IsBound( enum!.PositionCanonical ) then
return enum!.PositionCanonical( enum, elm );
else
return enum!.NumberElement( enum, elm );
fi;
end );
# (was defined for EnumeratorByBasis, IsExternalOrbitByStabilizerEnumerator,
# IsRationalClassGroupEnumerator!)
# I am still convinced that `PositionCanonical' is not a well-defined concept!
InstallMethod( Length,
"for an enumerator that perhaps has its own `Length' function",
[ IsEnumeratorByFunctions ],
function( enum )
if IsBound( enum!.Length ) then
return enum!.Length( enum );
elif HasUnderlyingCollection( enum ) then
return Size( UnderlyingCollection( enum ) );
else
Error( "neither `Length' function nor `UnderlyingCollection' found ",
"in <enum>" );
fi;
end );
InstallMethod( IsBound\[\],
"for an enumerator that perhaps has its own `IsBound' function",
[ IsEnumeratorByFunctions, IsPosInt ],
function( enum, n )
if IsBound( enum!.IsBound\[\] ) then
return enum!.IsBound\[\]( enum, n );
else
return n <= Length( enum );
fi;
end );
InstallOtherMethod( \in,
"for an enumerator that perhaps has its own membership test function",
[ IsObject, IsEnumeratorByFunctions ],
function( elm, enum )
if IsBound( enum!.Membership ) then
return enum!.Membership( elm, enum );
else
return enum!.NumberElement( enum, elm ) <> fail;
fi;
end );
InstallMethod( AsList,
"for an enumerator that perhaps has its own `AsList' function",
[ IsEnumeratorByFunctions ],
function( enum )
if IsBound( enum!.AsList ) then
return enum!.AsList( enum );
else
return ConstantTimeAccessList( enum );
fi;
end );
InstallMethod( ViewObj,
"for an enumerator that perhaps has its own `ViewObj' function",
[ IsEnumeratorByFunctions ], SUM_FLAGS,
# override, e.g., the method for finite lists
# in the case of an enumerator of GF(q)^n
function( enum )
if IsBound( enum!.ViewObj ) then
enum!.ViewObj( enum );
elif IsBound( enum!.PrintObj ) then
enum!.PrintObj( enum );
elif HasUnderlyingCollection( enum ) then
Print( "<enumerator of " );
View( UnderlyingCollection( enum ) );
Print( ">" );
else
Print( "<enumerator>" );
fi;
end );
InstallMethod( PrintObj,
"for an enumerator that perhaps has its own `PrintObj' function",
[ IsEnumeratorByFunctions ],
function( enum )
if IsBound( enum!.PrintObj ) then
enum!.PrintObj( enum );
elif HasUnderlyingCollection( enum ) then
Print( "<enumerator of ", UnderlyingCollection( enum ), ">" );
else
Print( "<enumerator>" );
fi;
end );
#############################################################################
##
#F EnumeratorOfSubset( <list>, <blist>[, <ishomog>] )
##
BIND_GLOBAL( "ElementNumber_Subset", function( senum, num )
local pos;
pos:= PositionNthTrueBlist( senum!.blist, num );
if pos = fail then
Error( "List Element: <list>[", num, "] must have an assigned value" );
else
return senum!.list[ pos ];
fi;
end );
BIND_GLOBAL( "NumberElement_Subset", function( senum, elm )
local pos;
pos:= Position( senum!.list, elm );
if pos = fail or not senum!.blist[ pos ] then
return fail;
else
return SIZE_BLIST( senum!.blist{ [ 1 .. pos ] } );
fi;
end );
BIND_GLOBAL( "PositionCanonical_Subset", function( senum, elm )
local pos;
pos:= PositionCanonical( senum!.list, elm );
if pos = fail or not senum!.blist[ pos ] then
return fail;
else
return SIZE_BLIST( senum!.blist{ [ 1 .. pos ] } );
fi;
end );
BIND_GLOBAL( "Length_Subset", senum -> SIZE_BLIST( senum!.blist ) );
BIND_GLOBAL( "AsList_Subset",
senum -> senum!.list{ LIST_BLIST( [ 1 .. Length( senum!.list ) ],
senum!.blist ) } );
InstallGlobalFunction( EnumeratorOfSubset,
function( arg )
local list, blist, Fam;
# Get and check the arguments.
if Length( arg ) < 2 or 3 < Length( arg ) then
Error( "usage: EnumeratorOfSubset( <list>, <blist>[, <ishomog>] )" );
fi;
list:= arg[1];
blist:= arg[2];
# Determine the family of the result.
if IsHomogeneousList( list ) then
Fam:= FamilyObj( list );
elif Length( arg ) = 2 then
Error( "missing third argument <ishomog> for inhomog. <list>" );
elif arg[3] = true then
Fam:= FamilyObj( list );
else
Fam:= ListsFamily;
fi;
# Construct the enumerator.
return EnumeratorByFunctions( Fam, rec(
ElementNumber := ElementNumber_Subset,
NumberElement := NumberElement_Subset,
PositionCanonical := PositionCanonical_Subset,
Length := Length_Subset,
AsList := AsList_Subset,
list := list,
blist := blist ) );
end );
#############################################################################
##
#F List( <coll> )
#F List( <coll>, <func> )
##
InstallGlobalFunction( List,
function( arg )
local tnum, C, func, res, i, l;
l := Length(arg);
if l = 0 or l > 2 then
ErrorNoReturn( "usage: List( <C>[, <func>] )" );
fi;
tnum:= TNUM_OBJ( arg[1] );
# handle built-in lists directly, to avoid method dispatch overhead
if FIRST_LIST_TNUM <= tnum and tnum <= LAST_LIST_TNUM then
C:= arg[1];
if l = 1 then
return ShallowCopy( C );
else
func:= arg[2];
res := EmptyPlist(Length(C));
# hack to save type adjustments and conversions (e.g. to blist)
if Length(C) > 0 then res[Length(C)] := 1; fi;
if IsDenseList(C) then
# save the IsBound tests from general case
for i in [1..Length(C)] do
res[i] := func( C[i] );
od;
else
for i in [1..Length(C)] do
if IsBound(C[i]) then
res[i] := func( C[i] );
fi;
od;
fi;
return res;
fi;
else
return CallFuncList( ListOp, arg );
fi;
end );
#############################################################################
##
#M ListOp( <coll> )
##
InstallMethod( ListOp,
"for a collection",
[ IsCollection ],
C -> ShallowCopy( Enumerator( C ) ) );
InstallMethod( ListOp,
"for a collection that is a list",
[ IsCollection and IsList ],
ShallowCopy );
InstallMethod( ListOp,
"for a list",
[ IsList ],
ShallowCopy );
#############################################################################
##
#M ListOp( <coll>, <func> )
##
InstallMethod( ListOp,
"for a list/collection, and a function",
[ IsListOrCollection, IsFunction ],
function ( C, func )
local res, i, elm;
res := [];
i := 0;
for elm in C do
i:= i+1;
res[i]:= func( elm );
od;
return res;
end );
InstallMethod( ListOp,
"for a list, and a function",
[ IsList, IsFunction ],
function ( C, func )
local res, i, elm;
res := [];
i := 0;
for elm in [1..Length(C)] do
if IsBound(C[elm]) then
i:= i+1;
res[i]:= func( C[elm] );
fi;
od;
return res;
end );
InstallMethod( ListOp,
"for a dense list, and a function",
[ IsDenseList, IsFunction ],
function ( C, func )
local res, elm;
res := EmptyPlist(Length(C));
for elm in [1..Length(C)] do
res[elm]:= func( C[elm] );
od;
return res;
end );
#############################################################################
##
#M SortedList( <C> )
##
InstallMethod( SortedList, "for a list or collection",
true, [ IsListOrCollection ], 0,
function(C)
local l;
if IsList(C) then
l := Compacted(C);
else
l := List(C);
fi;
Sort(l);
return l;
end);
InstallMethod(SortedList, "for a list or collection and a function",
[ IsListOrCollection, IsFunction ],
function(C, func)
local l;
if IsList(C) then
l := Compacted(C);
else
l := List(C);
fi;
Sort(l, func);
return l;
end);
InstallMethod( AsSortedList, "for a list or collection",
true, [ IsListOrCollection ], 0,
function(l)
local s;
s := SortedList(l);
MakeImmutable(s);
return s;
end);
#############################################################################
##
#M SortedListBy( <C> , <func> )
##
InstallMethod(SortedListBy, "for a list or collection and a function",
[ IsListOrCollection, IsFunction ],
function(C, func)
local images, l;
if IsList(C) then
l := Compacted(C);
else
l := List(C);
fi;
images := List(l, func);
SortParallel(images, l);
return l;
end);
#############################################################################
##
#M SSortedList( <C> )
##
InstallMethod( SSortedList,
"for a collection",
true, [ IsCollection ], 0,
C -> ShallowCopy( EnumeratorSorted( C ) ) );
InstallMethod( SSortedList,
"for a collection that is a small list",
true, [ IsCollection and IsList and IsSmallList ], 0,
SSortedListList );
InstallMethod( SSortedList,
"for a collection that is a list",
true, [ IsCollection and IsList ], 0,
function(list)
if IsSmallList(list) then
return SSortedListList(list);
else
Error("Sort for large lists not yet implemented");
fi;
end
);
#############################################################################
##
#M SSortedList( <C>, <func> )
##
InstallOtherMethod( SSortedList,
"for a collection, and a function",
true, [ IsCollection, IsFunction ], 0,
function ( C, func )
return SSortedListList( List( C, func ) );
end );
#############################################################################
##
#M Iterator(<C>)
##
InstallMethod( Iterator,
"for a collection",
[ IsCollection ],
C -> IteratorList( Enumerator( C ) ) );
InstallMethod( Iterator,
"for a collection that is a list",
[ IsCollection and IsList ],
C -> IteratorList( C ) );
InstallOtherMethod( Iterator,
"for a mutable iterator",
[ IsIterator and IsMutable ],
IdFunc );
#T or change the for-loop to accept iterators?
#############################################################################
##
#M List( <iter> ) . . . . . . return list of remaining objects in an iterator
##
## Does not change the iterator.
##
InstallOtherMethod( ListOp,
"for an iterator",
[ IsIterator ],
function ( iter )
local res, elm;
res := [];
iter := ShallowCopy( iter );
for elm in iter do
Add( res, elm );
od;
return res;
end );
InstallOtherMethod( ListOp,
"for an iterator, and a function",
[ IsIterator, IsFunction ],
function ( iter, func )
local res, elm;
res := [];
iter := ShallowCopy( iter );
for elm in iter do
Add( res, func( elm ) );
od;
return res;
end );
#############################################################################
##
#M IteratorSorted(<C>)
##
InstallMethod( IteratorSorted,
"for a collection",
[ IsCollection ],
C -> IteratorList( EnumeratorSorted( C ) ) );
InstallMethod( IteratorSorted,
"for a collection that is a list",
[ IsCollection and IsList ],
C -> IteratorList( SSortedListList( C ) ) );
#############################################################################
##
#M NextIterator( <iter> ) . . . . . . for immutable iterator (error message)
##
InstallOtherMethod( NextIterator,
"for an immutable iterator (print a reasonable error message)",
[ IsIterator ],
function( iter )
if IsMutable( iter ) then
TryNextMethod();
fi;
Error( "no `NextIterator' method for immutable iterator <iter>" );
end );
#############################################################################
##
#F IteratorByFunctions( <record> )
##
if IsHPCGAP then
DeclareRepresentation( "IsIteratorByFunctionsRep", IsNonAtomicComponentObjectRep );
else
DeclareRepresentation( "IsIteratorByFunctionsRep", IsComponentObjectRep );
fi;
DeclareSynonym( "IsIteratorByFunctions",
IsIteratorByFunctionsRep and IsIterator );
InstallGlobalFunction( IteratorByFunctions, function( record )
local filter;
if not ( IsRecord( record ) and IsBound( record.NextIterator )
and IsBound( record.IsDoneIterator )
and IsBound( record.ShallowCopy ) ) then
Error( "<record> must be a record with components `NextIterator',\n",
"`IsDoneIterator', and `ShallowCopy'" );
fi;
filter:= IsIteratorByFunctions and IsStandardIterator and IsMutable;
return Objectify( NewType( IteratorsFamily, filter ), record );
end );
InstallMethod( IsDoneIterator,
"for `IsIteratorByFunctions'",
[ IsIteratorByFunctions ],
iter -> iter!.IsDoneIterator( iter ) );
InstallMethod( NextIterator,
"for `IsIteratorByFunctions'",
[ IsIteratorByFunctions and IsMutable ],
iter -> iter!.NextIterator( iter ) );
InstallMethod( ShallowCopy,
"for `IsIteratorByFunctions'",
[ IsIteratorByFunctions ],
function( iter )
local new;
new:= iter!.ShallowCopy( iter );
new.NextIterator := iter!.NextIterator;
new.IsDoneIterator := iter!.IsDoneIterator;
new.ShallowCopy := iter!.ShallowCopy;
if IsBound(iter!.ViewObj) then
new.ViewObj := iter!.ViewObj;
fi;
if IsBound(iter!.PrintObj) then
new.PrintObj := iter!.PrintObj;
fi;
return IteratorByFunctions( new );
end );
InstallMethod( ViewObj,
"for an iterator that perhaps has its own `ViewObj' function",
[ IsIteratorByFunctions ], 20,
function( iter )
if IsBound( iter!.ViewObj ) then
iter!.ViewObj( iter );
elif IsBound( iter!.PrintObj ) then
iter!.PrintObj( iter );
elif HasUnderlyingCollection( iter ) then
Print( "<iterator of " );
View( UnderlyingCollection( iter ) );
Print( ">" );
else
Print( "<iterator>" );
fi;
end );
InstallMethod( PrintObj,
"for an iterator that perhaps has its own `PrintObj' function",
[ IsIteratorByFunctions ],
function( iter )
if IsBound( iter!.PrintObj ) then
iter!.PrintObj( iter );
elif HasUnderlyingCollection( iter ) then
Print( "<iterator of ", UnderlyingCollection( iter ), ">" );
else
Print( "<iterator>" );
fi;
end );
#############################################################################
##
#F ConcatenationIterators( <iters> ) . . . . . . . combine list of iterators
## to one iterator
##
BIND_GLOBAL("NextIterator_Concatenation", function(it)
local i, it1, res;
i := it!.i;
it1 := it!.iters[i];
res := NextIterator(it1);
while i <= Length(it!.iters) and IsDoneIterator(it!.iters[i]) do
i := i+1;
od;
it!.i := i;
return res;
end);
BIND_GLOBAL("IsDoneIterator_Concatenation", function(it)
return it!.i > Length(it!.iters);
end);
BIND_GLOBAL("ShallowCopy_Concatenation", function(it)
return rec(NextIterator := it!.NextIterator,
IsDoneIterator := it!.IsDoneIterator,
ShallowCopy := it!.ShallowCopy,
i := it!.i,
iters := List(it!.iters, ShallowCopy)
);
end);
BIND_GLOBAL("ConcatenationIterators", function(iters)
local i;
i := 1;
while i <= Length(iters) and IsDoneIterator(iters[i]) do
i := i+1;
od;
return IteratorByFunctions(rec(
NextIterator := NextIterator_Concatenation,
IsDoneIterator := IsDoneIterator_Concatenation,
ShallowCopy := ShallowCopy_Concatenation,
i := i,
iters := iters,
));
end);
#############################################################################
##
#F TrivialIterator( <elm> )
##
BIND_GLOBAL( "IsDoneIterator_Trivial", iter -> iter!.isDone );
BIND_GLOBAL( "NextIterator_Trivial", function( iter )
iter!.isDone:= true;
return iter!.element;
end );
BIND_GLOBAL( "ShallowCopy_Trivial",
iter -> rec( element:= iter!.element, isDone:= iter!.isDone ) );
InstallGlobalFunction( TrivialIterator, function( elm )
return IteratorByFunctions( rec(
IsDoneIterator := IsDoneIterator_Trivial,
NextIterator := NextIterator_Trivial,
ShallowCopy := ShallowCopy_Trivial,
element := elm,
isDone := false ) );
end );
InstallMethod( Iterator,
"for a trivial collection",
[ IsCollection and IsTrivial ], SUM_FLAGS,
D -> TrivialIterator( Enumerator( D )[1] ) );
#############################################################################
##
#F Sum( <coll> )
#F Sum( <coll>, <func> )
#F Sum( <coll>, <init> )
#F Sum( <coll>, <func>, <init> )
##
InstallGlobalFunction( Sum,
function( arg )
local tnum, C, func, sum, i, l;
l := Length( arg );
if l = 0 then
Error( "usage: Sum( <C>[, <func>][, <init>] )" );
fi;
tnum:= TNUM_OBJ( arg[1] );
# handle built-in lists directly, to avoid method dispatch overhead
if FIRST_LIST_TNUM <= tnum and tnum <= LAST_LIST_TNUM then
C:= arg[1];
if l = 1 then
if IsEmpty( C ) then
sum:= 0;
else
sum:= C[1];
for i in [ 2 .. Length( C ) ] do
sum:= sum + C[i];
od;
fi;
elif l = 2 and IsFunction( arg[2] ) then
func:= arg[2];
if IsEmpty( C ) then
sum:= 0;
else
sum:= func( C[1] );
for i in [ 2 .. Length( C ) ] do
sum:= sum + func( C[i] );
od;
fi;
elif l = 2 then
sum:= arg[2];
for i in C do
sum:= sum + i;
od;
elif l = 3 and IsFunction( arg[2] ) then
func:= arg[2];
sum:= arg[3];
for i in C do
sum:= sum + func( i );
od;
else
Error( "usage: Sum( <C>[, <func>][, <init>] )" );
fi;
return sum;
else
return CallFuncList( SumOp, arg );
fi;
end );
#############################################################################
##
#M SumOp( <C> ) . . . . . . . . . . . . . . . . . . . for a list/collection
##
InstallMethod( SumOp,
"for a list/collection",
[ IsListOrCollection ],
function ( C )
local sum;
C := Iterator( C );
if not IsDoneIterator( C ) then
sum := NextIterator( C );
while not IsDoneIterator( C ) do
sum := sum + NextIterator( C );
od;
else
sum := 0;
fi;
return sum;
end );
#############################################################################
##
#M SumOp( <C>, <func> ) . . . . . . . for a list/collection, and a function
##
InstallOtherMethod( SumOp,
"for a list/collection, and a function",
[ IsListOrCollection, IsFunction ],
function ( C, func )
local sum;
C := Iterator( C );
if not IsDoneIterator( C ) then
sum := func( NextIterator( C ) );
while not IsDoneIterator( C ) do
sum := sum + func( NextIterator( C ) );
od;
else
sum := 0;
fi;
return sum;
end );
#############################################################################
##
#M SumOp( <C>, <init> ) . . . . . . for a list/collection, and init. value
##
InstallOtherMethod( SumOp,
"for a list/collection, and init. value",
[ IsListOrCollection, IsAdditiveElement ],
function ( C, init )
C := Iterator( C );
while not IsDoneIterator( C ) do
init := init + NextIterator( C );
od;
return init;
end );
#############################################################################
##
#M SumOp( <C>, <func>, <init> ) . for a list/coll., a func., and init. val.
##
InstallOtherMethod( SumOp,
"for a list/collection, and a function, and an initial value",
[ IsListOrCollection, IsFunction, IsAdditiveElement ],
function ( C, func, init )
C := Iterator( C );
while not IsDoneIterator( C ) do
init := init + func( NextIterator( C ) );
od;
return init;
end );
#############################################################################
##
#F Product( <coll> )
#F Product( <coll>, <func> )
#F Product( <coll>, <init> )
#F Product( <coll>, <func>, <init> )
##
InstallGlobalFunction( Product,
function( arg )
local tnum, C, func, product, l, i;
l := Length(arg);
if l = 0 then
Error( "usage: Product( <C>[, <func>][, <init>] )" );
fi;
tnum:= TNUM_OBJ( arg[1] );
# handle built-in lists directly, to avoid method dispatch overhead
if FIRST_LIST_TNUM <= tnum and tnum <= LAST_LIST_TNUM then
C:= arg[1];
if l = 1 then
if IsEmpty( C ) then
product:= 1;
else
product:= C[1];
for i in [ 2 .. Length( C ) ] do
product:= product * C[i];
od;
fi;
elif l = 2 and IsFunction( arg[2] ) then
func:= arg[2];
if IsEmpty( C ) then
product:= 1;
else
product:= func( C[1] );
for i in [ 2 .. Length( C ) ] do
product:= product * func( C[i] );
od;
fi;
elif l = 2 then
product:= arg[2];
for i in C do
product:= product * i;
od;
elif l = 3 and IsFunction( arg[2] ) then
func:= arg[2];
product:= arg[3];
for i in C do
product:= product * func( i );
od;
else
Error( "usage: Product( <C>[, <func>][, <init>] )" );
fi;
return product;
else
return CallFuncList( ProductOp, arg );
fi;
end );
#############################################################################
##
#M ProductOp( <C> ) . . . . . . . . . . . . . . . . . for a list/collection
##
InstallMethod( ProductOp,
"for a list/collection",
[ IsListOrCollection ],
function ( C )
local prod;
C := Iterator( C );
if not IsDoneIterator( C ) then
prod := NextIterator( C );
while not IsDoneIterator( C ) do
prod := prod * NextIterator( C );
od;
else
prod := 1;
fi;
return prod;
end );
#############################################################################
##
#M ProductOp( <C>, <func> ) . . . . . for a list/collection, and a function
##
InstallOtherMethod( ProductOp,
"for a list/collection, and a function",
[ IsListOrCollection, IsFunction ],
function ( C, func )
local prod;
C := Iterator( C );
if not IsDoneIterator( C ) then
prod := func( NextIterator( C ) );
while not IsDoneIterator( C ) do
prod := prod * func( NextIterator( C ) );
od;
else
prod := 1;
fi;
return prod;
end );
#############################################################################
##
#M ProductOp( <C>, <init> ) . . . . for a list/collection, and init. value
##
InstallOtherMethod( ProductOp,
"for a list/collection, and initial value",
[ IsListOrCollection, IsMultiplicativeElement ],
function ( C, init )
C := Iterator( C );
while not IsDoneIterator( C ) do
init := init * NextIterator( C );
od;
return init;
end );
#############################################################################
##
#M ProductOp( <C>, <func>, <init> ) . . . for list/coll., func., init. val.
##
InstallOtherMethod( ProductOp,
"for a list/collection, a function, and an initial value",
[ IsListOrCollection, IsFunction, IsMultiplicativeElement ],
function ( C, func, init )
C := Iterator( C );
while not IsDoneIterator( C ) do
init := init * func( NextIterator( C ) );
od;
return init;
end );
#############################################################################
##
#F ProductMod(<l>,<m>) . . . . . . . . . . . . . . . . . . Product(l) mod m
##
BIND_GLOBAL( "ProductMod", function(l,m)
local i,p;
if l=[] then
p:=1;
else
p:=l[1]^0;
fi;
for i in l do
p:=p*i mod m;
od;
return p;
end );
#############################################################################
##
#F Filtered( <coll>, <func> )
##
InstallGlobalFunction( Filtered,
function( C, func )
local tnum, res, i, elm;
tnum:= TNUM_OBJ( C );
# handle built-in lists directly, to avoid method dispatch overhead
if FIRST_LIST_TNUM <= tnum and tnum <= LAST_LIST_TNUM then
# start with empty list of same representation
res := C{[]};
i := 0;
for elm in C do
if func( elm ) then
i:= i+1;
res[i]:= elm;
fi;
od;
else
res:= FilteredOp( C, func );
fi;
if HasIsSSortedList( C ) and IsSSortedList( C ) then
SetIsSSortedList( res, true );
fi;
return res;
end );
#############################################################################
##
#M FilteredOp( <C>, <func> ) . . . . . extract elements that have a property
##
InstallMethod( FilteredOp,
"for a list/collection, and a function",
[ IsListOrCollection, IsFunction ],
function ( C, func )
local res, elm;
res := [];
for elm in C do
if func( elm ) then
Add( res, elm );
fi;
od;
return res;
end );
InstallMethod( FilteredOp,
"for a list, and a function",
[ IsList, IsFunction ],
function ( C, func )
local res, elm, ob;
res := [];
for elm in [1..Length(C)] do
if IsBound(C[elm]) then
ob := C[elm];
if func( ob ) then
Add( res, ob );
fi;
fi;
od;
return res;
end );
InstallMethod( FilteredOp,
"for a dense list, and a function",
[ IsDenseList, IsFunction ],
function ( C, func )
local res, elm, ob;
res := [];
for elm in [1..Length(C)] do
ob := C[elm];
if func( ob ) then
Add( res, ob );
fi;
od;
return res;
end );
#############################################################################
##
#F Number( <coll> )
#F Number( <coll>, <func> )
##
InstallGlobalFunction( Number,
function( arg )
local tnum, C, func, nr, elm,l;
l := Length( arg );
if l = 0 then
Error( "usage: Number( <C>[, <func>] )" );
fi;
tnum:= TNUM_OBJ( arg[1] );
# handle built-in lists directly, to avoid method dispatch overhead
if FIRST_LIST_TNUM <= tnum and tnum <= LAST_LIST_TNUM then
C:= arg[1];
if l = 1 then
nr := 0;
for elm in C do
nr := nr + 1;
od;
return nr;
else
func:= arg[2];
nr := 0;
for elm in C do
if func( elm ) then
nr:= nr + 1;
fi;
od;
return nr;
fi;
else
return CallFuncList( NumberOp, arg );
fi;
end );
#############################################################################
##
#M NumberOp( <C>, <func> ) . . . . . . . count elements that have a property
##
InstallMethod( NumberOp,
"for a list/collection, and a function",
[ IsListOrCollection, IsFunction ],
function ( C, func )
local nr, elm;
nr := 0;
for elm in C do
if func( elm ) then
nr:= nr + 1;
fi;
od;
return nr;
end );
InstallMethod( NumberOp,
"for a list, and a function",
[ IsList, IsFunction ],
function ( C, func )
local nr, elm;
nr := 0;
for elm in [1..Length(C)] do
if IsBound(C[elm]) then
if func( C[elm] ) then
nr:= nr + 1;
fi;
fi;
od;
return nr;
end );
InstallMethod( NumberOp,
"for a dense list, and a function",
[ IsDenseList, IsFunction ],
function ( C, func )
local nr, elm;
nr := 0;
for elm in [1..Length(C)] do
if func( C[elm] ) then
nr:= nr + 1;
fi;
od;
return nr;
end );
#############################################################################
##
#M NumberOp( <C> ) . . . . . . . . . . . count elements
##
InstallOtherMethod( NumberOp,
"for a list/collection",
[ IsListOrCollection ],
function ( C )
local nr, elm;
nr := 0;
for elm in C do
nr := nr + 1;
od;
return nr;
end );
InstallOtherMethod( NumberOp,
"for a list",
[ IsList ],
function ( C )
local nr, elm;
nr := 0;
for elm in [1..Length(C)] do
if IsBound(C[elm]) then
nr := nr + 1;
fi;
od;
return nr;
end );
InstallOtherMethod( NumberOp,
"for a dense list",
[ IsDenseList ], Length );
#############################################################################
##
#F ForAll( <coll>, <func> )
##
InstallGlobalFunction( ForAll,
function( C, func )
local tnum, elm;
tnum:= TNUM_OBJ( C );
# handle built-in lists directly, to avoid method dispatch overhead
if FIRST_LIST_TNUM <= tnum and tnum <= LAST_LIST_TNUM then
for elm in C do
if not func( elm ) then
return false;
fi;
od;
return true;
else
return ForAllOp( C, func );
fi;
end );
#############################################################################
##
#M ForAllOp( <C>, <func> ) . . . test a property for all elements of a list
##
InstallMethod( ForAllOp,
"for a list/collection, and a function",
[ IsListOrCollection, IsFunction ],
function ( C, func )
local elm;
for elm in C do
if not func( elm ) then
return false;
fi;
od;
return true;
end );
InstallMethod( ForAllOp,
"for a list, and a function",
[ IsList and IsFinite, IsFunction ],
function ( C, func )
local elm;
for elm in [1..Length(C)] do
if IsBound(C[elm]) then
if not func( C[elm] ) then
return false;
fi;
fi;
od;
return true;
end );
InstallMethod( ForAllOp,
"for a dense list, and a function",
[ IsDenseList and IsFinite, IsFunction ],
function ( C, func )
local elm;
for elm in [1..Length(C)] do
if not func( C[elm] ) then
return false;
fi;
od;
return true;
end );
#############################################################################
##
#F ForAny( <coll>, <func> )
##
InstallGlobalFunction( ForAny,
function( C, func )
local tnum, elm;
tnum:= TNUM_OBJ( C );
# handle built-in lists directly, to avoid method dispatch overhead
if FIRST_LIST_TNUM <= tnum and tnum <= LAST_LIST_TNUM then
for elm in C do
if func( elm ) then
return true;
fi;
od;
return false;
else
return ForAnyOp( C, func );
fi;
end );
#############################################################################
##
#M ForAnyOp( <C>, <func> ) . . . . test a property for any element of a list
##
InstallMethod( ForAnyOp,
"for a list/collection, and a function",
[ IsListOrCollection, IsFunction ],
function ( C, func )
local elm;
for elm in C do
if func( elm ) then
return true;
fi;
od;
return false;
end );
InstallMethod( ForAnyOp,
"for a list, and a function",
[ IsList and IsFinite, IsFunction ],
function ( C, func )
local elm;
for elm in [1..Length(C)] do
if IsBound(C[elm]) then
if func( C[elm] ) then
return true;
fi;
fi;
od;
return false;
end );
InstallMethod( ForAnyOp,
"for a dense list, and a function",
[ IsDenseList and IsFinite, IsFunction ],
function ( C, func )
local elm;
for elm in [1..Length(C)] do
if func( C[elm] ) then
return true;
fi;
od;
return false;
end );
#############################################################################
##
#M ListX(<obj>,...)
##
DeclareGlobalName("ListXHelp");
BIND_GLOBAL( "ListXHelp", function ( result, gens, i, vals, l )
local gen, val;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := CallFuncList( gen, vals );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return;
elif IsListOrCollection( gen ) then
for val in gen do
vals[l+1] := val;
ListXHelp( result, gens, i+1, vals, l+1 );
od;
Unbind( vals[l+1] );
return;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
Add( result, CallFuncList( gens[i+1], vals ) );
end );
BIND_GLOBAL( "ListXHelp2", function ( result, gens, i, val1, val2 )
local gen, vals, val3;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen( val1, val2 );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return;
elif IsListOrCollection( gen ) then
vals := [ val1, val2 ];
for val3 in gen do
vals[3] := val3;
ListXHelp( result, gens, i+1, vals, 3 );
od;
Unbind( vals[3] );
return;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
Add( result, gens[i+1]( val1, val2 ) );
end );
BIND_GLOBAL( "ListXHelp1", function ( result, gens, i, val1 )
local gen, val2;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen( val1 );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return;
elif IsListOrCollection( gen ) then
for val2 in gen do
ListXHelp2( result, gens, i+1, val1, val2 );
od;
return;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
Add( result, gens[i+1]( val1 ) );
end );
BIND_GLOBAL( "ListXHelp0", function ( result, gens, i )
local gen, val1;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen();
fi;
if gen = true then
i := i + 1;
elif gen = false then
return;
elif IsListOrCollection( gen ) then
for val1 in gen do
ListXHelp1( result, gens, i+1, val1 );
od;
return;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
Add( result, gens[i+1]() );
end );
InstallGlobalFunction( ListX, function ( arg )
local result;
result := [];
ListXHelp0( result, arg, 0 );
return result;
end );
#############################################################################
##
#M SetX(<obj>,...)
##
DeclareGlobalName("SetXHelp");
BIND_GLOBAL( "SetXHelp", function ( result, gens, i, vals, l )
local gen, val;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := CallFuncList( gen, vals );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return;
elif IsListOrCollection( gen ) then
for val in gen do
vals[l+1] := val;
SetXHelp( result, gens, i+1, vals, l+1 );
od;
Unbind( vals[l+1] );
return;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
AddSet( result, CallFuncList( gens[i+1], vals ) );
end );
BIND_GLOBAL( "SetXHelp2", function ( result, gens, i, val1, val2 )
local gen, vals, val3;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen( val1, val2 );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return;
elif IsListOrCollection( gen ) then
vals := [ val1, val2 ];
for val3 in gen do
vals[3] := val3;
SetXHelp( result, gens, i+1, vals, 3 );
od;
Unbind( vals[3] );
return;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
AddSet( result, gens[i+1]( val1, val2 ) );
end );
BIND_GLOBAL( "SetXHelp1", function ( result, gens, i, val1 )
local gen, val2;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen( val1 );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return;
elif IsListOrCollection( gen ) then
for val2 in gen do
SetXHelp2( result, gens, i+1, val1, val2 );
od;
return;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
AddSet( result, gens[i+1]( val1 ) );
end );
BIND_GLOBAL( "SetXHelp0", function ( result, gens, i )
local gen, val1;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen();
fi;
if gen = true then
i := i + 1;
elif gen = false then
return;
elif IsListOrCollection( gen ) then
for val1 in gen do
SetXHelp1( result, gens, i+1, val1 );
od;
return;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
AddSet( result, gens[i+1]() );
end );
InstallGlobalFunction( SetX, function ( arg )
local result;
result := [];
SetXHelp0( result, arg, 0 );
return result;
end );
#############################################################################
##
#M SumX(<obj>,...)
##
DeclareGlobalName("SumXHelp");
BIND_GLOBAL( "SumXHelp", function ( result, gens, i, vals, l )
local gen, val;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := CallFuncList( gen, vals );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return result;
elif IsListOrCollection( gen ) then
for val in gen do
vals[l+1] := val;
result := SumXHelp( result, gens, i+1, vals, l+1 );
od;
Unbind( vals[l+1] );
return result;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
if result = fail then
result := CallFuncList( gens[i+1], vals );
else
result := result + CallFuncList( gens[i+1], vals );
fi;
return result;
end );
BIND_GLOBAL( "SumXHelp2", function ( result, gens, i, val1, val2 )
local gen, vals, val3;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen( val1, val2 );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return result;
elif IsListOrCollection( gen ) then
vals := [ val1, val2 ];
for val3 in gen do
vals[3] := val3;
result := SumXHelp( result, gens, i+1, vals, 3 );
od;
Unbind( vals[3] );
return result;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
if result = fail then
result := gens[i+1]( val1, val2 );
else
result := result + gens[i+1]( val1, val2 );
fi;
return result;
end );
BIND_GLOBAL( "SumXHelp1", function ( result, gens, i, val1 )
local gen, val2;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen( val1 );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return result;
elif IsListOrCollection( gen ) then
for val2 in gen do
result := SumXHelp2( result, gens, i+1, val1, val2 );
od;
return result;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
if result = fail then
result := gens[i+1]( val1 );
else
result := result + gens[i+1]( val1 );
fi;
return result;
end );
BIND_GLOBAL( "SumXHelp0", function ( result, gens, i )
local gen, val1;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen();
fi;
if gen = true then
i := i + 1;
elif gen = false then
return result;
elif IsListOrCollection( gen ) then
for val1 in gen do
result := SumXHelp1( result, gens, i+1, val1 );
od;
return result;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
if result = fail then
result := gens[i+1]();
else
result := result + gens[i+1]();
fi;
return result;
end );
InstallGlobalFunction( SumX, function ( arg )
local result;
result := fail;
result := SumXHelp0( result, arg, 0 );
return result;
end );
#############################################################################
##
#M ProductX(<obj>,...)
##
DeclareGlobalName("ProductXHelp");
BIND_GLOBAL( "ProductXHelp", function ( result, gens, i, vals, l )
local gen, val;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := CallFuncList( gen, vals );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return result;
elif IsListOrCollection( gen ) then
for val in gen do
vals[l+1] := val;
result := ProductXHelp( result, gens, i+1, vals, l+1 );
od;
Unbind( vals[l+1] );
return result;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
if result = fail then
result := CallFuncList( gens[i+1], vals );
else
result := result * CallFuncList( gens[i+1], vals );
fi;
return result;
end );
BIND_GLOBAL( "ProductXHelp2", function ( result, gens, i, val1, val2 )
local gen, vals, val3;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen( val1, val2 );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return result;
elif IsListOrCollection( gen ) then
vals := [ val1, val2 ];
for val3 in gen do
vals[3] := val3;
result := ProductXHelp( result, gens, i+1, vals, 3 );
od;
Unbind( vals[3] );
return result;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
if result = fail then
result := gens[i+1]( val1, val2 );
else
result := result * gens[i+1]( val1, val2 );
fi;
return result;
end );
BIND_GLOBAL( "ProductXHelp1", function ( result, gens, i, val1 )
local gen, val2;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen( val1 );
fi;
if gen = true then
i := i + 1;
elif gen = false then
return result;
elif IsListOrCollection( gen ) then
for val2 in gen do
result := ProductXHelp2( result, gens, i+1, val1, val2 );
od;
return result;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
if result = fail then
result := gens[i+1]( val1 );
else
result := result * gens[i+1]( val1 );
fi;
return result;
end );
BIND_GLOBAL( "ProductXHelp0", function ( result, gens, i )
local gen, val1;
while i+1 < Length(gens) do
gen := gens[i+1];
if IsFunction( gen ) then
gen := gen();
fi;
if gen = true then
i := i + 1;
elif gen = false then
return result;
elif IsListOrCollection( gen ) then
for val1 in gen do
result := ProductXHelp1( result, gens, i+1, val1 );
od;
return result;
else
Error( "gens[",i+1,"] must be a collection, a list, a boolean, ",
"or a function" );
fi;
od;
if result = fail then
result := gens[i+1]();
else
result := result * gens[i+1]();
fi;
return result;
end );
InstallGlobalFunction( ProductX, function ( arg )
local result;
result := fail;
result := ProductXHelp0( result, arg, 0 );
return result;
end );
#############################################################################
##
#F Perform( <list>, <func> )
##
InstallGlobalFunction( Perform, function(l, f)
local x;
for x in l do
f(x);
od;
end);
#############################################################################
##
#M IsSubset( <C1>, <C2> )
##
InstallMethod( IsSubset,
"for two collections in different families",
IsNotIdenticalObj,
[ IsCollection,
IsCollection ],
ReturnFalse );
InstallMethod( IsSubset,
"for empty list and collection",
[ IsList and IsEmpty,
IsCollection ],
function( empty, coll )
return IsEmpty( coll );
end );
InstallMethod( IsSubset,
"for collection and empty list",
[ IsCollection,
IsList and IsEmpty ],
ReturnTrue );
InstallMethod( IsSubset,
"for two collections, the first containing the whole family",
IsIdenticalObj,
[ IsCollection and IsWholeFamily,
IsCollection ],
SUM_FLAGS+2, # better than everything else, however we must override the
# following two which are already ranked high.
ReturnTrue );
InstallMethod( IsSubset,
"for two collections, check for identity",
IsIdenticalObj,
[ IsCollection,
IsCollection ],
SUM_FLAGS+1, # better than the following method
function ( D, E )
if not IsIdenticalObj( D, E ) then
TryNextMethod();
fi;
return true;
end );
InstallMethod( IsSubset,
"for two collections with known sizes, check sizes",
IsIdenticalObj,
[ IsCollection and HasSize,
IsCollection and HasSize ],
SUM_FLAGS, # do this before everything else
function ( D, E )
if Size( E ) <= Size( D ) then
TryNextMethod();
fi;
return false;
end );
InstallMethod( IsSubset,
"for two internal lists",
[ IsList and IsInternalRep,
IsList and IsInternalRep ],
IsSubsetSet );
InstallMethod( IsSubset,
"for two collections that are internal lists",
IsIdenticalObj,
[ IsCollection and IsList and IsInternalRep,
IsCollection and IsList and IsInternalRep ],
IsSubsetSet );
InstallMethod( IsSubset,
"for two collections with known `AsSSortedList'",
IsIdenticalObj,
[ IsCollection and HasAsSSortedList,
IsCollection and HasAsSSortedList ],
function ( D, E )
return IsSubsetSet( AsSSortedList( D ), AsSSortedList( E ) );
end );
InstallMethod( IsSubset,
"for two collections (loop over the elements of the second)",
IsIdenticalObj,
[ IsCollection,
IsCollection ],
function( D, E )
return ForAll( E, e -> e in D );
end );
#############################################################################
##
#M Intersection( <C>, ... )
##
BIND_GLOBAL( "IntersectionSet", function ( C1, C2 )
local I;
if Length( C1 ) < Length( C2 ) then
I := Set( C1 );
IntersectSet( I, C2 );
else
I := Set( C2 );
IntersectSet( I, C1 );
fi;
return I;
end );
InstallOtherMethod( Intersection2,
"for two lists (not necessarily in the same family)",
[ IsList, IsList ],
IntersectionSet );
InstallOtherMethod( Intersection2,
"for two lists or collections, the second being empty",
[ IsListOrCollection, IsListOrCollection and IsEmpty ],
function(C1, C2) return []; end);
InstallOtherMethod( Intersection2,
"for two lists or collections, the first being empty",
[ IsListOrCollection and IsEmpty, IsListOrCollection ],
function(C1, C2) return []; end);
InstallMethod( Intersection2,
"for two collections in the same family, both lists",
IsIdenticalObj,
[ IsCollection and IsList, IsCollection and IsList ],
IntersectionSet );
InstallMethod( Intersection2,
"for two collections in different families",
IsNotIdenticalObj,
[ IsCollection, IsCollection ],
function( C1, C2 ) return []; end );
InstallMethod( Intersection2,
"for two collections in the same family, the second being a list",
IsIdenticalObj,
[ IsCollection, IsCollection and IsList ],
function ( C1, C2 )
local I, elm;
if ( HasIsFinite( C1 ) or CanComputeSize( C1 ) ) and IsFinite( C1 ) then
I := ShallowCopy( AsSSortedList( C1 ) );
IntersectSet( I, C2 );
else
I := [];
for elm in C2 do
if elm in C1 then
AddSet( I, elm );
fi;
od;
fi;
return I;
end );
InstallMethod( Intersection2,
"for two collections in the same family, the first being a list",
IsIdenticalObj,
[ IsCollection and IsList, IsCollection ],
function ( C1, C2 )
local I, elm;
if ( HasIsFinite( C2 ) or CanComputeSize( C2 ) ) and IsFinite( C2 ) then
I := ShallowCopy( AsSSortedList( C2 ) );
IntersectSet( I, C1 );
else
I := [];
for elm in C1 do
if elm in C2 then
AddSet( I, elm );
fi;
od;
fi;
return I;
end );
InstallMethod( Intersection2,
"for two collections in the same family",
IsIdenticalObj,
[ IsCollection, IsCollection ],
function ( C1, C2 )
local I, elm;
if IsFinite( C1 ) then
if IsFinite( C2 ) then
I := ShallowCopy( AsSSortedList( C1 ) );
IntersectSet( I, AsSSortedList( C2 ) );
else
I := [];
for elm in C1 do
if elm in C2 then
AddSet( I, elm );
fi;
od;
fi;
elif IsFinite( C2 ) then
I := [];
for elm in C2 do
if elm in C1 then
AddSet( I, elm );
fi;
od;
else
TryNextMethod();
fi;
return I;
end );
InstallGlobalFunction( Intersection, function ( arg )
local I, # intersection, result
--> --------------------
--> maximum size reached
--> --------------------
[ Dauer der Verarbeitung: 0.39 Sekunden
(vorverarbeitet)
]
|
