Quelle trans.cc Sprache: C

/****************************************************************************
**
** 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
*/

/*****************************************************************************
*
* A transformation <f> has internal representation as follows:
*
* [Obj* image set, Obj* flat kernel, Obj* external degree,
* entries image list]
*
* The <internal degree> of <f> is just the length of <entries image
* list>, this is accessed here using <DEG_TRANS2> and <DEG_TRANS4>.
*
* Transformations must always have internal degree greater than or equal
* to the largest point in <entries image list>.
*
* An element of <entries image list> of a transformation in T_TRANS2
* must be at most 65535 and be UInt2. Hence the internal and external
* degrees of a T_TRANS2 are at most 65536. If <f> is T_TRANS4, then the
* elements of <entries image list> must be UInt4.
*
* The <image set> and <flat kernel> are found relative to the internal
* degree of the transformation, and must not be changed after they are
* first found.
*
* The <external degree> is the largest non-negative integer <n> such
* that n ^ f != n or i ^ f = n for some i != n, or equivalently the
* degree of a transformation is the least non-negative <n> such that [n
* + 1, n + 2, .. ] is fixed pointwise by <f>. This value is an invariant
* of <f>, in the sense that it does not depend on the internal
* representation. In GAP, DegreeOfTransformation(f) returns the external
* degree, so that if f = g, then DegreeOfTransformation(f) =
* DegreeOfTransformation(g).
*
* In this file, the external degree of a transformation is accessed
* using FuncDegreeOfTransformation(self, f), and the internal degree is
* accessed using DEG_TRANS2/4(f).
*
*****************************************************************************/

extern "C" {

#include "trans.h"

#include "ariths.h"
#include "bool.h"
#include "error.h"
#include "gapstate.h"
#include "gvars.h"
#include "integer.h"
#include "intfuncs.h"
#include "listfunc.h"
#include "lists.h"
#include "modules.h"
#include "opers.h"
#include "permutat.h"
#include "plist.h"
#include "saveload.h"

#include <stdio.h> // for snprintf

} // extern "C"

#include "permutat_intern.hh"

//
// convert TNUM to underlying C data type
//
template <UInt tnum>
struct DataType;

template <>
struct DataType<T_TRANS2> {
 typedef UInt2 type;
};
template <>
struct DataType<T_TRANS4> {
 typedef UInt4 type;
};

//
// convert underlying C data type to TNUM
//
template <typename T>
struct T_TRANS {
};
template <>
struct T_TRANS<UInt2> {
 static const UInt tnum = T_TRANS2;
};
template <>
struct T_TRANS<UInt4> {
 static const UInt tnum = T_TRANS4;
};

//
// Various helper functions for partial permutations
//
template <typename T>
static void ASSERT_IS_TRANS(Obj f)
{
 GAP_ASSERT(TNUM_OBJ(f) == T_TRANS<T>::tnum);
}

template <typename T>
static inline Obj NEW_TRANS(UInt deg)
{
 return NewBag(T_TRANS<T>::tnum, deg * sizeof(T) + 3 * sizeof(Obj));
}

template <typename T>
static inline T * ADDR_TRANS(Obj f)
{
 ASSERT_IS_TRANS<T>(f);
 return (T *)(ADDR_OBJ(f) + 3);
}

template <typename T>
static inline const T * CONST_ADDR_TRANS(Obj f)
{
 ASSERT_IS_TRANS<T>(f);
 return (const T *)(CONST_ADDR_OBJ(f) + 3);
}

template <typename T>
static inline UInt DEG_TRANS(Obj f)
{
 ASSERT_IS_TRANS<T>(f);
 return (UInt)(SIZE_OBJ(f) - 3 * sizeof(Obj)) / sizeof(T);
}

#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a < b ? b : a)

#define RequireTransformation(funcname, op) \
 RequireArgumentCondition(funcname, op, IS_TRANS(op), \
 "must be a transformation")

/****************************************************************************
**
*F GetPositiveListEntryEx, GetPositiveListEntry
**
** Extract list[idx] and check that it is a positive small integer; if so,
** return that integer; otherwise raise an error.
*/
static Int GetPositiveListEntryEx(const char * funcname,
 Obj list,
 Int idx,
 const char * argname)
{
 Obj value = ELM_LIST(list, idx);
 if (!IS_POS_INTOBJ(value)) {
 char buf[1024];
 snprintf(buf, sizeof(buf), "%s[%d]", argname, (int)idx);
 buf[sizeof(buf) - 1] = '\0';
 RequireArgumentEx(funcname, value, buf,
 "must be a positive small integer");
 }
 return INT_INTOBJ(value);
}

#define GetPositiveListEntry(funcname, list, idx) \
 GetPositiveListEntryEx(funcname, list, idx, NICE_ARGNAME(list))

static ModuleStateOffset TransStateOffset = -1;

typedef struct {
 // TmpTrans is essentially the same as TmpPerm
 Obj TmpTrans;
} TransModuleState;

static inline Obj GetTmpTrans(void)
{
 return MODULE_STATE(Trans).TmpTrans;
}

static inline UInt4 * AddrTmpTrans(void)
{
 return ADDR_TRANS4(GetTmpTrans());
}

/****************************************************************************
**
*V IdentityTrans . . . . . . . . . . . . . . . . . identity transformation
**
** 'IdentityTrans' is an identity transformation.
*/
// mp this will become a ReadOnly object?
static Obj IdentityTrans;

/*******************************************************************************
** Forward declarations
*******************************************************************************/

static Obj FuncIMAGE_SET_TRANS(Obj self, Obj f);

/*******************************************************************************
** Internal functions for transformations
*******************************************************************************/

static inline Obj IMG_TRANS(Obj f)
{
 GAP_ASSERT(IS_TRANS(f));
 return CONST_ADDR_OBJ(f)[0];
}

static inline Obj KER_TRANS(Obj f)
{
 GAP_ASSERT(IS_TRANS(f));
 return CONST_ADDR_OBJ(f)[1];
}

static inline Obj EXT_TRANS(Obj f)
{
 GAP_ASSERT(IS_TRANS(f));
 return CONST_ADDR_OBJ(f)[2];
}

static inline void SET_IMG_TRANS(Obj f, Obj img)
{
 GAP_ASSERT(IS_TRANS(f));
 GAP_ASSERT(img == NULL || (IS_PLIST(img) && !IS_PLIST_MUTABLE(img)));
 ADDR_OBJ(f)[0] = img;
}

static inline void SET_KER_TRANS(Obj f, Obj ker)
{
 GAP_ASSERT(IS_TRANS(f));
 GAP_ASSERT(ker == NULL || (IS_PLIST(ker) && !IS_PLIST_MUTABLE(ker) &&
 LEN_PLIST(ker) == DEG_TRANS(f)));
 ADDR_OBJ(f)[1] = ker;
}

