|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Martin Schönert, Werner Nickel.
##
## 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 the definition of operations and functions for lists.
##
#############################################################################
##
#C IsList( <obj> ) . . . . . . . . . . . . . . . test if an object is a list
##
## <#GAPDoc Label="IsList">
## <ManSection>
## <Filt Name="IsList" Arg='obj' Type='Category'/>
##
## <Description>
## tests whether <A>obj</A> is a list.
## <P/>
## <Example><![CDATA[
## gap> IsList( [ 1, 3, 5, 7 ] ); IsList( 1 );
## true
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategoryKernel( "IsList", IsListOrCollection, IS_LIST );
#############################################################################
##
#V ListsFamily . . . . . . . . . . . . . . . . . . . . . . . family of lists
##
## <ManSection>
## <Var Name="ListsFamily"/>
##
## <Description>
## </Description>
## </ManSection>
##
BIND_GLOBAL( "ListsFamily", NewFamily( "ListsFamily", IsList ) );
#############################################################################
##
#R IsPlistRep . . . . . . . . . . . . . . . . representation of plain lists
##
## <#GAPDoc Label="IsPlistRep">
## <ManSection>
## <Filt Name="IsPlistRep" Arg='obj' Type='Representation'/>
##
## <Description>
## &GAP; lists created by entering comma separated values in square brackets
## are usually represented internally as so-called <E>plain lists</E>.
## Other representations of lists are <Ref Filt="IsBlistRep"/>,
## <Ref Filt="IsRangeRep"/>, <Ref Filt="IsStringRep"/>,
## or the ones that are chosen for implementing enumerators,
## see Section <Ref Sect="Enumerators"/>.
## <P/>
## <Example><![CDATA[
## gap> IsPlistRep( [ 1, 2, 3 ] );
## true
## gap> IsPlistRep( "abc" );
## false
## gap> IsPlistRep( [ 1 .. 5 ] );
## false
## gap> IsPlistRep( BlistList( [ 1 .. 5 ], [ 1 ] ) );
## false
## gap> IsPlistRep( 0 );
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareRepresentationKernel( "IsPlistRep",
IsInternalRep, IS_PLIST_REP );
#############################################################################
##
#C IsConstantTimeAccessList( <list> )
##
## <#GAPDoc Label="IsConstantTimeAccessList">
## <ManSection>
## <Filt Name="IsConstantTimeAccessList" Arg='list' Type='Category'/>
##
## <Description>
## This category indicates whether the access to each element of the list
## <A>list</A> will take roughly the same time.
## This is implied for example by <C>IsList and IsInternalRep</C>,
## so all strings, Boolean lists, ranges, and internally represented plain
## lists are in this category.
## <P/>
## But also other enumerators (see <Ref Sect="Enumerators"/>) can lie
## in this category if they guarantee constant time access to their elements.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategory( "IsConstantTimeAccessList", IsList );
InstallTrueMethod( IsConstantTimeAccessList, IsList and IsInternalRep );
#############################################################################
##
#P IsSmallList . . . . . . . . . . . . . . . lists of length at most $2^28$
#V MAX_SIZE_LIST_INTERNAL
##
## <ManSection>
## <Prop Name="IsSmallList" Arg='obj'/>
## <Var Name="MAX_SIZE_LIST_INTERNAL"/>
##
## <Description>
## We need this property to describe for which lists the default methods for
## comparison, assignment, addition etc. are applicable.
## Note that these methods call <C>LEN_LIST</C>,
## and for that the list must be small.
## Of course every internally represented list is small,
## and every empty list is small.
## </Description>
## </ManSection>
##
DeclareProperty( "IsSmallList", IsList );
InstallTrueMethod( IsList, IsSmallList );
InstallTrueMethod( IsSmallList, IsList and IsInternalRep );
InstallTrueMethod( IsFinite, IsList and IsSmallList );
InstallTrueMethod( IsSmallList, IsList and IsEmpty );
BIND_GLOBAL( "MAX_SIZE_LIST_INTERNAL", 2^(8*GAPInfo.BytesPerVariable-4) - 1 );
#############################################################################
##
#A Length( <list> ) . . . . . . . . . . . . . . . . . . . length of a list
##
## <#GAPDoc Label="Length">
## <ManSection>
## <Attr Name="Length" Arg='list'/>
##
## <Description>
## returns the <E>length</E> of the list <A>list</A>, which is defined to be
## the index of the last bound entry in <A>list</A>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttributeKernel( "Length", IsList, LENGTH );
InstallTrueMethod(HasLength,IsPlistRep);
#############################################################################
##
#O IsBound( <list>[<pos>] ) . . . . . . . . test for an element from a list
##
## <#GAPDoc Label="IsBound_list">
## <ManSection>
## <Oper Name="IsBound" Arg='list[n]' Label="for a list index"/>
##
## <Description>
## <Ref Oper="IsBound" Label="for a list index"/> returns <K>true</K>
## if the list <A>list</A> has an element at index <A>n</A>,
## and <K>false</K> otherwise.
## <A>list</A> must evaluate to a list, or to an object for which a suitable
## method for <C>IsBound\[\]</C> has been installed, otherwise an error is signalled.
## <P/>
## <Example><![CDATA[
## gap> l := [ , 2, 3, , 5, , 7, , , , 11 ];;
## gap> IsBound( l[7] );
## true
## gap> IsBound( l[4] );
## false
## gap> IsBound( l[101] );
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperationKernel( "IsBound[]",
[ IsList, IS_INT ],
ISB_LIST );
#############################################################################
##
#o <list>[<pos>] . . . . . . . . . . . . . . . select an element from a list
##
DeclareOperationKernel( "[]",
[ IsList, IS_INT ],
ELM_LIST );
#############################################################################
##
## <#GAPDoc Label="GetWithDefault_list">
## <ManSection>
## <Oper Name="GetWithDefault" Arg='list, n, default'/>
##
## <Description>
## <Ref Oper="GetWithDefault"/> returns the <A>n</A>th element of the list
## <A>list</A>, if <A>list</A> has a value at index <A>n</A>, and
## <A>default</A> otherwise.
## <P/>
## While this method can be used on any list, it is particularly useful
## for Weak Pointer lists <Ref Sect="Weak Pointer Objects"/> where the
## value of the list can change.
## <P/>
## To distinguish between the <A>n</A>th element being unbound, or
## <A>default</A> being in <A>list</A>, users can create a new mutable
## object, such as a string. <Ref Func="IsIdenticalObj"/> returns
## <K>false</K> for different mutable strings, even if their contents are
## the same.
##
## <Example><![CDATA[
## gap> l := [1,2,,"a"];
## [ 1, 2,, "a" ]
## gap> newobj := "a";
## "a"
## gap> GetWithDefault(l, 2, newobj);
## 2
## gap> GetWithDefault(l, 3, newobj);
## "a"
## gap> GetWithDefault(l, 4, newobj);
## "a"
## gap> IsIdenticalObj(GetWithDefault(l, 3, newobj), newobj);
## true
## gap> IsIdenticalObj(GetWithDefault(l, 4, newobj), newobj);
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperationKernel( "GetWithDefault",
[ IsList, IS_INT, IsObject ],
ELM_DEFAULT_LIST );
#############################################################################
##
#o <list>{<poss>} . . . . . . . . . . . . . . . select elements from a list
##
DeclareOperationKernel( "{}",
[ IsList, IsList ],
ELMS_LIST );
#############################################################################
##
#O Unbind( <list>[<n>] )
##
## <#GAPDoc Label="Unbind_list">
## <ManSection>
## <Oper Name="Unbind" Arg='list[n]' Label="unbind a list entry"/>
##
## <Description>
## <Ref Oper="Unbind" Label="unbind a list entry"/> deletes the element with
## index <A>n</A> in the mutable list <A>list</A>. That is, after
## execution of <Ref Oper="Unbind" Label="unbind a list entry"/>,
## <A>list</A> no longer has an assigned value with index <A>n</A>.
## Thus <Ref Oper="Unbind" Label="unbind a list entry"/> can be used to
## produce holes in a list.
## Note that it is not an error to unbind a nonexistent list element.
## <A>list</A> must evaluate to a list, or to an object for which a suitable
## method for <C>Unbind\[\]</C> has been installed, otherwise an error is signalled.
## <P/>
## <Example><![CDATA[
## gap> l := [ , 2, 3, 5, , 7, , , , 11 ];;
## gap> Unbind( l[3] ); l;
## [ , 2,, 5,, 7,,,, 11 ]
## gap> Unbind( l[4] ); l;
## [ , 2,,,, 7,,,, 11 ]
## ]]></Example>
## <P/>
## Note that <Ref Oper="IsBound" Label="for a list index"/> and
## <Ref Oper="Unbind" Label="unbind a list entry"/> are special
## in that they do not evaluate their argument,
## otherwise <Ref Oper="IsBound" Label="for a list index"/>
## would always signal an error when it is supposed to return <K>false</K>
## and there would be no way to tell
## <Ref Oper="Unbind" Label="unbind a list entry"/>
## which component to remove.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperationKernel( "Unbind[]",
[ IsList and IsMutable, IS_INT ],
UNB_LIST );
#############################################################################
##
#o <list>[<pos>] := <obj>
##
DeclareOperationKernel( "[]:=",
[ IsList and IsMutable, IS_INT, IsObject ],
ASS_LIST );
#############################################################################
##
#o <list>{<poss>} := <objs>
##
DeclareOperationKernel( "{}:=",
[ IsList and IsMutable, IsList, IsList ],
ASSS_LIST );
#############################################################################
##
#A ConstantTimeAccessList( <list> )
##
## <#GAPDoc Label="ConstantTimeAccessList">
## <ManSection>
## <Attr Name="ConstantTimeAccessList" Arg='list'/>
##
## <Description>
## <Ref Attr="ConstantTimeAccessList"/> returns an immutable list containing
## the same elements as the list <A>list</A> (which may have holes) in the
## same order.
## If <A>list</A> is already a constant time access list,
## <Ref Attr="ConstantTimeAccessList"/> returns an immutable copy of
## <A>list</A> directly.
## Otherwise it puts all elements and holes of <A>list</A> into a new list
## and makes that list immutable.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "ConstantTimeAccessList", IsList );
#############################################################################
##
#F AsSSortedListList( <list> )
##
## <ManSection>
## <Func Name="AsSSortedListList" Arg='list'/>
##
## <Description>
## <Ref Func="AsSSortedListList"/> returns an immutable list containing the
## same elements as the <E>internally represented</E> list <A>list</A>
## (which may have holes) in strictly sorted order.
## If <A>list</A> is already immutable and strictly sorted,
## <Ref Func="AsSSortedListList"/> returns <A>list</A> directly.
## Otherwise it makes a deep copy, and makes that copy immutable.
## <Ref Func="AsSSortedListList"/> is an internal function.
## </Description>
## </ManSection>
##
DeclareSynonym( "AsSSortedListList", AS_LIST_SORTED_LIST );
#############################################################################
##
#A AsPlist( <l> )
##
## <ManSection>
## <Attr Name="AsPlist" Arg='l'/>
##
## <Description>
## <Ref Attr="AsPlist"/> returns a list in the representation
## <Ref Filt="IsPlistRep"/> that is equal to the list <A>l</A>.
## It is used before calling kernel functions to sort plists.
## </Description>
## </ManSection>
##
DeclareOperation( "AsPlist", [IsListOrCollection] );
#############################################################################
##
#C IsDenseList( <obj> )
##
## <#GAPDoc Label="IsDenseList">
## <ManSection>
## <Filt Name="IsDenseList" Arg='obj' Type='Category'/>
##
## <Description>
## A list is <E>dense</E> if it has no holes, i.e., contains an element at
## every position up to the length.
## It is absolutely legal to have lists with holes.
## They are created by leaving the entry between the commas empty.
## Holes at the end of a list are ignored.
## Lists with holes are sometimes convenient when the list represents
## a mapping from a finite, but not consecutive,
## subset of the positive integers.
## <Log><![CDATA[
## gap> IsDenseList( [ 1, 2, 3 ] );
## true
## gap> l := [ , 4, 9,, 25,, 49,,,, 121 ];; IsDenseList( l );
## false
## gap> l[3];
## 9
## gap> l[4];
## List Element: <list>[4] must have an assigned value
## not in any function
## Entering break read-eval-print loop ...
## you can 'quit;' to quit to outer loop, or
## you can 'return;' after assigning a value to continue
## brk> l[4] := 16;; # assigning a value
## brk> return; # to escape the break-loop
## 16
## gap>
## ]]></Log>
## <P/>
## Observe that requesting the value of <C>l[4]</C>, which was not
## assigned, caused the entry of a <K>break</K>-loop
## (see Section <Ref Sect="Break Loops"/>).
## After assigning a value and typing <C>return;</C>, &GAP; is finally
## able to comply with our request (by responding with <C>16</C>).
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategoryKernel( "IsDenseList", IsList, IS_DENSE_LIST );
InstallTrueMethod( IsDenseList, IsList and IsEmpty );
#############################################################################
##
#C IsHomogeneousList( <obj> )
##
## <#GAPDoc Label="IsHomogeneousList">
## <ManSection>
## <Filt Name="IsHomogeneousList" Arg='obj' Type='Category'/>
##
## <Description>
## returns <K>true</K> if <A>obj</A> is a list and it is homogeneous,
## and <K>false</K> otherwise.
## <P/>
## A <E>homogeneous</E> list is a dense list whose elements lie in the same
## family (see <Ref Sect="Families"/>).
## The empty list is homogeneous but not a collection
## (see <Ref Chap="Collections"/>),
## a nonempty homogeneous list is also a collection.
## <!-- can we guarantee this? -->
## <Example><![CDATA[
## gap> IsHomogeneousList( [ 1, 2, 3 ] ); IsHomogeneousList( [] );
## true
## true
## gap> IsHomogeneousList( [ 1, false, () ] );
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategoryKernel( "IsHomogeneousList", IsDenseList, IS_HOMOG_LIST );
#############################################################################
##
#M IsHomogeneousList( <coll_and_list> ) . . for a collection that is a list
#M IsHomogeneousList( <empty> ) . . . . . . . . . . . . . for an empty list
##
InstallTrueMethod( IsHomogeneousList, IsList and IsCollection );
InstallTrueMethod( IsHomogeneousList, IsList and IsEmpty );
#############################################################################
##
#M IsFinite( <homoglist> )
##
InstallTrueMethod( IsFinite, IsHomogeneousList and IsInternalRep );
#############################################################################
##
#P IsSortedList( <obj> )
##
## <#GAPDoc Label="IsSortedList">
## <ManSection>
## <Prop Name="IsSortedList" Arg='obj'/>
##
## <Description>
## returns <K>true</K> if <A>obj</A> is a list and it is sorted,
## <Index Subkey="sorted">list</Index> and <K>false</K> otherwise.
## <P/>
## A list <A>list</A> is <E>sorted</E> if it is dense
## (see <Ref Filt="IsDenseList"/>)
## and satisfies the relation <M><A>list</A>[i] \leq <A>list</A>[j]</M>
## whenever <M>i < j</M>.
## Note that a sorted list is not necessarily duplicate free
## (see <Ref Prop="IsDuplicateFree"/> and <Ref Prop="IsSSortedList"/>).
## <P/>
## Many sorted lists are in fact homogeneous
## (see <Ref Filt="IsHomogeneousList"/>),
## but also non-homogeneous lists may be sorted
## (see <Ref Sect="Comparison Operations for Elements"/>).
## <P/>
## In sorted lists, membership test and computing of positions can be done
## by binary search, see <Ref Sect="Sorted Lists and Sets"/>.
## <P/>
## Note that &GAP; cannot compare (by less than) arbitrary objects.
## This can cause that <Ref Prop="IsSortedList"/> runs into an error,
## if <A>obj</A> is a list with some non-comparable entries.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsSortedList", IsList);
InstallTrueMethod( IsList, IsSortedList );
#############################################################################
##
#P IsSSortedList( <obj> )
#P IsSet( <obj> )
##
## <#GAPDoc Label="IsSSortedList">
## <ManSection>
## <Prop Name="IsSSortedList" Arg='obj'/>
## <Prop Name="IsSet" Arg='obj'/>
##
## <Description>
## returns <K>true</K> if <A>obj</A> is a list and it is strictly sorted,
## <Index>strictly sorted list</Index>
## and <K>false</K> otherwise.
## <Ref Prop="IsSSortedList"/> is short for <Q>is strictly sorted list</Q>;
## <Ref Prop="IsSet"/> is just a synonym for <Ref Prop="IsSSortedList"/>.
## <P/>
## A list <A>list</A> is <E>strictly sorted</E> if it is sorted
## (see <Ref Prop="IsSortedList"/>)
## and satisfies the relation <M><A>list</A>[i] < <A>list</A>[j]</M>
## whenever <M>i < j</M>.
## In particular, such lists are duplicate free
## (see <Ref Prop="IsDuplicateFree"/>).
## <P/>
## (Currently there is little special treatment of lists that are sorted
## but not strictly sorted.
## In particular, internally represented lists will <E>not</E> store
## that they are sorted but not strictly sorted.)
## <P/>
## Note that &GAP; cannot compare (by less than) arbitrary objects.
## This can cause that <Ref Prop="IsSSortedList"/> runs into an error,
## if <A>obj</A> is a list with some non-comparable entries.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclarePropertyKernel( "IsSSortedList", IsList, IS_SSORT_LIST );
DeclareSynonym( "IsSet", IsSSortedList );
InstallTrueMethod( IsSortedList, IsSSortedList );
InstallTrueMethod( IsSSortedList, IsList and IsEmpty );
#############################################################################
##
#P IsDuplicateFree( <obj> )
#P IsDuplicateFreeList( <obj> )
##
## <#GAPDoc Label="IsDuplicateFree">
## <ManSection>
## <Prop Name="IsDuplicateFree" Arg='obj'/>
## <Filt Name="IsDuplicateFreeList" Arg='obj'/>
##
## <Description>
## <Ref Prop="IsDuplicateFree"/> returns <K>true</K> if <A>obj</A> is both a
## list or collection, and it is duplicate free;
## <Index>duplicate free</Index>
## otherwise it returns <K>false</K>.
## <Ref Filt="IsDuplicateFreeList"/> is a synonym for
## <C>IsDuplicateFree and IsList</C>.
## <P/>
## A list is <E>duplicate free</E> if it is dense and does not contain equal
## entries in different positions.
## Every domain (see <Ref Sect="Domains"/>) is duplicate free.
## <P/>
## Note that &GAP; cannot compare arbitrary objects (by equality).
## This can cause that <Ref Prop="IsDuplicateFree"/> runs into an error,
## if <A>obj</A> is a list with some non-comparable entries.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty( "IsDuplicateFree", IsListOrCollection );
DeclareSynonymAttr( "IsDuplicateFreeList", IsDuplicateFree and IsList );
InstallTrueMethod( IsDuplicateFree, IsList and IsSSortedList );
#############################################################################
##
#P IsPositionsList(<obj>)
##
## <ManSection>
## <Prop Name="IsPositionsList" Arg='obj'/>
##
## <Description>
## <!-- 1996/09/01 M.Schönert should inherit from <C>IsHomogeneousList</C>-->
## <!-- but the empty list is a positions list but not homogeneous-->
## </Description>
## </ManSection>
##
DeclarePropertyKernel( "IsPositionsList", IsDenseList, IS_POSS_LIST );
#############################################################################
##
#C IsTable( <obj> )
##
## <#GAPDoc Label="IsTable">
## <ManSection>
## <Filt Name="IsTable" Arg='obj' Type='Category'/>
##
## <Description>
## A <E>table</E> is a nonempty list of homogeneous lists which lie in the
## same family.
## Typical examples of tables are matrices
## (see <Ref Chap="Matrices"/>).
## <Example><![CDATA[
## gap> IsTable( [ [ 1, 2 ], [ 3, 4 ] ] ); # in fact a matrix
## true
## gap> IsTable( [ [ 1 ], [ 2, 3 ] ] ); # not rectangular but a table
## true
## gap> IsTable( [ [ 1, 2 ], [ () , (1,2) ] ] ); # not homogeneous
## false
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareCategoryKernel( "IsTable", IsHomogeneousList and IsCollection,
IS_TABLE_LIST );
#############################################################################
##
#O Position( <list>, <obj>[, <from>] ) . . . position of an object in a list
##
## <#GAPDoc Label="Position">
## <ManSection>
## <Oper Name="Position" Arg='list, obj[, from]'/>
##
## <Description>
## returns the position of the first occurrence <A>obj</A> in <A>list</A>,
## or <K>fail</K> if <A>obj</A> is not contained in <A>list</A>.
## If a starting index <A>from</A> is given, it
## returns the position of the first occurrence starting the search
## <E>after</E> position <A>from</A>.
## <P/>
## Each call to the two argument version is translated into a call of the
## three argument version, with third argument the integer zero <C>0</C>.
## (Methods for the two argument version must be installed as methods for
## the version with three arguments, the third being described by
## <C>IsZeroCyc</C>.)
## <P/>
## <Example><![CDATA[
## gap> Position( [ 2, 2, 1, 3 ], 1 );
## 3
## gap> Position( [ 2, 1, 1, 3 ], 1 );
## 2
## gap> Position( [ 2, 1, 1, 3 ], 1, 2 );
## 3
## gap> Position( [ 2, 1, 1, 3 ], 1, 3 );
## fail
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperationKernel( "Position", [ IsList, IsObject ], POS_LIST );
DeclareOperation( "Position", [ IsList, IsObject, IS_INT ] );
#############################################################################
##
#F Positions( <list>, <obj> ) . . . . . . . positions of an object in a list
#O PositionsOp( <list>, <obj> ) . . . . . . . . . . . . underlying operation
##
## <#GAPDoc Label="Positions">
## <ManSection>
## <Func Name="Positions" Arg='list, obj'/>
##
## <Description>
## returns the set of positions of <E>all</E> occurrences of <A>obj</A> in
## <A>list</A>.
## <P/>
## Developers who wish to adapt this for custom list types need to
## install suitable methods for the operation <C>PositionsOp</C>.
## <Index Key="PositionsOp"><C>PositionsOp</C></Index>
## <P/>
## <Example><![CDATA[
## gap> Positions([1,2,1,2,3,2,2],2);
## [ 2, 4, 6, 7 ]
## gap> Positions([1,2,1,2,3,2,2],4);
## [ ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
## We catch plain lists by a function to avoid method selection:
DeclareGlobalFunction( "Positions" );
DeclareOperation( "PositionsOp", [ IsList, IsObject ] );
#############################################################################
##
#O PositionCanonical( <list>, <obj> ) . . . position of canonical associate
##
## <#GAPDoc Label="PositionCanonical">
## <ManSection>
## <Oper Name="PositionCanonical" Arg='list, obj'/>
##
## <Description>
## returns the position of the canonical associate of <A>obj</A> in
## <A>list</A>.
## The definition of this associate depends on <A>list</A>.
## For internally represented lists it is defined as the element itself
## (and <Ref Oper="PositionCanonical"/> thus defaults to
## <Ref Oper="Position"/>,
## but for example for certain enumerators
## (see <Ref Sect="Enumerators"/>)
## other canonical associates can be defined.
## <P/>
## For example <Ref Oper="RightTransversal"/> defines the
## canonical associate to be the element in the transversal defining the
## same coset of a subgroup in a group.
## <P/>
## <Example><![CDATA[
## gap> g:=Group((1,2,3,4),(1,2));;u:=Subgroup(g,[(1,2)(3,4),(1,3)(2,4)]);;
## gap> rt:=RightTransversal(g,u);;AsList(rt);
## [ (), (3,4), (2,3), (2,3,4), (2,4,3), (2,4) ]
## gap> Position(rt,(1,2));
## fail
## gap> PositionCanonical(rt,(1,2));
## 2
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "PositionCanonical", [ IsList, IsObject ]);
#############################################################################
##
#O PositionNthOccurrence(<list>,<obj>,<n>) pos. of <n>th occurrence of <obj>
##
## <#GAPDoc Label="PositionNthOccurrence">
## <ManSection>
## <Oper Name="PositionNthOccurrence" Arg='list,obj,n'/>
##
## <Description>
## returns the position of the <A>n</A>-th occurrence of <A>obj</A> in
## <A>list</A>
## and returns <K>fail</K> if <A>obj</A> does not occur <A>n</A> times.
## <P/>
## <Example><![CDATA[
## gap> PositionNthOccurrence([1,2,3,2,4,2,1],1,1);
## 1
## gap> PositionNthOccurrence([1,2,3,2,4,2,1],1,2);
## 7
## gap> PositionNthOccurrence([1,2,3,2,4,2,1],2,3);
## 6
## gap> PositionNthOccurrence([1,2,3,2,4,2,1],2,4);
## fail
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "PositionNthOccurrence", [ IsList, IsObject, IS_INT ] );
#############################################################################
##
#F PositionSorted( <list>, <elm>[, <func>] ) . . . . position in sorted list
##
## <#GAPDoc Label="PositionSorted">
## <ManSection>
## <Func Name="PositionSorted" Arg='list, elm[, func]'/>
##
## <Description>
## Called with two arguments, <Ref Func="PositionSorted"/> returns
## the position of the element <A>elm</A> in the sorted list <A>list</A>.
## <P/>
## Called with three arguments, <Ref Func="PositionSorted"/> returns
## the position of the element <A>elm</A> in the list <A>list</A>,
## which must be sorted with respect to <A>func</A>.
## <A>func</A> must be a function of two arguments that returns <K>true</K>
## if the first argument is less than the second argument,
## and <K>false</K> otherwise.
## <P/>
## <Ref Func="PositionSorted"/> returns <A>pos</A> such that
## <M><A>list</A>[<A>pos</A>-1] < <A>elm</A> \leq
## <A>list</A>[<A>pos</A>]</M> holds.
## That means, if <A>elm</A> appears once in <A>list</A>,
## its position is returned.
## If <A>elm</A> appears several times in <A>list</A>,
## the position of the first occurrence is returned.
## If <A>elm</A> is not an element of <A>list</A>,
## the index where <A>elm</A> must be inserted to keep the list sorted
## is returned.
## <P/>
## <Ref Func="PositionSorted"/> uses binary search,
## whereas <Ref Oper="Position"/> can in general
## use only linear search, see the remark at the beginning
## of <Ref Sect="Sorted Lists and Sets"/>.
## For sorting lists, see <Ref Sect="Sorting Lists"/>,
## for testing whether a list is sorted,
## see <Ref Prop="IsSortedList"/> and <Ref Prop="IsSSortedList"/>.
## <P/>
## Developers who wish to adapt this for custom list types need to
## install suitable methods for the operation <C>PositionSortedOp</C>.
## <Index Key="PositionSortedOp"><C>PositionSortedOp</C></Index>
## <P/>
## <Example><![CDATA[
## gap> PositionSorted( [1,4,5,5,6,7], 0 );
## 1
## gap> PositionSorted( [1,4,5,5,6,7], 2 );
## 2
## gap> PositionSorted( [1,4,5,5,6,7], 4 );
## 2
## gap> PositionSorted( [1,4,5,5,6,7], 5 );
## 3
## gap> PositionSorted( [1,4,5,5,6,7], 8 );
## 7
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
## We catch plain lists by a function to avoid method selection:
DeclareGlobalFunction( "PositionSorted" );
DeclareOperation( "PositionSortedOp", [ IsList, IsObject ] );
DeclareOperation( "PositionSortedOp", [ IsList, IsObject, IsFunction ] );
#############################################################################
##
#F PositionSortedBy( <list>, <val>, <func> )
##
## <#GAPDoc Label="PositionSortedBy">
## <ManSection>
## <Func Name="PositionSortedBy" Arg='list, val, func'/>
##
## <Description>
## This function returns the same value that would be returned by
## <C>PositionSorted(List(list, func), val)</C>, but computes it in
## a more efficient way.
## <P/>
## To be more precise, <A>func</A> must be a function on one argument which
## returns values that can be compared to <A>val</A>, and <A>list</A>
## must be a list for which <C>func(list[i]) <= func(list[i+1])</C> holds
## for all relevant <A>i</A>. This property is not verified, and if the
## input violates it, then the result is undefined.
## <P/>
## <Ref Func="PositionSortedBy"/> returns <A>pos</A> such that
## <M><A>func</A>(<A>list</A>[<A>pos</A>-1]) < <A>val</A>
## \leq <A>func</A>(<A>list</A>[<A>pos</A>])</M> holds.
## That means, if there are elements <C>elm</C> in <A>list</A>
## for which <M><A>func</A>(elm) = <A>val</A></M> holds, then
## the position of the first such element is returned.
## If no element of <A>list</A> satisfies this condition, then
## the lowest index where an element <A>elm</A> satisfying
## <M><A>func</A>(elm) = <A>val</A></M> must be inserted to preserve
## the property <C>func(list[i]) <= func(list[i+1])</C> is returned.
## <P/>
## <Ref Func="PositionSortedBy"/> uses binary search.
## Each <C>func(list[i])</C> is computed at most once.
## <P/>
## Developers who wish to adapt this for custom list types need to
## install suitable methods for the operation <C>PositionSortedByOp</C>.
## <Index Key="PositionSortedByOp"><C>PositionSortedByOp</C></Index>
## <P/>
## <Example><![CDATA[
## gap> PositionSortedBy( [ "", "ab", ], -1, Length );
## 1
## gap> PositionSortedBy( [ "", "ab", ], 0, Length );
## 1
## gap> PositionSortedBy( [ "", "ab", ], 1, Length );
## 2
## gap> PositionSortedBy( [ "", "ab", ], 2, Length );
## 2
## gap> PositionSortedBy( [ "", "ab", ], 3, Length );
## 3
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
## We catch plain lists by a function to avoid method selection:
DeclareGlobalFunction( "PositionSortedBy" );
DeclareOperation("PositionSortedByOp", [ IsList, IsObject, IsFunction ]);
#############################################################################
##
#F PositionSet( <list>, <obj>[, <func>] )
##
## <#GAPDoc Label="PositionSet">
## <ManSection>
## <Func Name="PositionSet" Arg='list, obj[, func]'/>
##
## <Description>
## <Ref Func="PositionSet"/> is a slight variation of
## <Ref Func="PositionSorted"/>.
## The only difference to <Ref Func="PositionSorted"/> is that
## <Ref Func="PositionSet"/> returns
## <K>fail</K> if <A>obj</A> is not in <A>list</A>.
## <P/>
## <Example><![CDATA[
## gap> PositionSet( [1,4,5,5,6,7], 0 );
## fail
## gap> PositionSet( [1,4,5,5,6,7], 2 );
## fail
## gap> PositionSet( [1,4,5,5,6,7], 4 );
## 2
## gap> PositionSet( [1,4,5,5,6,7], 5 );
## 3
## gap> PositionSet( [1,4,5,5,6,7], 8 );
## fail
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "PositionSet" );
#############################################################################
##
#O PositionProperty( <list>, <func>[, <from>] )
##
## <#GAPDoc Label="PositionProperty">
## <ManSection>
## <Oper Name="PositionProperty" Arg='list, func[, from]'/>
##
## <Description>
## returns the position of the first entry in the list <A>list</A>
## for which the property tester function <A>func</A> returns <K>true</K>,
## or <K>fail</K> if no such entry exists.
## If a starting index <A>from</A> is given, it
## returns the position of the first entry satisfying <A>func</A>,
## starting the search <E>after</E> position <A>from</A>.
## <P/>
## <Example><![CDATA[
## gap> PositionProperty( [10^7..10^8], IsPrime );
## 20
## gap> PositionProperty( [10^5..10^6],
## > n -> not IsPrime(n) and IsPrimePowerInt(n) );
## 490
## ]]></Example>
## <P/>
## <Ref Oper="First"/> allows you to extract the first element of a list
## that satisfies a certain property.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "PositionProperty", [ IsList, IsFunction ] );
DeclareOperation( "PositionProperty", [ IsList, IsFunction, IS_INT ] );
#############################################################################
##
#O PositionMaximum( <list> [, <func>] )
#O PositionMinimum( <list> [, <func>] )
##
## <#GAPDoc Label="PositionMaximum">
## <ManSection>
## <Func Name="PositionMaximum" Arg='list [, func]'/>
## <Func Name="PositionMinimum" Arg='list [, func]'/>
##
## <Description>
## returns the position of maximum (with <Ref Func="PositionMaximum"/>) or
## minimum (with <Ref Func="PositionMinimum"/>) entry in the list <A>list</A>.
## If a second argument <A>func</A> is passed, then return instead the position
## of the largest/smallest entry in <C>List( <A>list</A> , <A>func</A> )</C>.
## If several entries of the list are equal
## to the maximum/minimum, the first such position is returned.
## <P/>
## <Example><![CDATA[
## gap> PositionMaximum( [2,4,-6,2,4] );
## 2
## gap> PositionMaximum( [2,4,-6,2,4], x -> -x);
## 3
## gap> PositionMinimum( [2,4,-6,2,4] );
## 3
## gap> PositionMinimum( [2,4,-6,2,4], x -> -x);
## 2
## ]]></Example>
## <P/>
## <Ref Func="Maximum" Label="for various objects"/> and
## <Ref Func="Minimum" Label="for various objects"/>
## allow you to find the maximum or minimum element of a list directly.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "PositionMaximum" );
DeclareGlobalFunction( "PositionMinimum" );
#############################################################################
##
#O PositionsProperty( <list>, <func> )
##
## <#GAPDoc Label="PositionsProperty">
## <ManSection>
## <Oper Name="PositionsProperty" Arg='list, func'/>
##
## <Description>
## returns the set of all those positions in the list <A>list</A>
## which are bound and
## for which the property tester function <A>func</A> returns <K>true</K>.
## <P/>
## <Example><![CDATA[
## gap> l:= [ -5 .. 5 ];;
## gap> PositionsProperty( l, IsPosInt );
## [ 7, 8, 9, 10, 11 ]
## gap> PositionsProperty( l, IsPrimeInt );
## [ 1, 3, 4, 8, 9, 11 ]
## ]]></Example>
## <P/>
## <Ref Oper="PositionProperty"/> allows you to extract the position of the
## first element in a list that satisfies a certain property.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "PositionsProperty", [ IsList, IsFunction ] );
#############################################################################
##
#O PositionBound( <list> ) . . . . position of first bound element in a list
##
## <#GAPDoc Label="PositionBound">
## <ManSection>
## <Oper Name="PositionBound" Arg='list'/>
##
## <Description>
## returns the first bound position of the list
## <A>list</A>.
## For the empty list it returns <K>fail</K>.
## <P/>
## <Example><![CDATA[
## gap> PositionBound([1,2,3]);
## 1
## gap> PositionBound([,1,2,3]);
## 2
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "PositionBound", [ IsList ] );
#############################################################################
##
#F PositionsBound( <list> ) . . . . . . . . . positions of all bound entries
##
## <#GAPDoc Label="PositionsBound">
## <ManSection>
## <Func Name="PositionsBound" Arg='list'/>
##
## <Description>
## returns the set of all bound positions in the list
## <A>list</A>.
## <P/>
## <Example><![CDATA[
## gap> PositionsBound([1,2,3]);
## [ 1 .. 3 ]
## gap> PositionsBound([,1,,3]);
## [ 2, 4 ]
## gap> PositionsBound([]);
## []
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "PositionsBound" );
#############################################################################
##
#O PositionSublist( <list>, <sub>[, <from>] )
##
## <#GAPDoc Label="PositionSublist">
## <ManSection>
## <Oper Name="PositionSublist" Arg='list, sub[, from]'/>
##
## <Description>
## returns the smallest index in the list <A>list</A> at which a sublist
## equal to <A>sub</A> starts.
## If <A>sub</A> does not occur the operation returns <K>fail</K>.
## The version with given <A>from</A> starts searching <E>after</E>
## position <A>from</A>.
## <P/>
## To determine whether <A>sub</A> matches <A>list</A> at a particular
## position, use <Ref Oper="IsMatchingSublist"/> instead.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "PositionSublist", [ IsList,IsList,IS_INT ] );
#############################################################################
##
#O IsMatchingSublist( <list>, <sub>[, <at>] )
##
## <#GAPDoc Label="IsMatchingSublist">
## <ManSection>
## <Oper Name="IsMatchingSublist" Arg='list, sub[, at]'/>
##
## <Description>
## returns <K>true</K> if <A>sub</A> matches a sublist of <A>list</A> from
## position <C>1</C> (or position <A>at</A>, in the case of three arguments),
## or <K>false</K>, otherwise.
## If <A>sub</A> is empty <K>true</K> is returned.
## If <A>list</A> is empty but <A>sub</A> is non-empty
## <K>false</K> is returned.
## <P/>
## If you actually want to know whether there is an <A>at</A> for which
## <C>IsMatchingSublist( <A>list</A>, <A>sub</A>, <A>at</A> )</C> is true,
## use a construction like
## <C>PositionSublist( <A>list</A>, <A>sub</A> ) &tlt;&tgt; fail</C> instead
## (see <Ref Oper="PositionSublist"/>); it's more efficient.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "IsMatchingSublist", [ IsList,IsList,IS_INT ] );
#############################################################################
##
#F IsQuickPositionList( <list> )
##
## <#GAPDoc Label="IsQuickPositionList">
## <ManSection>
## <Filt Name="IsQuickPositionList" Arg='list'/>
##
## <Description>
## This filter indicates that a position test in <A>list</A> is quicker than
## about 5 or 6 element comparisons for <Q>smaller</Q>.
## If this is the case it can be beneficial to use <Ref Oper="Position"/>
## in <A>list</A> and a bit list than ordered lists to represent subsets
## of <A>list</A>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareFilter( "IsQuickPositionList" );
#############################################################################
##
#O Add( <list>, <obj>[, <pos>] ) . . . . . add an element anywhere in a list
##
## <#GAPDoc Label="Add">
## <ManSection>
## <Oper Name="Add" Arg='list, obj[, pos]'/>
##
## <Description>
## adds the element <A>obj</A> to the mutable list <A>list</A>.
## The two argument version adds <A>obj</A> at the end of <A>list</A>,
## i.e., it is equivalent to the assignment
## <C><A>list</A>[ Length(<A>list</A>) + 1 ] := <A>obj</A></C>,
## see <Ref Sect="List Assignment"/>.
## <P/>
## The three argument version adds <A>obj</A> in position <A>pos</A>,
## moving all later elements of the list (if any) up by one position.
## Any holes at or after position <A>pos</A> are also moved up by one
## position, and new holes are created before <A>pos</A> if they are needed.
## <P/>
## Nothing is returned by <Ref Oper="Add"/>,
## the function is only called for its side effect.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperationKernel( "Add", [ IsList and IsMutable, IsObject ], ADD_LIST );
DeclareOperation( "Add", [ IsList and IsMutable, IsObject, IS_INT ]);
#############################################################################
##
#O Remove( <list>[, <pos>] ) . . remove an entry from pos. <pos> of a list
##
## <#GAPDoc Label="Remove">
## <ManSection>
## <Oper Name="Remove" Arg='list[, pos]'/>
##
## <Description>
## removes an element from <A>list</A>.
## The one argument form removes the last element.
## The two argument form removes the element in position <A>pos</A>,
## moving all subsequent elements down one position. Any holes after
## position <A>pos</A> are also moved down by one position.
## <P/>
## The one argument form always returns the removed element.
## In this case <A>list</A> must be non-empty.
## <P/>
## The two argument form returns the old value of <A>list</A>[<A>pos</A>]
## if it was bound, and nothing if it was not.
## Note that accessing or assigning the return value of this form of
## the <Ref Oper="Remove"/> operation is only safe when you <E>know</E>
## that there will be a value, otherwise it will cause an error.
## <P/>
## <Example><![CDATA[
## gap> l := [ 2, 3, 5 ];; Add( l, 7 ); l;
## [ 2, 3, 5, 7 ]
## gap> Add(l,4,2); l;
## [ 2, 4, 3, 5, 7 ]
## gap> Remove(l,2); l;
## 4
## [ 2, 3, 5, 7 ]
## gap> Remove(l); l;
## 7
## [ 2, 3, 5 ]
## gap> Remove(l,5); l;
## [ 2, 3, 5 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperationKernel( "Remove", [IsList and IsMutable], REM_LIST);
DeclareOperation( "Remove", [IsList and IsMutable, IS_INT]);
DeclareSynonym( "CopyListEntries", COPY_LIST_ENTRIES );
#############################################################################
##
#O Append( <list1>, <list2> ) . . . . . . . . . . . append a list to a list
##
## <#GAPDoc Label="Append">
## <ManSection>
## <Oper Name="Append" Arg='list1, list2'/>
##
## <Description>
## adds the elements of the list <A>list2</A> to the end of the mutable list
## <A>list1</A>, see <Ref Sect="List Assignment"/>.
## <A>list2</A> may contain holes, in which case the corresponding entries
## in <A>list1</A> will be left unbound.
## <Ref Oper="Append"/> returns nothing,
## it is only called for its side effect.
## <P/>
## Note that <Ref Oper="Append"/> changes its first argument,
## while <Ref Func="Concatenation" Label="for a list of lists"/> creates
## a new list and leaves its arguments unchanged.
## <P/>
## <Example><![CDATA[
## gap> l := [ 2, 3, 5 ];; Append( l, [ 7, 11, 13 ] ); l;
## [ 2, 3, 5, 7, 11, 13 ]
## gap> Append( l, [ 17,, 23 ] ); l;
## [ 2, 3, 5, 7, 11, 13, 17,, 23 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperationKernel( "Append", [ IsList and IsMutable, IsList ],
APPEND_LIST );
#############################################################################
##
#F Apply( <list>, <func> ) . . . . . . . . apply a function to list entries
##
## <#GAPDoc Label="Apply">
## <ManSection>
## <Func Name="Apply" Arg='list, func'/>
##
## <Description>
## <Ref Func="Apply"/> applies the function <A>func</A> to every element
## of the dense and mutable list <A>list</A>,
## and replaces each element entry by the corresponding return value.
## <P/>
## <Ref Func="Apply"/> changes its argument.
## The nondestructive counterpart of <Ref Func="Apply"/>
## is <Ref Func="List" Label="for a collection"/>.
## <P/>
## <Example><![CDATA[
## gap> l:= [ 1, 2, 3 ];; Apply( l, i -> i^2 ); l;
## [ 1, 4, 9 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Apply" );
#############################################################################
##
#F Concatenation( <list1>, <list2>, ... ) . . . . . concatenation of lists
#F Concatenation( <list> ) . . . . . . . . . . . . . concatenation of lists
##
## <#GAPDoc Label="Concatenation">
## <ManSection>
## <Func Name="Concatenation" Arg='list1, list2, ...'
## Label="for several lists"/>
## <Func Name="Concatenation" Arg='list' Label="for a list of lists"/>
##
## <Description>
## In the first form <Ref Func="Concatenation" Label="for several lists"/>
## returns the concatenation of the lists <A>list1</A>, <A>list2</A>, etc.
## The <E>concatenation</E> is the list that begins with the elements of
## <A>list1</A>, followed by the elements of <A>list2</A>, and so on.
## Each list may also contain holes, in which case the concatenation also
## contains holes at the corresponding positions.
## <P/>
## In the second form <A>list</A> must be a dense list of lists
## <A>list1</A>, <A>list2</A>, etc.,
## and <Ref Func="Concatenation" Label="for a list of lists"/> returns the
## concatenation of those lists.
## <P/>
## The result is a new mutable list,
## that is not identical to any other list.
## The elements of that list however are identical to the corresponding
## elements of <A>list1</A>, <A>list2</A>, etc.
## (see <Ref Sect="Identical Lists"/>).
## <P/>
## Note that <Ref Func="Concatenation" Label="for several lists"/> creates
## a new list and leaves its arguments unchanged,
## while <Ref Oper="Append"/> changes its first argument.
## For computing the union of proper sets,
## <Ref Func="Union" Label="for a list"/> can be used,
## see also <Ref Sect="Sorted Lists and Sets"/>.
## <P/>
## <Example><![CDATA[
## gap> Concatenation( [ 1, 2, 3 ], [ 4, 5 ] );
## [ 1, 2, 3, 4, 5 ]
## gap> Concatenation( [2,3,,5,,7], [11,,13,,,,17,,19] );
## [ 2, 3,, 5,, 7, 11,, 13,,,, 17,, 19 ]
## gap> Concatenation( [ [1,2,3], [2,3,4], [3,4,5] ] );
## [ 1, 2, 3, 2, 3, 4, 3, 4, 5 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Concatenation" );
#############################################################################
##
#O Compacted( <list> ) . . . . . . . . . . . . . . remove holes from a list
##
## <#GAPDoc Label="Compacted">
## <ManSection>
## <Oper Name="Compacted" Arg='list'/>
##
## <Description>
## returns a new mutable list that contains the elements of <A>list</A>
## in the same order but omitting the holes.
## <P/>
## <Example><![CDATA[
## gap> l:=[,1,,,3,,,4,[5,,,6],7];; Compacted( l );
## [ 1, 3, 4, [ 5,,, 6 ], 7 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "Compacted", [ IsList ] );
#############################################################################
##
#O Collected( <list> ) . . . . . . . . . . collect like elements from a list
##
## <#GAPDoc Label="Collected">
## <ManSection>
## <Oper Name="Collected" Arg='list'/>
##
## <Description>
## returns a new list <A>new</A> that contains for each element <A>elm</A>
## of the list <A>list</A> a list of length two,
## the first element of this is <A>elm</A> itself and the second element is
## the number of times <A>elm</A> appears in <A>list</A>.
## The order of those pairs in <A>new</A> corresponds to the ordering of
## the elements elm, so that the result is sorted.
## <P/>
## For all pairs of elements in <A>list</A> the comparison via <C><</C>
## must be defined.
## <P/>
## <Example><![CDATA[
## gap> Factors( Factorial( 10 ) );
## [ 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 7 ]
## gap> Collected( last );
## [ [ 2, 8 ], [ 3, 4 ], [ 5, 2 ], [ 7, 1 ] ]
## gap> Collected( last );
## [ [ [ 2, 8 ], 1 ], [ [ 3, 4 ], 1 ], [ [ 5, 2 ], 1 ], [ [ 7, 1 ], 1 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "Collected", [ IsList ] );
#############################################################################
##
#O DuplicateFreeList( <list> ) . . . . duplicate free list of list elements
#O Unique( <list> )
##
## <#GAPDoc Label="DuplicateFreeList">
## <ManSection>
## <Oper Name="DuplicateFreeList" Arg='list'/>
## <Oper Name="Unique" Arg='list'/>
##
## <Description>
## returns a new mutable list whose entries are the elements of the list
## <A>list</A> with duplicates removed.
## <Ref Oper="DuplicateFreeList"/> only uses the <C>=</C> comparison
## and will not sort the result.
## Therefore <Ref Oper="DuplicateFreeList"/> can be used even if the
## elements of <A>list</A> do not lie in the same family.
## Otherwise, if <A>list</A> contains objects that can be compared with
## <Ref Oper="\<"/> then it is much more efficient to use
## <Ref Oper="Set"/> instead of <Ref Oper="DuplicateFreeList"/>.
## <P/>
## <Ref Oper="Unique"/> is a synonym for <Ref Oper="DuplicateFreeList"/>.
## <P/>
## <Example><![CDATA[
## gap> l:=[1,Z(3),1,"abc",Group((1,2,3),(1,2)),Z(3),Group((1,2),(2,3))];;
## gap> DuplicateFreeList( l );
## [ 1, Z(3), "abc", Group([ (1,2,3), (1,2) ]) ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "DuplicateFreeList", [ IsList ] );
DeclareSynonym( "Unique", DuplicateFreeList );
#############################################################################
##
#A AsDuplicateFreeList( <list> ) . . . duplicate free list of list elements
##
## <#GAPDoc Label="AsDuplicateFreeList">
## <ManSection>
## <Attr Name="AsDuplicateFreeList" Arg='list'/>
##
## <Description>
## returns the same result as <Ref Oper="DuplicateFreeList"/>,
## except that the result is immutable.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "AsDuplicateFreeList", IsList );
#############################################################################
##
#O DifferenceLists(<list1>,<list2>) . list without elements in another list
##
## <ManSection>
## <Oper Name="DifferenceLists" Arg='list1,list2'/>
##
## <Description>
## This operation accepts two lists <A>list1</A> and <A>list2</A>
## and returns a list containing the elements in <A>list1</A>
## that do not lie in <A>list2</A>.
## The elements of the resulting list are in the same order as they are in
## <A>list1</A>. The result of this operation is the same as that of the
## operation <Ref Func="Difference"/>
## except that the first argument is not treated as a proper set,
## and therefore the result need not be duplicate-free or sorted.
## </Description>
## </ManSection>
##
DeclareOperation( "DifferenceLists", [IsList, IsList] );
#############################################################################
##
#O Flat( <list> ) . . . . . . . list of elements of a nested list structure
##
## <#GAPDoc Label="Flat">
## <ManSection>
## <Oper Name="Flat" Arg='list'/>
##
## <Description>
## returns the list of all elements that are contained in the list
## <A>list</A> or its sublists.
## That is, <Ref Oper="Flat"/> first makes a new empty list <A>new</A>.
## Then it loops over the elements <A>elm</A> of <A>list</A>.
## If <A>elm</A> is not a list it is added to <A>new</A>,
## otherwise <Ref Oper="Flat"/> appends <C>Flat( <A>elm</A> )</C>
## to <A>new</A>.
## <P/>
## <Example><![CDATA[
## gap> Flat( [ 1, [ 2, 3 ], [ [ 1, 2 ], 3 ] ] );
## [ 1, 2, 3, 1, 2, 3 ]
## gap> Flat( [ ] );
## [ ]
## ]]></Example>
## <P/>
## To reconstruct a matrix from the list obtained by applying
## <Ref Oper="Flat"/> to the matrix,
## the sublist operator can be used, as follows.
## <P/>
## <Example><![CDATA[
## gap> l:=[9..14];;w:=2;; # w is the length of each row
## gap> sub:=[1..w];;List([1..Length(l)/w],i->l{(i-1)*w+sub});
## [ [ 9, 10 ], [ 11, 12 ], [ 13, 14 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "Flat", [ IsList ] );
#############################################################################
##
#F Reversed( <list> ) . . . . . . . . . . . reverse the elements in a list
##
## <#GAPDoc Label="Reversed">
## <ManSection>
## <Func Name="Reversed" Arg='list'/>
##
## <Description>
## returns a new mutable list, containing the elements of the dense list
## <A>list</A> in reversed order.
## <P/>
## The argument list is unchanged.
## The result list is a new list, that is not identical to any other list.
## The elements of that list however are identical to the corresponding
## elements of the argument list (see <Ref Sect="Identical Lists"/>).
## <P/>
## <Ref Func="Reversed"/> implements a special case of list assignment,
## which can also be formulated in terms of the <C>{}</C> operator
## (see <Ref Sect="List Assignment"/>).
## <P/>
## Developers who wish to adapt this for custom list types need to
## install suitable methods for the operation <C>ReversedOp</C>.
## <Index Key="ReversedOp"><C>ReversedOp</C></Index>
## <P/>
## <Example><![CDATA[
## gap> Reversed( [ 1, 4, 9, 5, 6, 7 ] );
## [ 7, 6, 5, 9, 4, 1 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
## We catch internal lists by a function to avoid method selection:
DeclareGlobalFunction( "Reversed" );
DeclareOperation( "ReversedOp", [ IsDenseList ] );
#############################################################################
##
#F Shuffle( <list> ) . . . . . . . . . . . . . . . permute entries randomly
##
## <#GAPDoc Label="Shuffle">
## <ManSection>
## <Oper Name="Shuffle" Arg='list'/>
##
## <Description>
## The argument <A>list</A> must be a dense mutable list. This operation
## permutes the entries of <A>list</A> randomly (in place), and returns
## <A>list</A>.
## <Example>
## gap> Reset(GlobalMersenneTwister, 12345);; # make manual tester happy
## gap> l := [1..20];
## [ 1 .. 20 ]
## gap> m := Shuffle(ShallowCopy(l));
## [ 8, 13, 1, 3, 20, 15, 4, 7, 5, 18, 6, 12, 16, 11, 2, 10, 19, 17, 9,
## 14 ]
## gap> l;
## [ 1 .. 20 ]
## gap> Shuffle(l);;
## gap> l;
## [ 19, 5, 7, 20, 16, 1, 10, 15, 12, 11, 13, 2, 14, 3, 4, 17, 6, 8, 9,
## 18 ]
## </Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "Shuffle", [IsDenseList and IsMutable] );
#############################################################################
##
#O Sort( <list>[, <func>] ) . . . . . . . . . . . . . . . . . . sort a list
#O SortBy( <list>, <func> ) . . . . . . . . . . . . . . . . . . sort a list
##
## <#GAPDoc Label="Sort">
## <ManSection>
## <Oper Name="Sort" Arg='list[, func]'/>
## <Oper Name="SortBy" Arg='list, func'/>
## <Oper Name="StableSort" Arg='list, [func]'/>
## <Oper Name="StableSortBy" Arg='list, [func]'/>
## <Description>
## <Ref Oper="Sort"/> sorts the list <A>list</A> in increasing order.
## In the one argument form <Ref Oper="Sort"/> uses the operator <C><</C>
## to compare the elements.
## (If the list is not homogeneous it is the user's responsibility to ensure
## that <C><</C> is defined for all element pairs,
## see <Ref Sect="Comparison Operations for Elements"/>)
## In the two argument form <Ref Oper="Sort"/> uses the function <A>func</A>
## to compare elements.
## <A>func</A> must be a function taking two arguments that returns
## <K>true</K> if the first is regarded as strictly smaller than the second,
## and <K>false</K> otherwise.
## <P/>
## <Ref Oper="StableSort"/> behaves identically to <Ref Oper="Sort"/>, except
## that <Ref Oper="StableSort"/> will keep elements which compare equal in the
## same relative order, while <Ref Oper="Sort"/> may change their relative order.
## <P/>
## <Ref Oper="Sort"/> does not return anything,
## it just changes the argument <A>list</A>.
## Use <Ref Oper="ShallowCopy"/> if you want to keep <A>list</A>.
## Use <Ref Func="Reversed"/> if you want to get a new list that is
## sorted in decreasing order.
## <P/>
## <Ref Oper="SortBy"/> sorts the list <A>list</A> into an order such that
## <C>func(list[i]) <= func(list[i+1])</C> for all relevant
## <A>i</A>. <A>func</A> must thus be a function on one argument which returns
## values that can be compared. Each <C>func(list[i])</C> is computed just
## once and stored, making this more efficient than using the two-argument
## version of <Ref Oper="Sort"/> in many cases.
## <P/>
## <Ref Oper="StableSortBy"/> behaves the same as <Ref Oper="SortBy"/> except that,
## like <Ref Oper="StableSort"/>, it keeps pairs of values which compare equal when
## <C>func</C> is applied to them in the same relative order.
## <P/>
## <Example><![CDATA[
## gap> list := [ 5, 4, 6, 1, 7, 5 ];; Sort( list ); list;
## [ 1, 4, 5, 5, 6, 7 ]
## gap> SortBy(list, x -> x mod 3);
## gap> list; # Sorted by mod 3
## [ 6, 1, 4, 7, 5, 5]
## gap> list := [ [0,6], [1,2], [1,3], [1,5], [0,4], [3,4] ];;
## gap> Sort( list, function(v,w) return v*v < w*w; end );
## gap> list; # sorted according to the Euclidean distance from [0,0]
## [ [ 1, 2 ], [ 1, 3 ], [ 0, 4 ], [ 3, 4 ], [ 1, 5 ], [ 0, 6 ] ]
## gap> SortBy( list, function(v) return v[1] + v[2]; end );
## gap> list; # sorted according to Manhattan distance from [0,0]
## [ [ 1, 2 ], [ 1, 3 ], [ 0, 4 ], [ 1, 5 ], [ 0, 6 ], [ 3, 4 ] ]
## gap> list := [ [0,6], [1,3], [3,4], [1,5], [1,2], [0,4], ];;
## gap> Sort( list, function(v,w) return v[1] < w[1]; end );
## gap> # note the random order of the elements with equal first component:
## gap> list;
## [ [ 0, 6 ], [ 0, 4 ], [ 1, 3 ], [ 1, 5 ], [ 1, 2 ], [ 3, 4 ] ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "Sort", [ IsList and IsMutable ] );
DeclareOperation( "Sort", [ IsList and IsMutable, IsFunction ] );
DeclareOperation( "SortBy", [IsList and IsMutable, IsFunction ] );
DeclareOperation( "StableSort", [ IsList and IsMutable ] );
DeclareOperation( "StableSort", [ IsList and IsMutable, IsFunction ] );
DeclareOperation( "StableSortBy", [IsList and IsMutable, IsFunction ] );
#############################################################################
##
#O Sortex( <list>[, <func>] ) . . sort a list (stable), return applied perm.
##
## <#GAPDoc Label="Sortex">
## <ManSection>
## <Oper Name="Sortex" Arg='list[, func]'/>
##
## <Description>
## sorts the list <A>list</A> and returns a permutation
## that can be applied to <A>list</A> to obtain the sorted list.
## The one argument form sorts via the operator <C><</C>,
## the two argument form sorts w.r.t. the function <A>func</A>.
## The permutation returned by <Ref Oper="Sortex"/> will keep
## elements which compare equal in the same relative order.
## (If the list is not homogeneous it is the user's responsibility to ensure
## that <C><</C> is defined for all element pairs,
## see <Ref Sect="Comparison Operations for Elements"/>)
## <P/>
## <Ref Oper="Permuted"/> allows you to rearrange a list according to
## a given permutation.
## <P/>
## <Example><![CDATA[
## gap> list1 := [ 5, 4, 6, 1, 7, 5 ];;
## gap> list2 := ShallowCopy( list1 );;
## gap> perm := Sortex( list1 );
## (1,3,5,6,4)
## gap> list1;
## [ 1, 4, 5, 5, 6, 7 ]
## gap> Permuted( list2, perm );
## [ 1, 4, 5, 5, 6, 7 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "Sortex", [ IsList and IsMutable ] );
DeclareOperation( "Sortex", [ IsList and IsMutable, IsFunction ] );
#############################################################################
##
#A SortingPerm( <list> )
##
## <#GAPDoc Label="SortingPerm">
## <ManSection>
## <Attr Name="SortingPerm" Arg='list'/>
##
## <Description>
## <Ref Attr="SortingPerm"/> returns the same as <Ref Oper="Sortex"/>
## but does <E>not</E> change the argument.
## <P/>
## <Example><![CDATA[
## gap> list1 := [ 5, 4, 6, 1, 7, 5 ];;
## gap> list2 := ShallowCopy( list1 );;
## gap> perm := SortingPerm( list1 );
## (1,3,5,6,4)
## gap> list1;
## [ 5, 4, 6, 1, 7, 5 ]
## gap> Permuted( list2, perm );
## [ 1, 4, 5, 5, 6, 7 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute( "SortingPerm", IsList );
#############################################################################
##
#F PermListList( <list1>, <list2> ) . what permutation of <list1> is <list2>
##
## <#GAPDoc Label="PermListList">
## <ManSection>
## <Func Name="PermListList" Arg='list1, list2'/>
##
## <Description>
## returns a permutation <M>p</M> of <C>[ 1 .. Length( <A>list1</A> ) ]</C>
## such that <A>list1</A><M>[i</M><C>^</C><M>p] =</M> <A>list2</A><M>[i]</M>.
## It returns <K>fail</K> if there is no such permutation.
## <P/>
## <Example><![CDATA[
## gap> list1 := [ 5, 4, 6, 1, 7, 5 ];;
## gap> list2 := [ 4, 1, 7, 5, 5, 6 ];;
## gap> perm := PermListList(list1, list2);
## (1,2,4)(3,5,6)
## gap> Permuted( list2, perm );
## [ 5, 4, 6, 1, 7, 5 ]
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "PermListList" );
#############################################################################
##
#O SortParallel( <list1>, <list2>[, <func>] ) . sort two lists in parallel
##
## <#GAPDoc Label="SortParallel">
## <ManSection>
## <Oper Name="SortParallel" Arg='list1, list2[, func]'/>
## <Oper Name="StableSortParallel" Arg='list1, list2[, func]'/>
##
## <Description>
## <Ref Oper="SortParallel"/> sorts the list <A>list1</A> in increasing order
## just as <Ref Oper="Sort"/> does.
## In parallel it applies the same exchanges that are necessary to sort
## <A>list1</A> to the list <A>list2</A>,
## which must of course have at least as many elements as <A>list1</A> does.
## <P/>
## <Ref Oper="StableSortParallel"/> behaves identically to
## <Ref Oper="SortParallel"/>, except it keeps elements in <A>list1</A> which
## compare equal in the same relative order.
## <P/>
## <Example><![CDATA[
## gap> list1 := [ 5, 4, 6, 1, 7, 5 ];;
## gap> list2 := [ 2, 3, 5, 7, 8, 9 ];;
## gap> SortParallel( list1, list2 );
## gap> list1;
## [ 1, 4, 5, 5, 6, 7 ]
## gap> list2;
## [ 7, 3, 2, 9, 5, 8 ]
## ]]></Example>
## <P/>
## Note that <C>[ 7, 3, 2, 9, 5, 8 ]</C> or <C>[ 7, 3, 9, 2, 5, 8 ]</C>
## are possible results. <Ref Oper="StableSortParallel"/> will always
## return <C>[ 7, 3, 2, 9, 5, 8]</C>.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation( "SortParallel",
[ IsList and IsMutable, IsList and IsMutable ] );
DeclareOperation( "SortParallel",
[ IsList and IsMutable, IsList and IsMutable, IsFunction ] );
DeclareOperation( "StableSortParallel",
[ IsList and IsMutable, IsList and IsMutable ] );
DeclareOperation( "StableSortParallel",
[ IsList and IsMutable, IsList and IsMutable, IsFunction ] );
#############################################################################
##
#F Maximum( <obj1>, <obj2>, ... ) . . . . . . . . . . . maximum of objects
#F Maximum( <list> )
##
## <#GAPDoc Label="Maximum">
## <ManSection>
## <Heading>Maximum</Heading>
## <Func Name="Maximum" Arg='obj1, obj2, ...' Label="for various objects"/>
## <Func Name="Maximum" Arg='list' Label="for a list"/>
##
## <Description>
## In the first form <Ref Func="Maximum" Label="for various objects"/>
## returns the <E>maximum</E> of its arguments, i.e.,
## one argument <A>obj</A> for which <M><A>obj</A> \geq <A>obj1</A></M>,
## <M><A>obj</A> \geq <A>obj2</A></M> etc.
## <P/>
## In the second form <Ref Func="Maximum" Label="for a list"/> takes a
## homogeneous list <A>list</A> and returns the maximum of the elements in
## this list.
## <P/>
## <Example><![CDATA[
## gap> Maximum( -123, 700, 123, 0, -1000 );
## 700
## gap> Maximum( [ -123, 700, 123, 0, -1000 ] );
## 700
## gap> # lists are compared elementwise:
## gap> Maximum( [1,2], [0,15], [1,5], [2,-11] );
## [ 2, -11 ]
## ]]></Example>
## To get the index of the maximum element use <Ref Func="PositionMaximum"/>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Maximum" );
#############################################################################
##
#F Minimum( <obj1>, <obj2>, ... ) . . . . . . . . . . . minimum of objects
#F Minimum( <list> )
##
## <#GAPDoc Label="Minimum">
## <ManSection>
## <Heading>Minimum</Heading>
## <Func Name="Minimum" Arg='obj1, obj2, ...' Label="for various objects"/>
## <Func Name="Minimum" Arg='list' Label="for a list"/>
##
## <Description>
## In the first form <Ref Func="Minimum" Label="for various objects"/>
## returns the <E>minimum</E> of its arguments, i.e.,
## one argument <A>obj</A> for which <M><A>obj</A> \leq <A>obj1</A></M>,
## <M><A>obj</A> \leq <A>obj2</A></M> etc.
## <P/>
## In the second form <Ref Func="Minimum" Label="for a list"/> takes a
## homogeneous list <A>list</A> and returns the minimum of the elements in
## this list.
## <P/>
## Note that for both <Ref Func="Maximum" Label="for various objects"/> and
## <Ref Func="Minimum" Label="for various objects"/> the comparison of the
## objects <A>obj1</A>, <A>obj2</A> etc. must be defined;
## for that, usually they must lie in the same family
## (see <Ref Sect="Families"/>).
## <P/>
## <Example><![CDATA[
## gap> Minimum( -123, 700, 123, 0, -1000 );
## -1000
## gap> Minimum( [ -123, 700, 123, 0, -1000 ] );
## -1000
## gap> Minimum( [ 1, 2 ], [ 0, 15 ], [ 1, 5 ], [ 2, -11 ] );
## [ 0, 15 ]
## ]]></Example>
## To get the index of the minimum element use <Ref Func="PositionMinimum"/>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction( "Minimum" );
#############################################################################
##
#O MaximumList( <list> ) . . . . . . . . . . . . . . . . maximum of a list
#O MinimumList( <list> ) . . . . . . . . . . . . . . . . minimum of a list
##
## <#GAPDoc Label="MaximumList">
## <ManSection>
## <Heading>MaximumList and MinimumList</Heading>
## <Oper Name="MaximumList" Arg='list [seed]'/>
## <Oper Name="MinimumList" Arg='list [seed]'/>
##
## <Description>
## return the maximum resp. the minimum of the elements in the list
## <A>list</A>.
## They are the operations called by
## <Ref Func="Maximum" Label="for various objects"/>
## resp. <Ref Func="Minimum" Label="for various objects"/>.
## Methods can be installed for special kinds of lists.
--> --------------------
--> maximum size reached
--> --------------------
[ Konzepte0.64Was zu einem Entwurf gehört
Wie die Entwicklung von Software durchgeführt wird
]
|
