|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Martin Schönert.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains methods for lists in general.
##
#############################################################################
##
#M methods for nesting depths for some quick cases
##
InstallMethod(NestingDepthA, [IsCyclotomicCollection and IsGeneralizedRowVector],
v->1);
InstallMethod(NestingDepthM, [IsCyclotomicCollection and IsMultiplicativeGeneralizedRowVector],
v->1);
InstallMethod(NestingDepthA, [IsFFECollection and IsGeneralizedRowVector],
v->1);
InstallMethod(NestingDepthM, [IsFFECollection and IsMultiplicativeGeneralizedRowVector],
v->1);
InstallMethod(NestingDepthA, [IsCyclotomicCollColl and
IsGeneralizedRowVector],
m->2);
InstallMethod(NestingDepthM, [IsCyclotomicCollColl and
IsOrdinaryMatrix and IsMultiplicativeGeneralizedRowVector],
function( m )
local t;
t := TNUM_OBJ(m[1]);
if FIRST_LIST_TNUM > t or LAST_LIST_TNUM < t then
TryNextMethod();
else
return 2;
fi;
end );
#T just a temporary (?) hack in order to exclude lists of class functions
InstallMethod(NestingDepthA, [IsFFECollColl and IsGeneralizedRowVector],
m->2);
InstallMethod(NestingDepthM, [IsFFECollColl and IsOrdinaryMatrix and IsMultiplicativeGeneralizedRowVector],
function(m)
local t;
t := TNUM_OBJ(m[1]);
if FIRST_LIST_TNUM > t or LAST_LIST_TNUM < t then
TryNextMethod();
else
return 2;
fi;
end);
#############################################################################
##
#M methods for comparisons
##
## The default method `EQ_LIST_LIST_DEFAULT' is applicable only to small
## lists in the sense of `IsSmallList'.
## For finite lists that do not know to be small, first this property is
## checked, and if the lists are not small then the loop is done in {\GAP}.
##
InstallMethod( EQ,
"for two small lists",
IsIdenticalObj,
[ IsList and IsSmallList, IsList and IsSmallList ],
EQ_LIST_LIST_DEFAULT );
InstallMethod( EQ,
"for two finite lists (not necessarily small)",
IsIdenticalObj,
[ IsList and IsFinite, IsList and IsFinite ],
function( list1, list2 )
local len, i;
# We ask for being small in order to catch the default methods
# directly in the next call if possible.
if IsSmallList( list1 ) then
if IsSmallList( list2 ) then
return EQ_LIST_LIST_DEFAULT( list1, list2 );
else
return false;
fi;
elif IsSmallList( list2 ) then
return false;
else
# None of the lists is small.
len:= Length( list1 );
if len <> Length( list2 ) then
return false;
fi;
i:= 1;
while i <= len do
if IsBound( list1[i] ) then
if IsBound( list2[i] ) then
if list1[i] <> list2[i] then
return false;
fi;
else
return false;
fi;
elif IsBound( list2[i] ) then
return false;
fi;
i:= i+1;
od;
return true;
fi;
end );
InstallMethod( EQ,
"for two lists, the first being empty",
[ IsList and IsEmpty, IsList ],
SUM_FLAGS, #can't do better
function( empty, list )
return IsEmpty( list );
end );
InstallMethod( EQ,
"for two lists, the second being empty",
[ IsList, IsList and IsEmpty ],
SUM_FLAGS, #can't do better
function( list, empty )
return IsEmpty( list );
end );
#############################################################################
##
#M \=( <list1>, <list2> ) . . .. . . . . . . . . . for two lists
##
InstallMethod( EQ,
"for two lists with length - last resort",
IsIdenticalObj,
[ IsList and HasLength, IsList and HasLength ],
function(list1, list2)
if Length(list1) <> Length(list2) then
return false;
fi;
# use the kernel method if small lists
if IsSmallList(list1) and IsSmallList(list2) then
return EQ_LIST_LIST_DEFAULT(list1, list2);
fi;
if IsInfinity(Length(list1)) then
## warning - trying to compare infinite lists
Info(InfoWarning, 1, "EQ: Attempting EQ on infinite lists");
fi;
TryNextMethod();
end);
InstallMethod( EQ,
"for two lists - last resort",
IsIdenticalObj,
[ IsList, IsList],
function(list1, list2)
local i;
# just compare elementwise
i := 1;
while true do
while IsBound(list1[i]) and IsBound(list2[i]) do
if list1[i] <> list2[i] then
return false;
fi;
i := i + 1;
od;
if IsBound(list1[i]) or IsBound(list2[i]) then
return false;
fi;
# Now we've found an unbound spot on both lists
# maybe we know enough to stop now
# anyway at this stage we really must check the Lengths and hope
# that they are computable now.
if Length(list1) <= i then
return Length(list2) <= i;
elif Length(list2) <= i then
return false;
fi;
i := i + 1;
od;
end);
InstallMethod( LT,
"for two small homogeneous lists",
IsIdenticalObj,
[ IsHomogeneousList and IsSmallList,
IsHomogeneousList and IsSmallList ],
LT_LIST_LIST_DEFAULT );
InstallMethod( LT,
"for two finite homogeneous lists (not necessarily small)",
IsIdenticalObj,
[ IsHomogeneousList and IsFinite, IsHomogeneousList and IsFinite ],
LT_LIST_LIST_FINITE );
#############################################################################
##
#M \in( <obj>, <list> )
##
InstallMethod( IN,
"for an object, and an empty list",
[ IsObject, IsList and IsEmpty ],
ReturnFalse );
InstallMethod( IN,
"for wrong family relation",
IsNotElmsColls,
[ IsObject, IsCollection ],
SUM_FLAGS, # can't do better
ReturnFalse );
InstallMethod( IN,
"for an object, and a small list",
[ IsObject, IsList and IsSmallList ],
IN_LIST_DEFAULT );
InstallMethod( IN,
"for an object, and a list",
[ IsObject, IsList ],
function( elm, list )
local len, i;
if IsSmallList( list ) then
return IN_LIST_DEFAULT( elm, list );
elif IsFinite( list ) then
len:= Length( list );
i:= 1;
while i <= len do
if IsBound( list[i] ) and elm = list[i] then
return true;
fi;
i:= i+1;
od;
return false;
else
TryNextMethod();
fi;
end );
#############################################################################
##
#M <elm> \in <whole-family>
##
InstallMethod( IN,
"for an object, and a collection that contains the whole family",
IsElmsColls,
[ IsObject, IsCollection and IsWholeFamily ],
SUM_FLAGS, # can't do better
ReturnTrue );
#############################################################################
##
#M Display( <list> )
##
InstallMethod( Display,
"for a (finite) list",
[ IsList ],
function( list )
Print( list, "\n" );
end );
#############################################################################
##
#M String( <list> ) . . . . . . . . . . . . . . . . . . . . . . for a list
#M String( <range> ) . . . . . . . . . . . . . . . . . . . . . . for a range
##
InstallMethod( String,
"for a (finite) list",
[ IsList ],
function ( list )
local str, i;
# Check that we are in the right method.
if not IsFinite( list ) then
TryNextMethod();
fi;
# We cannot handle the case of an empty string in the method for strings
# because the type of the empty string need not satisfy the requirement
# `IsString'.
if IsEmptyString( list ) then
return "";
fi;
str := "[ ";
for i in [ 1 .. Length( list ) ] do
if IsBound( list[ i ] ) then
if IsStringRep( list[i] )
or ( IsString( list[i] ) and not IsEmpty( list[i] ) ) then
Append( str, "\"" );
Append( str, String( list[i] ) );
Append( str, "\"" );
else
Append( str, String( list[i] ) );
fi;
fi;
if i <> Length( list ) then
Append( str, ", " );
fi;
od;
Append( str, " ]" );
ConvertToStringRep( str );
return str;
end );
InstallMethod( ViewString, "call ViewString and incorporate hints",
[ IsList and IsFinite],
function ( list )
local str,ls, i;
# We have to handle empty string and empty list specially because
# IsString( [ ] ) returns true
if Length(list) = 0 then
if IsEmptyString( list ) then
return "\"\"";
else
return "[ ]";
fi;
fi;
if IsString( list ) then
return VIEW_STRING_FOR_STRING(list);
fi;
# make strings for objects in l
ls:=[];
for i in [1..Length(list)] do
if IsBound(list[i]) then
str:=ViewString(list[i]);
if str=DEFAULTVIEWSTRING then
# there might not be a method
str:=String(list[i]);
fi;
ls[i]:=str;
else
ls[i]:="";
fi;
od;
# The line break hints are consistent with those
# that appear in the kernel function 'PrintListDefault'
# and in the 'ViewObj' method for finite lists.
str:= "\>\>[ \>\>";
for i in [ 1 .. Length( list ) ] do
if ls[i] <> "" then
if 1 < i then
Append( str, "\<,\< \>\>" );
fi;
Append( str, ls[i] );
elif 1 < i then
Append( str, "\<,\<\>\>" );
fi;
od;
Append( str, " \<\<\<\<]" );
ConvertToStringRep( str );
return str;
end );
InstallMethod( DisplayString,
"for a range",
[ IsRange ],
range -> Concatenation( String( range ), "\n" ) );
InstallMethod( ViewString,
"for a range",
[ IsRange ],
function( list )
local str;
str := "[ ";
Append( str, String( list[1] ) );
if Length( list ) > 1 then
if Length(list) = 2 or list[2] - list[1] <> 1 then
Append( str, ", " );
Append( str, String( list[2] ) );
fi;
if Length(list) > 2 then
Append( str, " .. " );
Append( str, String( Last(list) ) );
fi;
fi;
Append( str, " ]" );
Assert(0, IsStringRep(str));
ConvertToStringRep( str );
return str;
end );
InstallMethod( String,
"for a range",
[ IsRange ],
function( list )
local str;
str := Concatenation( "[ ", String( list[ 1 ] ) );
if Length( list ) > 1 then
if list[ 2 ] - list[ 1 ] <> 1 then
Append( str, ", " );
Append( str, String( list[ 2 ] ) );
fi;
Append( str, " .. " );
Append( str, String( Last(list) ) );
fi;
Append( str, " ]" );
ConvertToStringRep( str );
return str;
end );
#############################################################################
##
#M Size( <list> ) . . . . . . . . . . . . . . . . . . . . . . . for a list
##
InstallOtherMethod( Size,
"for a list",
[ IsList ],
Length );
InstallOtherMethod( Size,
"for a list that is a collection",
[ IsList and IsCollection ],
Length );
#############################################################################
##
#M Representative( <list> )
##
InstallOtherMethod( Representative,
"for a list",
[ IsList ],
function( list )
local elm;
for elm in list do
return elm;
od;
Error( "<list> must be nonempty to have a representative" );
end );
#############################################################################
##
#M RepresentativeSmallest( <list> )
##
InstallOtherMethod( RepresentativeSmallest,
"for an empty list",
[ IsList and IsEmpty ],
function( list )
Error( "<C> must be nonempty to have a representative" );
end );
InstallOtherMethod( RepresentativeSmallest,
"for a strictly sorted list",
[ IsSSortedList ],
function( list )
return list[1];
end );
InstallOtherMethod(
RepresentativeSmallest,
"for a list",
[ IsList ],
MinimumList );
#############################################################################
##
#M Random( <list> ) . . . . . . . . . . . . . . . . for a dense small list
##
InstallMethod( Random,
"for a dense small list",
[ IsList and IsDenseList and IsSmallList ],
RandomList );
InstallMethod( Random,
"for a dense (small) list",
[ IsList and IsDenseList ],
function( list )
if IsSmallList( list ) then
return RandomList( list );
else
TryNextMethod();
fi;
end );
#############################################################################
##
#M IsSmallList( <list> )
##
InstallMethod( IsSmallList,
"for a list",
[ IsList ],
list -> Length( list ) <= MAX_SIZE_LIST_INTERNAL );
#############################################################################
##
#M IsSmallList( <non-list> )
##
InstallOtherMethod( IsSmallList,
"for a non-list",
[ IsObject ],
function( nonlist )
if IsList( nonlist ) then
TryNextMethod();
else
return false;
fi;
end );
#############################################################################
##
#M ConstantTimeAccessList( <list> )
#M ShallowCopy( <list> )
##
## `ConstantTimeAccessList' and `ShallowCopy' have the same methods for
## lists: These methods return mutable lists, but since
## `ConstantTimeAccessList' is an attribute, its results are made immutable
## by the kernel.
##
## `ConstantTimeAccessList' has an additional ``almost immediate method''
## constant time access lists: this method just returns the argument. (This
## cannot work for `ShallowCopy', because the argument could be immutable.)
##
Perform( [ ConstantTimeAccessList, ShallowCopy ], function(op)
InstallMethod( op,
"for a list",
[ IsList ],
function( list )
local new, i;
new:= [ ];
for i in [ 1 .. Length( list ) ] do
if IsBound( list[ i ] ) then
new[ i ] := list[ i ];
fi;
od;
return new;
end );
InstallMethod( op,
"for a strictly sorted list",
[ IsList and IsSSortedList ],
function( list )
local new, i;
new:= [ ];
for i in [ 1 .. Length( list ) ] do
if IsBound( list[ i ] ) then
new[ i ] := list[ i ];
fi;
od;
SetIsSSortedList( new, true );
return new;
end );
InstallMethod( op,
"for a dense list",
[ IsList and IsDenseList ],
function( list )
if IsSmallList( list ) then
return list{ [ 1 .. Length( list ) ] };
else
Error( "resulting list would be too large (length ",
Length( list ), ")" );
fi;
end );
InstallMethod( op,
"for a strictly sorted dense list",
[ IsList and IsDenseList and IsSSortedList ],
function( list )
if IsSmallList( list ) then
list:= list{ [ 1 .. Length( list ) ] };
SetIsSSortedList( list, true );
return list;
else
Error( "resulting list would be too large (length ",
Length( list ), ")" );
fi;
end );
end);
InstallMethod( ConstantTimeAccessList,
"for a constant time access list",
[ IsList and IsConstantTimeAccessList ],
SUM_FLAGS, # can't do better
Immutable );
#############################################################################
##
#M AsList( <list> )
##
InstallOtherMethod( AsList,
"for a list",
[ IsList ],
list -> ConstantTimeAccessList( Enumerator( list ) ) );
InstallOtherMethod( AsList,
"for a constant time access list",
[ IsList and IsConstantTimeAccessList ],
Immutable );
#############################################################################
##
#M AsPlist( <list> )
##
InstallOtherMethod( AsPlist,
"for a plist",
[IsList and IsPlistRep],
x -> x );
InstallOtherMethod( AsPlist,
"for a list",
[ IsList ],
function(l)
l:=AsList(l);
if not IsPlistRep(l) then
l:=PlainListCopy(l); # explicit copy for objects that claim to
# be constant time access but not plists.
fi;
return l;
end );
#############################################################################
##
#M AsSSortedList( <list> )
##
## If <list> is a (not necessarily dense) list whose elements lie in the
## same family then 'AsSSortedList' is applicable.
##
InstallOtherMethod( AsSSortedList,
"for a list",
[ IsList ],
list -> ConstantTimeAccessList( EnumeratorSorted( list ) ) );
InstallOtherMethod(AsSSortedList,
"for a plist",
[IsList and IsPlistRep],
AsSSortedListList );
InstallOtherMethod(AsSSortedList,
"for a list",
[ IsList ],
l -> AsSSortedListList( AsPlist( l ) ) );
InstallMethod( AsSSortedList,
"for a strictly sorted list",
[ IsSSortedList ],
SUM_FLAGS,
Immutable );
#############################################################################
##
#M Enumerator( <list> )
##
InstallOtherMethod( Enumerator,
"for a list",
[ IsList ],
Immutable );
#############################################################################
##
#M EnumeratorSorted( <list> )
##
InstallOtherMethod( EnumeratorSorted,
"for a plist",
[IsList and IsPlistRep],
function( l )
if IsSSortedList( l ) then
return l;
fi;
return AsSSortedListList( l );
end );
InstallOtherMethod( EnumeratorSorted, "for a list", [ IsList ],
function(l)
if IsSSortedList(l) then
return l;
fi;
return AsSSortedListList(AsPlist(l));
end);
#############################################################################
##
#M SSortedList( <list> ) . . . . . . . . . . . set of the elements of a list
##
InstallMethod( SSortedList, "for a plist",
[ IsList and IsPlistRep ],
SSortedListList );
InstallMethod( SSortedList, "for a list",
[ IsList ],
l->SSortedListList(AsPlist(l)) );
#############################################################################
##
#M SSortedList( <list>, <func> )
##
InstallMethod( SSortedList,
"for a list, and a function",
[ IsList, IsFunction ],
function ( list, func )
local res, i, squashsize;
squashsize := 100;
res := [];
for i in list do
Add( res, func( i ) );
if Length(res) > squashsize then
res := Set(res);
squashsize := Maximum(100, Size(res) * 2);
fi;
od;
return Set(res);
end );
#############################################################################
##
#F IteratorList( <list> )
##
## returns an iterator constructed from the list <list>,
## which stores the underlying list in the component `list'
## and the current position in the component `pos'.
##
## It may happen that the underlying list is a enumerator of a domain
## whose size cannot be computed easily.
## In such cases, the methods for `IsDoneIterator' and `NextIterator'
## shall avoid calling `Length' for the enumerator.
## Therefore a special representation exist for iterators of dense immutable
## lists.
## (Note that the `Length' call is unavoidable for iterators of non-dense
## lists.)
##
BindGlobal( "IsDoneIterator_List",
iter -> ( iter!.pos >= iter!.len ) );
BindGlobal( "NextIterator_List", function ( iter )
local p, l;
p := iter!.pos;
if p = iter!.len then
Error("<iter> is exhausted");
fi;
l := iter!.list;
p := p + 1;
while not IsBound( l[ p ] ) do
p := p + 1;
od;
iter!.pos := p;
return l[ p ];
end );
BindGlobal( "NextIterator_DenseList", function ( iter )
local p;
p := iter!.pos + 1;
iter!.pos := p;
#if not IsBound( iter!.list[ iter!.pos ] ) then
# Error("<iter> is exhausted");
#fi;
return iter!.list[ p ];
end );
BindGlobal( "ShallowCopy_List",
iter -> rec( list := iter!.list,
pos := iter!.pos,
len := iter!.len ) );
InstallGlobalFunction( IteratorList, function ( list )
local iter;
iter := rec(
list := list,
pos := 0,
len := Length(list),
IsDoneIterator := IsDoneIterator_List,
ShallowCopy := ShallowCopy_List );
if IsDenseList( list ) and not IsMutable( list ) then
iter.NextIterator := NextIterator_DenseList;
else
iter.NextIterator := NextIterator_List;
fi;
return IteratorByFunctions( iter );
end );
#############################################################################
##
#M Iterator( <list> )
##
InstallOtherMethod( Iterator,
"for a list",
[ IsList ],
IteratorList );
#############################################################################
##
#M IteratorSorted( <list> )
##
InstallOtherMethod( IteratorSorted,
"for a list",
[ IsList ],
function( list )
if IsSSortedList( list ) then
return IteratorList( list );
else
return IteratorList( SSortedListList( list ) );
#T allowed??
fi;
end );
#############################################################################
##
#M SumOp( <list> ) . . . . . . . . . . . . . . . . . . . . for a dense list
##
InstallOtherMethod( SumOp,
"for a dense list",
[ IsDenseList ], 1,
function ( list )
local sum, i;
if IsEmpty(list) then
sum := 0;
else
sum := list[1];
for i in [2..Length(list)] do
sum := sum + list[i];
od;
fi;
return sum;
end );
#############################################################################
##
#M SumOp( <list>, <init> ) . . . . . . . . . . for a list, and initial value
##
InstallOtherMethod( SumOp,
"for a list, and initial value",
[ IsList, IsAdditiveElement ], 1,
function ( list, init )
local elm;
for elm in list do
init := init + elm;
od;
return init;
end );
#############################################################################
##
#M SumOp( <list>, <func> ) . . . . . . . . for a dense list, and a function
##
InstallOtherMethod( SumOp,
"for a dense list, and a function",
[ IsDenseList, IsFunction ], 1,
function( list, func )
local sum, i;
if IsEmpty(list) then
sum := 0;
else
sum := func( list[1] );
for i in [2..Length(list)] do
sum := sum + func( list[i] );
od;
fi;
return sum;
end );
#############################################################################
##
#M SumOp( <list>, <func>, <init> ) . . . for list, function, and init. value
##
InstallOtherMethod( SumOp,
"for a list, a function, and initial value",
[ IsList, IsFunction, IsAdditiveElement ], 1,
function ( list, func, init )
local elm;
for elm in list do
init := init + func( elm );
od;
return init;
end );
#############################################################################
##
#M ProductOp( <list> ) . . . . . . . . . . . . . . . . . . for a dense list
##
InstallOtherMethod( ProductOp,
"for a dense list",
[ IsDenseList ], 1,
function ( list )
local prod, i;
if IsEmpty(list) then
prod := 1;
else
prod := list[1];
for i in [2..Length(list)] do
prod := prod * list[i];
od;
fi;
return prod;
end );
#############################################################################
##
#M ProductOp( <list>, <init> ) . . . . . . . . for a list, and initial value
##
InstallOtherMethod( ProductOp,
"for a list, and initial value",
[ IsList, IsMultiplicativeElement ], 1,
function ( list, init )
local elm;
for elm in list do
init := init * elm;
od;
return init;
end );
#############################################################################
##
#M ProductOp( <list>, <func> ) . . . . . . for a dense list, and a function
##
InstallOtherMethod( ProductOp,
"for a dense list and a function",
[ IsDenseList, IsFunction ], 1,
function( list, func )
local prod, i;
if IsEmpty(list) then
prod := 1;
else
prod := func( list[1] );
for i in [2..Length(list)] do
prod := prod * func( list[i] );
od;
fi;
return prod;
end );
#############################################################################
##
#M ProductOp( <list>, <func>, <init> ) . for list, function, and init. value
##
InstallOtherMethod( ProductOp,
"for a list, a function, and initial value",
[ IsList, IsFunction, IsMultiplicativeElement ], 1,
function ( list, func, init )
local elm;
for elm in list do
init := init * func( elm );
od;
return init;
end );
#############################################################################
##
#M <list>{<poss>}
#M <list>{<poss>}:=<objs>
##
## `ELMS_LIST_DEFAULT' applies `LEN_LIST' to both of its arguments,
## so its use is restricted to small lists.
##
## `ASSS_LIST_DEFAULT' tries to change its first argument into a plain list,
## and applies `LEN_LIST' to the other two arguments,
## so also the usage of `ASSS_LIST_DEFAULT' is restricted to small lists.
##
InstallMethod( ELMS_LIST,
"for a small list and a small dense list",
[ IsList and IsSmallList, IsDenseList and IsSmallList ],
ELMS_LIST_DEFAULT );
InstallMethod( ELMS_LIST,
"for a list and a dense list",
[ IsList, IsDenseList ],
function( list, poslist )
local choice, i;
if IsSmallList( poslist ) then
if IsSmallList( list ) then
return ELMS_LIST_DEFAULT( list, poslist );
else
choice:= [];
for i in poslist do
Add( choice, list[i] );
od;
return choice;
fi;
else
TryNextMethod();
fi;
end );
InstallMethod( ASSS_LIST,
"for a small mutable list, a small dense list, and a small list",
[ IsList and IsSmallList and IsMutable, IsDenseList and IsSmallList,
IsList and IsSmallList ],
ASSS_LIST_DEFAULT );
InstallMethod( ASSS_LIST,
"for a mutable list, a dense list, and a list",
[ IsList and IsMutable, IsDenseList, IsList ],
function( list, poslist, vallist )
local i;
if IsSmallList( poslist ) and IsSmallList( vallist ) then
if IsSmallList( list ) then
ASSS_LIST_DEFAULT( list, poslist, vallist );
else
for i in [ 1 .. Length( poslist ) ] do
list[ poslist[i] ]:= vallist[i];
od;
fi;
else
TryNextMethod();
fi;
end );
InstallOtherMethod( ASS_LIST,
"error message for immutable list",
[IsList, IsPosInt, IsObject], -100,
function(list, pos, v)
if not IsMutable( list ) then
Error("The list you are trying to assign to is immutable");
else
TryNextMethod();
fi;
end );
#############################################################################
##
#M IsSSortedList( <non-list> )
##
InstallOtherMethod( IsSSortedList,
"for non-lists",
[ IsObject ],
function( nonlist )
if IsList( nonlist ) then
TryNextMethod();
else
return false;
fi;
end );
#############################################################################
##
#M IsSSortedList(<list>)
##
InstallMethod( IsSSortedList,
"for a small list",
[ IsSmallList ],
IS_SSORT_LIST_DEFAULT );
InstallMethod( IsSSortedList,
"for a homogeneous list (not nec. finite)",
[ IsHomogeneousList ],
function( list )
local i;
if IsSmallList( list ) then
return IS_SSORT_LIST_DEFAULT( list );
else
i:= 1;
while i+1 <= Length( list ) do
if list[ i+1 ] <= list[i] then
return false;
fi;
i:= i+1;
od;
fi;
end );
#############################################################################
##
#M IsSortedList(<list>)
##
InstallMethod( IsSortedList,
"for a finite list",
[ IsList and IsFinite ],
function(l)
local i;
# shortcut: strictly sorted is stored for internally represented lists
if IsInternalRep( l ) and IsSSortedList( l ) then
return true;
fi;
if not IsBound(l[1]) then
return false;
fi;
for i in [1..Length(l)-1] do
if not IsBound(l[i+1]) or l[i+1] < l[i] then
return false;
fi;
od;
return true;
end);
InstallMethod( IsSortedList,
"for a list (not nec. finite)",
[ IsList ],
function( list )
local i;
i:= 1;
if not IsBound(list[1]) then
return false;
fi;
while i+1 <= Length( list ) do
if not IsBound(list[i+1]) or list[ i+1 ] < list[i] then
return false;
fi;
i:= i+1;
od;
return true;
end );
#############################################################################
##
#M IsSortedList( <non-list> )
##
InstallOtherMethod( IsSortedList,
"for non-lists",
[ IsObject ],
function( nonlist )
if IsList( nonlist ) then
TryNextMethod();
else
return false;
fi;
end );
#############################################################################
##
#M IsDuplicateFree( <list> )
##
InstallMethod( IsDuplicateFree,
"for a finite list",
[ IsList ],
function( list )
local i;
if not IsDenseList( list ) then
return false;
elif not IsFinite( list ) then
TryNextMethod();
fi;
for i in [ 1 .. Length( list ) ] do
if Position( list, list[i], 0 ) < i then
return false;
fi;
od;
return true;
end );
#############################################################################
##
#M DifferenceLists . . . . . . . . list without the elements in another list
##
InstallMethod( DifferenceLists,
"homogeneous lists",
[IsHomogeneousList, IsHomogeneousList],
function( list1, list2 )
local diff, e;
list2 := Set( list2 );
diff := [];
for e in list1 do
if not e in list2 then
Add( diff, e );
fi;
od;
return diff;
end );
#############################################################################
##
#M IsPositionsList(<list>)
##
InstallMethod( IsPositionsList,
"for a small homogeneous list",
[ IsHomogeneousList and IsSmallList ],
IS_POSS_LIST_DEFAULT );
InstallMethod( IsPositionsList,
"for a homogeneous list",
[ IsHomogeneousList ],
function( list )
if IsSmallList( list ) then
return IS_POSS_LIST_DEFAULT( list );
else
TryNextMethod();
fi;
end );
#############################################################################
##
#M IsPositionsList( <non-list> )
##
InstallOtherMethod( IsPositionsList,
"for non-lists",
[ IsObject ],
function( nonlist )
if IsList( nonlist ) then
TryNextMethod();
else
return false;
fi;
end );
#############################################################################
##
#M Position( <list>, <obj>, <from> )
##
InstallMethod( Position,
"for a small list, an object, and an integer",
[ IsList and IsSmallList, IsObject, IsInt ],
POS_LIST_DEFAULT );
InstallMethod( Position,
"for a (small) list, an object, and an integer",
[ IsList, IsObject, IsInt ],
function( list, obj, start )
if IsSmallList( list ) then
return POS_LIST_DEFAULT( list, obj, start );
else
TryNextMethod();
fi;
end );
InstallMethod( Position,
"for a homog. list, an object not in the elements family, and an int.",
function( F1, F2, F3 )
return HasElementsFamily(F1)
and not IsIdenticalObj( ElementsFamily(F1), F2 );
end,
[ IsHomogeneousList,
IsObject,
IsInt ],
ReturnFail );
InstallMethod( Position,
"for a small sorted list, an object, and an integer",
[ IsSSortedList and IsSmallList, IsObject, IsInt ],
function ( list, obj, start )
local pos;
#N 1996/08/14 M.Schönert 'POSITION_SORTED_LIST' should take 3 arguments
#T (This method is used only for ``external'' lists, the kernel methods
#T `PosPlistSort', `PosPlistHomSort' support the argument `start'.)
if start = 0 then
pos := POSITION_SORTED_LIST( list, obj );
# `PositionSorted' will not return fail. Therefore we have to test
# explicitly once it had been called.
if pos > Length( list ) or list[pos] <> obj then
return fail;
fi;
else
pos := POS_LIST_DEFAULT( list, obj, start );
fi;
return pos;
end );
InstallMethod( Position,
"for a sorted list, an object, and an integer",
[ IsSSortedList, IsObject, IsInt ],
function ( list, obj, start )
local pos;
if IsSmallList( list ) then
if start = 0 then
pos := POSITION_SORTED_LIST( list, obj );
# `PositionSorted' will not return fail. Therefore we have to test
# explicitly once it had been called.
if pos > Length( list ) or list[pos] <> obj then
return fail;
fi;
else
pos := POS_LIST_DEFAULT( list, obj, start );
fi;
return pos;
else
TryNextMethod();
fi;
end );
#############################################################################
##
#M Position(<list>,<obj>,<from>)
##
## The following method is installed for external lists since internal lists
## do not store whether they are duplicate free.
## For external lists such as special enumerators of domains,
## e.g.~`Integers', one needs only a special method for `Position' with
## third argument zero (installed with requirement `IsZeroCyc'),
## the case of a positive third argument is then handled by the following
## generic method.
##
InstallMethod( Position,
"for duplicate free list, object, and positive integer",
[ IsDuplicateFreeList, IsObject, IsPosInt ],
function( list, obj, start )
local pos;
pos:= Position( list, obj, 0 );
if pos <> fail and start < pos then
return pos;
else
return fail;
fi;
end );
#############################################################################
##
#F Positions( <list>, <obj> )
##
InstallGlobalFunction( Positions,
function( list, obj )
local res, p;
if IsPlistRep(list) then
res := [];
p := 0;
while true do
p := Position(list,obj,p);
if p <> fail then
Add(res,p);
else
break;
fi;
od;
else
res:= PositionsOp(list,obj);
fi;
SetIsSSortedList( res, true );
return res;
end );
# generic method for non-plain lists
InstallMethod(PositionsOp, [IsList, IsObject], function(list, obj)
local res, p;
res := [];
p := Position(list, obj);
while p <> fail do
Add(res, p);
p := Position(list, obj, p);
od;
return res;
end);
#############################################################################
##
#M PositionCanonical( <list>, <obj> ) . . for internally represented lists
##
InstallMethod( PositionCanonical,
"for internally represented lists, fall back on `Position'",
[ IsList and IsInternalRep, IsObject ],
function( list, obj )
return Position( list, obj, 0 );
end );
InstallMethod( PositionCanonical,
"internal small sorted lists, use `POSITION_SORTED_LIST'",
[ IsList and IsInternalRep and IsSSortedList and IsSmallList, IsObject ],
function(l,o)
local p;
p:=POSITION_SORTED_LIST(l,o);
if p=0 or p>Length(l) or l[p]<>o then
return fail;
else
return p;
fi;
end);
#############################################################################
##
#M PositionNthOccurrence( <list>, <obj>, <n> ) . . call `Position' <n> times
##
InstallMethod( PositionNthOccurrence,
"for list, object, integer",
[ IsList, IsObject, IsInt ],
function( list, obj, n )
local pos, i;
pos := 0;
for i in [ 1 .. n ] do
pos := Position( list, obj, pos );
if pos = fail then
return fail;
fi;
od;
return pos;
end );
#############################################################################
##
#M PositionNthOccurrence( <blist>, <bool>, <n> ) kernel function for blists
##
InstallMethod( PositionNthOccurrence,
"for boolean list, boolean, integer",
[ IsBlist, IsBool, IsInt ],
function( blist, bool, n )
if bool then return PositionNthTrueBlist( blist, n );
else TryNextMethod(); fi;
end );
#############################################################################
##
#F PositionSorted( <list>, <obj>[, <func> ] )
#M PositionSortedOp( <list>, <obj> )
#M PositionSortedOp( <list>, <obj>, <func> )
##
InstallGlobalFunction( PositionSorted, function(arg)
if IsPlistRep(arg[1]) then
if Length(arg) = 3 then
return CallFuncList(POSITION_SORTED_LIST_COMP, arg);
else
return CallFuncList(POSITION_SORTED_LIST, arg);
fi;
else
return CallFuncList(PositionSortedOp, arg);
fi;
end);
InstallMethod( PositionSortedOp,
"for small list, and object",
[ IsList and IsSmallList, IsObject ],
POSITION_SORTED_LIST );
InstallMethod( PositionSortedOp,
[ IsList, IsObject ],
function( list, elm )
if IsSmallList( list ) then
return POSITION_SORTED_LIST( list, elm );
else
TryNextMethod();
fi;
end );
InstallMethod( PositionSortedOp,
"for small list, object, and function",
[ IsList and IsSmallList, IsObject, IsFunction ],
POSITION_SORTED_LIST_COMP );
InstallMethod( PositionSortedOp,
"for list, object, and function",
[ IsList, IsObject, IsFunction ],
function( list, elm, func )
if IsSmallList( list ) then
return POSITION_SORTED_LIST_COMP( list, elm, func );
else
TryNextMethod();
fi;
end );
#############################################################################
##
#F PositionSortedBy( <list>, <val>, <func> )
#F PositionSortedByOp( <list>, <val>, <func> )
##
InstallGlobalFunction( PositionSortedBy, function( list, val, func )
if IsPlistRep(list) then
return POSITION_SORTED_BY(list, val, func);
else
return PositionSortedByOp(list, val, func);
fi;
end);
InstallMethod( PositionSortedByOp,
"for a dense plain list, an object and a function",
[ IsDenseList and IsPlistRep, IsObject, IsFunction ],
POSITION_SORTED_BY);
InstallMethod( PositionSortedByOp,
"for a dense list, an object and a function",
[ IsDenseList, IsObject, IsFunction ],
function ( list, val, func )
local l, h, m;
# simple binary search. The entry is in the range [l..h]
l := 0;
h := Length(list) + 1;
while l + 1 < h do # list[l] < val && val <= list[h]
m := QuoInt(l + h, 2); # l < m < h
if func(list[m]) < val then
l := m; # it's not in [lo..m], so take the upper part.
else
h := m; # So val<=list[m][1], so the new range is [1..m].
fi;
od;
return h;
end );
#############################################################################
##
#F PositionSet( <list>, <obj> )
#F PositionSet( <list>, <obj>, <func> )
##
InstallGlobalFunction( PositionSet, function( arg )
local list, obj, pos;
if Length( arg ) = 2 and IsList( arg[1] ) then
list := arg[1];
obj := arg[2];
pos := PositionSorted( list, obj );
elif Length( arg ) = 3 and IsList( arg[1] ) and IsFunction( arg[3] ) then
list := arg[1];
obj := arg[2];
pos := PositionSorted( list, obj, arg[3] );
else
Error( "usage: PositionSet( <list>, <elm>[, <func>] )" );
fi;
if ( not IsBound( list[ pos ] ) ) or list[ pos ] <> obj then
pos:= fail;
fi;
return pos;
end );
#############################################################################
##
#M PositionProperty(<list>,<func>) . position of an element with a property
#M PositionProperty( <list>, <func>, <from> )
##
InstallMethod( PositionProperty,
"for list and function",
[ IsList, IsFunction ],
function ( list, func )
local i;
for i in [ 1 .. Length( list ) ] do
if IsBound( list[i] ) then
if func( list[ i ] ) then
return i;
fi;
fi;
od;
return fail;
end );
InstallMethod( PositionProperty,
"for list, function, and integer",
[ IsList, IsFunction, IsInt ],
function( list, func, from )
local i;
if from < 0 then
from:= 0;
fi;
for i in [ from+1 .. Length( list ) ] do
if IsBound( list[i] ) then
if func( list[i] ) then
return i;
fi;
fi;
od;
return fail;
end );
InstallMethod( PositionProperty,
"for dense list and function",
[ IsDenseList, IsFunction ],
function ( list, func )
local i;
for i in [ 1 .. Length( list ) ] do
if func( list[ i ] ) then
return i;
fi;
od;
return fail;
end );
InstallMethod( PositionProperty,
"for dense list, function, and integer",
[ IsDenseList, IsFunction, IsInt ],
function( list, func, from )
local i;
if from < 0 then
from:= 0;
fi;
for i in [ from+1 .. Length( list ) ] do
if func( list[i] ) then
return i;
fi;
od;
return fail;
end );
#############################################################################
##
#M PositionMaximum(<list>[, <func>]) . position of the largest element
#M PositionMinimum(<list>[, <func>]) . position of the smallest element
##
InstallGlobalFunction( PositionMaximum,
function ( args... )
local list, func, i, bestval, bestindex, ival;
if Length(args) < 1 or Length(args) > 2
or not(IsList(args[1]))
or (Length(args) = 2 and not(IsFunction(args[2]))) then
ErrorNoReturn("Usage: PositionMaximum(<list>, [<func>])");
fi;
list := args[1];
if Length(args) = 2 then
func := args[2];
else
func := IdFunc;
fi;
bestindex := fail;
for i in [ 1 .. Length( list ) ] do
if IsBound( list[i] ) then
ival := func ( list[ i ] );
if not( IsBound(bestval) ) or ival > bestval then
bestval := ival;
bestindex := i;
fi;
fi;
od;
return bestindex;
end );
InstallGlobalFunction( PositionMinimum,
function ( args... )
local list, func, i, bestval, bestindex, ival;
if Length(args) < 1 or Length(args) > 2
or not(IsList(args[1]))
or (Length(args) = 2 and not(IsFunction(args[2]))) then
ErrorNoReturn("Usage: PositionMinimum(<list>, [<func>])");
fi;
list := args[1];
if Length(args) = 2 then
func := args[2];
else
func := IdFunc;
fi;
bestindex := fail;
for i in [ 1 .. Length( list ) ] do
if IsBound( list[i] ) then
ival := func ( list[ i ] );
if not( IsBound(bestval) ) or ival < bestval then
bestval := ival;
bestindex := i;
fi;
fi;
od;
return bestindex;
end );
#############################################################################
##
#M PositionsProperty(<list>,<func>) . positions of elements with a property
##
InstallMethod( PositionsProperty,
"for list and function",
[ IsList, IsFunction ],
function( list, func )
local result, i;
result:= [];
for i in [ 1 .. Length( list ) ] do
if IsBound( list[ i ] ) and func( list[i] ) then
Add( result, i );
fi;
od;
SetIsSSortedList( result, true );
return result;
end );
InstallMethod( PositionsProperty,
"for dense list and function",
[ IsDenseList, IsFunction ],
function( list, func )
local result, i;
result:= [];
for i in [ 1 .. Length( list ) ] do
if func( list[i] ) then
Add( result, i );
fi;
od;
SetIsSSortedList( result, true );
return result;
end );
#############################################################################
##
#M PositionBound( <list> ) . . . . . . . . . . position of first bound entry
##
InstallMethod( PositionBound,
"for a list",
[ IsList ],
function( list )
local i;
for i in [ 1 .. Length( list ) ] do
if IsBound( list[i] ) then
return i;
fi;
od;
return fail;
end );
#############################################################################
##
#M PositionsBound( <list> ) . . . . . . . . . positions of all bound entries
##
InstallGlobalFunction( PositionsBound, function( list )
local i, bound;
if IsDenseList( list ) then
return [ 1 .. Length( list ) ];
fi;
bound := [];
for i in [ 1 .. Length( list ) ] do
if IsBound( list[i] ) then
Add( bound, i );
fi;
od;
SetIsSSortedList( bound, true );
return bound;
end );
#############################################################################
##
#M PositionSublist( <list>,<sub>[,<ind>] )
##
InstallMethod( PositionSublist,
"list,sub,pos",
[IsList,IsList,IS_INT],
function( list,sub,start )
local n, m, next, j, max, i;
n:=Length(list);
m:=Length(sub);
start:=Position(list, sub[1], start);
# trivial case
if m = 1 or start = fail then
return start;
fi;
# string-match algorithm, cf. Manber, section 6.7
# compute the next entries
next:=[-1,0];
for i in [3..m] do
j:=next[i-1]+1;
while j>0 and sub[i-1]<>sub[j] do
j:=next[j]+1;
od;
next[i]:=j;
od;
if Maximum(next) * 3 < m then
# in this case reduce overhead and use naive loop
i := start;
max := n - m + 1;
while i<>fail and i <= max do
for j in [2..m] do
if list[i+j-1] <> sub[j] then
j := 0;
break;
fi;
od;
if j <> 0 then
return i;
fi;
i:=Position(list, sub[1], i);
od;
return fail;
fi;
# otherwise repeat with Manber
i:=start;
j:=1;
while i<=n do
if sub[j]=list[i] then
i:=i+1;
j:=j+1;
else
j:=next[j]+1;
if j=0 then
j:=1;
i:=i+1;
fi;
fi;
if j=m+1 then
return i-m;
fi;
od;
return fail;
end);
# no installation restrictions to avoid extra installations for empty list
#T but the first two arguments should be in `IsList', shouldn't they?
InstallOtherMethod( PositionSublist,
"list, sub",
[IsObject,IsObject],
function( list,sub )
return PositionSublist(list,sub,0);
end);
InstallOtherMethod( PositionSublist,
"empty list,sub,pos",
[IsEmpty,IsList,IS_INT],
ReturnFail);
InstallOtherMethod( PositionSublist,
"list,empty,pos",
[IsList,IsEmpty,IS_INT],
function(a,b,c)
return Maximum(c+1,1);
end);
#############################################################################
##
#M IsMatchingSublist( <list>,<sub>[,<ind>] )
##
InstallMethod( IsMatchingSublist,
"list,sub,pos",
IsFamFamX,
[IsList,IsList,IS_INT],
function( list,sub,first )
local last;
last:=first+Length(sub)-1;
return Length(list) >= last and list{[first..last]} = sub;
end);
# no installation restrictions to avoid extra installations for empty list
InstallOtherMethod( IsMatchingSublist,
"list, sub",
[IsObject,IsObject],
function( list,sub )
return IsMatchingSublist(list,sub,1);
end);
InstallOtherMethod( IsMatchingSublist,
"empty list,sub,pos",
[IsEmpty,IsList,IS_INT],
function(list,sub,first )
return not IsEmpty(sub);
end);
InstallOtherMethod( IsMatchingSublist,
"list,empty,pos",
[IsList,IsEmpty,IS_INT],
ReturnTrue);
#############################################################################
##
#M Add( <list>, <obj> )
##
InstallMethod( Add,
"for mutable list and list",
[ IsList and IsMutable, IsObject ],
ADD_LIST_DEFAULT );
InstallMethod( Add, "three arguments fast version",
[ IsPlistRep and IsList and IsMutable, IsObject, IsPosInt],
function(l, o, p)
local len;
len := Length(l);
if p <= len then
CopyListEntries(l,p,1,l,p+1,1,len-p+1);
fi;
l[p] := o;
return;
end);
InstallMethod( Add, "three arguments fast version sorted",
[ IsPlistRep and IsSSortedList and IsMutable, IsObject, IsPosInt],
function(l, o, p)
local len;
len := Length(l);
if p <= len then
CopyListEntries(l,p,1,l,p+1,1,len-p+1);
fi;
l[p] := o;
if IS_DENSE_LIST(l) and (p = 1 or l[p-1] < o) and (p = len+1 or o < l[p+1]) then
SET_IS_SSORTED_PLIST(l);
fi;
return;
end);
InstallMethod( Add, "three arguments general version",
[IsList and IsMutable, IsObject, IsPosInt],
function(l, o, p)
local len;
len := Length(l);
if p <= len then
l{[len+1,len..p+1]} := l{[len,len-1..p]};
fi;
l[p] := o;
return;
end);
#############################################################################
##
#M Remove(<list>[,<pos>])
##
InstallMethod(Remove, "one argument", [IsList and IsMutable],
function(l)
local x,len;
len := Length(l);
if len = 0 then
Error("Remove: list <l> must not be empty.\n");
fi;
x := l[len];
Unbind(l[len]);
return x;
end);
InstallEarlyMethod(Remove,
function(l,p)
local ret,x,len;
if not (IsPlistRep(l) and IsMutable(l) and IsPosInt(p)) then
TryNextMethod();
fi;
len := Length(l);
ret := IsBound(l[p]);
if ret then
x := l[p];
fi;
if p <= len then
CopyListEntries(l,p+1,1,l,p,1,len-p);
Unbind(l[len]);
fi;
if ret then
return x;
fi;
end);
InstallMethod(Remove, "two arguments, general", [IsList and IsMutable, IsPosInt],
function(l,p)
local ret,x,len;
len := Length(l);
ret := IsBound(l[p]);
if ret then
x := l[p];
fi;
if p <= len then
l{[p..len-1]} := l{[p+1..len]};
Unbind(l[len]);
fi;
if ret then
return x;
fi;
end);
#############################################################################
##
#M Append(<list1>,<list2>)
##
BindGlobal( "APPEND_LIST_DEFAULT", function ( list1, list2 )
local len1, len2, i;
len1 := Length(list1);
len2 := Length(list2);
if len1 = infinity then
Error("Append: can't append to an infinite list");
fi;
if len2 = infinity then
Error("Append: Default method can't append an infinite list");
fi;
for i in [1..len2] do
if IsBound(list2[i]) then
list1[len1+i] := list2[i];
fi;
od;
end );
InstallMethod( Append,
"for mutable list and list",
[ IsList and IsMutable , IsList ],
APPEND_LIST_DEFAULT );
InstallMethod( Append,
"for mutable list in plist representation, and small list",
[ IsList and IsPlistRep and IsMutable, IsList and IsSmallList ],
APPEND_LIST_INTR );
#############################################################################
##
#F Apply( <list>, <func> ) . . . . . . . . apply a function to list entries
##
InstallGlobalFunction( Apply, function( list, func )
local i;
for i in [1..Length( list )] do
if IsBound(list[i]) then
list[i] := func( list[i] );
fi;
od;
end );
#############################################################################
##
#F Concatenation( <list1>, <list2>, ... )
#F Concatenation( <list> )
##
InstallGlobalFunction( Concatenation, function ( arg )
local res, i;
if Length( arg ) = 1 and IsList( arg[1] ) then
arg := arg[1];
fi;
if Length( arg ) = 0 then
return [ ];
fi;
if not IsList( arg[1] ) then
Error( "Concatenation: arguments must be lists" );
fi;
res := ShallowCopy( arg[1] );
for i in [ 2 .. Length( arg ) ] do
if not IsList( arg[i] ) then
Error( "Concatenation: arguments must be lists" );
fi;
Append( res, arg[i] );
od;
return res;
end );
#############################################################################
##
#M Compacted( <list> ) . . . . . . . . . . . . . . remove holes from a list
##
InstallMethod( Compacted,
"for a list",
[ IsList ],
function ( list )
local res, # compacted of <list>, result
elm; # element of <list>
if IsDenseList(list) then
return ShallowCopy(list);
fi;
res := [];
for elm in list do
Add( res, elm );
od;
return res;
end );
#############################################################################
##
#M Collected( <list> ) . . . . .
##
InstallMethod( Collected,
"for a list",
[ IsList ],
function ( list )
local res, # collected, result
col, # one element of collected list
sorted, # list in sorted order
elm; # one element of list
# special case for empty list
if IsEmpty( list ) then
return [];
fi;
# sort a shallow copy of the list
sorted := ShallowCopy( list );
Sort( sorted );
# now collect
res := [];
col := [ sorted[1], 0 ];
for elm in sorted do
if elm <> col[1] then
Add( res, col );
col := [ elm, 0 ];
fi;
col[2] := col[2] + 1;
od;
Add( res, col );
# return the collected list
return res;
end );
#############################################################################
##
#M DuplicateFreeList( <list> ) . . . . duplicate free list of list elements
##
InstallMethod( DuplicateFreeList,
"for a list",
[ IsList ],
function ( list )
local l,i;
l:= [];
for i in list do
if not i in l then
Add(l,i);
fi;
od;
return l;
end );
#############################################################################
##
#M AsDuplicateFreeList( <list> ) . . . duplicate free list of list elements
##
InstallMethod( AsDuplicateFreeList,
"for a list",
[ IsList ],
DuplicateFreeList );
#############################################################################
##
#M Flat( <list> ) . . . . . . . list of elements of a nested list structure
##
InstallMethod( Flat,
"for a list",
[ IsList ],
function ( list )
local res, # list <list> flattened, result
elm; # one element of <list>
res := [];
for elm in list do
if not IsList(elm) then
Add( res, elm );
else
Append( res, Flat(elm) );
fi;
od;
return res;
end );
#############################################################################
##
#F Reversed( <list> ) . . . . . . . . . . . reverse the elements in a list
##
## Note that the special case that <list> is a range is dealt with by the
## `{}' implementation, we need not introduce a special treatment for this.
##
InstallGlobalFunction( Reversed,
function( list )
local tnum, len;
tnum:= TNUM_OBJ( list );
if FIRST_LIST_TNUM <= tnum and tnum <= LAST_LIST_TNUM then
len:= Length( list );
return list{ [ len, len-1 .. 1 ] };
else
return ReversedOp( list );
fi;
end );
#############################################################################
##
#M ReversedOp( <list> ) . . . . . . . . . . reverse the elements in a list
##
## We install just two generic methods;
## they deal with (non-internal) finite lists only.
##
InstallMethod( ReversedOp,
"for a dense list",
[ IsDenseList ],
function( list )
local len;
if not IsFinite( list ) then
TryNextMethod();
fi;
len:= Length( list );
return list{ [ len, len-1 .. 1 ] };
end );
InstallMethod( ReversedOp,
"for a range",
[ IsRange ],
function ( list )
local len;
len := Length( list );
if len = 0 then
return [];
elif len = 1 then
return [ list[1] ];
else
return [ list[len], list[len-1] .. list[1] ];
fi;
end );
#############################################################################
##
#M Shuffle( <list> ) . . . . . . . . . . . . . . . . permute entries randomly
InstallMethod(Shuffle, [IsDenseList and IsMutable], function(l)
local len, j, tmp, i;
len := Length(l);
for i in [1..len-1] do
j := Random(i, len);
if i <> j then
tmp := l[i];
l[i] := l[j];
l[j] := tmp;
fi;
od;
return l;
end);
#############################################################################
##
#M Sort( <list>[, <func>] )
##
InstallMethod( Sort,
"for a mutable small list",
[ IsList and IsMutable and IsSmallList ],
SORT_LIST );
InstallMethod( StableSort,
"for a mutable small list",
[ IsList and IsMutable and IsSmallList ],
STABLE_SORT_LIST );
InstallMethod( Sort,
"for a mutable list",
[ IsList and IsMutable ],
function( list )
if IsSmallList( list ) then
SORT_LIST( list );
else
TryNextMethod();
fi;
end );
InstallMethod( StableSort,
"for a mutable list",
[ IsList and IsMutable ],
function( list )
if IsSmallList( list ) then
STABLE_SORT_LIST( list );
else
TryNextMethod();
fi;
end );
InstallMethod( Sort,
"for a mutable set",
[ IsList and IsMutable and IsSortedList ], SUM_FLAGS,
Ignore );
InstallMethod( StableSort,
"for a mutable set",
[ IsList and IsMutable and IsSortedList ], SUM_FLAGS,
Ignore );
InstallMethod( Sort,
"for a mutable small list and a function",
[ IsList and IsMutable and IsSmallList, IsFunction ],
SORT_LIST_COMP );
InstallMethod( StableSort,
"for a mutable small list and a function",
[ IsList and IsMutable and IsSmallList, IsFunction ],
STABLE_SORT_LIST_COMP );
InstallMethod( Sort,
"for a mutable list and a function",
[ IsList and IsMutable, IsFunction ],
function( list, func )
if IsSmallList( list ) then
SORT_LIST_COMP( list, func );
else
TryNextMethod();
fi;
end );
InstallMethod( StableSort,
"for a mutable list and a function",
[ IsList and IsMutable, IsFunction ],
function( list, func )
if IsSmallList( list ) then
STABLE_SORT_LIST_COMP( list, func );
else
TryNextMethod();
fi;
end );
#############################################################################
##
#M SortBy( <list>, <func> )
##
InstallMethod( SortBy, "for a mutable list and a function",
[IsList and IsMutable, IsFunction ],
function(list, func)
local images;
images := List(list, func);
SortParallel(images, list);
return;
end);
InstallMethod( StableSortBy, "for a mutable list and a function",
[IsList and IsMutable, IsFunction ],
function(list, func)
local images;
images := List(list, func);
StableSortParallel(images, list);
return;
end);
#############################################################################
##
#F SORT_MUTABILITY_ERROR_HANDLER( <list> )
#F SORT_MUTABILITY_ERROR_HANDLER( <list>, <func> )
#F SORT_MUTABILITY_ERROR_HANDLER( <list1>, <list2> )
#F SORT_MUTABILITY_ERROR_HANDLER( <list1>, <list2>, <func> )
##
## This function will be installed as method for `Sort', `Sortex' and
## `SortParallel', for the sake of a more gentle error message.
##
BindGlobal( "SORT_MUTABILITY_ERROR_HANDLER", function( arg )
if ( Length( arg ) = 1 and IsMutable( arg[1] ) )
or ( Length( arg ) = 2 and IsMutable( arg[1] )
and ( IsFunction( arg[2] ) or IsMutable( arg[2] ) ) )
or ( Length( arg ) = 3 and IsMutable( arg[1] )
and IsMutable( arg[2] ) ) then
TryNextMethod();
fi;
Error( "immutable lists cannot be sorted" );
end );
InstallOtherMethod( Sort,
"for an immutable list",
[ IsList ],
SORT_MUTABILITY_ERROR_HANDLER );
InstallOtherMethod( StableSort,
"for an immutable list",
[ IsList ],
SORT_MUTABILITY_ERROR_HANDLER );
InstallOtherMethod( Sort,
"for an immutable list and a function",
[ IsList, IsFunction ],
SORT_MUTABILITY_ERROR_HANDLER );
InstallOtherMethod( StableSort,
"for an immutable list and a function",
[ IsList, IsFunction ],
SORT_MUTABILITY_ERROR_HANDLER );
#############################################################################
##
#M Sortex( <list> ) . . sort a list (stable), return the applied permutation
##
InstallMethod( Sortex,
"for a mutable list",
[ IsList and IsMutable ],
function ( list )
local n, index;
# {\GAP} supports permutations only up to `MAX_SIZE_LIST_INTERNAL'.
if not IsSmallList( list ) then
Error( "<list> must have length at most ", MAX_SIZE_LIST_INTERNAL );
fi;
n := Length(list);
index := [1..n];
StableSortParallel(list, index);
return PermList(index)^-1;
end );
InstallMethod( Sortex,
"for a mutable list and a function",
[ IsList and IsMutable, IsFunction ],
function ( list, comp )
local n, index;
# {\GAP} supports permutations only up to `MAX_SIZE_LIST_INTERNAL'.
if not IsSmallList( list ) then
Error( "<list> must have length at most ", MAX_SIZE_LIST_INTERNAL );
fi;
n := Length(list);
index := [1..n];
StableSortParallel(list, index, comp);
return PermList(index)^-1;
end );
InstallMethod( Sortex,
"for a mutable sorted list",
[ IsDenseList and IsSortedList and IsMutable ], SUM_FLAGS,
list -> () );
InstallOtherMethod( Sortex,
"for an immutable list",
[ IsList ],
SORT_MUTABILITY_ERROR_HANDLER );
#############################################################################
##
#F PermListList( <list1>, <list2> ) what permutation of <list1> is <list2>
##
InstallGlobalFunction( PermListList, function( list1, list2 )
local perm;
# to not destroy list1 and list2
list1:= ShallowCopy(list1);
list2:= ShallowCopy(list2);
perm:= Sortex( list2 ) / Sortex( list1 );
if list1 <> list2 then
return fail;
else
return perm;
fi;
end );
#############################################################################
##
#M SortingPerm( <list> )
##
InstallMethod( SortingPerm,
[ IsDenseList ],
function( list )
local copy;
copy := ShallowCopy(list);
return Sortex(copy);
end );
InstallMethod( SortingPerm,
"for a dense and sorted list",
[ IsDenseList and IsSortedList ], SUM_FLAGS,
list -> () );
#############################################################################
##
#M SortParallel( <list>, <list2> ) . . . . . . . sort two lists in parallel
##
InstallMethod( SortParallel,
"for two mutable lists",
[ IsList and IsMutable,
IsList and IsMutable ],
SORT_PARA_LIST );
InstallMethod( StableSortParallel,
"for two mutable lists",
[ IsList and IsMutable,
IsList and IsMutable ],
STABLE_SORT_PARA_LIST );
#############################################################################
##
#M SortParallel( <sorted>, <list> )
##
InstallMethod( SortParallel,
"for a mutable set and a dense mutable list",
[ IsDenseList and IsSortedList and IsMutable,
IsDenseList and IsMutable ],
SUM_FLAGS,
Ignore );
InstallMethod( StableSortParallel,
"for a mutable set and a dense mutable list",
[ IsDenseList and IsSortedList and IsMutable,
IsDenseList and IsMutable ],
SUM_FLAGS,
Ignore );
#############################################################################
##
#M SortParallel( <list>, <list2>, <func> )
##
InstallMethod( SortParallel,
"for mutable lists, and function",
[ IsList and IsMutable,
IsList and IsMutable,
IsFunction ],
SORT_PARA_LIST_COMP );
InstallMethod( StableSortParallel,
"for two mutable lists, and function",
[ IsList and IsMutable,
IsList and IsMutable,
IsFunction ],
STABLE_SORT_PARA_LIST_COMP );
InstallOtherMethod( SortParallel,
"for two immutable lists",
[IsList,IsList],
SORT_MUTABILITY_ERROR_HANDLER);
InstallOtherMethod( StableSortParallel,
"for two immutable lists",
[IsList,IsList],
SORT_MUTABILITY_ERROR_HANDLER);
InstallOtherMethod( SortParallel,
"for two immutable lists and function",
[IsList,IsList,IsFunction],
SORT_MUTABILITY_ERROR_HANDLER);
InstallOtherMethod( StableSortParallel,
"for two immutable lists and function",
[IsList,IsList,IsFunction],
SORT_MUTABILITY_ERROR_HANDLER);
#############################################################################
##
#F Maximum( <obj>, ... )
##
InstallGlobalFunction( Maximum, function ( arg )
if Length( arg ) = 1 then
return MaximumList( arg[1] );
elif Length( arg ) > 2 then
return MaximumList( arg );
elif Length( arg ) = 2 then
if arg[1] > arg[2] then
return arg[1];
else
return arg[2];
fi;
else
Error( "usage: Maximum( <arg1>,... )" );
fi;
end );
#############################################################################
##
#M MaximumList( <list> )
##
InstallMethod( MaximumList,
"for a list",
[ IsList ],
function ( list )
local max, elm;
--> --------------------
--> maximum size reached
--> --------------------
[ 0.58Quellennavigators
Projekt
]
|