static inline void SET_EXT_TRANS(Obj f, Obj deg)
{
 GAP_ASSERT(IS_TRANS(f));
 GAP_ASSERT(deg == NULL ||
 (IS_INTOBJ(deg) && INT_INTOBJ(deg) <= DEG_TRANS(f)));
 ADDR_OBJ(f)[2] = deg;
}

static inline void ResizeTmpTrans(UInt len)
{
 Obj tmpTrans = GetTmpTrans();
 if (tmpTrans == (Obj)0) {
 MODULE_STATE(Trans).TmpTrans = NewBag(T_TRANS4, len * sizeof(UInt4) + 3 * sizeof(Obj));
 }
 else if (SIZE_OBJ(tmpTrans) < len * sizeof(UInt4) + 3 * sizeof(Obj)) {
 ResizeBag(tmpTrans, len * sizeof(UInt4) + 3 * sizeof(Obj));
 }
}

static inline UInt4 * ResizeInitTmpTrans(UInt len)
{
 ResizeTmpTrans(len);

 UInt4 * pttmp = AddrTmpTrans();
 memset(pttmp, 0, len * sizeof(UInt4));
 return pttmp;
}

// Find the rank, flat kernel, and image set (unsorted) of a transformation of
// degree at most 65536.

static UInt INIT_TRANS2(Obj f)
{
 UInt deg, rank, i, j;
 const UInt2 * ptf;
 UInt4 * pttmp;
 Obj img, ker;

 deg = DEG_TRANS2(f);

 if (deg == 0) {
 // special case for degree 0
 img = NewImmutableEmptyPlist();
 SET_IMG_TRANS(f, img);
 SET_KER_TRANS(f, img);
 CHANGED_BAG(f);
 return 0;
 }

 img = NEW_PLIST_IMM(T_PLIST_CYC, deg);
 ker = NEW_PLIST_IMM(T_PLIST_CYC_NSORT, deg);
 SET_LEN_PLIST(ker, (Int)deg);

 pttmp = ResizeInitTmpTrans(deg);
 ptf = CONST_ADDR_TRANS2(f);

 rank = 0;
 for (i = 0; i < deg; i++) {
 j = ptf[i];
 if (pttmp[j] == 0) {
 pttmp[j] = ++rank;
 SET_ELM_PLIST(img, rank, INTOBJ_INT(j + 1));
 }
 SET_ELM_PLIST(ker, i + 1, INTOBJ_INT(pttmp[j]));
 }

 SHRINK_PLIST(img, (Int)rank);
 SET_LEN_PLIST(img, (Int)rank);

 SET_IMG_TRANS(f, img);
 SET_KER_TRANS(f, ker);
 CHANGED_BAG(f);
 return rank;
}

// Find the rank, flat kernel, and image set (unsorted) of a transformation of
// degree at least 65537.

static UInt INIT_TRANS4(Obj f)
{
 UInt deg, rank, i, j;
 const UInt4 * ptf;
 UInt4 * pttmp;
 Obj img, ker;

 deg = DEG_TRANS4(f);

 if (deg == 0) {
 // Special case for degree 0.

 // 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.

 img = NewImmutableEmptyPlist();
 SET_IMG_TRANS(f, img);
 SET_KER_TRANS(f, img);
 CHANGED_BAG(f);
 return 0;
 }

 img = NEW_PLIST_IMM(T_PLIST_CYC, deg);
 ker = NEW_PLIST_IMM(T_PLIST_CYC_NSORT, deg);
 SET_LEN_PLIST(ker, (Int)deg);

 pttmp = ResizeInitTmpTrans(deg);
 ptf = CONST_ADDR_TRANS4(f);

 rank = 0;
 for (i = 0; i < deg; i++) {
 j = ptf[i];
 if (pttmp[j] == 0) {
 pttmp[j] = ++rank;
 SET_ELM_PLIST(img, rank, INTOBJ_INT(j + 1));
 }
 SET_ELM_PLIST(ker, i + 1, INTOBJ_INT(pttmp[j]));
 }

 SHRINK_PLIST(img, (Int)rank);
 SET_LEN_PLIST(img, (Int)rank);

 SET_IMG_TRANS(f, img);
 SET_KER_TRANS(f, ker);
 CHANGED_BAG(f);
 return rank;
}

static UInt INIT_TRANS(Obj f)
{
 return (TNUM_OBJ(f) == T_TRANS2) ? INIT_TRANS2(f) : INIT_TRANS4(f);

}

UInt RANK_TRANS2(Obj f)
{
 GAP_ASSERT(TNUM_OBJ(f) == T_TRANS2);
 return (IMG_TRANS(f) == NULL ? INIT_TRANS2(f) : LEN_PLIST(IMG_TRANS(f)));
}

UInt RANK_TRANS4(Obj f)
{
 GAP_ASSERT(TNUM_OBJ(f) == T_TRANS4);
 return (IMG_TRANS(f) == NULL ? INIT_TRANS4(f) : LEN_PLIST(IMG_TRANS(f)));
}

// Retyping is the responsibility of the caller, this should only be called
// after a call to SortPlistByRawObj.

static void REMOVE_DUPS_PLIST_INTOBJ(Obj res)
{
 Obj tmp;
 UInt i, k, len;
 Obj *data;

 len = LEN_PLIST(res);

 if (0 < len) {
 data = ADDR_OBJ(res);
 tmp = data[1];
 k = 1;
 for (i = 2; i <= len; i++) {
 if (tmp != data[i]) {
 k++;
 tmp = data[i];
 data[k] = tmp;
 }
 }
 if (k < len) {
 ResizeBag(res, (k + 1) * sizeof(Obj));
 SET_LEN_PLIST(res, k);
 }
 }
}

/*******************************************************************************
** GAP level functions for creating transformations
*******************************************************************************/

// 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.

static Obj FuncTransformationNC(Obj self, Obj list)
{
 UInt i, deg;
 UInt2 * ptf2;
 UInt4 * ptf4;
 Obj f;

 deg = LEN_LIST(list);

 if (deg <= 65536) {
 f = NEW_TRANS2(deg);
 ptf2 = ADDR_TRANS2(f);
 for (i = 0; i < deg; i++) {
 ptf2[i] = INT_INTOBJ(ELM_LIST(list, i + 1)) - 1;
 }
 }
 else {
 f = NEW_TRANS4(deg);
 ptf4 = ADDR_TRANS4(f);
 for (i = 0; i < deg; i++) {
 ptf4[i] = INT_INTOBJ(ELM_LIST(list, i + 1)) - 1;
 }
 }
 return f;
}

// Returns a transformation that maps <src> to <ran>, this does not check that
// <src> is duplicate-free.

