/**************************************************************************** ** *VIdentityTrans.................identitytransformation ** **'IdentityTrans'isanidentitytransformation.
*/ // mp this will become a ReadOnly object? static Obj IdentityTrans;
// The only transformation created within this file that is of type // T_TRANS4 and that does not have (internal) degree 65537 or greater // is ID_TRANS4.
// Returns a transformation with list of images <list>, this does not check // that <list> is really a list or that its entries define a transformation.
deg = 0; for (i = LEN_LIST(src); 1 <= i; i--) {
s = GetPositiveListEntry("TransformationListListNC", src, i);
r = GetPositiveListEntry("TransformationListListNC", ran, i);
if (s != r) { if (s > deg) {
deg = s;
} if (r > deg) {
deg = r;
}
}
}
if (deg <= 65536) {
f = NEW_TRANS2(deg);
ptf2 = ADDR_TRANS2(f); for (i = 0; i < deg; i++) {
ptf2[i] = i;
} for (i = LEN_LIST(src); 1 <= i; i--) {
s = INT_INTOBJ(ELM_LIST(src, i));
r = INT_INTOBJ(ELM_LIST(ran, i)); // deg may be smaller than s if s = r if (s != r) {
ptf2[s - 1] = r - 1;
}
}
} else {
f = NEW_TRANS4(deg);
ptf4 = ADDR_TRANS4(f); for (i = 0; i < deg; i++) {
ptf4[i] = i;
} for (i = LEN_LIST(src); 1 <= i; i--) {
s = INT_INTOBJ(ELM_LIST(src, i));
r = INT_INTOBJ(ELM_LIST(ran, i)); if (s != r) {
ptf4[s - 1] = r - 1;
}
}
} return f;
}
// Returns a transformation with image <img> and flat kernel <ker> under the // (unchecked) assumption that the arguments are valid and that there is such // a transformation, i.e. that the maximum value in <ker> equals the length // of <img>.
// Returns an idempotent transformation with image <img> and flat kernel <ker> // under the (unchecked) assumption that the arguments are valid and that // there // is such a transformation, i.e. that the maximum value in <ker> equals the // length of <img>. // // Note that this does not return the same transformation as TRANS_IMG_KER_NC // with the same arguments.
m = INT_INTOBJ(n);
deg = DEG_TRANS(f); if (m >= deg) {
rank = RANK_TRANS(f) - deg + m;
} elseif (TNUM_OBJ(f) == T_TRANS2) {
pttmp = ResizeInitTmpTrans(deg);
ptf2 = CONST_ADDR_TRANS2(f);
rank = 0; for (i = 0; i < m; i++) { if (pttmp[ptf2[i]] == 0) {
rank++;
pttmp[ptf2[i]] = 1;
}
}
} else {
pttmp = ResizeInitTmpTrans(deg);
ptf4 = CONST_ADDR_TRANS4(f);
rank = 0; for (i = 0; i < m; i++) { if (pttmp[ptf4[i]] == 0) {
rank++;
pttmp[ptf4[i]] = 1;
}
}
} return INTOBJ_INT(rank);
}
// Returns the rank of the transformation <f> on the <list>, i.e. the number // of // distinct values in [(list[1])f .. (list[n])f], where <list> consists of // positive ints.
// copy the kernel set up to minimum of m, deg if (m < deg) { for (i = 0; i < m; i++) {
*ptnew++ = *ptker++;
}
} else { // m > deg for (i = 0; i < deg; i++) {
*ptnew++ = *ptker++;
} // we must now add another (m - deg) points, // starting with the class number (rank + 1) for (i = 1; i <= m - deg; i++) {
*ptnew++ = INTOBJ_INT(i + RANK_TRANS(f));
}
} return newObj;
}
// Returns the kernel of a transformation <f> as a partition of [1 .. n].
// copy the image set for (i = 0; i < len; i++) {
*ptnew++ = *ptim++;
} // add newObj points for (i = deg + 1; i <= m; i++) {
*ptnew++ = INTOBJ_INT(i);
}
} return newObj;
}
// Returns the image list [(1)f .. (n)f] of the transformation f.
if (deg == 0) { return NewPlistFromArgs(INTOBJ_INT(1), INTOBJ_INT(1));
}
// seen[pt] = 0 -> haven't seen pt before // // seen[pt] = d where (1 <= d <= deg) // -> pt belongs to a component we've seen before and (pt)f ^ (d - 1) // belongs to a cycle // // seen[pt] = deg + 1 -> pt belongs to a component not seen before
seen = ResizeInitTmpTrans(deg);
pow = 2;
ord = INTOBJ_INT(1);
if (TNUM_OBJ(f) == T_TRANS2) {
ptf2 = CONST_ADDR_TRANS2(f); for (i = 0; i < deg; i++) { if (seen[i] == 0) {
len = 0; // repeatedly apply f to pt until we see something we've seen // already for (pt = i; seen[pt] == 0; pt = ptf2[pt], len++) {
seen[pt] = deg + 1;
}
last_pt = pt; if (seen[pt] <= deg) { // pt belongs to a component we've seen before
dist = seen[pt] + len; // the distance of i from the cycle in its component + 1
} else { // pt belongs to a component we've not seen before
for (cyc = 0; seen[pt] == deg + 1; pt = ptf2[pt], cyc++) { // go around the cycle again and set the value of // seen, // and get the length of the cycle
seen[pt] = 1;
}
ord = LcmInt(ord, INTOBJ_INT(cyc));
// the distance of i from the cycle in its component + 1
dist = len - cyc + 1;
// update bag pointers, in case a garbage collection happened
ptf2 = CONST_ADDR_TRANS2(f);
seen = AddrTmpTrans();
} if (dist > pow) {
pow = dist;
} // record the distances of the points from the cycle for (pt = i; pt != last_pt; pt = ptf2[pt]) {
seen[pt] = dist--;
}
}
}
} else {
ptf4 = CONST_ADDR_TRANS4(f); for (i = 0; i < deg; i++) { if (seen[i] == 0) {
len = 0; // repeatedly apply f to pt until we see something we've seen // already for (pt = i; seen[pt] == 0; pt = ptf4[pt], len++) {
seen[pt] = deg + 1;
}
last_pt = pt; if (seen[pt] <= deg) { // pt belongs to a component we've seen before
dist = seen[pt] + len; // the distance of i from the cycle in its component + 1
} else { // pt belongs to a component we've not seen before
for (cyc = 0; seen[pt] == deg + 1; pt = ptf4[pt], cyc++) { // go around the cycle again and set the value of // seen, // and get the length of the cycle
seen[pt] = 1;
}
ord = LcmInt(ord, INTOBJ_INT(cyc));
// the distance of i from the cycle in its component + 1
dist = len - cyc + 1;
// update bag pointers, in case a garbage collection happened
ptf4 = CONST_ADDR_TRANS4(f);
seen = AddrTmpTrans();
} if (dist > pow) {
pow = dist;
} // record the distances of the points from the cycle for (pt = i; pt != last_pt; pt = ptf4[pt]) {
seen[pt] = dist--;
}
}
}
}
RequireSmallList(SELF_NAME, list); if (!IS_TRANS(obj) && !IS_LIST(obj)) {
RequireArgument(SELF_NAME, obj, "must be a transformation or a list");
} // init buffer
n = (IS_TRANS(obj) ? DEG_TRANS(obj) : LEN_LIST(obj));
pttmp = ResizeInitTmpTrans(n);
if (TNUM_OBJ(obj) == T_TRANS2) {
ptt2 = CONST_ADDR_TRANS2(obj); for (i = LEN_LIST(list); i >= 1; i--) {
j = GetPositiveListEntry("IsInjectiveListTrans", list, i); if (j <= n) { if (pttmp[ptt2[j - 1]] != 0) { returnFalse;
}
pttmp[ptt2[j - 1]] = 1;
}
}
} elseif (TNUM_OBJ(obj) == T_TRANS4) {
ptt4 = CONST_ADDR_TRANS4(obj); for (i = LEN_LIST(list); i >= 1; i--) {
j = GetPositiveListEntry("IsInjectiveListTrans", list, i); if (j <= n) { if (pttmp[ptt4[j - 1]] != 0) { returnFalse;
}
pttmp[ptt4[j - 1]] = 1;
}
}
} else { // obj is a list, first we check it describes a transformation for (i = 1; i <= n; i++) {
j = GetPositiveListEntry("IsInjectiveListTrans", obj, i); if (j > n) {
ErrorQuit( "<obj> must be a list of positive small integers " "in the range [1 .. %d]",
(Int)n, 0);
}
} for (i = LEN_LIST(list); i >= 1; i--) {
j = GetPositiveListEntry("IsInjectiveListTrans", list, i); if (j <= n) { if (pttmp[INT_INTOBJ(ELM_LIST(obj, j)) - 1] != 0) { returnFalse;
}
pttmp[INT_INTOBJ(ELM_LIST(obj, j)) - 1] = 1;
}
}
} returnTrue;
}
// Returns a transformation g such that transformation f * g * f = f and // g * f * g = g, where f is a transformation.
if (TNUM_OBJ(f) == T_TRANS2) {
deg = DEG_TRANS2(f);
g = NEW_TRANS2(deg);
ptf2 = CONST_ADDR_TRANS2(f);
ptg2 = ADDR_TRANS2(g); for (i = 0; i < deg; i++) {
ptg2[i] = 0;
} for (i = deg - 1; i > 0; i--) {
ptg2[ptf2[i]] = i;
} // to ensure that 1 is in the image and so rank of g equals that of f
ptg2[ptf2[0]] = 0;
} else {
deg = DEG_TRANS4(f);
g = NEW_TRANS4(deg);
ptf4 = CONST_ADDR_TRANS4(f);
ptg4 = ADDR_TRANS4(g); for (i = 0; i < deg; i++) {
ptg4[i] = 0;
} for (i = deg - 1; i > 0; i--) {
ptg4[ptf4[i]] = i;
} // to ensure that 1 is in the image and so rank of g equals that of f
ptg4[ptf4[0]] = 0;
} return g;
}
// Returns the flat kernel of a transformation obtained by multiplying <f> by // any transformation with kernel equal to <ker>. If the argument <ker> = // [0], then the flat kernel of <f> on [1 .. <n>] is returned. Otherwise, the // argument <n> is redundant.
// FIXME this should just always return a flat kernel of length <n>, the // special case should be removed, and [0] should be replaced by [1 .. n] in // the Semigroup package.
len = LEN_LIST(ker); if (len == 1 && ELM_LIST(ker, 1) == INTOBJ_INT(0)) { return FuncFLAT_KERNEL_TRANS_INT(self, f, n);
}
rank = 1;
deg = INT_INTOBJ(FuncDegreeOfTransformation(self, f)); if (len < deg) {
ErrorQuit("ON_KERNEL_ANTI_ACTION: the length of <ker> " "must be at least %d",
(Int)deg, 0);
}
if (len == 0) {
out = NewImmutableEmptyPlist(); return out;
}
out = NEW_PLIST_IMM(T_PLIST_CYC, len);
SET_LEN_PLIST(out, len);
pttmp = ResizeInitTmpTrans(len);
if (TNUM_OBJ(f) == T_TRANS2) {
ptf2 = CONST_ADDR_TRANS2(f); for (i = 0; i < deg; i++) { // <f> then <g> with ker(<g>) = <ker>
j = INT_INTOBJ(ELM_LIST(ker, ptf2[i] + 1)) - 1; // f first! if (pttmp[j] == 0) {
pttmp[j] = rank++;
}
SET_ELM_PLIST(out, i + 1, INTOBJ_INT(pttmp[j]));
}
} else {
ptf4 = CONST_ADDR_TRANS4(f); for (i = 0; i < deg; i++) { // <f> then <g> with ker(<g>) = <ker>
j = INT_INTOBJ(ELM_LIST(ker, ptf4[i] + 1)) - 1; // f first! if (pttmp[j] == 0) {
pttmp[j] = rank++;
}
SET_ELM_PLIST(out, i + 1, INTOBJ_INT(pttmp[j]));
}
}
i++; for (; i <= len; i++) { // just <ker>
j = INT_INTOBJ(ELM_LIST(ker, i)) - 1; if (pttmp[j] == 0) {
pttmp[j] = rank++;
}
SET_ELM_PLIST(out, i, INTOBJ_INT(pttmp[j]));
} return out;
}
// Returns a transformation <f> such that (i)f = (i)p for all i <= n where <p> // is a permutation <p> and <n> is a positive integer. Note that the returned // transformation is not necessarily a permutation (mathematically), when n is // less than the largest moved point of p.
for (i = 0; i < max; i++) {
ptp[i] = i;
} for (i = 0; i < min; i++) {
ptp[ptf2[i]] = ptg2[i];
} for (; i < deg; i++) {
ptp[i] = ptg2[i];
} for (; i < def; i++) {
ptp[ptf2[i]] = i;
}
} elseif (TNUM_OBJ(f) == T_TRANS2 && TNUM_OBJ(g) == T_TRANS4) {
ptf2 = CONST_ADDR_TRANS2(f);
ptg4 = CONST_ADDR_TRANS4(g);
for (i = 0; i < max; i++) {
ptp[i] = i;
} for (i = 0; i < min; i++) {
ptp[ptf2[i]] = ptg4[i];
} for (; i < deg; i++) {
ptp[i] = ptg4[i];
} for (; i < def; i++) { // The only transformation created within this file that is of // type // T_TRANS4 and that does not have (internal) degree 65537 or // greater // is ID_TRANS4.
ptp[ptf2[i]] = i;
}
} elseif (TNUM_OBJ(f) == T_TRANS4 && TNUM_OBJ(g) == T_TRANS2) {
ptf4 = CONST_ADDR_TRANS4(f);
ptg2 = CONST_ADDR_TRANS2(g);
for (i = 0; i < max; i++) {
ptp[i] = i;
} for (i = 0; i < min; i++) {
ptp[ptf4[i]] = ptg2[i];
} for (; i < deg; i++) { // The only transformation created within this file that is of // type // T_TRANS4 and that does not have (internal) degree 65537 or // greater // is ID_TRANS4.
ptp[i] = ptg2[i];
} for (; i < def; i++) {
ptp[ptf4[i]] = i;
}
} elseif (TNUM_OBJ(f) == T_TRANS4 && TNUM_OBJ(g) == T_TRANS4) {
ptf4 = CONST_ADDR_TRANS4(f);
ptg4 = CONST_ADDR_TRANS4(g);
for (i = 0; i < max; i++) {
ptp[i] = i;
} for (i = 0; i < min; i++) {
ptp[ptf4[i]] = ptg4[i];
} for (; i < deg; i++) {
ptp[i] = ptg4[i];
} for (; i < def; i++) {
ptp[ptf4[i]] = i;
}
} return perm;
}
// g fixes every point for (i = 0; i < deg; i++) {
ptg2[i] = i;
}
// g acts like f on list * / for (i = 0; i < len; i++) {
k = GetPositiveListEntry("RestrictedTransformation", list, i + 1) - 1; if (k < deg) {
ptg2[k] = ptf2[k];
}
}
} else {
deg = DEG_TRANS4(f);
g = NEW_TRANS4(deg);
// g fixes every point for (i = 0; i < deg; i++) {
ptg4[i] = i;
}
// g acts like f on list for (i = 0; i < len; i++) {
k = GetPositiveListEntry("RestrictedTransformation", list, i + 1) - 1; if (k < deg) {
ptg4[k] = ptf4[k];
}
}
} return g;
}
// AsTransformation for a transformation <f> and a pos int <m> either // restricts // <f> to [1 .. m] or returns <f> depending on whether m is less than or equal // DegreeOfTransformation(f) or not.
// In the first form, this is similar to TRIM_TRANS except that a new // transformation is returned.
static Obj FuncAS_TRANS_TRANS(Obj self, Obj f, Obj m)
{ const UInt2 *ptf2; const UInt4 *ptf4;
UInt2 *ptg2;
UInt4 *ptg4;
UInt i, n, def;
Obj g;
if (TNUM_OBJ(f) == T_TRANS2) {
g = NEW_TRANS2(n);
ptf2 = CONST_ADDR_TRANS2(f);
ptg2 = ADDR_TRANS2(g); for (i = 0; i < n; i++) { if (ptf2[i] > n - 1) { return Fail;
}
ptg2[i] = ptf2[i];
}
} else { if (n > 65536) { // g is T_TRANS4
g = NEW_TRANS4(n);
ptf4 = CONST_ADDR_TRANS4(f);
ptg4 = ADDR_TRANS4(g); for (i = 0; i < n; i++) { if (ptf4[i] > n - 1) { return Fail;
}
ptg4[i] = ptf4[i];
}
} else { // f is T_TRANS4 but n <= 65536 < def and so g will be T_TRANS2
g = NEW_TRANS2(n);
ptf4 = CONST_ADDR_TRANS4(f);
ptg2 = ADDR_TRANS2(g); for (i = 0; i < n; i++) { if (ptf4[i] > n - 1) { return Fail;
}
ptg2[i] = (UInt2)ptf4[i];
}
}
} return g;
}
// Changes the transformation <f> in-place to reduce the degree to <m>. It is // assumed that f is actually a transformation of [1 .. m], i.e. that i ^ f <= // m for all i in [1 .. m].
RequireTransformation(SELF_NAME, f);
max = 0; if (TNUM_OBJ(f) == T_TRANS2) {
def = DEG_TRANS2(f);
ptf2 = CONST_ADDR_TRANS2(f); for (i = DEG_TRANS2(f); 1 <= i; i--) { if (ptf2[i - 1] != i - 1) { break;
}
} for (; 1 <= i; i--) { if (ptf2[i - 1] + 1 > max) {
max = ptf2[i - 1] + 1; if (max == def) { break;
}
}
}
} else {
def = DEG_TRANS4(f);
ptf4 = CONST_ADDR_TRANS4(f); for (i = DEG_TRANS4(f); 1 <= i; i--) { if (ptf4[i - 1] != i - 1) { break;
}
} for (; 1 <= i; i--) { if (ptf4[i - 1] + 1 > max) {
max = ptf4[i - 1] + 1; if (max == def) break;
}
}
} return INTOBJ_INT(max);
}
// Returns the smallest value <i> such that (i)f <> i if it exists, and Fail // if // not. Note that this differs from the GAP level function which returns // infinity if (i)f = i for all i.
if (TNUM_OBJ(f) == T_TRANS2) {
ptf2 = CONST_ADDR_TRANS2(f);
deg = DEG_TRANS2(f); for (i = 1; i <= deg; i++) { if (ptf2[i - 1] != i - 1) { break;
}
}
} else {
ptf4 = CONST_ADDR_TRANS4(f);
deg = DEG_TRANS4(f); for (i = 1; i <= deg; i++) { if (ptf4[i - 1] != i - 1) { break;
}
}
} return INTOBJ_INT(i);
}
// Returns the smallest value in [SmallestMovedPoint(f) .. // LargestMovedPoint(f)] ^ f if it exists and Fail if it does not. Note that // this differs from the GAP level function which returns infinity if (i)f = i // for all i.
// Returns the representatives, in the following sense, of the components of // the transformation <f>. For every i in [1 .. DegreeOfTransformation(<f>)] // there exists a representative j and a positive integer k such that i ^ (<f> // ^ k) = j. The least number of representatives is returned and these // representatives are partitioned according to the component they belong to.
if (deg == 0) {
out = NewEmptyPlist(); return out;
}
img = FuncUNSORTED_IMAGE_SET_TRANS(self, f);
out = NEW_PLIST(T_PLIST, 1);
seen = ResizeInitTmpTrans(deg);
for (i = 1; i <= (UInt)LEN_PLIST(img); i++) {
seen[INT_INTOBJ(ELM_PLIST(img, i)) - 1] = 1;
}
if (TNUM_OBJ(f) == T_TRANS2) {
ptf2 = CONST_ADDR_TRANS2(f);
nr = 1; for (i = 0; i < deg; i++) { if (seen[i] == 0) { // i belongs to dom(f) but not im(f) // repeatedly apply f to pt until we see something we've seen // already
pt = i; do {
seen[pt] = nr + 1;
pt = ptf2[pt];
} while (seen[pt] == 1);
index = seen[pt];
if (index != nr + 1) { // pt belongs to a component we've seen before
ptf2 = CONST_ADDR_TRANS2(f);
pt = i; do {
seen[pt] = index;
pt = ptf2[pt];
} while (seen[pt] == nr + 1);
comp = ELM_PLIST(out, seen[pt] - 1);
AssPlist(comp, LEN_PLIST(comp) + 1, INTOBJ_INT(i + 1));
} else { // pt belongs to a component we've not seen before
comp = NEW_PLIST(T_PLIST_CYC, 1);
SET_LEN_PLIST(comp, 1);
SET_ELM_PLIST(comp, 1, INTOBJ_INT(i + 1));
AssPlist(out, nr++, comp);
}
ptf2 = CONST_ADDR_TRANS2(f);
seen = AddrTmpTrans();
}
} for (i = 0; i < deg; i++) { if (seen[i] == 1) { // i belongs to a cycle for (pt = i; seen[pt] == 1; pt = ptf2[pt]) {
seen[pt] = 0;
}
comp = NEW_PLIST(T_PLIST_CYC, 1);
SET_LEN_PLIST(comp, 1);
SET_ELM_PLIST(comp, 1, INTOBJ_INT(i + 1));
AssPlist(out, nr++, comp);
ptf2 = CONST_ADDR_TRANS2(f);
seen = AddrTmpTrans();
}
}
} else {
ptf4 = CONST_ADDR_TRANS4(f);
nr = 1; for (i = 0; i < deg; i++) { if (seen[i] == 0) { // i belongs to dom(f) but not im(f) // repeatedly apply f to pt until we see something we've seen // already
pt = i; do {
seen[pt] = nr + 1;
pt = ptf4[pt];
} while (seen[pt] == 1);
index = seen[pt];
if (index != nr + 1) { // pt belongs to a component we've seen before
pt = i; do {
seen[pt] = index;
pt = ptf4[pt];
} while (seen[pt] == nr + 1);
comp = ELM_PLIST(out, seen[pt] - 1);
AssPlist(comp, LEN_PLIST(comp) + 1, INTOBJ_INT(i + 1));
} else { // pt belongs to a component we've not seen before
comp = NEW_PLIST(T_PLIST_CYC, 1);
SET_LEN_PLIST(comp, 1);
SET_ELM_PLIST(comp, 1, INTOBJ_INT(i + 1));
AssPlist(out, nr++, comp);
}
ptf4 = CONST_ADDR_TRANS4(f);
seen = AddrTmpTrans();
}
} for (i = 0; i < deg; i++) { if (seen[i] == 1) { // i belongs to a cycle for (pt = i; seen[pt] == 1; pt = ptf4[pt]) {
seen[pt] = 0;
}
comp = NEW_PLIST(T_PLIST_CYC, 1);
SET_LEN_PLIST(comp, 1);
SET_ELM_PLIST(comp, 1, INTOBJ_INT(i + 1));
AssPlist(out, nr++, comp);
ptf4 = CONST_ADDR_TRANS4(f);
seen = AddrTmpTrans();
}
}
} return out;
}
// Returns the number of connected components of the transformation <f>, // thought of as a functional digraph with DegreeOfTransformation(f) vertices.
if (deg == 0) {
out = NewEmptyPlist(); return out;
}
out = NEW_PLIST(T_PLIST, 1);
seen = ResizeInitTmpTrans(deg);
nr = 0;
if (TNUM_OBJ(f) == T_TRANS2) {
ptf2 = CONST_ADDR_TRANS2(f); for (i = 0; i < deg; i++) { if (seen[i] == 0) { // repeatedly apply f to pt until we see something we've seen // already
csize = 0;
pt = i; do {
csize++;
seen[pt] = deg + 1;
pt = ptf2[pt];
} while (seen[pt] == 0);
if (seen[pt] <= deg) { // pt belongs to a component we've seen before
index = seen[pt];
comp = ELM_PLIST(out, index);
pos = LEN_PLIST(comp) + 1;
GROW_PLIST(comp, LEN_PLIST(comp) + csize);
SET_LEN_PLIST(comp, LEN_PLIST(comp) + csize);
} else { // pt belongs to a component we've not seen before
index = ++nr;
pos = 1;
pt = i; while (seen[pt] == deg + 1) {
SET_ELM_PLIST(comp, pos++, INTOBJ_INT(pt + 1));
seen[pt] = index;
pt = ptf2[pt];
}
CHANGED_BAG(out);
}
}
} else {
ptf4 = CONST_ADDR_TRANS4(f); for (i = 0; i < deg; i++) { if (seen[i] == 0) { // repeatedly apply f to pt until we see something we've seen // already
csize = 0;
pt = i; do {
csize++;
seen[pt] = deg + 1;
pt = ptf4[pt];
} while (seen[pt] == 0);
if (seen[pt] <= deg) { // pt belongs to a component we've seen before
index = seen[pt];
comp = ELM_PLIST(out, index);
pos = LEN_PLIST(comp) + 1;
GROW_PLIST(comp, LEN_PLIST(comp) + csize);
SET_LEN_PLIST(comp, LEN_PLIST(comp) + csize);
} else { // pt belongs to a component we've not seen before
index = ++nr;
pos = 1;
if (deg == 0) {
out = NewEmptyPlist(); return out;
}
out = NEW_PLIST(T_PLIST, 0);
nr = 0;
seen = ResizeInitTmpTrans(deg);
if (TNUM_OBJ(f) == T_TRANS2) {
ptf2 = CONST_ADDR_TRANS2(f); for (i = 0; i < deg; i++) { if (seen[i] == 0) { // repeatedly apply f to pt until we see something we've seen // already for (pt = i; seen[pt] == 0; pt = ptf2[pt]) {
seen[pt] = 1;
} if (seen[pt] == 1) { // pt belongs to a component we've not seen before
// Returns a transformation g such that ((i)f)g = i for all i in list, // it is assumed (and not checked) that the transformation f is injective on // list.
if (TNUM_OBJ(f) == T_TRANS2) {
deg = DEG_TRANS2(f);
g = NEW_TRANS2(deg);
ptf2 = CONST_ADDR_TRANS2(f);
ptg2 = ADDR_TRANS2(g);
for (j = 0; j < deg; j++) {
ptg2[j] = j;
} for (j = 1; j <= (UInt)LEN_LIST(list); j++) {
i = GetPositiveListEntry("INV_LIST_TRANS", list, j) - 1; if (i < deg) {
ptg2[ptf2[i]] = i;
}
}
} else {
deg = DEG_TRANS4(f);
g = NEW_TRANS4(deg);
ptf4 = CONST_ADDR_TRANS4(f);
ptg4 = ADDR_TRANS4(g);
for (j = 0; j < deg; j++) {
ptg4[j] = j;
} for (j = 1; j <= (UInt)LEN_LIST(list); j++) {
i = GetPositiveListEntry("INV_LIST_TRANS", list, j) - 1; if (i < deg) {
ptg4[ptf4[i]] = i;
}
}
} return g;
}
// If ker(f) = ker(g), then TRANS_IMG_CONJ returns the permutation p // such that i ^ (f ^ -1 * g) = i ^ p for all i in im(f). // // The permutation returned is the same as: // // MappingPermListList(ImageListOfTransformation(f, n), // ImageListOfTransformation(g, n)); // // where n = max{DegreeOfTransformation(f), DegreeOfTransformation(g)}. // However, this is included to avoid the overhead of producing the image // lists // of f and g in the above.
for (i = 0; i < min; i++) {
ptsrc[ptf2[i]] = 1;
ptdst[ptg2[i]] = 1;
ptp[ptf2[i]] = ptg2[i];
}
// if deg = min, then this isn't executed for (; i < deg; i++) { // ptsrc[i] = 1;
ptdst[ptg2[i]] = 1;
ptp[i] = ptg2[i];
}
// if def = min, then this isn't executed for (; i < def; i++) {
ptsrc[ptf2[i]] = 1;
ptdst[i] = 1;
ptp[ptf2[i]] = i;
}
} elseif (TNUM_OBJ(f) == T_TRANS2 && TNUM_OBJ(g) == T_TRANS4) {
ptf2 = CONST_ADDR_TRANS2(f);
ptg4 = CONST_ADDR_TRANS4(g);
for (i = 0; i < min; i++) {
ptsrc[ptf2[i]] = 1;
ptdst[ptg4[i]] = 1;
ptp[ptf2[i]] = ptg4[i];
}
// if deg = min, then this isn't executed for (; i < deg; i++) { // ptsrc[i] = 1;
ptdst[ptg4[i]] = 1;
ptp[i] = ptg4[i];
}
// if def = min, then this isn't executed for (; i < def; i++) { // The only transformation created within this file that is of // type // T_TRANS4 and that does not have (internal) degree 65537 or // greater // is ID_TRANS4.
ptsrc[ptf2[i]] = 1;
ptdst[i] = 1;
ptp[ptf2[i]] = i;
}
} elseif (TNUM_OBJ(f) == T_TRANS4 && TNUM_OBJ(g) == T_TRANS2) {
ptf4 = CONST_ADDR_TRANS4(f);
ptg2 = CONST_ADDR_TRANS2(g);
for (i = 0; i < min; i++) {
ptsrc[ptf4[i]] = 1;
ptdst[ptg2[i]] = 1;
ptp[ptf4[i]] = ptg2[i];
}
// if deg = min, then this isn't executed for (; i < deg; i++) { // The only transformation created within this file that is of // type // T_TRANS4 and that does not have (internal) degree 65537 or // greater // is ID_TRANS4. // ptsrc[i] = 1;
ptdst[ptg2[i]] = 1;
ptp[i] = ptg2[i];
}
// if def = min, then this isn't executed for (; i < def; i++) {
ptsrc[ptf4[i]] = 1;
ptdst[i] = 1;
ptp[ptf4[i]] = i;
}
} elseif (TNUM_OBJ(f) == T_TRANS4 && TNUM_OBJ(g) == T_TRANS4) {
ptf4 = CONST_ADDR_TRANS4(f);
ptg4 = CONST_ADDR_TRANS4(g);
for (i = 0; i < min; i++) {
ptsrc[ptf4[i]] = 1;
ptdst[ptg4[i]] = 1;
ptp[ptf4[i]] = ptg4[i];
}
// if deg = min, then this isn't executed for (; i < deg; i++) { // ptsrc[i] = 1;
ptdst[ptg4[i]] = 1;
ptp[i] = ptg4[i];
}
// if def = min, then this isn't executed for (; i < def; i++) {
ptsrc[ptf4[i]] = 1;
ptdst[i] = 1;
ptp[ptf4[i]] = i;
}
}
// complete the permutation
j = 0; for (i = 0; i < def; i++) { if (ptsrc[i] == 0) { while (ptdst[j] != 0) {
j++;
}
ptp[i] = j;
j++;
}
} return perm;
}
// Returns the flat kernel of <p> ^ -1 * f * <p> where f is any transformation // such that ker(f) = <ker>, <p> is a permutation and <ker> is itself a flat // kernel of transformation. This assumes (but doesn't check) that <p> is a // permutation of [1 .. Length(<ker>)] regardless of its degree.
if (len == 0) {
out = NEW_PLIST_IMM(T_PLIST_EMPTY, len);
SET_LEN_PLIST(out, len); return out;
}
out = NEW_PLIST_IMM(T_PLIST_CYC, len);
SET_LEN_PLIST(out, len);
ResizeTmpTrans(2 * len);
ptcnj = AddrTmpTrans();
rank = 1;
ptlkp = ptcnj + len;
if (TNUM_OBJ(p) == T_PERM2) {
dep = DEG_PERM2(p);
ptp2 = CONST_ADDR_PERM2(p);
if (dep <= len) { // form the conjugate in ptcnj and init the lookup for (i = 0; i < dep; i++) { // < p ^ - 1 * g * p > then < g > with ker( < g >) = < ker >
ptcnj[ptp2[i]] = ptp2[INT_INTOBJ(ELM_LIST(ker, i + 1)) - 1];
ptlkp[i] = 0;
} for (; i < len; i++) {
ptcnj[i] = IMAGE((UInt)INT_INTOBJ(ELM_LIST(ker, i + 1)) - 1,
ptp2, dep);
ptlkp[i] = 0;
}
} else { // dep > len but p fixes [1..len] setwise
// form the conjugate in ptcnj and init the lookup for (i = 0; i < len; i++) { // < p ^ - 1 * g * p > then < g > with ker( < g >) = < ker >
ptcnj[ptp2[i]] = ptp2[INT_INTOBJ(ELM_LIST(ker, i + 1)) - 1];
ptlkp[i] = 0;
}
}
} else {
dep = DEG_PERM4(p);
ptp4 = CONST_ADDR_PERM4(p);
if (dep <= len) { // form the conjugate in ptcnj and init the lookup for (i = 0; i < dep; i++) { // < p ^ - 1 * g * p > then < g > with ker( < g >) = < ker >
ptcnj[ptp4[i]] = ptp4[INT_INTOBJ(ELM_LIST(ker, i + 1)) - 1];
ptlkp[i] = 0;
} for (; i < len; i++) {
ptcnj[i] = IMAGE((UInt)INT_INTOBJ(ELM_LIST(ker, i + 1)) - 1,
ptp4, dep);
ptlkp[i] = 0;
}
} else { // dep > len but p fixes [1..len] setwise
// form the conjugate in ptcnj and init the lookup for (i = 0; i < len; i++) { // < p ^ - 1 * g * p > then < g > with ker( < g >) = < ker >
ptcnj[ptp4[i]] = ptp4[INT_INTOBJ(ELM_LIST(ker, i + 1)) - 1];
ptlkp[i] = 0;
}
}
}
// form the flat kernel for (i = 0; i < len; i++) { if (ptlkp[ptcnj[i]] == 0) {
ptlkp[ptcnj[i]] = rank++;
}
SET_ELM_PLIST(out, i + 1, INTOBJ_INT(ptlkp[ptcnj[i]]));
} return out;
}
// If <f> is a transformation and <X> is a flat kernel of a transformation, // then we denote OnKernelAntiAction(X, f) by f ^ X. Suppose that x is a // transformation with ker(x) = <X> and ker(<f>x) = f ^ ker(x) has the same // number of classes as ker(x). Then INV_KER_TRANS(X, f) returns a // transformation g such that g<f> ^ ker(x) = ker(x) = ker(gfx) and the action // of g<f> on ker(x) is the identity. template <typename TF, typename TG> static Obj INV_KER_TRANS(Obj X, Obj f)
{
Obj g; const TF * ptf;
TG * ptg;
UInt4 * pttmp;
UInt deg, i, len;
len = LEN_LIST(X);
ResizeTmpTrans(len);
deg = DEG_TRANS<TF>(f);
g = NEW_TRANS<TG>(len);
pttmp = AddrTmpTrans();
ptf = CONST_ADDR_TRANS<TF>(f);
ptg = ADDR_TRANS<TG>(g); if (deg >= len) { // calculate a transversal of f ^ ker(x) = ker(fx) for (i = 0; i < len; i++) {
pttmp[INT_INTOBJ(ELM_LIST(X, ptf[i] + 1)) - 1] = i;
}
} else { for (i = 0; i < deg; i++) {
pttmp[INT_INTOBJ(ELM_LIST(X, ptf[i] + 1)) - 1] = i;
} for (; i < len; i++) {
pttmp[INT_INTOBJ(ELM_LIST(X, i + 1)) - 1] = i;
}
} for (i = len; i >= 1; i--) {
ptg[i - 1] = pttmp[INT_INTOBJ(ELM_LIST(X, i)) - 1];
} return g;
}
// Returns the same value as OnSets(set, f) except if set = [0], when the // image // set of <f> on [1 .. n] is returned instead. If the argument <set> is not // [0], then the third argument is ignored.
if (IS_PLIST(set)) {
res = NEW_PLIST_WITH_MUTABILITY(IS_PLIST_MUTABLE(set), T_PLIST_CYC_SSORT, len);
SET_LEN_PLIST(res, len);
} else { // input is not a plain list, so we make a copy of it, and then also reuse // that copy for our output
res = PLAIN_LIST_COPY(set); if (!IS_MUTABLE_OBJ(set))
MakeImmutableNoRecurse(res);
set = res;
}
if (def <= deg) { for (i = 0; i < def; i++) { if (*(ptf++) != *(ptg++)) { return0;
}
} for (; i < deg; i++) { if (*(ptg++) != i) { return0;
}
}
} else { // The only transformation created within this file that is of type // T_TRANS4 and that does not have (internal) degree 65537 or greater // is ID_TRANS4.
for (i = 0; i < deg; i++) { if (*(ptf++) != *(ptg++)) { return0;
}
} for (; i < def; i++) { if (*(ptf++) != i) { return0;
}
}
}
// copy the list into a mutable plist, which we will then modify in place
res = PLAIN_LIST_COPY(tup);
RESET_FILT_LIST(res, FN_IS_NSORT); const UInt len = LEN_PLIST(res);
#ifdef GAP_ENABLE_SAVELOAD // Save and load staticvoid SaveTrans2(Obj f)
{ const UInt2 * ptr;
UInt len, i;
ptr = CONST_ADDR_TRANS2(f); // save the image list
len = DEG_TRANS2(f); for (i = 0; i < len; i++) {
SaveUInt2(*ptr++);
}
}
staticvoid LoadTrans2(Obj f)
{
UInt2 * ptr;
UInt len, i;
len = DEG_TRANS2(f);
ptr = ADDR_TRANS2(f); for (i = 0; i < len; i++) {
*ptr++ = LoadUInt2();
}
}
staticvoid SaveTrans4(Obj f)
{ const UInt4 * ptr;
UInt len, i;
ptr = CONST_ADDR_TRANS4(f); // save the image list
len = DEG_TRANS4(f); for (i = 0; i < len; i++) {
SaveUInt4(*ptr++);
}
}
staticvoid LoadTrans4(Obj f)
{
UInt4 * ptr;
UInt len, i;
len = DEG_TRANS4(f);
ptr = ADDR_TRANS4(f); for (i = 0; i < len; i++) {
*ptr++ = LoadUInt4();
}
} #endif
/****************************************************************************** *FInitKernel(<module>)........initialisekerneldatastructures
*/ staticInt InitKernel(StructInitInfo * module)
{ // set the bag type names (for error messages and debugging)
InitBagNamesFromTable( BagNames );
// install the marking functions
InitMarkFuncBags(T_TRANS2, MarkThreeSubBags);
InitMarkFuncBags(T_TRANS4, MarkThreeSubBags);
// init filters and functions
InitHdlrFiltsFromTable(GVarFilts);
InitHdlrFuncsFromTable(GVarFuncs);
// register global bags with the garbage collector
InitGlobalBag(&MODULE_STATE(Trans).TmpTrans, "src/trans.c:TmpTrans");
InitGlobalBag(&IdentityTrans, "src/trans.c:IdentityTrans");
// We make the next transformation to allow testing of some parts of the // code which would not otherwise be accessible, since no other // transformation created in this file is a T_TRANS4 unless its internal // degree is > 65536. Such transformation can be created by packages with // a // kernel module, and so we introduce the next transformation for testing // purposes.
Obj ID_TRANS4 = NEW_TRANS4(0);
AssReadOnlyGVar(GVarName("ID_TRANS4"), ID_TRANS4);
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 und die Messung sind noch experimentell.
