#######################################################################
##
#F MakeHalfInfList( <start>, <direction>, <typeWithArgs>, <callback>, <repeatifyCallback> )
##
## Creates a IsHalfInfList with start index <start>, <direction> is
## -1 for negative or 1 for positive, <typeWithArgs> is a list of either
## two or three arguments describing the nature of the infinite list
## (see the documentation), and <callback> is a function which is called
## whenever a new list element is computed.
##
InstallGlobalFunction( MakeHalfInfList,
function( start, direction, typeWithArgs, callback, repeatifyCallback )
local type, repeatingList, func, initialValue, storeValues, data, list,
repeatify;
type := typeWithArgs[ 1 ];
if type = "next/repeat" then
type := "next";
repeatify := true;
else
repeatify := false;
fi;
if type = "repeat" then
repeatingList := typeWithArgs[ 2 ];
func := fail;
storeValues := false;
else
repeatingList := fail;
func := typeWithArgs[ 2 ];
storeValues := true;
fi;
initialValue := fail;
if type = "next" then
initialValue := typeWithArgs[ 3 ];
elif type = "pos" and Length( typeWithArgs ) = 3 then
storeValues := typeWithArgs[ 3 ];
fi;
data := rec( values := [],
start := start,
direction := direction,
type := type,
func := func,
repeatingList := repeatingList,
storingValues := storeValues,
initialValue := initialValue,
callback := callback,
repeatify := repeatify,
repeatifyCallback := repeatifyCallback );
list := Objectify( NewType( NewFamily( "HalfInfListsFamily" ),
IsHalfInfList and IsHalfInfListDefaultRep ),
data );
return list;
end );
#######################################################################
##
#M StartPosition( <list> )
##
## Returns the start position of a IsHalfInfList <list>.
##
InstallMethod( StartPosition,
[ IsHalfInfList ],
function( list )
return list!.start;
end );
#######################################################################
##
#M Direction( <list> )
##
## Returns the direction of a IsHalfInfList <list>.
##
InstallMethod( Direction,
[ IsHalfInfList ],
function( list )
return list!.direction;
end );
#######################################################################
##
#M InfListType( <list> )
##
## Returns the type of a IsHalfInfList <list>.
##
InstallMethod( InfListType,
[ IsHalfInfList ],
function( list )
return list!.type;
end );
#######################################################################
##
#M RepeatingList( <list> )
##
## Returns the repeatingList of a IsHalfInfList <list>.
##
InstallMethod( RepeatingList,
[ IsHalfInfList ],
function( list )
return list!.repeatingList;
end );
#######################################################################
##
#M ElementFunction( <list> )
##
## Returns the element-function of a IsHalfInfList <list>.
##
InstallMethod( ElementFunction,
[ IsHalfInfList ],
function( list )
return list!.func;
end );
#######################################################################
##
#M IsStoringValues( <list> )
##
## Returns the value of the (boolean) storingValues of a
## IsHalfInfList <list>.
##
InstallMethod( IsStoringValues,
[ IsHalfInfList ],
function( list )
return list!.storingValues;
end );
#######################################################################
##
#M NewValueCallback( <list> )
##
## Returns the callback function of a IsHalfInfList <list>.
##
InstallMethod( NewValueCallback,
[ IsHalfInfList ],
function( list )
return list!.callback;
end );
#######################################################################
##
#M IsRepeating( <list> )
##
## Returns true if the type of the IsHalfInfList <list> is "repeat",
## false otherwise.
##
InstallMethod( IsRepeating,
[ IsHalfInfList ],
function( list )
return list!.type = "repeat";
end );
#######################################################################
##
#M InitialValue( <list> )
##
## Returns the initial value of a IsHalfInfList <list>.
##
InstallMethod( InitialValue,
[ IsHalfInfList ],
function( list )
return list!.initialValue;
end );
#######################################################################
##
#M \^( <list>, <pos> )
##
## Returns the stored value at index <pos> in the IsHalfInfList
## <list>.
##
InstallMethod( \^,
[ IsHalfInfList and IsHalfInfListDefaultRep, IsInt ],
function( list, pos )
local index, i, callCallbackFunction, r;
index := (pos - StartPosition( list )) * Direction( list );
if index < 0 then
Error( "illegal half inf list position ", pos, "\n" );
fi;
callCallbackFunction := function( index )
local pos, cb;
pos := StartPosition( list ) + index * Direction( list );
cb := NewValueCallback( list );
if IsFunction( cb ) then
cb( pos, Direction( list ), InfListType( list ) );
fi;
end;
if InfListType( list ) = "repeat" then
index := index mod Length( RepeatingList( list ) );
return RepeatingList( list )[ index + 1 ];
elif InfListType( list ) = "next" then
if Length( list!.values ) = 0 then
list!.values[ 1 ] := ElementFunction( list )( InitialValue( list ) );
callCallbackFunction( 0 );
fi;
for i in [ Length( list!.values ) .. index ] do
list!.values[ i + 1 ] := ElementFunction( list )( list!.values[ i ] );
callCallbackFunction( i );
if list!.repeatify and i mod 2 = 0 then
if list!.values[ i / 2 + 1 ] = list!.values[ i + 1 ] then
r := MakeRepeatingList( list, i / 2 + 1, i + 1 );
list!.repeatifyCallback( r[ 1 ], r[ 2 ] );
list!.repeatify := false;
return r[ 2 ]^pos;
fi;
fi;
od;
return list!.values[ index + 1 ];
elif InfListType( list ) = "pos" then
if IsStoringValues( list ) then
for i in [ Length( list!.values ) .. index ] do
list!.values[ i + 1 ]
:= ElementFunction( list )( StartPosition( list )
+ i * Direction( list ) );
callCallbackFunction( i );
od;
return list!.values[ index + 1 ];
else
return ElementFunction( list )( pos );
fi;
fi;
end );
InstallMethod( MakeRepeatingList,
[ IsHalfInfList, IsPosInt, IsPosInt ],
function( list, collisionIndex1, collisionIndex2 )
local values, i1, i2, i, repeatStartIndex, repeatEndIndex,
tail, repeatedList, newList;
values := list!.values;
i1 := collisionIndex1;
i2 := collisionIndex2;
while i1 > 0 and values[ i1 ] = values[ i2 ] do
i1 := i1 - 1;
i2 := i2 - 1;
od;
repeatStartIndex := i1 + 1;
i := repeatStartIndex + 1;
while values[ i ] <> values[ repeatStartIndex ] do
i := i + 1;
od;
repeatEndIndex := i - 1;
tail := values{ [ 1 .. ( repeatStartIndex - 1 ) ] };
if Direction( list ) = -1 then
tail := Reversed( tail );
fi;
repeatedList := values{ [ repeatStartIndex .. repeatEndIndex ] };
newList := MakeHalfInfList( StartPosition( list ) + ( repeatStartIndex - 1 ) * Direction( list
),
Direction( list ),
[ "repeat", repeatedList ],
false, false );
return [ tail, newList ];
end );
#######################################################################
##
#M LowestKnownPosition( <list> )
##
## Returns the lowest index of the list where the value is known
## without computation.
##
InstallMethod( LowestKnownPosition,
[ IsHalfInfList ],
function( list )
if Direction( list ) = 1 then
if Length( list!.values ) = 0 and InfListType( list ) <> "repeat" then
return "none";
else
return StartPosition( list );
fi;
else
if InfListType( list ) = "repeat" then
return -infinity;
elif Length( list!.values ) = 0 and InfListType( list ) <> "repeat" then
return "none";
else
return StartPosition( list ) - (Length( list!.values ) - 1);
fi;
fi;
end );
#######################################################################
##
#M HighestKnownPosition( <list> )
##
## Returns the highest index of the list where the value is known
## without computation.
##
InstallMethod( HighestKnownPosition,
[ IsHalfInfList ],
function( list )
if Direction( list ) = -1 then
if Length( list!.values ) = 0 and InfListType( list ) <> "repeat" then
return "none";
else
return StartPosition( list );
fi;
else
if InfListType( list ) = "repeat" then
return infinity;
elif Length( list!.values ) = 0 and InfListType( list ) <> "repeat" then
return "none";
else
return StartPosition( list ) + (Length( list!.values ) - 1);
fi;
fi;
end );
#######################################################################
##
#F MakeInfList( <basePosition>, <middle>, <positive>, <negative>,
## <callback> )
##
## Creates an IsInfList object. <basePostition> tells in which index
## the values should be put, <middle> is a list of known values,
## <positive> is a list describing the positive part of the infinite
## list, and <negative> part is a list describing the negative part
## of the list. <callback> is a function to be called whenever a
## new value of the infinite list is computed.
##
InstallGlobalFunction( MakeInfList,
function( basePosition, middle, positive, negative, callback )
local list, posList, negList, posRepeatify, negRepeatify;
# TODO: automatic initialValue for "next" parts if middle is nonempty
# TODO: allow empty positive/negative?
posRepeatify := function( tail, repeating )
list!.middle := Concatenation( list!.middle, tail );
list!.positive := repeating;
end;
posList := MakeHalfInfList( basePosition + Length( middle ),
1, positive, callback, posRepeatify );
negRepeatify := function( tail, repeating )
list!.middle := Concatenation( tail, list!.middle );
list!.negative := repeating;
end;
negList := MakeHalfInfList( basePosition - 1,
-1, negative, callback, negRepeatify );
list := MakeInfListFromHalfInfLists( basePosition, middle, posList, negList );
return list;
end );
#######################################################################
##
#F MakeInfListFromHalfInfLists( <basePosition>, <middle>, <positive>,
## <negative> )
##
## Creates an IsInfList from a middle part (a list) and two IsHalfInfLists
## <positive> and <negative>.
##
InstallGlobalFunction( MakeInfListFromHalfInfLists,
function( basePosition, middle, positive, negative )
local list;
if negative <> fail and basePosition <> StartPosition( negative ) + 1 then
Error( "negative list starts at incorrect position" );
fi;
if positive <> fail and basePosition + Length( middle ) <> StartPosition( positive ) then
Error( "positive list starts at incorrect position" );
fi;
list := Objectify( NewType( NewFamily( "InfListsFamily" ),
IsInfList and IsInfListDefaultRep ),
rec( basePosition := basePosition,
middle := middle,
positive := positive,
negative := negative ) );
return list;
end );
#######################################################################
##
#F FunctionInfList( <func> )
##
## Creates an IsInfList where all list entries are described by a
## function.
##
InstallGlobalFunction( FunctionInfList,
function( func )
local positiveNegativeList;
positiveNegativeList := [ "pos", func, false ];
return MakeInfList( 0, [], positiveNegativeList, positiveNegativeList, false );
end );
#######################################################################
##
#F ConstantInfList( <value> )
##
## Creates an IsInfList with <value> in each position.
##
InstallGlobalFunction( ConstantInfList,
function( value )
return MakeInfList( 0, [], [ "repeat", [ value ] ], [ "repeat", [ value ] ], false );
end );
#######################################################################
##
#F FiniteInfList( <basePosition>, <list> )
##
## Creates an IsInfList which is finite. Only indexes in the interval
## [basePostition, basePosition + length(<list>) - 1] is allowed.
##
InstallGlobalFunction( FiniteInfList,
function( basePosition, list )
return MakeInfListFromHalfInfLists( basePosition, list, fail, fail );
end );
#######################################################################
##
#M MiddleStart( <list> )
##
## Returns the first index of the middle part, or the basePosition,
## of the IsInfList <list>.
##
InstallMethod( MiddleStart,
[ IsInfList ],
function( list )
return list!.basePosition;
end );
#######################################################################
##
#M MiddleEnd( <list> )
##
## Returns the last index of the middle part of the IsInfList <list>.
##
InstallMethod( MiddleEnd,
[ IsInfList ],
function( list )
return list!.basePosition + Length( list!.middle ) - 1;
end );
#######################################################################
##
#M MiddlePart( <list> )
##
## Returns the middle part of the IsInfList <list>, as a list.
##
InstallMethod( MiddlePart,
[ IsInfList ],
function( list )
return list!.middle;
end );
#######################################################################
##
#M PositivePart( <list> )
##
## Returns the positive part of the IsInfList <list>, as an IsHalfInfList.
##
InstallMethod( PositivePart,
[ IsInfList ],
function( list )
return list!.positive;
end );
#######################################################################
##
#M NegativePart( <list> )
##
## Returns the negative part of the IsInfList <list>, as an IsHalfInfList.
##
InstallMethod( NegativePart,
[ IsInfList ],
function( list )
return list!.negative;
end );
#######################################################################
##
#M LowestKnownPosition( <list> )
##
## Returns the lowest index where the value of the IsInfList <list>
## is computed or otherwise known.
##
InstallMethod( LowestKnownPosition,
[ IsInfList ],
function( list )
if NegativePart( list ) <> fail
and LowestKnownPosition( NegativePart( list ) ) <> "none" then
return LowestKnownPosition( NegativePart( list ) );
elif Length( MiddlePart( list ) ) > 0 then
return MiddleStart( list );
else
return LowestKnownPosition( PositivePart( list ) );
fi;
end );
#######################################################################
##
#M HighestKnownPosition( <list> )
##
## Returns the highest index where the value of the IsInfList <list>
## is computed or otherwise known.
##
InstallMethod( HighestKnownPosition,
[ IsInfList ],
function( list )
if PositivePart( list ) <> fail
and HighestKnownPosition( PositivePart( list ) ) <> "none" then
return HighestKnownPosition( PositivePart( list ) );
elif Length( MiddlePart( list ) ) > 0 then
return MiddleEnd( list );
else
return HighestKnownPosition( NegativePart( list ) );
fi;
end );
#######################################################################
##
#M UpperBound( <list> )
##
## Returns the highest index where the value of the IsInfList <list>
## exists (but is not necessarily known).
##
InstallMethod( UpperBound,
[ IsInfList ],
function( list )
if PositivePart( list ) <> fail then
return infinity;
elif Length( MiddlePart( list ) ) > 0 then
return MiddleEnd( list );
elif NegativePart( list ) <> fail then
return StartPosition( NegativePart( list ) );
else
return -infinity;
fi;
end );
#######################################################################
##
#M LowerBound( <list> )
##
## Returns the smallest index where the value of the IsInfList <list>
## exists (but is not necessarily known).
##
InstallMethod( LowerBound,
[ IsInfList ],
function( list )
if NegativePart( list ) <> fail then
return -infinity;
elif Length( MiddlePart( list ) ) > 0 then
return MiddleStart( list );
elif PositivePart( list ) <> fail then
return StartPosition( PositivePart( list ) );
else
return infinity;
fi;
end );
#######################################################################
##
#M \^( <list>, <pos> )
##
## Returns the value of the IsInfList <list> at the index <pos>.
##
InstallMethod( \^,
[ IsInfList, IsInt ],
function( list, pos )
local positive, negative;
positive := PositivePart( list );
negative := NegativePart( list );
if pos >= MiddleStart( list ) and pos <= MiddleEnd( list ) then
return MiddlePart( list )[ pos - MiddleStart( list ) + 1 ];
elif positive <> fail and pos >= StartPosition( positive ) then
return positive^pos;
elif negative <> fail and pos <= StartPosition( negative ) then
return negative^pos;
else
Error( "position ", pos, " outside index range of inflist ", list, "\n" );
fi;
end );
#######################################################################
##
#M Shift( <list>, <shift> )
##
## <list> is an IsHalfInfList. The method shifts the list <shift>
## positions; to the right if <shift> is positive or to the left if
## <shift> is negative.
##
InstallMethod( Shift,
[ IsHalfInfList, IsInt ],
function( list, shift )
if IsRepeating( list ) then
return MakeHalfInfList( StartPosition( list ) - shift, Direction( list ),
[ "repeat", RepeatingList( list ) ], false, false );
else
return MakeHalfInfList( StartPosition( list ) - shift, Direction( list ),
[ "pos", i -> list^(i + shift) ], false, false );
fi;
end );
#######################################################################
##
#M Shift( <list>, <shift> )
##
## <list> is an IsInfList. The method shifts the list <shift>
## positions; to the right if <shift> is positive or to the left if
## <shift> is negative.
##
InstallMethod( Shift,
[ IsInfList and IsInfListDefaultRep, IsInt ],
function( list, shift )
return MakeInfListFromHalfInfLists
( MiddleStart( list ) - shift,
MiddlePart( list ),
Shift( PositivePart( list ), shift ),
Shift( NegativePart( list ), shift ) );
end );
#######################################################################
##
#M FinitePartAsList( <list>, <startPos>, <endPos> )
##
## <list> is an IsInfList. The part of the list starting at index
## <startPos> and ending at index <endPos> is returned as a list.
## Note that <endPos> > <startPos>.
##
InstallMethod( FinitePartAsList,
[ IsInfList, IsInt, IsInt ],
function( list, startPos, endPos )
return List( [ startPos .. endPos ], i -> list^i );
end );
#######################################################################
##
#M Cut( <list>, <pos> )
##
## Returns a new IsHalfInfList which the old IsHalfInfList except
## that the positions with indices smaller than <pos> is removed.
##
InstallMethod( Cut,
[ IsHalfInfList, IsInt ],
function( list, pos )
local middle, half, middleLength, middlePositions, newStartPos;
if Direction( list ) = 1 and pos < StartPosition( list )
or Direction( list ) = -1 and pos > StartPosition( list ) then
Error( "position outside range of list" );
fi;
if pos = StartPosition( list ) then
middle := [];
half := list;
elif InfListType( list ) = "repeat" then
middleLength := ((StartPosition( list ) - pos) * Direction( list ))
mod Length( RepeatingList( list ) );
if Direction( list ) = 1 then
middlePositions := [ pos .. pos + middleLength - 1 ];
else
middlePositions := [ pos - middleLength + 1 .. pos ];
fi;
middle := List( middlePositions, i -> list^i );
newStartPos := pos + middleLength * Direction( list );
half := Shift( list, StartPosition( list ) - newStartPos );
else
middle := [];
half := MakeHalfInfList( pos, Direction( list ),
[ "pos", i -> list^i ],
false, false );
fi;
if Direction( list ) = 1 then
return MakeInfListFromHalfInfLists( pos, middle, half, fail );
else
return MakeInfListFromHalfInfLists( pos + 1 - Length( middle ),
middle, fail, half );
fi;
end );
#######################################################################
##
#M PositivePartFrom( <list>, <pos> )
##
## Returns a new IsInfList with only the positions with indices
## greater than or equal to <pos>.
##
InstallMethod( PositivePartFrom,
[ IsInfList, IsInt ],
function( list, pos )
local middle, positiveStart;
positiveStart := StartPosition( PositivePart( list ) );
if pos >= positiveStart then
return Cut( PositivePart( list ), pos );
else
middle := FinitePartAsList( list, pos, positiveStart - 1 );
return MakeInfListFromHalfInfLists( pos, middle, PositivePart( list ), fail );
fi;
end );
#######################################################################
##
#M NegativePartFrom( <list>, <pos> )
##
## Returns a new IsInfList with only the positions with indices
## smaller than or equal to <pos>.
##
InstallMethod( NegativePartFrom,
[ IsInfList, IsInt ],
function( list, pos )
local middle, negativeStart;
negativeStart := StartPosition( NegativePart( list ) );
if pos <= negativeStart then
return Cut( NegativePart( list ), pos );
else
middle := FinitePartAsList( list, negativeStart + 1, pos );
return MakeInfListFromHalfInfLists( negativeStart + 1, middle, fail,
NegativePart( list ) );
fi;
end );
#######################################################################
##
#M Splice( <positiveList>, <negativeList>, <joinPosition> )
##
## Returns a new IsInfList which is identical to <positiveList> for
## indices greater than <joinPosition> and identical to <negativeList>
## for indices smaller than or equal to <joinPosition>.
##
InstallMethod( Splice,
[ IsInfList, IsInfList, IsInt ],
function( positiveList, negativeList, joinPosition )
local positiveCut, negativeCut, middle;
positiveCut := PositivePartFrom( positiveList, joinPosition + 1 );
negativeCut := NegativePartFrom( negativeList, joinPosition );
middle := Concatenation( MiddlePart( negativeCut ), MiddlePart( positiveCut ) );
return MakeInfListFromHalfInfLists( MiddleStart( negativeCut ),
middle,
PositivePart( positiveCut ),
NegativePart( negativeCut ) );
end );
#######################################################################
##
#F InfConcatenation( <arg> )
##
## <arg> is a list of IsInfLists. The method creates a new IsInfList
## where the middle part is the middle parts of the respective lists
## of <arg>, the positive part is the positive part of the first list
## and the negative part is the negative part of the last list.
##
InstallGlobalFunction( InfConcatenation,
function( arg )
local middle, basePosition, positive, negative;
# TODO: error if arguments are of wrong type
if Length( arg ) = 0 then
return FiniteInfList( 0, [] );
elif Length( arg ) = 1 then
return arg[ 1 ];
fi;
middle := CallFuncList( Concatenation, List( Reversed( arg ), MiddlePart ) );
basePosition := MiddleEnd( arg[ 1 ] ) - Length( middle ) + 1;
positive := PositivePart( arg[ 1 ] );
negative := NegativePart( arg[ Length( arg ) ] );
if negative <> fail then
# Want to have StartPosition( negative ) = basePosition - 1
negative := Shift( negative, StartPosition( negative ) - basePosition + 1 );
fi;
return MakeInfListFromHalfInfLists( basePosition, middle, positive, negative );
end );
#######################################################################
##
#M InfList( <list>, <func> )
##
## <list> is an InfList and <func> is a function which can take
## elements of <list> as argument. The method returns a new list
## where the elements are the elements of <list> with <func> applied
## to them.
##
InstallMethod( InfList,
[ IsInfList, IsFunction ],
function( list, func )
return MakeInfListFromHalfInfLists
( MiddleStart( list ),
List( MiddlePart( list ), func ),
HalfInfList( PositivePart( list ), func ),
HalfInfList( NegativePart( list ), func ) );
end );
#######################################################################
##
#M HalfInfList( <list>, <func> )
##
## <list> is a HalfInfList and <func> is a function which can take
## elements of <list> as argument. The method returns a new list
## where the elements are the elements of <list> with <func> applied
## to them.
##
InstallMethod( HalfInfList,
[ IsHalfInfList, IsFunction ],
function( list, func )
if IsRepeating( list ) then
return MakeHalfInfList( StartPosition( list ), Direction( list ),
[ "repeat", List( RepeatingList( list ), func ) ],
false, false );
else
return MakeHalfInfList( StartPosition( list ), Direction( list ),
[ "pos", i -> func( list^i ) ],
false, false );
fi;
end );
#######################################################################
##
#V IntegersList
##
## An IsInfList with the integer i at position i.
##
BindGlobal( "IntegersList", FunctionInfList( IdFunc ) );