static Obj FuncTransformationListListNC(Obj self, Obj src, Obj ran)
{
 Int deg, i, s, r;
 Obj f;
 UInt2 * ptf2;
 UInt4 * ptf4;

 RequireSmallList(SELF_NAME, src);
 RequireSmallList(SELF_NAME, ran);
 RequireSameLength(SELF_NAME, src, ran);

 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>.

static Obj FuncTRANS_IMG_KER_NC(Obj self, Obj img, Obj ker)
{
 Obj f, copy_img, copy_ker;
 UInt2 * ptf2;
 UInt4 * ptf4;
 UInt i, pos, deg;

 copy_img = PLAIN_LIST_COPY(img);
 copy_ker = PLAIN_LIST_COPY(ker);
 MakeImmutableNoRecurse(copy_img);
 MakeImmutableNoRecurse(copy_ker);

 deg = LEN_LIST(copy_ker);

 if (deg <= 65536) {
 f = NEW_TRANS2(deg);
 ptf2 = ADDR_TRANS2(f);
 for (i = 0; i < deg; i++) {
 pos = INT_INTOBJ(ELM_PLIST(copy_ker, i + 1));
 ptf2[i] = INT_INTOBJ(ELM_PLIST(copy_img, pos)) - 1;
 }
 }
 else {
 f = NEW_TRANS4(deg);
 ptf4 = ADDR_TRANS4(f);
 for (i = 0; i < deg; i++) {
 pos = INT_INTOBJ(ELM_PLIST(copy_ker, i + 1));
 ptf4[i] = INT_INTOBJ(ELM_PLIST(copy_img, pos)) - 1;
 }
 }

 SET_IMG_TRANS(f, copy_img);
 SET_KER_TRANS(f, copy_ker);
 CHANGED_BAG(f);

 return f;
}

// 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.

static Obj FuncIDEM_IMG_KER_NC(Obj self, Obj img, Obj ker)
{
 Obj f, copy_img, copy_ker;
 UInt2 * ptf2;
 UInt4 * ptf4, *pttmp;
 UInt i, j, deg, rank;

 copy_img = PLAIN_LIST_COPY(img);
 copy_ker = PLAIN_LIST_COPY(ker);
 MakeImmutableNoRecurse(copy_img);
 MakeImmutableNoRecurse(copy_ker);

 deg = LEN_LIST(copy_ker);
 rank = LEN_LIST(copy_img);
 ResizeTmpTrans(deg);
 pttmp = AddrTmpTrans();

 // setup the lookup table
 for (i = 0; i < rank; i++) {
 j = INT_INTOBJ(ELM_PLIST(copy_img, i + 1));
 pttmp[INT_INTOBJ(ELM_PLIST(copy_ker, j)) - 1] = j - 1;
 }
 if (deg <= 65536) {
 f = NEW_TRANS2(deg);
 ptf2 = ADDR_TRANS2(f);
 pttmp = AddrTmpTrans();

 for (i = 0; i < deg; i++) {
 ptf2[i] = pttmp[INT_INTOBJ(ELM_PLIST(copy_ker, i + 1)) - 1];
 }
 }
 else {
 f = NEW_TRANS4(deg);
 ptf4 = ADDR_TRANS4(f);
 pttmp = AddrTmpTrans();

 for (i = 0; i < deg; i++) {
 ptf4[i] = pttmp[INT_INTOBJ(ELM_PLIST(copy_ker, i + 1)) - 1];
 }
 }

 SET_IMG_TRANS(f, copy_img);
 SET_KER_TRANS(f, copy_ker);
 CHANGED_BAG(f);
 return f;
}

// Returns an idempotent transformation e with ker(e) = ker(f), where <f> is a
// transformation.

static Obj FuncLEFT_ONE_TRANS(Obj self, Obj f)
{
 Obj ker, img;
 UInt rank, n, i;

 RequireTransformation(SELF_NAME, f);

 rank = RANK_TRANS(f);
 ker = KER_TRANS(f);
 img = NEW_PLIST(T_PLIST_CYC, rank);
 n = 1;

 for (i = 1; n <= rank; i++) {
 if ((UInt)INT_INTOBJ(ELM_PLIST(ker, i)) == n) {
 SET_ELM_PLIST(img, n++, INTOBJ_INT(i));
 }
 }

 SET_LEN_PLIST(img, (Int)n - 1);
 return FuncIDEM_IMG_KER_NC(self, img, ker);
}

// Returns an idempotent transformation e with im(e) = im(f), where <f> is a
// transformation.

static Obj FuncRIGHT_ONE_TRANS(Obj self, Obj f)
{
 Obj ker, img;
 UInt deg, len, i, j, n;

 RequireTransformation(SELF_NAME, f);

 deg = DEG_TRANS(f);
 img = FuncIMAGE_SET_TRANS(self, f);
 ker = NEW_PLIST(T_PLIST_CYC, deg);
 SET_LEN_PLIST(ker, deg);
 len = LEN_PLIST(img);
 j = 1;
 n = 0;

 for (i = 0; i < deg; i++) {
 if (j < len && i + 1 == (UInt)INT_INTOBJ(ELM_PLIST(img, j + 1))) {
 j++;
 }
 SET_ELM_PLIST(ker, ++n, INTOBJ_INT(j));
 }
 return FuncIDEM_IMG_KER_NC(self, img, ker);
}

/*******************************************************************************
** GAP level functions for degree and rank of transformations
*******************************************************************************/

// Returns the degree of the transformation <f>, i.e. the least value <n> such
// that <f> fixes [n + 1, n + 2, .. ].

static Obj FuncDegreeOfTransformation(Obj self, Obj f)
{
 UInt n, i, deg;
 const UInt2 * ptf2;
 const UInt4 * ptf4;

 RequireTransformation(SELF_NAME, f);

 if (EXT_TRANS(f) == NULL) {
 n = DEG_TRANS(f);
 if (TNUM_OBJ(f) == T_TRANS2) {
 ptf2 = CONST_ADDR_TRANS2(f);
 if (ptf2[n - 1] != n - 1) {
 SET_EXT_TRANS(f, INTOBJ_INT(n));
 }
 else {
 deg = 0;
 for (i = 0; i < n; i++) {
 if (ptf2[i] > i && ptf2[i] + 1 > deg) {
 deg = ptf2[i] + 1;
 }
 else if (ptf2[i] deg) {
 deg = i + 1;
 }
 }
 SET_EXT_TRANS(f, INTOBJ_INT(deg));
 }
 }
 else {
 ptf4 = CONST_ADDR_TRANS4(f);
 if (ptf4[n - 1] != n - 1) {
 SET_EXT_TRANS(f, INTOBJ_INT(n));
 }
 else {
 deg = 0;
 for (i = 0; i < n; i++) {
 if (ptf4[i] > i && ptf4[i] + 1 > deg) {
 deg = ptf4[i] + 1;
 }
 else if (ptf4[i] deg) {
 deg = i + 1;
 }
 }
 SET_EXT_TRANS(f, INTOBJ_INT(deg));
 }
 }
 }
 return EXT_TRANS(f);
}

// Returns the rank of transformation, i.e. number of distinct values in
// [(1)f .. (n)f] where n = DegreeOfTransformation(f).

static Obj FuncRANK_TRANS(Obj self, Obj f)
{
 RequireTransformation(SELF_NAME, f);
 return SumInt(INTOBJ_INT(RANK_TRANS(f) - DEG_TRANS(f)),
 FuncDegreeOfTransformation(self, f));
}

// Returns the rank of the transformation <f> on [1 .. n], i.e. the number of
// distinct values in [(1)f .. (n)f].

static Obj FuncRANK_TRANS_INT(Obj self, Obj f, Obj n)
{
 UInt rank, i, m, deg;
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt4 * pttmp;

 RequireTransformation(SELF_NAME, f);
 RequireNonnegativeSmallInt(SELF_NAME, n);

 m = INT_INTOBJ(n);
 deg = DEG_TRANS(f);
 if (m >= deg) {
 rank = RANK_TRANS(f) - deg + m;
 }
 else if (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.

static Obj FuncRANK_TRANS_LIST(Obj self, Obj f, Obj list)
{
 UInt rank, i, j, len, def;
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt4 * pttmp;

 RequireTransformation(SELF_NAME, f);
 RequireSmallList(SELF_NAME, list);

 len = LEN_LIST(list);
 rank = 0;
 if (TNUM_OBJ(f) == T_TRANS2) {
 def = DEG_TRANS2(f);
 pttmp = ResizeInitTmpTrans(def);
 ptf2 = CONST_ADDR_TRANS2(f);
 for (i = 1; i <= len; i++) {
 j = GetPositiveListEntry("RANK_TRANS_LIST", list, i) - 1;
 if (j < def) {
 j = ptf2[j];
 if (pttmp[j] == 0) {
 rank++;
 pttmp[j] = 1;
 }
 }
 else {
 rank++;
 }
 }
 }
 else {
 def = DEG_TRANS4(f);
 pttmp = ResizeInitTmpTrans(def);
 ptf4 = CONST_ADDR_TRANS4(f);
 for (i = 1; i <= len; i++) {
 j = GetPositiveListEntry("RANK_TRANS_LIST", list, i) - 1;
 if (j < def) {
 j = ptf4[j];
 if (pttmp[j] == 0) {
 rank++;
 pttmp[j] = 1;
 }
 }
 else {
 rank++;
 }
 }
 }

 return INTOBJ_INT(rank);
}

/*******************************************************************************
** GAP level functions for the kernel and preimages of a transformation
*******************************************************************************/

// Returns the flat kernel of transformation on
// [1 .. DegreeOfTransformation(f)].

static Obj FuncFLAT_KERNEL_TRANS(Obj self, Obj f)
{
 RequireTransformation(SELF_NAME, f);

 if (KER_TRANS(f) == NULL) {
 INIT_TRANS(f);
 }
 return KER_TRANS(f);
}

// Returns the flat kernel of the transformation <f> on [1 .. n].

static Obj FuncFLAT_KERNEL_TRANS_INT(Obj self, Obj f, Obj n)
{
 Obj newObj, *ptnew;
 const Obj *ptker;
 UInt deg, m, i;

 RequireTransformation(SELF_NAME, f);
 RequireNonnegativeSmallInt(SELF_NAME, n);

 m = INT_INTOBJ(n);
 if (m == 0) {
 return NewEmptyPlist();
 }
 if (KER_TRANS(f) == NULL) {
 INIT_TRANS(f);
 }
 deg = DEG_TRANS(f);
 if (m == deg) {
 return KER_TRANS(f);
 }

 newObj = NEW_PLIST(T_PLIST_CYC_NSORT, m);
 SET_LEN_PLIST(newObj, m);
 ptker = CONST_ADDR_OBJ(KER_TRANS(f)) + 1;
 ptnew = ADDR_OBJ(newObj) + 1;

 // 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].

static Obj FuncKERNEL_TRANS(Obj self, Obj f, Obj n)
{
 Obj ker;
 UInt i, j, deg, nr, m, rank, min;
 UInt4 * pttmp;

 RequireNonnegativeSmallInt(SELF_NAME, n);
 RequireTransformation(SELF_NAME, f);

 m = INT_INTOBJ(n);

 // special case for the identity
 if (m == 0) {
 return NewEmptyPlist();
 }

 deg = DEG_TRANS(f);
 rank = RANK_TRANS(f);
 min = MIN(m, deg);
 nr = (min == m ? rank : rank + m - deg); // the number of classes

 ker = NEW_PLIST(T_PLIST_HOM_SSORT, nr);
 pttmp = ResizeInitTmpTrans(nr);

 // RANK_TRANS(f) should install KER_TRANS(f)
 assert(KER_TRANS(f) != NULL);

 nr = 0;
 // read off flat kernel
 for (i = 0; i < min; i++) {
 j = INT_INTOBJ(ELM_PLIST(KER_TRANS(f), i + 1));
 if (pttmp[j - 1] == 0) {
 nr++;
 SET_ELM_PLIST(ker, j, NEW_PLIST(T_PLIST_CYC_SSORT, 1));
 CHANGED_BAG(ker);
 pttmp = AddrTmpTrans();
 }
 AssPlist(ELM_PLIST(ker, j), (Int)++pttmp[j - 1], INTOBJ_INT(i + 1));
 pttmp = AddrTmpTrans();
 }

 // add trailing singletons, if any
 for (i = deg; i < m; i++) {
 SET_ELM_PLIST(ker, ++nr, NEW_PLIST(T_PLIST_CYC_SSORT, 1));
 SET_LEN_PLIST(ELM_PLIST(ker, nr), 1);
 SET_ELM_PLIST(ELM_PLIST(ker, nr), 1, INTOBJ_INT(i + 1));
 CHANGED_BAG(ker);
 }
 SET_LEN_PLIST(ker, (Int)nr);
 return ker;
}

// Returns the set (pt)f ^ -1.

static Obj FuncPREIMAGES_TRANS_INT(Obj self, Obj f, Obj pt)
{
 UInt deg, nr, i, j;
 Obj out;

 RequireTransformation(SELF_NAME, f);
 i = GetPositiveSmallInt(SELF_NAME, pt) - 1;

 deg = DEG_TRANS(f);

 if (i >= deg) {
 return NewPlistFromArgs(pt);
 }

 out = NEW_PLIST(T_PLIST_CYC_SSORT, 0);
 nr = 0;

 if (TNUM_OBJ(f) == T_TRANS2) {
 for (j = 0; j < deg; j++) {
 if ((CONST_ADDR_TRANS2(f))[j] == i) {
 AssPlist(out, ++nr, INTOBJ_INT(j + 1));
 }
 }
 }
 else {
 for (j = 0; j < deg; j++) {
 if ((CONST_ADDR_TRANS4(f))[j] == i) {
 AssPlist(out, ++nr, INTOBJ_INT(j + 1));
 }
 }
 }

 if (nr == 0) {
 RetypeBag(out, T_PLIST_EMPTY);
 SET_LEN_PLIST(out, 0);
 }

 return out;
}

/*******************************************************************************
** GAP level functions for the image sets and lists of a transformation
*******************************************************************************/

// Returns the duplicate free list of images of the transformation f on
// [1 .. n] where n = DEG_TRANS(f). Note that this might not be sorted.

static Obj FuncUNSORTED_IMAGE_SET_TRANS(Obj self, Obj f)
{
 RequireTransformation(SELF_NAME, f);

 if (IMG_TRANS(f) == NULL) {
 INIT_TRANS(f);
 }
 return IMG_TRANS(f);
}

// Returns the image set of the transformation f on [1 .. n] where n =
// DegreeOfTransformation(f).

static Obj FuncIMAGE_SET_TRANS(Obj self, Obj f)
{

 Obj out = FuncUNSORTED_IMAGE_SET_TRANS(self, f);

 if (!IS_SSORT_LIST(out)) {
 SortPlistByRawObj(out);
 RetypeBagSM(out, T_PLIST_CYC_SSORT);
 return out;
 }
 return out;
}

// Returns the image set of the transformation f on [1 .. n].

static Obj FuncIMAGE_SET_TRANS_INT(Obj self, Obj f, Obj n)
{
 Obj im, newObj;
 UInt deg, m, len, i, j, rank;
 Obj * ptnew;
 const Obj *ptim;
 UInt4 * pttmp;
 const UInt4 * ptf4;
 const UInt2 * ptf2;

 RequireNonnegativeSmallInt(SELF_NAME, n);
 RequireTransformation(SELF_NAME, f);

 m = INT_INTOBJ(n);
 deg = DEG_TRANS(f);

 if (m == deg) {
 return FuncIMAGE_SET_TRANS(self, f);
 }
 else if (m == 0) {
 return NewImmutableEmptyPlist();
 }
 else if (m < deg) {
 newObj = NEW_PLIST_IMM(T_PLIST_CYC, m);
 pttmp = ResizeInitTmpTrans(deg);

 if (TNUM_OBJ(f) == T_TRANS2) {
 ptf2 = CONST_ADDR_TRANS2(f);
 rank = 0;
 for (i = 0; i < m; i++) {
 j = ptf2[i];
 if (pttmp[j] == 0) {
 pttmp[j] = ++rank;
 SET_ELM_PLIST(newObj, rank, INTOBJ_INT(j + 1));
 }
 }
 }
 else {
 ptf4 = CONST_ADDR_TRANS4(f);
 rank = 0;
 for (i = 0; i < m; i++) {
 j = ptf4[i];
 if (pttmp[j] == 0) {
 pttmp[j] = ++rank;
 SET_ELM_PLIST(newObj, rank, INTOBJ_INT(j + 1));
 }
 }
 }
 SHRINK_PLIST(newObj, (Int)rank);
 SET_LEN_PLIST(newObj, (Int)rank);
 SortPlistByRawObj(newObj);
 RetypeBagSM(newObj, T_PLIST_CYC_SSORT);
 }
 else {
 // m > deg and so m is at least 1!
 im = FuncIMAGE_SET_TRANS(self, f);
 len = LEN_PLIST(im);
 newObj = NEW_PLIST(T_PLIST_CYC_SSORT, m - deg + len);
 SET_LEN_PLIST(newObj, m - deg + len);

 ptnew = ADDR_OBJ(newObj) + 1;
 ptim = CONST_ADDR_OBJ(im) + 1;

 // 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.

static Obj FuncIMAGE_LIST_TRANS_INT(Obj self, Obj f, Obj n)
{
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt i, deg, m;
 Obj out;

 RequireNonnegativeSmallInt(SELF_NAME, n);
 RequireTransformation(SELF_NAME, f);

 m = INT_INTOBJ(n);

 if (m == 0) {
 out = NewImmutableEmptyPlist();
 return out;
 }

 out = NEW_PLIST_IMM(T_PLIST_CYC, m);

 if (TNUM_OBJ(f) == T_TRANS2) {
 ptf2 = CONST_ADDR_TRANS2(f);
 deg = MIN(DEG_TRANS2(f), m);
 for (i = 0; i < deg; i++) {
 SET_ELM_PLIST(out, i + 1, INTOBJ_INT(ptf2[i] + 1));
 }
 }
 else {
 ptf4 = CONST_ADDR_TRANS4(f);
 deg = MIN(DEG_TRANS4(f), m);
 for (i = 0; i < deg; i++) {
 SET_ELM_PLIST(out, i + 1, INTOBJ_INT(ptf4[i] + 1));
 }
 }
 for (; i < m; i++)
 SET_ELM_PLIST(out, i + 1, INTOBJ_INT(i + 1));
 SET_LEN_PLIST(out, (Int)m);
 return out;
}

/*******************************************************************************
** GAP level functions for properties of transformations
*******************************************************************************/

// Test if a transformation is the identity.

static Obj FuncIS_ID_TRANS(Obj self, Obj f)
{
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt deg, i;

 RequireTransformation(SELF_NAME, f);

 if (TNUM_OBJ(f) == T_TRANS2) {
 ptf2 = CONST_ADDR_TRANS2(f);
 deg = DEG_TRANS2(f);
 for (i = 0; i < deg; i++) {
 if (ptf2[i] != i) {
 return False;
 }
 }
 }
 else {
 ptf4 = CONST_ADDR_TRANS4(f);
 deg = DEG_TRANS4(f);
 for (i = 0; i < deg; i++) {
 if (ptf4[i] != i) {
 return False;
 }
 }
 }
 return True;
}

// Returns true if the transformation <f> is an idempotent and false if it is
// not.

static Obj FuncIS_IDEM_TRANS(Obj self, Obj f)
{
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt deg, i;

 RequireTransformation(SELF_NAME, f);

 if (TNUM_OBJ(f) == T_TRANS2) {
 deg = DEG_TRANS2(f);
 ptf2 = CONST_ADDR_TRANS2(f);
 for (i = 0; i < deg; i++) {
 if (ptf2[ptf2[i]] != ptf2[i]) {
 return False;
 }
 }
 }
 else {
 deg = DEG_TRANS4(f);
 ptf4 = CONST_ADDR_TRANS4(f);
 for (i = 0; i < deg; i++) {
 if (ptf4[ptf4[i]] != ptf4[i]) {
 return False;
 }
 }
 }
 return True;
}

/*******************************************************************************
** GAP level functions for attributes of transformations
*******************************************************************************/

// Returns the least m and r such that f ^ (m + r) = f ^ m, where f is a
// transformation.

static Obj FuncIndexPeriodOfTransformation(Obj self, Obj f)
{
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt4 * seen;
 UInt deg, i, pt, dist, pow, len, last_pt;
 Obj ord;
 Int cyc;

 RequireTransformation(SELF_NAME, f);

 deg = INT_INTOBJ(FuncDegreeOfTransformation(self, 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--;
 }
 }
 }
 }

 return NewPlistFromArgs(INTOBJ_INT(--pow), ord);
}

// Returns the least integer m such that f ^ m is an idempotent.

static Obj FuncSMALLEST_IDEM_POW_TRANS(Obj self, Obj f)
{
 Obj x, ind, per, pow;

 x = FuncIndexPeriodOfTransformation(self, f);
 ind = ELM_PLIST(x, 1);
 per = ELM_PLIST(x, 2);
 pow = per;
 while (LtInt(pow, ind)) {
 pow = SumInt(pow, per);
 }
 return pow;
}

/*******************************************************************************
** GAP level functions for regularity of transformations
*******************************************************************************/

// Returns True if the transformation or list <obj> is injective on the list
// <list>.

static Obj FuncIsInjectiveListTrans(Obj self, Obj list, Obj obj)
{
 UInt n, i, j;
 const UInt2 * ptt2;
 const UInt4 * ptt4;
 UInt4 * pttmp = 0;

 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) {
 return False;
 }
 pttmp[ptt2[j - 1]] = 1;
 }
 }
 }
 else if (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) {
 return False;
 }
 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(
 " 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) {
 return False;
 }
 pttmp[INT_INTOBJ(ELM_LIST(obj, j)) - 1] = 1;
 }
 }
 }
 return True;
}

