/**************************************************************************** ** ** This file is part of GAP, a system for computational discrete algebra. ** ** 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 functions for generic lists.
*/
/**************************************************************************** ** *F AddList(<list>,<obj>) . . . . . . . . add an object to the end of a list ** ** 'AddList' adds the object <obj> to the end of the list <list>, i.e., ** it is equivalent to the assignment '<list>[ Length(<list>)+1 ] := <obj>'. ** The list is automatically extended to make room for the new element. ** 'AddList' returns nothing, it is called only for its side effect.
*/ staticvoid AddList3(Obj list, Obj obj, Int pos)
{ Int len; Int i;
len = LEN_LIST(list); if (pos == (Int)-1)
pos = len + 1; for (i = len + 1; i > pos; i--)
ASS_LIST(list, i, ELM_LIST(list, i - 1));
ASS_LIST(list, pos, obj);
}
void AddPlist3(Obj list, Obj obj, Int pos)
{
UInt len;
if (!IS_PLIST_MUTABLE(list)) {
ErrorMayQuit("List Assignment: must be a mutable list", 0, 0);
} // in order to be optimistic when building list call assignment
len = LEN_PLIST(list); if (pos == (Int)-1)
pos = len + 1; if (len == 0) {
AssPlistEmpty(list, pos, obj); return;
} if (pos <= len) {
GROW_PLIST(list, len + 1);
SET_LEN_PLIST(list, len + 1);
Obj * ptr = ADDR_OBJ(list) + pos;
SyMemmove(ptr + 1, ptr, sizeof(Obj) * (len - pos + 1));
}
ASS_LIST(list, pos, obj);
}
/**************************************************************************** ** *F RemList(<list>) . . . . . . . . remove an object from the end of a list ** ** 'RemList' removes the last object <obj> from the end of the list <list>, ** and returns it.
*/ static Obj RemList(Obj list)
{ Int pos;
Obj result;
pos = LEN_LIST( list ) ; if ( pos == 0 ) {
ErrorMayQuit("Remove: must not be empty", 0, 0);
}
result = ELM_LIST(list, pos);
UNB_LIST(list, pos); return result;
}
static Obj RemPlist(Obj list)
{ Int pos;
Obj removed;
if ( ! IS_PLIST_MUTABLE(list) ) {
ErrorMayQuit("Remove: must be a mutable list", 0, 0);
}
pos = LEN_PLIST( list ); if ( pos == 0 ) {
ErrorMayQuit("Remove: must not be empty", 0, 0);
}
removed = ELM_PLIST(list, pos);
SET_ELM_PLIST(list, pos, 0);
pos--; while ( 1 <= pos && ELM_PLIST( list, pos ) == 0 ) { pos--; }
SET_LEN_PLIST(list, pos); if ( pos == 0 ) {
RetypeBag(list, T_PLIST_EMPTY);
} if (4*pos*sizeof(Obj) < 3*SIZE_BAG(list))
SHRINK_PLIST(list, pos); return removed;
}
/**************************************************************************** ** *F FuncAPPEND_LIST_INTR(<list1>,<list2>) . . . . . append elements to a list ** ** 'FuncAPPEND_LIST_INTR' implements the function 'Append'. ** ** 'Append(<list1>,<list2>)' ** ** 'Append' adds (see "Add") the elements of the list <list2> to the end ** of the list <list1>. It is allowed that <list2> contains empty positions, ** in which case the corresponding positions will be left empty in <list1>. ** 'Append' returns nothing, it is called only for its side effect.
*/ static Obj FuncAPPEND_LIST_INTR(Obj self, Obj list1, Obj list2)
{
UInt len1; // length of the first list
UInt len2; // length of the second list
Obj elm; // one element of the second list Int i; // loop variable
// handle the case of strings now if (IS_STRING_REP(list1) && IS_STRING(list2)) { if (!IS_STRING_REP(list2)) {
list2 = ImmutableString(list2);
}
AppendString(list1, list2); return 0;
}
// check the type of the first argument if ( TNUM_OBJ( list1 ) != T_PLIST ) { if ( ! IS_PLIST( list1 ) ) {
PLAIN_LIST( list1 );
}
RetypeBag( list1, T_PLIST );
}
len1 = LEN_PLIST( list1 );
// check the type of the second argument if ( ! IS_PLIST( list2 ) ) {
len2 = LEN_LIST( list2 );
} else {
len2 = LEN_PLIST( list2 );
}
// if the list has no room at the end, enlarge it if ( 0 < len2 ) {
GROW_PLIST( list1, len1+len2 );
SET_LEN_PLIST( list1, len1+len2 );
}
// add the elements if ( IS_PLIST(list2) ) { // note that the two memory regions can never overlap, even // if list1 and list2 are identical
memcpy(ADDR_OBJ(list1) + 1 + len1, CONST_ADDR_OBJ(list2) + 1,
len2 * sizeof(Obj));
CHANGED_BAG( list1 );
} else { for ( i = 1; i <= len2; i++ ) {
elm = ELMV0_LIST( list2, i );
SET_ELM_PLIST( list1, i+len1, elm );
CHANGED_BAG( list1 );
}
}
/**************************************************************************** ** *F POSITION_SORTED_LIST(<list>,<obj>) . . . . find an object in a sorted list *F PositionSortedDensePlist(<list>,<obj>) . find an object in a sorted list ** ** 'POSITION_SORTED_LIST' returns the position of the object <obj>, which may ** be an object of any type, with respect to the sorted list <list>. ** ** 'POSITION_SORTED_LIST' returns <pos> such that '<list>[<pos>-1] < <obj>' ** and '<obj> <= <list>[<pos>]'. That means if <obj> appears once in <list> ** its position is returned. If <obj> appears several times in <list>, the ** position of the first occurrence is returned. If <obj> is not an element ** of <list>, the index where <obj> must be inserted to keep the list sorted ** is returned.
*/ static UInt POSITION_SORTED_LIST(Obj list, Obj obj)
{
UInt l; // low
UInt h; // high
UInt m; // mid
Obj v; // one element of the list
// perform the binary search to find the position
l = 0; h = LEN_LIST( list ) + 1; while ( l+1 < h ) { // list[l] < obj && obj <= list[h]
m = (l + h) / 2; // l < m < h
v = ELMV_LIST( list, m ); if ( LT( v, obj ) ) { l = m; } else { h = m; }
}
// return the position return h;
}
UInt PositionSortedDensePlist (
Obj list,
Obj obj )
{
UInt l; // low
UInt h; // high
UInt m; // mid
Obj v; // one element of the list
// perform the binary search to find the position
l = 0; h = LEN_PLIST( list ) + 1; while ( l+1 < h ) { // list[l] < obj && obj <= list[h]
m = (l + h) / 2; // l < m < h
v = ELM_PLIST( list, m ); if ( LT( v, obj ) ) { l = m; } else { h = m; }
}
UInt h; if ( IS_DENSE_PLIST(list) ) {
h = PositionSortedDensePlist( list, obj );
} else {
h = POSITION_SORTED_LIST( list, obj );
}
return INTOBJ_INT( h );
}
/**************************************************************************** ** *F POSITION_SORTED_LISTComp(<list>,<obj>,<func>) . . find an object in a list *F PositionSortedDensePlistComp(<list>,<obj>,<func>)find an object in a list ** ** 'POSITION_SORTED_LISTComp' returns the position of the object <obj>, which ** may be an object of any type, with respect to the list <list>, which is ** sorted with respect to the comparison function <func>. ** ** 'POSITION_SORTED_LISTComp' returns <pos> such that '<list>[<pos>-1] < <obj>' ** and '<obj> <= <list>[<pos>]'. That means if <obj> appears once in <list> ** its position is returned. If <obj> appears several times in <list>, the ** position of the first occurrence is returned. If <obj> is not an element ** of <list>, the index where <obj> must be inserted to keep the list sorted ** is returned.
*/ static UInt POSITION_SORTED_LISTComp(Obj list, Obj obj, Obj func)
{
UInt l; // low
UInt h; // high
UInt m; // mid
Obj v; // one element of the list
// perform the binary search to find the position
l = 0; h = LEN_LIST( list ) + 1; while ( l+1 < h ) { // list[l] < obj && obj <= list[h]
m = (l + h) / 2; // l < m < h
v = ELMV_LIST( list, m ); if ( CALL_2ARGS( func, v, obj ) == True ) { l = m; } else { h = m; }
}
// return the position return h;
}
static UInt PositionSortedDensePlistComp(Obj list, Obj obj, Obj func)
{
UInt l; // low
UInt h; // high
UInt m; // mid
Obj v; // one element of the list
// perform the binary search to find the position
l = 0; h = LEN_PLIST( list ) + 1; while ( l+1 < h ) { // list[l] < obj && obj <= list[h]
m = (l + h) / 2; // l < m < h
v = ELM_PLIST( list, m ); if ( CALL_2ARGS( func, v, obj ) == True ) { l = m; } else { h = m; }
}
UInt h; if ( IS_DENSE_PLIST(list) ) {
h = PositionSortedDensePlistComp( list, obj, func );
} else {
h = POSITION_SORTED_LISTComp( list, obj, func );
}
return INTOBJ_INT( h );
}
/**************************************************************************** ** ** Low-level implementations of PositionSortedBy for dense Plists and lists.
*/ static Obj FuncPOSITION_SORTED_BY(Obj self, Obj list, Obj val, Obj func)
{
RequirePlainList(SELF_NAME, list);
RequireFunction(SELF_NAME, func);
// perform the binary search to find the position
UInt l = 0;
UInt h = LEN_PLIST(list) + 1; while (l + 1 < h) { // list[l] < val && val <= list[h]
UInt m = (l + h) / 2; // l < m < h
Obj v = CALL_1ARGS(func, ELM_PLIST(list, m)); if (LT(v, val)) {
l = m;
} else {
h = m;
}
}
return INTOBJ_INT(h);
}
/**************************************************************************** ** *F SORT_LIST( <list> ) . . . . . . . . . . . . . . . . . . . . sort a list *F SortDensePlist( <list> ) . . . . . . . . . . . . . . . . . . sort a list ** ** 'SORT_LIST' sorts the list <list> in increasing order.
*/
// See sortbase.h for a description of these macros.
// We put these first, as they are the same for the next 4 functions so // we do not have to repeat them #define SORT_CREATE_TEMP_BUFFER(len) NEW_PLIST( T_PLIST, len + 1000); #define SORT_ASS_BUF_TO_LOCAL(buffer, t, i) t = ELM_PLIST(buffer, i); #define SORT_ASS_LOCAL_TO_BUF(buffer, i, j) \
SET_ELM_PLIST(buffer, i, j); \
CHANGED_BAG(buffer);
#define SORT_FUNC_NAME SORT_LIST #define SORT_FUNC_ARGS Obj list #define SORT_ARGS list #define SORT_CREATE_LOCAL(name) Obj name ; #define SORT_LEN_LIST() LEN_LIST(list) #define SORT_ASS_LIST_TO_LOCAL(t, i) t = ELMV_LIST(list, i) #define SORT_ASS_LOCAL_TO_LIST(i, j) ASS_LIST(list, i, j) #define SORT_COMP(v, w) LT(v, w) #define SORT_FILTER_CHECKS() \ if(IS_PLIST(list)) \
RESET_FILT_LIST(list, FN_IS_NSORT);
#include"sortbase.h"
#define SORT_FUNC_NAME SortDensePlist #define SORT_FUNC_ARGS Obj list #define SORT_ARGS list #define SORT_CREATE_LOCAL(name) Obj name ; #define SORT_LEN_LIST() LEN_PLIST(list) #define SORT_ASS_LIST_TO_LOCAL(t, i) t = ELM_PLIST(list, i) #define SORT_ASS_LOCAL_TO_LIST(i, j) \
SET_ELM_PLIST(list, i, j); \
CHANGED_BAG(list); #define SORT_COMP(v, w) LT(v, w) #define SORT_FILTER_CHECKS() \
RESET_FILT_LIST(list, FN_IS_NSORT);
#include"sortbase.h"
// This is a variant of SortDensePlist, which sorts plists by // Obj pointer. It works on non-dense plists, and can be // used to efficiently sort lists of small integers.
/**************************************************************************** ** *F SORT_PARA_LIST( <list> ) . . . . . . . . . . . sort a lists with shadow *F SortParaDensePlistPara( <list> ) . . . . . . . sort a lists with shadow *F SORT_PARA_LISTComp(<list>,<func>) . . . . . . . sort a lists with shadow *F SortParaDensePlistComp(<list>,<func>) . . . . . sort a lists with shadow ** ** The following suite of functions mirrors the sort functions above. They ** sort the first list given and perform the same operations on the second ** list, the shadow list. All functions assume that shadow list has (at ** least) the length of the first list. ** ** The code here is a duplication of the code above with the operations on ** the second list added in.
*/
// Through this section, code of the form (void)(varname); stops // various compilers warning about unused variables. // These 3 macros are the same for all 4 of the following functions. #undef SORT_CREATE_TEMP_BUFFER #undef SORT_ASS_BUF_TO_LOCAL #undef SORT_ASS_LOCAL_TO_BUF
/**************************************************************************** ** *F RemoveDupsDensePlist(<list>) . . . . remove duplicates from a plain list ** ** 'RemoveDupsDensePlist' removes duplicate elements from the dense ** plain list <list>. <list> must be sorted. 'RemoveDupsDensePlist' ** returns 0 if <list> contains mutable elements, 1 if not and 2 if ** the list contains immutable elements all lying in the same family.
*/
UInt RemoveDupsDensePlist (
Obj list )
{
UInt mutable; // the elements are mutable
UInt homog; // the elements all lie in the same family Int len; // length of the list
Obj v, w; // two elements of the list
UInt l, i; // loop variables
Obj fam;
// get the length, nothing to be done for empty lists
len = LEN_PLIST( list ); if ( len == 0 ) { return 0; }
// select the first element as the first representative
l = 1;
v = ELM_PLIST( list, l ); mutable = IS_MUTABLE_OBJ(v);
homog = 1;
fam = FAMILY_OBJ(v);
// loop over the other elements, compare them with the current rep. for ( i = 2; i <= len; i++ ) {
w = ELM_PLIST( list, i ); mutable = (mutable || IS_MUTABLE_OBJ(w)); if ( ! EQ( v, w ) ) { if ( l+1 != i ) {
SET_ELM_PLIST( list, l+1, w );
SET_ELM_PLIST( list, i, (Obj)0 );
}
l += 1;
v = w;
homog = (!mutable && homog && fam == FAMILY_OBJ(w));
}
}
// the list may be shorter now
SET_LEN_PLIST( list, l );
SHRINK_PLIST( list, l );
// Set appropriate filters if (!mutable)
{ if (!homog)
SET_FILT_LIST(list, FN_IS_NHOMOG); else
SET_FILT_LIST(list, FN_IS_HOMOG);
SET_FILT_LIST(list, FN_IS_SSORT);
}
// return whether the list contains mutable elements if (mutable) return 0; if (!homog) return 1; else return 2;
}
/**************************************************************************** ** *F FuncOnPoints( <self>, <point>, <elm> ) . . . . . . . operation on points ** ** 'FuncOnPoints' implements the internal function 'OnPoints'. ** ** 'OnPoints( <point>, <elm> )' ** ** specifies the canonical default operation. Passing this function is ** equivalent to specifying no operation. This function exists because ** there are places where the operation in not an option.
*/ static Obj FuncOnPoints(Obj self, Obj point, Obj elm)
{ return POW( point, elm );
}
/**************************************************************************** ** *F FuncOnPairs( <self>, <pair>, <elm> ) . . . operation on pairs of points ** ** 'FuncOnPairs' implements the internal function 'OnPairs'. ** ** 'OnPairs( <pair>, <elm> )' ** ** specifies the componentwise operation of group elements on pairs of ** points, which are represented by lists of length 2.
*/ static Obj FuncOnPairs(Obj self, Obj pair, Obj elm)
{
Obj img; // image, result
Obj tmp; // temporary
RequireSmallList(SELF_NAME, pair); if (LEN_LIST(pair) != 2) {
ErrorMayQuit("OnPairs: must have length 2, not length %d",
LEN_LIST(pair), 0);
}
// create a new bag for the result
img = NEW_PLIST_WITH_MUTABILITY( IS_MUTABLE_OBJ(pair), T_PLIST, 2 );
SET_LEN_PLIST( img, 2 );
// and enter the images of the points into the result bag
tmp = POW( ELMV_LIST( pair, 1 ), elm );
SET_ELM_PLIST( img, 1, tmp );
CHANGED_BAG( img );
tmp = POW( ELMV_LIST( pair, 2 ), elm );
SET_ELM_PLIST( img, 2, tmp );
CHANGED_BAG( img );
return img;
}
/**************************************************************************** ** *F FuncOnTuples( <self>, <tuple>, <elm> ) . . operation on tuples of points ** ** 'FuncOnTuples' implements the internal function 'OnTuples'. ** ** 'OnTuples( <tuple>, <elm> )' ** ** specifies the componentwise operation of group elements on tuples of ** points, which are represented by lists. 'OnPairs' is the special case of ** 'OnTuples' for tuples with two elements.
*/ static Obj FuncOnTuples(Obj self, Obj tuple, Obj elm)
{
Obj img; // image, result
Obj tmp; // temporary
UInt i; // loop variable
RequireSmallList(SELF_NAME, tuple);
// special case for the empty list if (LEN_LIST(tuple) == 0) { if (IS_MUTABLE_OBJ(tuple)) {
img = NewEmptyPlist(); return img;
} else { return tuple;
}
} // special case for permutations if (IS_PERM(elm)) { return OnTuplesPerm( tuple, elm );
}
// special case for transformations if (IS_TRANS(elm)) { return OnTuplesTrans( tuple, elm );
}
// special case for partial perms if (IS_PPERM(elm)) { return OnTuplesPPerm( tuple, elm );
}
// create a new bag for the result
img = NEW_PLIST_WITH_MUTABILITY( IS_MUTABLE_OBJ(tuple), T_PLIST, LEN_LIST(tuple) );
SET_LEN_PLIST( img, LEN_LIST(tuple) );
// and enter the images of the points into the result bag for ( i = LEN_LIST(tuple); 1 <= i; i-- ) {
tmp = POW( ELMV_LIST( tuple, i ), elm );
SET_ELM_PLIST( img, i, tmp );
CHANGED_BAG( img );
}
return img;
}
/**************************************************************************** ** *F FuncOnSets( <self>, <tuple>, <elm> ) . . . . operation on sets of points ** ** 'FuncOnSets' implements the internal function 'OnSets'. ** ** 'OnSets( <tuple>, <elm> )' ** ** specifies the operation of group elements on sets of points, which are ** represented by sorted lists of points without duplicates (see "Sets").
*/
static Obj FuncOnSets(Obj self, Obj set, Obj elm)
{
Obj img; // handle of the image, result
UInt status; // the elements are mutable
if (!HAS_FILT_LIST(set, FN_IS_SSORT) && !IS_SSORT_LIST(set)) {
RequireArgument(SELF_NAME, set, "must be a set");
}
// special case for the empty list if (LEN_LIST(set) == 0) { if (IS_MUTABLE_OBJ(set)) {
img = NewEmptyPlist(); return img;
} else { return set;
}
}
// special case for permutations if (IS_PERM(elm)) { return OnSetsPerm( set, elm );
}
// special case for transformations if (IS_TRANS(elm)){ return OnSetsTrans( set, elm);
}
// special case for partial perms if (IS_PPERM(elm)){ return OnSetsPPerm( set, elm);
}
// compute the list of images
img = FuncOnTuples( self, set, elm );
// sort the images list (which is a dense plain list)
SortDensePlist( img );
// remove duplicates, check for mutable elements
status = RemoveDupsDensePlist( img );
// if possible, turn this into a set switch (status)
{ case 0: break;
case 1:
RetypeBagSM( img, T_PLIST_DENSE_NHOM_SSORT );
case 2:
RetypeBagSM( img, T_PLIST_HOM_SSORT );
}
// return set return img;
}
/**************************************************************************** ** *F FuncOnRight( <self>, <point>, <elm> ) . operation by mult. from the right ** ** 'FuncOnRight' implements the internal function 'OnRight'. ** ** 'OnRight( <point>, <elm> )' ** ** specifies that group elements operate by multiplication from the right.
*/ static Obj FuncOnRight(Obj self, Obj point, Obj elm)
{ return PROD( point, elm );
}
/**************************************************************************** ** *F FuncOnLeftInverse( <self>, <point>, <elm> ) . . op by mult. from the left ** ** 'FuncOnLeftInverse' implements the internal function 'OnLeftInverse'. ** ** 'OnLeftInverse( <point>, <elm> )' ** ** specifies that group elements operate by multiplication from the left ** with the inverse.
*/ static Obj FuncOnLeftInverse(Obj self, Obj point, Obj elm)
{ return LQUO(elm, point);
}
/**************************************************************************** ** *F FuncSTRONGLY_CONNECTED_COMPONENTS_DIGRAPH ** ** `digraph' should be a list whose entries and the lists of out-neighbours ** of the vertices. So [[2,3],[1],[2]] represents the graph whose edges are ** 1->2, 1->3, 2->1 and 3->2. ** ** returns a newly constructed list whose elements are lists representing the ** strongly connected components of the directed graph. Neither the components, ** nor their elements are in any particular order. ** ** The algorithm is that of Tarjan, based on the implementation in Sedgwick, ** with a bug fixed, and made non-recursive to avoid problems with stack limits ** under (for instance) Linux. This version is a bit slower than the recursive ** version, but much faster than any of the GAP implementations. ** ** A possible change is to allocate the internal arrays rather smaller, and ** grow them if needed. This might allow some computations to complete that would ** otherwise run out of memory, but would slow things down a bit.
*/
/**************************************************************************** ** *F FuncCOPY_LIST_ENTRIES( <self>, <args> ) . . mass move of list entries ** ** Argument names in the manual: fromlst, fromind, fromstep, tolst, toind, tostep, n
*/
static Obj FuncCOPY_LIST_ENTRIES(Obj self, Obj args)
{
Obj srclist; Int srcstart; Int srcinc;
Obj dstlist; Int dststart; Int dstinc;
UInt number;
UInt srcmax;
UInt dstmax; const Obj *sptr;
Obj *dptr;
UInt ct;
GAP_ASSERT(IS_PLIST(args)); if (LEN_PLIST(args) != 7) {
ErrorMayQuitNrArgs(7, LEN_PLIST(args));
}
srclist = ELM_PLIST(args, 1);
GAP_ASSERT(srclist != 0); if (!IS_PLIST(srclist))
RequireArgumentEx(SELF_NAME, srclist, "", "must be a plain list");
// ADD_LIST can take 2 or 3 arguments; since NewOperation ignores the // handler for variadic operations, use DoOperation0Args as a placeholder.
{ "ADD_LIST", -1, "list, obj[, pos]", &AddListOper,
DoOperation0Args, "src/listfunc.c:ADD_LIST" },
// ADD_LIST needs special consideration because we want distinct kernel // handlers for 2 and 3 arguments
InitHandlerFunc( FuncADD_LIST, "src/listfunc.c:FuncADD_LIST" );
InitHandlerFunc( FuncADD_LIST3, "src/listfunc.c:FuncADD_LIST3" );
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
