|
#############################################################################
##
## 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 declares the operations for collections.
##
#T change the installation of isomorphism and factor maintained methods
#T in the same way as that of subset maintained methods!
#############################################################################
##
## <#GAPDoc Label="[1]{coll}">
## A <E>collection</E> in &GAP; consists of elements in the same family
## (see <Ref Sect="Families"/>).
## The most important kinds of collections are <E>homogeneous lists</E>
## (see <Ref Chap="Lists"/>)
## and <E>domains</E> (see <Ref Chap="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.
## <P/>
## Basic operations for collections are <Ref Attr="Size"/>
## and <Ref Attr="Enumerator"/>;
## for <E>finite</E> collections,
## <Ref Attr="Enumerator"/> admits to delegate the other
## operations for collections
## (see <Ref Sect="Attributes and Properties for Collections"/>
## and <Ref Sect="Operations for Collections"/>)
## to functions for lists (see <Ref Chap="Lists"/>).
## Obviously, special methods depending on the arguments are needed for
## the computation of e.g. the intersection of two <E>infinite</E>
## domains.
## <#/GAPDoc>
##
#############################################################################
##
#C IsListOrCollection( <obj> )
##
## <#GAPDoc Label="IsListOrCollection">
## <ManSection>
## <Filt Name="IsListOrCollection" Arg='obj' Type='Category'/>
##
## <Description>
## Several functions are defined for both lists and collections,
## for example <Ref Func="Intersection" Label="for a list"/>,
## <Ref Oper="Iterator"/>,
## and <Ref Oper="Random" Label="for a list or collection"/>.
## <Ref Filt="IsListOrCollection"/> is a supercategory of
## <Ref Filt="IsList"/> and <Ref Filt="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.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategory( "IsListOrCollection", IsObject );
#############################################################################
##
#C IsCollection( <obj> ) . . . . . . . . . test if an object is a collection
##
## <#GAPDoc Label="IsCollection">
## <ManSection>
## <Filt Name="IsCollection" Arg='obj' Type='Category'/>
##
## <Description>
## tests whether an object is a collection.
## <P/>
## Some of the functions for lists and collections are described in the
## chapter about lists,
## mainly in Section <Ref Sect="Operations for Lists"/>.
## In the current chapter, we describe those functions for which the
## <Q>collection aspect</Q> seems to be more important than the
## <Q>list aspect</Q>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategory( "IsCollection", IsListOrCollection );
#############################################################################
##
#A CollectionsFamily( <Fam> ) . . . . . . . . . . make a collections family
##
## <#GAPDoc Label="CollectionsFamily">
## <ManSection>
## <Attr Name="CollectionsFamily" Arg='Fam'/>
##
## <Description>
## For a family <A>Fam</A>, <Ref Attr="CollectionsFamily"/> returns the
## family of all collections over <A>Fam</A>,
## that is, of all dense lists and domains that consist of objects in
## <A>Fam</A>.
## <P/>
## The <Ref Func="NewFamily"/> call in the standard method of
## <Ref Attr="CollectionsFamily"/> is executed with second argument
## <Ref Filt="IsCollection"/>,
## since every object in the collections family must be a collection,
## and with third argument the collections categories of the involved
## categories in the implied filter of <A>Fam</A>.
## <P/>
## Note that families (see <Ref Sect="Families"/>)
## are used to describe relations between objects.
## Important such relations are that between an element <M>e</M> and each
## collection of elements that lie in the same family as <M>e</M>,
## and that between two collections whose elements lie in the same family.
## Therefore, all collections of elements in the family <A>Fam</A> form the
## new family <C>CollectionsFamily( <A>Fam</A> )</C>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "CollectionsFamily", IsFamily );
#############################################################################
##
#C IsCollectionFamily( <Fam> ) test if an object is a family of collections
##
## <#GAPDoc Label="IsCollectionFamily">
## <ManSection>
## <Filt Name="IsCollectionFamily" Arg='obj' Type='Category'/>
##
## <Description>
## is <K>true</K> if <A>Fam</A> is a family of collections,
## and <K>false</K> otherwise.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategoryFamily( "IsCollection" );
#############################################################################
##
#A ElementsFamily( <Fam> ) . . . . . . . . . . . . fetch the elements family
##
## <#GAPDoc Label="ElementsFamily">
## <ManSection>
## <Attr Name="ElementsFamily" Arg='Fam'/>
##
## <Description>
## If <A>Fam</A> is a collections family
## (see <Ref Filt="IsCollectionFamily"/>)
## then <Ref Attr="ElementsFamily"/>
## returns the family from which <A>Fam</A> was created
## by <Ref Attr="CollectionsFamily"/>.
## The way a collections family is created, it always has its elements
## family stored.
## If <A>Fam</A> is not a collections family then an error is signalled.
## <P/>
## <Example><![CDATA[
## gap> fam:= FamilyObj( (1,2) );;
## gap> collfam:= CollectionsFamily( fam );;
## gap> fam = collfam; fam = ElementsFamily( collfam );
## false
## true
## gap> collfam = FamilyObj( [ (1,2,3) ] );
## true
## gap> collfam = FamilyObj( Group( () ) );
## true
## gap> collfam = CollectionsFamily( collfam );
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "ElementsFamily", IsFamily );
#############################################################################
##
#V CATEGORIES_COLLECTIONS . . . . . . global list of collections categories
##
## <ManSection>
## <Var Name="CATEGORIES_COLLECTIONS"/>
##
## <Description>
## </Description>
## </ManSection>
##
BIND_GLOBAL( "CATEGORIES_COLLECTIONS", [] );
if IsHPCGAP then
ShareSpecialObj(CATEGORIES_COLLECTIONS, "CATEGORIES_COLLECTIONS");
fi;
#############################################################################
##
#F CategoryCollections( <filter> ) . . . . . . . . . . collections category
##
## <#GAPDoc Label="CategoryCollections">
## <ManSection>
## <Func Name="CategoryCollections" Arg='filter'/>
##
## <Description>
## Let <A>filter</A> be a filter that is <K>true</K> for all elements of a
## family <A>Fam</A>, by the construction of <A>Fam</A>.
## Then <Ref Func="CategoryCollections"/> returns the
## <E>collections category</E> of <A>filter</A>.
## This is a category that is <K>true</K> for all elements in
## <C>CollectionsFamily( <A>Fam</A> )</C>.
## <P/>
## For example, the construction of
## <Ref Fam="PermutationsFamily"/> guarantees that
## each of its elements lies in the filter
## <Ref Filt="IsPerm"/>,
## and each collection of permutations (permutation group or dense list of
## permutations) lies in the category <C>CategoryCollections( IsPerm )</C>.
## <C>CategoryCollections( IsPerm )</C>.
## Note that this works only if the collections category is created
## <E>before</E> the collections family.
## So it is necessary to construct interesting collections categories
## immediately after the underlying category has been created.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BIND_GLOBAL( "CategoryCollections", function ( elms_filter )
local pair, super, flags, name, coll_filter, len;
# check once with read lock -- common case
atomic readonly CATEGORIES_COLLECTIONS do
# Check whether the collections category is already defined.
for pair in CATEGORIES_COLLECTIONS do
if IsIdenticalObj( pair[1], elms_filter ) then
return pair[2];
fi;
od;
if IsHPCGAP then
len := LENGTH(CATEGORIES_COLLECTIONS);
fi;
od; # end atomic
# that failed, so get exclusive lock as we may need to modify
atomic readwrite CATEGORIES_COLLECTIONS do
if IsHPCGAP then
# Check whether in the meantime another thread defined the collections category
if LENGTH(CATEGORIES_COLLECTIONS) > len then
for pair in CATEGORIES_COLLECTIONS do
if IsIdenticalObj( pair[1], elms_filter ) then
return pair[2];
fi;
od;
fi;
fi;
# Find the super category among the known collections categories.
super := IsCollection;
flags := WITH_IMPS_FLAGS( FLAGS_FILTER( elms_filter ) );
for pair in CATEGORIES_COLLECTIONS do
if IS_SUBSET_FLAGS( flags, FLAGS_FILTER( pair[1] ) ) then
super := super and pair[2];
fi;
od;
# Construct the name of the category.
name := "CategoryCollections(";
APPEND_LIST_INTR( name, SHALLOW_COPY_OBJ( NameFunction(elms_filter) ) );
APPEND_LIST_INTR( name, ")" );
CONV_STRING( name );
# Construct the collections category.
coll_filter:= NewCategory( name, super );
ADD_LIST( CATEGORIES_COLLECTIONS, MakeImmutable([ elms_filter, coll_filter ]) );
return coll_filter;
od; # end atomic
end );
#############################################################################
##
#f DeclareCategoryCollections( <name> )
##
## <#GAPDoc Label="DeclareCategoryCollections">
## <ManSection>
## <Func Name="DeclareCategoryCollections" Arg='name'/>
##
## <Description>
## Calls <Ref Func="CategoryCollections"/> on the category that is bound to
## the global variable with name <A>name</A> to obtain its collections
## category, and binds the latter to the global variable with name
## <C>nname</C>. This name is defined as follows: If <A>name</A> is of the
## form <C><A>Something</A>Collection</C> then <C>nname</C> is set to
## <C><A>Something</A>CollColl</C>, if <A>name</A> is of the form
## <C><A>Something</A>Coll</C> then <C>nname</C> is set to
## <C><A>Something</A>CollColl</C>, otherwise we set <C>nname</C> to
## <C><A>name</A>Collection</C>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BIND_GLOBAL( "NameOfCategoryCollections", function( name )
local len, coll_name;
len:= LEN_LIST( name );
if 3 < len and name{ [ len-3 .. len ] } = "Coll" then
coll_name:= SHALLOW_COPY_OBJ( name );
APPEND_LIST_INTR( coll_name, "Coll" );
elif 9 < len and name{ [ len-9 .. len ] } = "Collection" then
coll_name:= name{ [ 1 .. len-6 ] };
APPEND_LIST_INTR( coll_name, "Coll" );
else
coll_name:= SHALLOW_COPY_OBJ( name );
APPEND_LIST_INTR( coll_name, "Collection" );
fi;
return coll_name;
end );
BIND_GLOBAL( "DeclareCategoryCollections", function( name )
local coll_name;
coll_name := NameOfCategoryCollections( name );
BIND_GLOBAL( coll_name, CategoryCollections( VALUE_GLOBAL( name ) ) );
end );
#############################################################################
##
#F DeclareSynonym( <name>, <value> )
#F DeclareSynonymAttr( <name>, <value> )
##
## <#GAPDoc Label="DeclareSynonym">
## <ManSection>
## <Func Name="DeclareSynonym" Arg='name, value'/>
## <Func Name="DeclareSynonymAttr" Arg='name, value'/>
##
## <Description>
## <Ref Func="DeclareSynonym"/> assigns the string <A>name</A> to a global
## variable as a synonym for <A>value</A>.
## Two typical intended usages are to declare an <Q>and-filter</Q>, e.g.
## <P/>
## <Log><![CDATA[
## DeclareSynonym( "IsGroup", IsMagmaWithInverses and IsAssociative );
## ]]></Log>
## <P/>
## and to provide a previously declared global function with an alternative
## name, e.g.
## <P/>
## <Log><![CDATA[
## DeclareGlobalFunction( "SizeOfSomething" );
## DeclareSynonym( "OrderOfSomething", SizeOfSomething );
## ]]></Log>
## <P/>
## <E>Note:</E> Before using <Ref Func="DeclareSynonym"/> in the way of this
## second example,
## one should determine whether the synonym is really needed.
## Perhaps an extra index entry in the documentation would be sufficient.
## <P/>
## When <A>value</A> is actually an attribute then
## <Ref Func="DeclareSynonymAttr"/> should be used;
## this binds also globals variables <C>Set</C><A>name</A> and
## <C>Has</C><A>name</A> for its setter and tester, respectively.
## <P/>
## <Log><![CDATA[
## DeclareSynonymAttr( "IsField", IsDivisionRing and IsCommutative );
## DeclareAttribute( "GeneratorsOfDivisionRing", IsDivisionRing );
## DeclareSynonymAttr( "GeneratorsOfField", GeneratorsOfDivisionRing );
## ]]></Log>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BIND_GLOBAL( "DeclareSynonym", function( name, value )
if ISBOUND_GLOBAL(name) and IS_IDENTICAL_OBJ(VALUE_GLOBAL(name), value) then
if not REREADING then
INFO_DEBUG( 1, "multiple declarations for synonym `", name, "'\n" );
fi;
else
BIND_GLOBAL( name, value );
fi;
end );
BIND_GLOBAL( "DeclareSynonymAttr", function( name, value )
local nname;
DeclareSynonym( name, value );
nname:= "Set";
APPEND_LIST_INTR( nname, name );
DeclareSynonym( nname, Setter( value ) );
nname:= "Has";
APPEND_LIST_INTR( nname, name );
DeclareSynonym( nname, Tester( value ) );
end );
#############################################################################
##
#V SUBSET_MAINTAINED_INFO
##
## <ManSection>
## <Var Name="SUBSET_MAINTAINED_INFO"/>
##
## <Description>
## is a list of length two.
## At the first position, a list of lists of the form
## <C>[ <A>filtsuper</A>, <A>filtsub</A>, <A>opr</A>, <A>testopr</A>, <A>settopr</A> ]</C>
## is stored,
## which is used for calls of <C>UseSubsetRelation( <A>super</A>, <A>sub</A> )</C>.
## At the second position, a corresponding list of lists of the form
## <C>[ <A>flagsopr</A>, <A>flagssub</A>, <A>rank</A> ]</C>
## is stored, which is used for choosing an appropriate ordering of the
## entries when the lists are enlarged in a call to
## <C>InstallSubsetMaintenance</C>.
## <P/>
## The meaning of the entries is as follows.
## <List>
## <Mark><A>filtsuper</A> </Mark>
## <Item>
## required filter for <A>super</A>,
## </Item>
## <Mark><A>filtsub</A> </Mark>
## <Item>
## required filter for <A>sub</A>,
## </Item>
## <Mark><A>opr</A> </Mark>
## <Item>
## operation whose value is inherited from <A>super</A> to <A>sub</A>,
## </Item>
## <Mark><A>testopr</A> </Mark>
## <Item>
## tester filter of <A>opr</A>,
## </Item>
## <Mark><A>settopr</A> </Mark>
## <Item>
## setter filter of <A>opr</A>,
## </Item>
## <Mark><A>flagsopr</A> </Mark>
## <Item>
## list of those true flags of <A>opr</A>
## that belong neither to categories nor to representations,
## </Item>
## <Mark><A>flagssub</A> </Mark>
## <Item>
## list of those true flags of <A>filtsub</A>
## that belong neither to categories nor to representations,
## </Item>
## <Mark><A>rank</A> </Mark>
## <Item>
## a rational number that denotes the priority of the information
## in the list; <C>SUBSET_MAINTAINED_INFO</C> is sorted according to
## decreasing <A>rank</A> value.
## <!-- We must be careful to choose the right succession of the methods.-->
## <!-- Note that one method may require a property that is acquired using-->
## <!-- another method.-->
## <!-- For that, we give a method a rank that is lower than that of all methods-->
## <!-- that may yield some of the requirements and that is higher than that of-->
## <!-- all methods that require <A>opr</A>;-->
## <!-- if this is not possible then a warning is printed.-->
## <!-- (Maybe the mechanism has to be changed at some time because of this.-->
## <!-- Another reason would be the direct installation of methods for-->
## <!-- <C>UseSubsetRelation</C>, i.e., the ranks of these methods are not affected-->
## <!-- by the code in <C>InstallSubsetMaintenance</C>.) -->
## </Item>
## </List>
## </Description>
## </ManSection>
##
BIND_GLOBAL( "SUBSET_MAINTAINED_INFO", [ [], [] ] );
if IsHPCGAP then
ShareSpecialObj(SUBSET_MAINTAINED_INFO, "SUBSET_MAINTAINED_INFO");
fi;
#############################################################################
##
#O UseSubsetRelation( <super>, <sub> )
##
## <#GAPDoc Label="UseSubsetRelation">
## <ManSection>
## <Oper Name="UseSubsetRelation" Arg='super, sub'/>
##
## <Description>
## Methods for this operation transfer possibly useful information from the
## domain <A>super</A> to its subset <A>sub</A>, and vice versa.
## <P/>
## <Ref Oper="UseSubsetRelation"/> is designed to be called automatically
## whenever substructures of domains are constructed.
## So the methods must be <E>cheap</E>, and the requirements should be as
## sharp as possible!
## <P/>
## To achieve that <E>all</E> applicable methods are executed, all methods for
## this operation except the default method must end with <C>TryNextMethod()</C>.
## This default method deals with the information that is available by
## the calls of <Ref Func="InstallSubsetMaintenance"/> in the &GAP; library.
## <P/>
## <Example><![CDATA[
## gap> g:= Group( (1,2), (3,4), (5,6) );; h:= Group( (1,2), (3,4) );;
## gap> IsAbelian( g ); HasIsAbelian( h );
## true
## false
## gap> UseSubsetRelation( g, h );; HasIsAbelian( h ); IsAbelian( h );
## true
## true
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "UseSubsetRelation", [ IsCollection, IsCollection ] );
InstallMethod( UseSubsetRelation,
"default method that checks maintenances and then returns `true'",
IsIdenticalObj,
[ IsCollection, IsCollection ],
# Make sure that this method is installed with ``real'' rank zero.
{} -> - 2 * RankFilter( IsCollection ),
function( super, sub )
local entry;
atomic readonly SUBSET_MAINTAINED_INFO do
for entry in SUBSET_MAINTAINED_INFO[1] do
if entry[1]( super ) and entry[2]( sub ) and not entry[4]( sub ) then
entry[5]( sub, entry[3]( super ) );
fi;
od;
od; # end atomic
return true;
end );
#############################################################################
##
#F InstallSubsetMaintenance( <opr>, <super_req>, <sub_req> )
##
## <#GAPDoc Label="InstallSubsetMaintenance">
## <ManSection>
## <Func Name="InstallSubsetMaintenance" Arg='opr, super_req, sub_req'/>
##
## <Description>
## <A>opr</A> must be a property or an attribute.
## The call of <Ref Func="InstallSubsetMaintenance"/> has the effect that
## for a domain <M>D</M> in the filter <A>super_req</A>,
## and a domain <M>S</M> in the filter <A>sub_req</A>,
## the call <C>UseSubsetRelation</C><M>( D, S )</M>
## (see <Ref Oper="UseSubsetRelation"/>)
## sets a known value of <A>opr</A> for <M>D</M> as value of <A>opr</A> also
## for <M>S</M>.
## A typical example for which <Ref Func="InstallSubsetMaintenance"/> is
## applied is given by <A>opr</A> <C>= IsFinite</C>,
## <A>super_req</A> <C>= IsCollection and IsFinite</C>,
## and <A>sub_req</A> <C>= IsCollection</C>.
## <P/>
## If <A>opr</A> is a property and the filter <A>super_req</A> lies in the
## filter <A>opr</A> then we can use also the following inverse implication.
## If <M>D</M> is in the filter whose intersection with <A>opr</A> is
## <A>super_req</A> and if <M>S</M> is in the filter <A>sub_req</A>,
## <M>S</M> is a subset of <M>D</M>, and the value of <A>opr</A> for
## <M>S</M> is <K>false</K> then the value of <A>opr</A> for <M>D</M> is
## also <K>false</K>.
## <!-- This is implemented only for the case <A>super_req</A> = <A>opr</A>
## and <A>sub_req</A>.-->
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BIND_GLOBAL( "InstallSubsetMaintenance",
function( operation, super_req, sub_req )
local setter, # setter filter of `operation'
tester, # tester filter of `operation'
upper,
lower,
attrprop, # id `operation' an attribute/property?
rank,
filtssub, # property and attribute flags of `sub_req'
filtsopr, # property and attribute flags of `operation'
triple, # loop over `SUBSET_MAINTAINED_INFO[2]'
req,
flag,
filt1,
filt2,
i;
setter:= Setter( operation );
tester:= Tester( operation );
# Are there methods that may give us some of the requirements?
upper:= SUM_FLAGS;
# (We must not call `SUBTR_SET' here because the lists types may be
# not yet defined.)
filtssub:= [];
atomic readwrite SUBSET_MAINTAINED_INFO, readonly FILTER_REGION do
for flag in TRUES_FLAGS( FLAGS_FILTER( sub_req ) ) do
if not INFO_FILTERS[flag] in FNUM_CATS_AND_REPS then
ADD_LIST_DEFAULT( filtssub, flag );
fi;
od;
for triple in SUBSET_MAINTAINED_INFO[2] do
req:= SHALLOW_COPY_OBJ( filtssub );
INTER_SET( req, triple[1] );
if LEN_LIST( req ) <> 0 and triple[3] < upper then
upper:= triple[3];
fi;
od;
# Are there methods that require `operation'?
lower:= 0;
attrprop:= true;
filt1:= FLAGS_FILTER( operation );
if filt1 = false then
# `operation' is an attribute.
filt1:= FLAGS_FILTER( tester );
else
# Special treatment of categories, representations (makes sense?),
# and filters created by `NewFilter'.
if FLAG2_FILTER( operation ) = 0 then
attrprop:= false;
fi;
fi;
# (We must not call `SUBTR_SET' here because the lists types may be
# not yet defined.)
filtsopr:= [];
for flag in TRUES_FLAGS( filt1 ) do
if not INFO_FILTERS[flag] in FNUM_CATS_AND_REPS then
ADD_LIST_DEFAULT( filtsopr, flag );
fi;
od;
for triple in SUBSET_MAINTAINED_INFO[2] do
req:= SHALLOW_COPY_OBJ( filtsopr );
INTER_SET( req, triple[2] );
if LEN_LIST( req ) <> 0 and lower < triple[3] then
lower:= triple[3];
fi;
od;
# Compute the ``rank'' of the maintenance.
# (Do we have a cycle?)
if upper <= lower then
Print( "#W warning: cycle in `InstallSubsetMaintenance'\n" );
rank:= lower;
else
rank:= ( upper + lower ) / 2;
fi;
filt1:= IsCollection and Tester( super_req ) and super_req and tester;
filt2:= IsCollection and Tester( sub_req ) and sub_req;
# Update the info list.
i:= LEN_LIST( SUBSET_MAINTAINED_INFO[2] );
while 0 < i and SUBSET_MAINTAINED_INFO[2][i][3] < rank do
SUBSET_MAINTAINED_INFO[1][ i+1 ]:= SUBSET_MAINTAINED_INFO[1][ i ];
SUBSET_MAINTAINED_INFO[2][ i+1 ]:= SUBSET_MAINTAINED_INFO[2][ i ];
i:= i-1;
od;
SUBSET_MAINTAINED_INFO[2][ i+1 ]:=
MakeImmutable([ filtsopr, filtssub, rank ]);
if attrprop then
SUBSET_MAINTAINED_INFO[1][ i+1 ]:=
MakeImmutable([ filt1, filt2, operation, tester, setter ]);
else
SUBSET_MAINTAINED_INFO[1][ i+1 ]:= MakeImmutable(
[ filt1, filt2, operation, operation,
function( sub, val )
if val then
SetFilterObj( sub, operation );
else
ResetFilterObj( sub, operation );
fi;
end ]);
fi;
od; # end atomic
#T missing in new implementation!
# # Install the method.
# if FLAGS_FILTER( operation ) <> false
# and IS_EQUAL_FLAGS( FLAGS_FILTER( operation and sub_req ),
# FLAGS_FILTER( super_req ) ) then
# InstallMethod( UseSubsetRelation, infostring, IsIdenticalObj,
# [ sub_req, sub_req ], 0,
# function( super, sub )
# if tester( sub ) and not operation( sub ) then
# setter( super, false );
# fi;
# TryNextMethod();
# end );
# fi;
end );
#############################################################################
##
#V ISOMORPHISM_MAINTAINED_INFO
##
## <ManSection>
## <Var Name="ISOMORPHISM_MAINTAINED_INFO"/>
##
## <Description>
## is a list of lists of the form
## <C>[ <A>filtsold</A>, <A>filtsnew</A>, <A>opr</A>, <A>testopr</A>, <A>settopr</A>, <A>old_req</A>,
## <A>new-req</A> ]</C>
## which is used for calls of <C>UseIsomorphismRelation( <A>old</A>, <A>new</A> )</C>.
## This list is enlarged by calls to <C>InstallIsomorphismMaintenance</C>.
## <P/>
## The meaning of the entries is as follows.
## <List>
## <Mark><A>filtsold</A> </Mark>
## <Item>
## required filter for <A>old</A>,
## </Item>
## <Mark><A>filtsnew</A> </Mark>
## <Item>
## required filter for <A>new</A>,
## </Item>
## <Mark><A>opr</A> </Mark>
## <Item>
## operation whose value is inherited from <A>old</A> to <A>new</A>,
## </Item>
## <Mark><A>testopr</A> </Mark>
## <Item>
## tester filter of <A>opr</A>,
## </Item>
## <Mark><A>settopr</A> </Mark>
## <Item>
## setter filter of <A>opr</A>,
## </Item>
## <Mark><A>old-req</A> </Mark>
## <Item>
## requirements for <A>old</A> in the <C>InstallIsomorphismMaintenance</C> call,
## </Item>
## <Mark><A>new-req</A> </Mark>
## <Item>
## requirements for <A>new</A> in the <C>InstallIsomorphismMaintenance</C> call.
## </Item>
## </List>
## </Description>
## </ManSection>
##
BIND_GLOBAL( "ISOMORPHISM_MAINTAINED_INFO", [] );
if IsHPCGAP then
ShareSpecialObj(ISOMORPHISM_MAINTAINED_INFO, "ISOMORPHISM_MAINTAINED_INFO");
fi;
#############################################################################
##
#O UseIsomorphismRelation( <old>, <new> )
##
## <#GAPDoc Label="UseIsomorphismRelation">
## <ManSection>
## <Oper Name="UseIsomorphismRelation" Arg='old, new'/>
##
## <Description>
## Methods for this operation transfer possibly useful information from the
## domain <A>old</A> to the isomorphic domain <A>new</A>.
## <P/>
## <Ref Oper="UseIsomorphismRelation"/> is designed to be called
## automatically whenever isomorphic structures of domains are constructed.
## So the methods must be <E>cheap</E>, and the requirements should be as
## sharp as possible!
## <P/>
## To achieve that <E>all</E> applicable methods are executed, all methods
## for this operation except the default method must end with a call to
## <Ref Func="TryNextMethod"/>.
## This default method deals with the information that is available by
## the calls of <Ref Func="InstallIsomorphismMaintenance"/> in the &GAP;
## library.
## <P/>
## <Example><![CDATA[
## gap> g:= Group( (1,2) );; h:= Group( [ [ -1 ] ] );;
## gap> Size( g ); HasSize( h );
## 2
## false
## gap> UseIsomorphismRelation( g, h );; HasSize( h ); Size( h );
## true
## 2
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "UseIsomorphismRelation", [ IsCollection, IsCollection ] );
InstallMethod( UseIsomorphismRelation,
"default method that checks maintenances and then returns `true'",
[ IsCollection, IsCollection ],
# Make sure that this method is installed with ``real'' rank zero.
{} -> - 2 * RankFilter( IsCollection ),
function( old, new )
local entry;
atomic readonly ISOMORPHISM_MAINTAINED_INFO do
for entry in ISOMORPHISM_MAINTAINED_INFO do
if entry[1]( old ) and entry[2]( new ) and not entry[4]( new ) then
entry[5]( new, entry[3]( old ) );
fi;
od;
od; # end atomic
return true;
end );
#############################################################################
##
#F InstallIsomorphismMaintenance( <opr>, <old_req>, <new_req> )
##
## <#GAPDoc Label="InstallIsomorphismMaintenance">
## <ManSection>
## <Func Name="InstallIsomorphismMaintenance" Arg='opr, old_req, new_req'/>
##
## <Description>
## <A>opr</A> must be a property or an attribute.
## The call of <Ref Func="InstallIsomorphismMaintenance"/> has the effect
## that for a domain <M>D</M> in the filter <A>old_req</A>,
## and a domain <M>E</M> in the filter <A>new_req</A>,
## the call <C>UseIsomorphismRelation</C><M>( D, E )</M>
## (see <Ref Oper="UseIsomorphismRelation"/>)
## sets a known value of <A>opr</A> for <M>D</M> as value of <A>opr</A> also
## for <M>E</M>.
## A typical example for which <Ref Func="InstallIsomorphismMaintenance"/>
## is applied is given by <A>opr</A> <C>= Size</C>,
## <A>old_req</A> <C>= IsCollection</C>,
## and <A>new_req</A> <C>= IsCollection</C>.
## <!-- Up to now, there are no dependencies between the maintenances-->
## <!-- (contrary to the case of subset maintenances),-->
## <!-- so we do not take care of the succession.-->
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BIND_GLOBAL( "InstallIsomorphismMaintenance",
function( opr, old_req, new_req )
local tester;
tester:= Tester( opr );
atomic ISOMORPHISM_MAINTAINED_INFO do
ADD_LIST( ISOMORPHISM_MAINTAINED_INFO, MakeImmutable(
[ IsCollection and Tester( old_req ) and old_req and tester,
IsCollection and Tester( new_req ) and new_req,
opr,
tester,
Setter( opr ),
old_req,
new_req ] ) );
od; # end atomic
end );
#############################################################################
##
#V FACTOR_MAINTAINED_INFO
##
## <ManSection>
## <Var Name="FACTOR_MAINTAINED_INFO"/>
##
## <Description>
## is a list of lists of the form
## <C>[ <A>filtsnum</A>, <A>filtsden</A>, <A>filtsfac</A>, <A>opr</A>, <A>testopr</A>, <A>settopr</A> ]</C>
## which is used for calls of <C>UseFactorRelation( <A>num</A>, <A>den</A>, <A>fac</A> )</C>.
## This list is enlarged by calls to <C>InstallFactorMaintenance</C>.
## <P/>
## The meaning of the entries is as follows.
## <List>
## <Mark><A>filtsnum</A> </Mark>
## <Item>
## required filter for <A>num</A>,
## </Item>
## <Mark><A>filtsden</A> </Mark>
## <Item>
## required filter for <A>den</A>,
## </Item>
## <Mark><A>filtsfac</A> </Mark>
## <Item>
## required filter for <A>fac</A>,
## </Item>
## <Mark><A>opr</A> </Mark>
## <Item>
## operation whose value is inherited from <A>num</A> to <A>fac</A>,
## </Item>
## <Mark><A>testopr</A> </Mark>
## <Item>
## tester filter of <A>opr</A>,
## </Item>
## <Mark><A>settopr</A> </Mark>
## <Item>
## setter filter of <A>opr</A>.
## </Item>
## </List>
## </Description>
## </ManSection>
##
BIND_GLOBAL( "FACTOR_MAINTAINED_INFO", [] );
if IsHPCGAP then
ShareSpecialObj(FACTOR_MAINTAINED_INFO, "FACTOR_MAINTAINED_INFO");
fi;
#############################################################################
##
#O UseFactorRelation( <numer>, <denom>, <factor> )
##
## <#GAPDoc Label="UseFactorRelation">
## <ManSection>
## <Oper Name="UseFactorRelation" Arg='numer, denom, factor'/>
##
## <Description>
## Methods for this operation transfer possibly useful information from the
## domain <A>numer</A> or its subset <A>denom</A> to the domain
## <A>factor</A> that is isomorphic to the factor of <A>numer</A> by
## <A>denom</A>, and vice versa.
## <A>denom</A> may be <K>fail</K>, for example if <A>factor</A> is just
## known to be a factor of <A>numer</A> but <A>denom</A> is not available as
## a &GAP; object;
## in this case those factor relations are used that are installed without
## special requirements for <A>denom</A>.
## <P/>
## <Ref Oper="UseFactorRelation"/> is designed to be called automatically
## whenever factor structures of domains are constructed.
## So the methods must be <E>cheap</E>, and the requirements should be as
## sharp as possible!
## <P/>
## To achieve that <E>all</E> applicable methods are executed, all methods
## for this operation except the default method must end with a call to
## <Ref Func="TryNextMethod"/>.
## This default method deals with the information that is available by
## the calls of <Ref Func="InstallFactorMaintenance"/> in the &GAP; library.
## <P/>
## <Example><![CDATA[
## gap> g:= Group( (1,2,3,4), (1,2) );; h:= Group( (1,2,3), (1,2) );;
## gap> IsSolvableGroup( g ); HasIsSolvableGroup( h );
## true
## false
## gap> UseFactorRelation(g, Subgroup( g, [ (1,2)(3,4), (1,3)(2,4) ] ), h);;
## gap> HasIsSolvableGroup( h ); IsSolvableGroup( h );
## true
## true
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "UseFactorRelation",
[ IsCollection, IsObject, IsCollection ] );
InstallMethod( UseFactorRelation,
"default method that checks maintenances and then returns `true'",
true,
[ IsCollection, IsObject, IsCollection ],
# Make sure that this method is installed with ``real'' rank zero.
{} -> - 2 * RankFilter( IsCollection )-RankFilter(IsObject),
function( num, den, fac )
local entry;
atomic readonly FACTOR_MAINTAINED_INFO do
for entry in FACTOR_MAINTAINED_INFO do
if entry[1]( num ) and entry[2]( den ) and entry[3]( fac )
and not entry[5]( fac ) then
entry[6]( fac, entry[4]( num ) );
fi;
od;
od; # end atomic
return true;
end );
#############################################################################
##
#F InstallFactorMaintenance( <opr>, <numer_req>, <denom_req>, <factor_req> )
##
## <#GAPDoc Label="InstallFactorMaintenance">
## <ManSection>
## <Func Name="InstallFactorMaintenance"
## Arg='opr, numer_req, denom_req, factor_req'/>
##
## <Description>
## <A>opr</A> must be a property or an attribute.
## The call of <Ref Func="InstallFactorMaintenance"/> has the effect that
## for collections <M>N</M>, <M>D</M>, <M>F</M> in the filters
## <A>numer_req</A>, <A>denom_req</A>, and <A>factor_req</A>, respectively,
## the call <C>UseFactorRelation</C><M>( N, D, F )</M>
## (see <Ref Oper="UseFactorRelation"/>)
## sets a known value of <A>opr</A> for <M>N</M> as value of <A>opr</A> also
## for <M>F</M>.
## A typical example for which <Ref Func="InstallFactorMaintenance"/> is
## applied is given by <A>opr</A> <C>= IsFinite</C>,
## <A>numer_req</A> <C>= IsCollection and IsFinite</C>,
## <A>denom_req</A> <C>= IsCollection</C>,
## and <A>factor_req</A> <C>= IsCollection</C>.
## <P/>
## For the other direction, if <A>numer_req</A> involves the filter
## <A>opr</A> then a known <K>false</K> value of <A>opr</A> for <M>F</M>
## implies a <K>false</K> value for <M>D</M> provided that <M>D</M> lies in
## the filter obtained from <A>numer_req</A> by removing <A>opr</A>.
## <P/>
## Note that an implication of a factor relation holds in particular for the
## case of isomorphisms.
## So one need <E>not</E> install an isomorphism maintained method when
## a factor maintained method is already installed.
## For example, <Ref Oper="UseIsomorphismRelation"/>
## will transfer a known <Ref Prop="IsFinite"/> value because of the
## installed factor maintained method.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
BIND_GLOBAL( "InstallFactorMaintenance",
function( opr, numer_req, denom_req, factor_req )
local tester;
# Information that is maintained under taking factors
# is especially maintained under isomorphisms.
InstallIsomorphismMaintenance( opr, numer_req, factor_req );
tester:= Tester( opr );
atomic FACTOR_MAINTAINED_INFO do
ADD_LIST( FACTOR_MAINTAINED_INFO, MakeImmutable(
[ IsCollection and Tester( numer_req ) and numer_req and tester,
Tester( denom_req ) and denom_req,
IsCollection and Tester( factor_req ) and factor_req,
opr,
tester,
Setter( opr ) ] ) );
od; # end atomic
#T not yet available in the new implementation
# if FLAGS_FILTER( opr ) <> false
# and IS_EQUAL_FLAGS( FLAGS_FILTER( opr and factor_req ),
# FLAGS_FILTER( numer_req ) ) then
# InstallMethod( UseFactorRelation, infostring, IsFamFamX,
# [ factor_req, denom_req, factor_req ], 0,
# function( numer, denom, factor )
# if tester( factor ) and not opr( factor ) then
# setter( numer, false );
# fi;
# TryNextMethod();
# end );
# fi;
end );
#############################################################################
##
#O Iterator( <listorcoll> ) . . . . . . . iterator for a list or collection
##
## <#GAPDoc Label="Iterator">
## <ManSection>
## <Oper Name="Iterator" Arg='listorcoll'/>
## <Filt Name="IsStandardIterator" Arg='listorcoll'/>
##
## <Description>
## Iterators provide a possibility to loop over the elements of a
## (countable) collection or list <A>listorcoll</A>, without repetition.
## For many collections <M>C</M>,
## an iterator of <M>C</M> need not store all elements of <M>C</M>,
## for example it is possible to construct an iterator of some infinite
## domains, such as the field of rational numbers.
## <P/>
## <Ref Oper="Iterator"/> returns a mutable <E>iterator</E> <M>iter</M> for
## its argument.
## If this argument is a list (which may contain holes),
## then <M>iter</M> iterates over the elements (but not the holes) of this
## list in the same order (see <Ref Func="IteratorList"/> for details).
## If this argument is a collection but not a list then <M>iter</M> iterates
## over the elements of this collection in an unspecified order,
## which may change for repeated calls of <Ref Oper="Iterator"/>.
## Because iterators returned by <Ref Oper="Iterator"/> are mutable
## (see <Ref Sect="Mutability and Copyability"/>),
## each call of <Ref Oper="Iterator"/> for the same argument returns a
## <E>new</E> iterator.
## Therefore <Ref Oper="Iterator"/> is not an attribute
## (see <Ref Sect="Attributes"/>).
## <P/>
## The only operations for iterators are <Ref Oper="IsDoneIterator"/>,
## <Ref Oper="NextIterator"/>, and <Ref Oper="ShallowCopy"/>.
## In particular, it is only possible to access the next element of the
## iterator with <Ref Oper="NextIterator"/> if there is one,
## and this can be checked with <Ref Oper="IsDoneIterator"/>
## For an iterator <M>iter</M>, <Ref Oper="ShallowCopy"/> returns a
## mutable iterator <M>new</M> that iterates over the remaining elements
## independent of <M>iter</M>;
## the results of <Ref Oper="IsDoneIterator"/> for <M>iter</M> and
## <M>new</M> are equal,
## and if <M>iter</M> is mutable then also the results of
## <Ref Oper="NextIterator"/> for <M>iter</M> and <M>new</M> are equal;
## note that <C>=</C> is not defined for iterators,
## so the equality of two iterators cannot be checked with <C>=</C>.
## <P/>
## When <Ref Oper="Iterator"/> is called for a <E>mutable</E> collection
## <M>C</M> then it is not defined whether <M>iter</M> respects changes to
## <M>C</M> occurring after the construction of <M>iter</M>,
## except if the documentation explicitly promises a certain behaviour.
## The latter is the case if the argument is a mutable list
## (see <Ref Func="IteratorList"/> for subtleties in this case).
## <P/>
## It is possible to have <K>for</K>-loops run over mutable iterators
## instead of lists.
## <P/>
## In some situations, one can construct iterators with a special
## succession of elements,
## see <Ref Oper="IteratorByBasis"/> for the possibility to loop over
## the elements of a vector space w.r.t. a given basis.
## <!-- (also for perm. groups, w.r.t. a given stabilizer chain?)-->
## <P/>
## For lists, <Ref Oper="Iterator"/> is implemented by
## <Ref Func="IteratorList"/>.
## For collections <M>C</M> that are not lists, the default method is
## <C>IteratorList( Enumerator( </C><M>C</M><C> ) )</C>.
## Better methods depending on <M>C</M> should be provided if possible.
## <P/>
## For random access to the elements of a (possibly infinite) collection,
## <E>enumerators</E> are used.
## See <Ref Sect="Enumerators"/> for the facility to compute a list
## from <M>C</M>, which provides a (partial) mapping from <M>C</M> to the
## positive integers.
## <P/>
## The filter <Ref Filt="IsStandardIterator"/> means that the iterator is
## implemented as a component object and has components <C>IsDoneIterator</C>
## and <C>NextIterator</C> which are bound to the methods of the operations of
## the same name for this iterator.
## <!-- (This is used to avoid overhead when looping over such iterators.) -->
## <!-- We wanted to admit an iterator as first argument of <C>Filtered</C>,-->
## <!-- <C>First</C>, <C>ForAll</C>, <C>ForAny</C>, <C>Number</C>.-->
## <!-- This is not yet implemented.-->
## <!-- (Note that the iterator is changed in the call,-->
## <!-- so the meaning of the operations would be slightly abused,-->
## <!-- or we must define that these operations first make a shallow copy.)-->
## <!-- (Additionally, the unspecified order of the elements makes it-->
## <!-- difficult to define what <C>First</C> and <C>Filtered</C> means for an iterator.)-->
## <Example><![CDATA[
## 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 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareFilter("IsStandardIterator");
DeclareOperation( "Iterator", [ IsListOrCollection ] );
#############################################################################
##
#O IteratorSorted( <C> ) . . . . . . . . . . . set iterator for a collection
#O IteratorSorted( <list> ) . . . . . . . . . . . . set iterator for a list
##
## <#GAPDoc Label="IteratorSorted">
## <ManSection>
## <Oper Name="IteratorSorted" Arg='listorcoll'/>
##
## <Description>
## <Ref Oper="IteratorSorted"/> returns a mutable iterator.
## The argument must be a collection or a list that is not
## necessarily dense but whose elements lie in the same family
## (see <Ref Sect="Families"/>).
## It loops over the different elements in sorted order.
## <P/>
## For a collection <M>C</M> that is not a list, the generic method is
## <C>IteratorList( EnumeratorSorted( </C><A>C</A><C> ) )</C>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "IteratorSorted", [ IsListOrCollection ] );
#############################################################################
##
#C IsIterator( <obj> ) . . . . . . . . . . test if an object is an iterator
##
## <#GAPDoc Label="IsIterator">
## <ManSection>
## <Filt Name="IsIterator" Arg='obj' Type='Category'/>
##
## <Description>
## Every iterator lies in the category <C>IsIterator</C>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategory( "IsIterator", IsObject );
#############################################################################
##
#O IsDoneIterator( <iter> ) . . . . . . . test if an iterator is exhausted
##
## <#GAPDoc Label="IsDoneIterator">
## <ManSection>
## <Oper Name="IsDoneIterator" Arg='iter'/>
##
## <Description>
## If <A>iter</A> is an iterator for the list or collection <M>C</M> then
## <C>IsDoneIterator( <A>iter</A> )</C> is <K>true</K> if all elements of
## <M>C</M> have been returned already by <C>NextIterator( <A>iter</A> )</C>,
## and <K>false</K> otherwise.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "IsDoneIterator", [ IsIterator ] );
#############################################################################
##
#O NextIterator( <iter> ) . . . . . . . . . . next element from an iterator
##
## <#GAPDoc Label="NextIterator">
## <ManSection>
## <Oper Name="NextIterator" Arg='iter'/>
##
## <Description>
## Let <A>iter</A> be a mutable iterator for the list or collection <M>C</M>.
## If <C>IsDoneIterator( <A>iter</A> )</C> is <K>false</K> then
## <Ref Oper="NextIterator"/> is applicable to <A>iter</A>,
## and the result is the next element of <M>C</M>,
## according to the succession defined by <A>iter</A>.
## <P/>
## If <C>IsDoneIterator( <A>iter</A> )</C> is <K>true</K> then it is not
## defined what happens when <Ref Oper="NextIterator"/> is called for
## <A>iter</A>;
## that is, it may happen that an error is signalled or that something
## meaningless is returned, or even that &GAP; crashes.
## <P/>
## <Example><![CDATA[
## 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
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "NextIterator", [ IsIterator and IsMutable ] );
#############################################################################
##
#F TrivialIterator( <elm> )
##
## <#GAPDoc Label="TrivialIterator">
## <ManSection>
## <Func Name="TrivialIterator" Arg='elm'/>
##
## <Description>
## is a mutable iterator for the collection <C>[ <A>elm</A> ]</C> that
## consists of exactly one element <A>elm</A>
## (see <Ref Prop="IsTrivial"/>).
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "TrivialIterator" );
#############################################################################
##
#F IteratorByFunctions( <record> )
##
## <#GAPDoc Label="IteratorByFunctions">
## <ManSection>
## <Func Name="IteratorByFunctions" Arg='record'/>
##
## <Description>
## <Ref Func="IteratorByFunctions"/> returns a (mutable) iterator
## <A>iter</A> for which <Ref Oper="NextIterator"/>,
## <Ref Oper="IsDoneIterator"/>,
## and <Ref Oper="ShallowCopy"/>
## are computed via prescribed functions.
## <P/>
## Let <A>record</A> be a record with at least the following components.
## <List>
## <Mark><C>NextIterator</C></Mark>
## <Item>
## a function taking one argument <A>iter</A>,
## which returns the next element of <A>iter</A>
## (see <Ref Oper="NextIterator"/>);
## for that, the components of <A>iter</A> are changed,
## </Item>
## <Mark><C>IsDoneIterator</C></Mark>
## <Item>
## a function taking one argument <A>iter</A>,
## which returns the <Ref Oper="IsDoneIterator"/> value of <A>iter</A>,
## </Item>
## <Mark><C>ShallowCopy</C></Mark>
## <Item>
## a function taking one argument <A>iter</A>,
## which returns a record for which <Ref Func="IteratorByFunctions"/>
## can be called in order to create a new iterator that is independent
## of <A>iter</A> but behaves like <A>iter</A> w.r.t. the operations
## <Ref Oper="NextIterator"/> and <Ref Oper="IsDoneIterator"/>.
## </Item>
## <Mark><C>ViewObj</C> and <C>PrintObj</C></Mark>
## <Item>
## two functions that print what one wants to be printed when
## <C>View( <A>iter</A> )</C> or <C>Print( <A>item</A> )</C> is called
## (see <Ref Sect="View and Print"/>),
## if the <C>ViewObj</C> component is missing then the <C>PrintObj</C>
## method is used as a default.
## </Item>
## </List>
## Further (data) components may be contained in <A>record</A> which can be
## used by these function.
## <P/>
## <Ref Func="IteratorByFunctions"/> does <E>not</E> make a shallow copy of
## <A>record</A>, this record is changed in place
## (see Section <Ref Sect="Creating Objects"/>).
## <P/>
## Iterators constructed with <Ref Func="IteratorByFunctions"/> are in the
## filter <Ref Filt="IsStandardIterator"/>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "IteratorByFunctions" );
#############################################################################
##
#P IsEmpty( <C> ) . . . . . . . . . . . . . . test if a collection is empty
#P IsEmpty( <list> ) . . . . . . . . . . . . . test if a collection is empty
##
## <#GAPDoc Label="IsEmpty">
## <ManSection>
## <Prop Name="IsEmpty" Arg='listorcoll'/>
##
## <Description>
## <Ref Prop="IsEmpty"/> returns <K>true</K> if the collection or list
## <A>listorcoll</A> is <E>empty</E> (that is it contains no elements),
## and <K>false</K> otherwise.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsEmpty", IsListOrCollection );
#############################################################################
##
#P IsTrivial( <C> ) . . . . . . . . . . . . test if a collection is trivial
##
## <#GAPDoc Label="IsTrivial">
## <ManSection>
## <Prop Name="IsTrivial" Arg='C'/>
##
## <Description>
## <Ref Prop="IsTrivial"/> returns <K>true</K> if the collection <A>C</A>
## consists of exactly one element.
## <!-- 1996/08/08 M.Schönert is this a sensible definition?-->
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsTrivial", IsCollection );
InstallFactorMaintenance( IsTrivial,
IsCollection and IsTrivial, IsObject, IsCollection );
#############################################################################
##
#P IsNonTrivial( <C> ) . . . . . . . . . test if a collection is nontrivial
##
## <#GAPDoc Label="IsNonTrivial">
## <ManSection>
## <Prop Name="IsNonTrivial" Arg='C'/>
##
## <Description>
## <Ref Prop="IsNonTrivial"/> returns <K>true</K> if the collection <A>C</A>
## is empty or consists of at least two elements
## (see <Ref Prop="IsTrivial"/>).
## <P/>
## <!-- I need this to distinguish trivial rings-with-one from fields!-->
## <!-- (indication to introduce antifilters?)-->
## <!-- 1996/08/08 M.Schönert is this a sensible definition?-->
## <Example><![CDATA[
## 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
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsNonTrivial", IsCollection );
InstallTrueMethod( IsNonTrivial, IsEmpty );
InstallTrueMethod( HasIsTrivial, IsNonTrivial );
InstallTrueMethod( HasIsEmpty, IsTrivial );
InstallTrueMethod( HasIsNonTrivial, IsTrivial );
#############################################################################
##
#P IsFinite( <C> ) . . . . . . . . . . . . . test if a collection is finite
##
## <#GAPDoc Label="IsFinite">
## <ManSection>
## <Prop Name="IsFinite" Arg='C'/>
##
## <Description>
## <Index Subkey="for a list or collection">finiteness test</Index>
## <Ref Prop="IsFinite"/> returns <K>true</K> if the collection <A>C</A>
## is finite, and <K>false</K> otherwise.
## <P/>
## The default method for <Ref Prop="IsFinite"/> checks the size
## (see <Ref Attr="Size"/>) of <A>C</A>.
## <P/>
## Methods for <Ref Prop="IsFinite"/> may call <Ref Attr="Size"/>,
## but methods for <Ref Attr="Size"/> must <E>not</E> call
## <Ref Prop="IsFinite"/>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsFinite", IsListOrCollection );
InstallSubsetMaintenance( IsFinite,
IsCollection and IsFinite, IsCollection );
InstallFactorMaintenance( IsFinite,
IsCollection and IsFinite, IsObject, IsCollection );
InstallTrueMethod( IsFinite, IsTrivial );
InstallTrueMethod( IsFinite, IsEmpty );
#############################################################################
##
#P IsWholeFamily( <C> ) . . test if a collection contains the whole family
##
## <#GAPDoc Label="IsWholeFamily">
## <ManSection>
## <Prop Name="IsWholeFamily" Arg='C'/>
##
## <Description>
## <Ref Prop="IsWholeFamily"/> returns <K>true</K> if the collection
## <A>C</A> contains the whole family (see <Ref Sect="Families"/>)
## of its elements.
## <P/>
## <Example><![CDATA[
## 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
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsWholeFamily", IsCollection );
#############################################################################
##
#A Size( <C> ) . . . . . . . . . . . . . . . . . . . . size of a collection
#A Size( <list> ) . . . . . . . . . . . . . . . . . . size of a collection
##
## <#GAPDoc Label="Size">
## <ManSection>
## <Attr Name="Size" Arg='listorcoll'/>
##
## <Description>
## <Index Subkey="of a list or collection">size</Index>
## <Index Subkey="of a list, collection or domain">order</Index>
## <Ref Attr="Size"/> returns the size of the list or collection
## <A>listorcoll</A>, which is either an integer or <Ref Var="infinity"/>.
## If the argument is a list then the result is its length
## (see <Ref Attr="Length"/>).
## <P/>
## The default method for <Ref Attr="Size"/> checks the length of an
## enumerator of <A>listorcoll</A>.
## <P/>
## Methods for <Ref Prop="IsFinite"/> may call <Ref Attr="Size"/>,
## but methods for <Ref Attr="Size"/> must not call <Ref Prop="IsFinite"/>.
## <P/>
## <Example><![CDATA[
## gap> Size( [1,2,3] ); Size( Group( () ) ); Size( Integers );
## 3
## 1
## infinity
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "Size", IsListOrCollection );
InstallIsomorphismMaintenance( Size, IsCollection, IsCollection );
#############################################################################
##
#A Representative( <C> ) . . . . . . . . . . . . one element of a collection
##
## <#GAPDoc Label="Representative">
## <ManSection>
## <Attr Name="Representative" Arg='C'/>
##
## <Description>
## <Ref Attr="Representative"/> returns a <E>representative</E>
## of the collection <A>C</A>.
## <P/>
## Note that <Ref Attr="Representative"/> is free in choosing
## a representative if there are several elements in <A>C</A>.
## It is not even guaranteed that <Ref Attr="Representative"/> returns
## the same representative if it is called several times for one collection.
## The main difference between <Ref Attr="Representative"/> and
## <Ref Oper="Random" Label="for a list or collection"/>
## is that <Ref Attr="Representative"/> is free
## to choose a value that is cheap to compute,
## while <Ref Oper="Random" Label="for a list or collection"/>
## must make an effort to randomly distribute its answers.
## <P/>
## If <A>C</A> is a domain then there are methods for
## <Ref Attr="Representative"/> that try
## to fetch an element from any known generator list of <A>C</A>,
## see <Ref Chap="Domains and their Elements"/>.
## Note that <Ref Attr="Representative"/> does not try to <E>compute</E>
## generators of <A>C</A>,
## thus <Ref Attr="Representative"/> may give up and signal an error
## if <A>C</A> has no generators stored at all.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "Representative", IsListOrCollection );
#############################################################################
##
#A RepresentativeSmallest( <C> ) . . . . . smallest element of a collection
##
## <#GAPDoc Label="RepresentativeSmallest">
## <ManSection>
## <Attr Name="RepresentativeSmallest" Arg='C'/>
##
## <Description>
## <Index Subkey="of a list or collection">representative</Index>
## returns the smallest element in the collection <A>C</A>, w.r.t. the
## ordering <Ref Oper="\<"/>.
## While the operation defaults to comparing all elements,
## better methods are installed for some collections.
## <P/>
## <Example><![CDATA[
## gap> Representative( Rationals );
## 0
## gap> Representative( [ -1, -2 .. -100 ] );
## -1
## gap> RepresentativeSmallest( [ -1, -2 .. -100 ] );
## -100
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "RepresentativeSmallest", IsListOrCollection );
#############################################################################
##
#O Random( <C> ) . . . . . . . . . . random element of a nonempty collection
#O Random( <list> ) . . . . . . . random element of a dense, nonempty list
#O Random( <from>, <to> )
##
## <#GAPDoc Label="Random:coll">
## <ManSection>
## <Oper Name="Random" Arg='listorcoll' Label="for a list or collection"/>
## <Oper Name="Random" Arg='from, to' Label="for lower and upper bound"/>
##
## <Description>
## <!-- to get this on top of results for ?Random -->
## <Index Key="Random"><Ref Oper="Random"
## Label="for a list or collection"/></Index>
## <Ref Oper="Random" Label="for a list or collection"/> returns a
## (pseudo-)random element of the dense, nonempty list or nonempty
## collection <A>listorcoll</A>.
## The behaviour for non-dense or empty lists, and for empty collections
## (see <Ref Filt="IsDenseList"/>, <Ref Prop="IsEmpty"/>)
## is undefined.
## <P/>
## As lists or ranges are restricted in length (<M>2^{28}-1</M> or
## <M>2^{60}-1</M> depending on your system), the second form returns a
## random integer in the range <A>from</A> to <A>to</A> (inclusive) for
## arbitrary integers <A>from</A> and <A>to</A>.
## The behaviour in the case that <A>from</A> is larger than <A>to</A>
## is undefined.
## <P/>
## See Section <Ref Sect="Random Sources"/> for more about computing
## random elements, in particular for
## <Ref Oper="Random" Label="for random source and list"/> methods
## that take a random source as the first argument.
## <P/>
## The distribution of elements returned by
## <Ref Oper="Random" Label="for a list or collection"/> depends
## on the argument.
## For a dense, nonempty list the distribution is uniform (all elements are
## equally likely).
## The same holds usually for finite collections that are
## not lists.
## For infinite collections some reasonable distribution is used.
## <P/>
## See the chapters of the various collections to find out
## which distribution is being used.
## <P/>
## For some collections ensuring a reasonable distribution can be
## difficult and require substantial runtime (for example for large
## finite groups). If speed is more important than a guaranteed
## distribution,
## the operation <Ref Oper="PseudoRandom"/> should be used instead.
## <P/>
## Note that <Ref Oper="Random" Label="for a list or collection"/>
## is of course <E>not</E> an attribute.
## <P/>
## <Example><![CDATA[
## gap> Random([1..6]);
## 6
## gap> Random(1, 2^100);
## 866227015645295902682304086250
## gap> g:= Group( (1,2,3) );; Random( g ); Random( g );
## (1,3,2)
## ()
## gap> Random(Rationals);
## -4
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
# We keep the declaration for non-dense lists
# in order not to break existing code.
DeclareOperation( "Random", [ IsListOrCollection ] );
DeclareOperation( "Random", [ IS_INT, IS_INT ] );
#############################################################################
##
## <#GAPDoc Label="[2]{coll}">
## The method used by &GAP; to obtain random elements may depend on the
## type object.
## <P/>
## Most methods which produce random elements in &GAP; use a global random
## number generator (see <Ref Var="GlobalMersenneTwister"/>).
## 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.
## <P/>
## See <Ref Oper="Reset"/> for a description of how to reset the
## random number generator to a previous state.
## <P/>
## <#/GAPDoc>
##
#############################################################################
##
#F RandomList( [<rs>, ]<list> )
##
## <#GAPDoc Label="RandomList">
## <ManSection>
## <Func Name="RandomList" Arg='[rs,] list'/>
##
## <Description>
## <Index>random seed</Index>
## For a dense list <A>list</A>,
## <Ref Func="RandomList"/> returns a (pseudo-)random element with equal
## distribution.
## <P/>
## The random source <A>rs</A> (see <Ref Sect="Random Sources"/>)
## is used to choose a random number.
## If <A>rs</A> is absent,
## this function uses the <Ref Var="GlobalMersenneTwister"/> to produce the
## random elements (a source of high quality random numbers).
## <P/>
## <Example><![CDATA[
## gap> RandomList( [ 1 .. 6 ] );
## 3
## gap> elms:= AsList( Group( (1,2,3) ) );;
## gap> RandomList( elms ); RandomList( elms );
## (1,3,2)
## (1,2,3)
## gap> rs:= RandomSource( IsMersenneTwister, 1 );
## <RandomSource in IsMersenneTwister>
## gap> RandomList( rs, elms );
## (1,3,2)
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "RandomList" );
#############################################################################
##
#O PseudoRandom( <C> ) . . . . . . . . pseudo random element of a collection
#O PseudoRandom( <list> ) . . . . . . . . . pseudo random element of a list
##
## <#GAPDoc Label="PseudoRandom">
## <ManSection>
## <Oper Name="PseudoRandom" Arg='listorcoll'/>
##
## <Description>
## <Ref Oper="PseudoRandom"/> returns a pseudo random element
## of the list or collection <A>listorcoll</A>,
## which can be roughly described as follows.
## For a list, <Ref Oper="PseudoRandom"/> returns the same as
## <Ref Oper="Random" Label="for a list or collection"/>.
## For collections that are not lists,
## the elements returned by <Ref Oper="PseudoRandom"/> are
## <E>not</E> necessarily equally distributed,
## even for finite collections;
## the idea is that <Ref Oper="Random" Label="for a list or collection"/>
## returns elements according to
## a reasonable distribution, <Ref Oper="PseudoRandom"/> returns elements
## that are cheap to compute but need not satisfy this strong condition, and
## <Ref Attr="Representative"/> returns arbitrary elements,
## probably the same element for each call.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "PseudoRandom", [ IsListOrCollection ] );
#############################################################################
##
#A PseudoRandomSeed( <C> )
##
## <ManSection>
## <Attr Name="PseudoRandomSeed" Arg='C'/>
##
## <Description>
## </Description>
## </ManSection>
##
DeclareAttribute( "PseudoRandomSeed", IsListOrCollection, "mutable" );
#############################################################################
##
#A Enumerator( <C> ) . . . . . . . . . . . list of elements of a collection
#A Enumerator( <list> ) . . . . . . . . . . . . list of elements of a list
##
## <#GAPDoc Label="Enumerator">
## <ManSection>
## <Attr Name="Enumerator" Arg='listorcoll'/>
##
## <Description>
## <Ref Attr="Enumerator"/> returns an immutable list <M>enum</M>.
## If the argument is a list (which may contain holes),
## then <C>Length( </C><M>enum</M><C> )</C> is the length of this list,
## and <M>enum</M> contains the elements (and holes) of this list in the
## same order.
## If the argument is a collection that is not a list,
## then <C>Length( </C><M>enum</M><C> )</C> is the number of different
## elements of <A>C</A>,
## and <M>enum</M> contains the different elements of the collection in an
## unspecified order, which may change for repeated calls of
## <Ref Attr="Enumerator"/>.
## <M>enum[pos]</M> may not execute in constant time
## (see <Ref Filt="IsConstantTimeAccessList"/>),
## and the size of <M>enum</M> in memory is as small as is feasible.
## <P/>
## For lists, the default method is <Ref Func="Immutable"/>.
## For collections that are not lists, there is no default method.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "Enumerator", IsListOrCollection );
#############################################################################
##
#A EnumeratorSorted( <C> ) . . . . . proper set of elements of a collection
#A EnumeratorSorted( <list> ) . . . . . . proper set of elements of a list
##
## <#GAPDoc Label="EnumeratorSorted">
## <ManSection>
## <Attr Name="EnumeratorSorted" Arg='listorcoll'/>
##
## <Description>
## <Ref Attr="EnumeratorSorted"/> returns an immutable list <M>enum</M>.
--> --------------------
--> maximum size reached
--> --------------------
[ Dauer der Verarbeitung: 0.53 Sekunden
(vorverarbeitet)
]
|