// Returns a transformation g such that transformation f * g * f = f and
// g * f * g = g, where f is a transformation.

static Obj FuncInverseOfTransformation(Obj self, Obj f)
{
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt2 * ptg2;
 UInt4 * ptg4;
 UInt deg, i;
 Obj g;

 RequireTransformation(SELF_NAME, f);
 if (FuncIS_ID_TRANS(self, f) == True) {
 return f;
 }

 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;
}

/*******************************************************************************
** GAP level functions for actions of transformations
*******************************************************************************/

// 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.

static Obj FuncON_KERNEL_ANTI_ACTION(Obj self, Obj ker, Obj f, Obj n)
{
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt4 * pttmp;
 UInt deg, i, j, rank, len;
 Obj out;

 RequireSmallList(SELF_NAME, ker);
 RequireTransformation(SELF_NAME, f);
 RequireNonnegativeSmallInt(SELF_NAME, n);

 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 "
 "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;
}

/*******************************************************************************
** GAP level functions for changing representation of a permutation to a
** transformation
*******************************************************************************/

// Returns a transformation <f> such that (i)f = (i)p for all i <= n where 
// is a permutation 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.

static Obj FuncAS_TRANS_PERM_INT(Obj self, Obj p, Obj deg)
{
 const UInt2 *ptp2;
 UInt2 *ptf2;
 const UInt4 *ptp4;
 UInt4 *ptf4;
 Obj f;
 UInt def, dep, i, min, n;

 RequireNonnegativeSmallInt(SELF_NAME, deg);
 RequirePermutation(SELF_NAME, p);

 n = INT_INTOBJ(deg);

 if (n == 0) {
 return IdentityTrans;
 }

 // find the degree of f
 def = n;
 dep = (TNUM_OBJ(p) == T_PERM2 ? DEG_PERM2(p) : DEG_PERM4(p));

 if (def < dep) {
 min = def;
 if (TNUM_OBJ(p) == T_PERM2) {
 ptp2 = CONST_ADDR_PERM2(p);
 for (i = 0; i < n; i++) {
 if (ptp2[i] + 1 > def) {
 def = ptp2[i] + 1;
 }
 }
 }
 else {
 ptp4 = CONST_ADDR_PERM4(p);
 for (i = 0; i < n; i++) {
 if (ptp4[i] + 1 > def) {
 def = ptp4[i] + 1;
 }
 }
 }
 }
 else {
 min = dep;
 def = dep; // no point in defining <f> to have lots of trailing
 // fixed points
 }

 if (def <= 65536) {
 f = NEW_TRANS2(def);
 ptf2 = ADDR_TRANS2(f);

 if (TNUM_OBJ(p) == T_PERM2) {
 ptp2 = CONST_ADDR_PERM2(p);
 for (i = 0; i < min; i++) {
 ptf2[i] = ptp2[i];
 }
 }
 else { // TNUM_OBJ(p) == T_PERM4
 ptp4 = CONST_ADDR_PERM4(p);
 for (i = 0; i < min; i++) {
 ptf2[i] = ptp4[i];
 }
 }
 for (; i < def; i++) {
 ptf2[i] = i;
 }
 }
 else { // dep >= def > 65536
 f = NEW_TRANS4(def);
 ptf4 = ADDR_TRANS4(f);
 assert(TNUM_OBJ(p) == T_PERM4);
 ptp4 = CONST_ADDR_PERM4(p);
 for (i = 0; i < min; i++) {
 ptf4[i] = ptp4[i];
 }
 for (; i < def; i++) {
 ptf4[i] = i;
 }
 }

 return f;
}

// Returns a transformation <f> such that (i)f = (i)p for all i <= n where 
// is a permutation and <n> is the largest moved point of .

static Obj FuncAS_TRANS_PERM(Obj self, Obj p)
{
 const UInt2 * ptPerm2;
 const UInt4 * ptPerm4;
 UInt sup;

 RequirePermutation(SELF_NAME, p);

 // find largest moved point
 if (TNUM_OBJ(p) == T_PERM2) {
 ptPerm2 = CONST_ADDR_PERM2(p);
 for (sup = DEG_PERM2(p); 1 <= sup; sup--) {
 if (ptPerm2[sup - 1] != sup - 1) {
 break;
 }
 }
 return FuncAS_TRANS_PERM_INT(self, p, INTOBJ_INT(sup));
 }
 else {
 ptPerm4 = CONST_ADDR_PERM4(p);
 for (sup = DEG_PERM4(p); 1 <= sup; sup--) {
 if (ptPerm4[sup - 1] != sup - 1) {
 break;
 }
 }
 return FuncAS_TRANS_PERM_INT(self, p, INTOBJ_INT(sup));
 }
}

/*******************************************************************************
** GAP level functions for changing representation of a transformation to a
** permutation
*******************************************************************************/

// Returns a permutation mathematically equal to the transformation <f> if
// possible, and returns Fail if it is not possible

static Obj FuncAS_PERM_TRANS(Obj self, Obj f)
{
 const UInt2 *ptf2;
 const UInt4 *ptf4;
 UInt2 *ptp2;
 UInt4 *ptp4;
 UInt deg, i;
 Obj p;

 RequireTransformation(SELF_NAME, f);

 deg = DEG_TRANS(f);
 if (RANK_TRANS(f) != deg) {
 return Fail;
 }
 if (TNUM_OBJ(f) == T_TRANS2) {
 p = NEW_PERM2(deg);
 ptp2 = ADDR_PERM2(p);
 ptf2 = CONST_ADDR_TRANS2(f);

 for (i = 0; i < deg; i++) {
 ptp2[i] = ptf2[i];
 }
 }
 else {
 p = NEW_PERM4(deg);
 ptp4 = ADDR_PERM4(p);
 ptf4 = CONST_ADDR_TRANS4(f);

 for (i = 0; i < deg; i++) {
 ptp4[i] = ptf4[i];
 }
 }
 return p;
}

// Returns the permutation of the image of the transformation <f> induced by
// <f> if possible, and returns Fail if it is not possible.

static Obj FuncPermutationOfImage(Obj self, Obj f)
{
 const UInt2 *ptf2;
 const UInt4 *ptf4;
 UInt2 *ptp2;
 UInt4 *ptp4, *pttmp;
 UInt deg, rank, i, j;
 Obj p, img;

 RequireTransformation(SELF_NAME, f);

 rank = RANK_TRANS(f);
 deg = DEG_TRANS(f);
 if (TNUM_OBJ(f) == T_TRANS2) {
 p = NEW_PERM2(deg);
 ResizeTmpTrans(deg);

 pttmp = AddrTmpTrans();
 ptp2 = ADDR_PERM2(p);
 for (i = 0; i < deg; i++) {
 pttmp[i] = 0;
 ptp2[i] = i;
 }

 ptf2 = CONST_ADDR_TRANS2(f);
 img = IMG_TRANS(f);
 assert(img != NULL); // should be installed by RANK_TRANS2

 for (i = 0; i < rank; i++) {
 j = INT_INTOBJ(ELM_PLIST(img, i + 1)) - 1;
 if (pttmp[ptf2[j]] != 0) {
 return Fail;
 }
 pttmp[ptf2[j]] = 1;
 ptp2[j] = ptf2[j];
 }
 }
 else {
 p = NEW_PERM4(deg);
 ResizeTmpTrans(deg);

 pttmp = AddrTmpTrans();
 ptp4 = ADDR_PERM4(p);
 for (i = 0; i < deg; i++) {
 pttmp[i] = 0;
 ptp4[i] = i;
 }

 ptf4 = CONST_ADDR_TRANS4(f);
 img = IMG_TRANS(f);
 assert(img != NULL); // should be installed by RANK_TRANS2

 for (i = 0; i < rank; i++) {
 j = INT_INTOBJ(ELM_PLIST(img, i + 1)) - 1;
 if (pttmp[ptf4[j]] != 0) {
 return Fail;
 }
 pttmp[ptf4[j]] = 1;
 ptp4[j] = ptf4[j];
 }
 }
 return p;
}

// Returns the permutation of the im(f) induced by f ^ -1 * g under the
// (unchecked) assumption that im(f) = im(g) and ker(f) = ker(g).

static Obj FuncPermLeftQuoTransformationNC(Obj self, Obj f, Obj g)
{
 const UInt2 *ptf2, *ptg2;
 const UInt4 *ptf4, *ptg4;
 UInt4 *ptp;
 UInt def, deg, i, min, max;
 Obj perm;

 RequireTransformation(SELF_NAME, f);
 RequireTransformation(SELF_NAME, g);

 def = DEG_TRANS(f);
 deg = DEG_TRANS(g);
 min = MIN(def, deg);
 max = MAX(def, deg);

 // always return a T_PERM4 to reduce the amount of code here.
 perm = NEW_PERM4(max);
 ptp = ADDR_PERM4(perm);

 if (TNUM_OBJ(f) == T_TRANS2 && TNUM_OBJ(g) == T_TRANS2) {
 ptf2 = CONST_ADDR_TRANS2(f);
 ptg2 = CONST_ADDR_TRANS2(g);

 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;
 }
 }
 else if (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;
 }
 }
 else if (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;
 }
 }
 else if (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;
}

/*******************************************************************************
** GAP level functions for changing representation of a transformation to a
** transformation
*******************************************************************************/

// Returns a transformation g such that (i)g = (i)f for all i in list, and
// where (i)g = i for every other value of i.

static Obj FuncRestrictedTransformation(Obj self, Obj f, Obj list)
{
 UInt deg, i, k, len;
 const UInt2 *ptf2;
 const UInt4 *ptf4;
 UInt2 *ptg2;
 UInt4 *ptg4;
 Obj g;

 RequireTransformation(SELF_NAME, f);
 RequireSmallList(SELF_NAME, list);

 len = LEN_LIST(list);

 if (TNUM_OBJ(f) == T_TRANS2) {
 deg = DEG_TRANS2(f);
 g = NEW_TRANS2(deg);

 ptf2 = CONST_ADDR_TRANS2(f);
 ptg2 = ADDR_TRANS2(g);

 // 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);

 ptf4 = CONST_ADDR_TRANS4(f);
 ptg4 = ADDR_TRANS4(g);

 // 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;

 RequireTransformation(SELF_NAME, f);
 RequireNonnegativeSmallInt(SELF_NAME, m);

 n = INT_INTOBJ(m);

 def = DEG_TRANS(f);
 if (def <= n) {
 return f;
 }

 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].

static Obj FuncTRIM_TRANS(Obj self, Obj f, Obj m)
{
 UInt deg, i;
 UInt4 * ptf;

 RequireTransformation(SELF_NAME, f);
 RequireNonnegativeSmallInt(SELF_NAME, m);

 deg = INT_INTOBJ(m);

 if (TNUM_OBJ(f) == T_TRANS2) {
 // output is T_TRANS2
 if (deg > DEG_TRANS2(f)) {
 return 0;
 }
 ResizeBag(f, deg * sizeof(UInt2) + 3 * sizeof(Obj));
 }
 else {
 if (deg > DEG_TRANS4(f)) {
 return 0;
 }
 if (deg > 65536UL) {
 // output is T_TRANS4
 ResizeBag(f, deg * sizeof(UInt4) + 3 * sizeof(Obj));
 }
 else {
 // output is T_TRANS2
 ptf = ADDR_TRANS4(f);
 for (i = 0; i < deg; i++) {
 ((UInt2 *)ptf)[i] = (UInt2)ptf[i];
 }
 RetypeBag(f, T_TRANS2);
 ResizeBag(f, deg * sizeof(UInt2) + 3 * sizeof(Obj));
 }
 }

 SET_IMG_TRANS(f, NULL);
 SET_KER_TRANS(f, NULL);
 SET_EXT_TRANS(f, NULL);
 CHANGED_BAG(f);

 return 0;
}

/*******************************************************************************
** GAP level functions for hashing transformations
*******************************************************************************/

// A hash function for transformations.

Int HashFuncForTrans(Obj f)
{
 UInt deg;

 GAP_ASSERT(TNUM_OBJ(f) == T_TRANS2 || TNUM_OBJ(f) == T_TRANS4);

 deg = INT_INTOBJ(FuncDegreeOfTransformation(0, f));

 if (TNUM_OBJ(f) == T_TRANS4) {
 if (deg <= 65536) {
 FuncTRIM_TRANS(0, f, INTOBJ_INT(deg));
 }
 else {
 return HASHKEY_BAG_NC(f, (UInt4)255, 3 * sizeof(Obj), (int)4 * deg);
 }
 }

 return HASHKEY_BAG_NC(f, (UInt4)255, 3 * sizeof(Obj), (int)2 * deg);
}

static Obj FuncHASH_FUNC_FOR_TRANS(Obj self, Obj f, Obj data)
{
 return INTOBJ_INT((HashFuncForTrans(f) % INT_INTOBJ(data)) + 1);
}

/*******************************************************************************
** GAP level functions for moved points (and related) of a transformation
*******************************************************************************/

// Returns the largest value i such that (i)f <> i or 0 if no such i exists.

static Obj FuncLARGEST_MOVED_PT_TRANS(Obj self, Obj f)
{
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt i;

 RequireTransformation(SELF_NAME, f);

 if (TNUM_OBJ(f) == T_TRANS2) {
 ptf2 = CONST_ADDR_TRANS2(f);
 for (i = DEG_TRANS2(f); 1 <= i; i--) {
 if (ptf2[i - 1] != i - 1) {
 break;
 }
 }
 }
 else {
 ptf4 = CONST_ADDR_TRANS4(f);
 for (i = DEG_TRANS4(f); 1 <= i; i--) {
 if (ptf4[i - 1] != i - 1) {
 break;
 }
 }
 }
 return INTOBJ_INT(i);
}

// Returns the largest value in [(1)f .. (n)f] where n = LargestMovedPoint(f).

static Obj FuncLARGEST_IMAGE_PT(Obj self, Obj f)
{
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt i, max, def;

 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 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.

static Obj FuncSMALLEST_MOVED_PT_TRANS(Obj self, Obj f)
{
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt i, deg;

 RequireTransformation(SELF_NAME, f);
 if (FuncIS_ID_TRANS(self, f) == True) {
 return Fail;
 }

 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.

static Obj FuncSMALLEST_IMAGE_PT(Obj self, Obj f)
{
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt i, min, deg;

 RequireTransformation(SELF_NAME, f);
 if (FuncIS_ID_TRANS(self, f) == True) {
 return Fail;
 }

 if (TNUM_OBJ(f) == T_TRANS2) {
 ptf2 = CONST_ADDR_TRANS2(f);
 deg = DEG_TRANS2(f);
 min = deg;
 for (i = 0; i < deg; i++) {
 if (ptf2[i] != i && ptf2[i] < min) {
 min = ptf2[i];
 }
 }
 return INTOBJ_INT(min + 1);
 }
 else {
 ptf4 = CONST_ADDR_TRANS4(f);
 deg = DEG_TRANS4(f);
 min = deg;
 for (i = 0; i < deg; i++) {
 if (ptf4[i] != i && ptf4[i] < min) {
 min = ptf4[i];
 }
 }
 }
 return INTOBJ_INT(min + 1);
}

// Returns the number of values in [1 .. n] such that (i)f <> i, where n =
// DegreeOfTransformation(f).

static Obj FuncNR_MOVED_PTS_TRANS(Obj self, Obj f)
{
 UInt nr, i, deg;
 const UInt2 * ptf2;
 const UInt4 * ptf4;

 RequireTransformation(SELF_NAME, f);

 nr = 0;
 if (TNUM_OBJ(f) == T_TRANS2) {
 ptf2 = CONST_ADDR_TRANS2(f);
 deg = DEG_TRANS2(f);
 for (i = 0; i < deg; i++) {
 if (ptf2[i] != i) {
 nr++;
 }
 }
 }
 else {
 ptf4 = CONST_ADDR_TRANS4(f);
 deg = DEG_TRANS4(f);
 for (i = 0; i < deg; i++) {
 if (ptf4[i] != i) {
 nr++;
 }
 }
 }
 return INTOBJ_INT(nr);
}

// Returns the set of values in [1 .. n] such that (i)f <> i, where n =
// DegreeOfTransformation(f).

static Obj FuncMOVED_PTS_TRANS(Obj self, Obj f)
{
 UInt len, deg, i;
 Obj out;
 const UInt2 * ptf2;
 const UInt4 * ptf4;

 RequireTransformation(SELF_NAME, f);

 len = 0;
 if (TNUM_OBJ(f) == T_TRANS2) {
 deg = DEG_TRANS2(f);
 out = NEW_PLIST(T_PLIST_CYC_SSORT, 0);
 ptf2 = CONST_ADDR_TRANS2(f);
 for (i = 0; i < deg; i++) {
 if (ptf2[i] != i) {
 AssPlist(out, ++len, INTOBJ_INT(i + 1));
 ptf2 = CONST_ADDR_TRANS2(f);
 }
 }
 }
 else {
 deg = DEG_TRANS4(f);
 out = NEW_PLIST(T_PLIST_CYC_SSORT, 0);
 ptf4 = CONST_ADDR_TRANS4(f);
 for (i = 0; i < deg; i++) {
 if (ptf4[i] != i) {
 AssPlist(out, ++len, INTOBJ_INT(i + 1));
 ptf4 = CONST_ADDR_TRANS4(f);
 }
 }
 }

 if (LEN_PLIST(out) == 0) {
 RetypeBag(out, T_PLIST_EMPTY);
 }

 return out;
}

/*******************************************************************************
** GAP level functions for connected components of a transformation
*******************************************************************************/

// 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.

static Obj FuncCOMPONENT_REPS_TRANS(Obj self, Obj f)
{
 UInt deg, i, nr, pt, index;
 Obj img, out, comp;
 const UInt2 * ptf2;
 const UInt4 * ptf4;
 UInt4 * seen;

 RequireTransformation(SELF_NAME, f);

 deg = INT_INTOBJ(FuncDegreeOfTransformation(self, f));

 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);
--> --------------------

--> maximum size reached

--> --------------------

quality92%

¤ Dauer der Verarbeitung: 0.80 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

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.