1 /****************************************************************************
2 **
3 ** This file is part of GAP, a system for computational discrete algebra.
4 **
5 ** Copyright of GAP belongs to its developers, whose names are too numerous
6 ** to list here. Please refer to the COPYRIGHT file for details.
7 **
8 ** SPDX-License-Identifier: GPL-2.0-or-later
9 **
10 ** This file defines the functions for permutations (small and large).
11 */
12
13 #ifndef GAP_PERMUTAT_H
14 #define GAP_PERMUTAT_H
15
16 #include "objects.h"
17
18 /****************************************************************************
19 **
20 *F NEW_PERM2(<deg>) . . . . . . . . . . . . make a new (small) permutation
21 *F DEG_PERM2(<perm>) . . . . . . . . . . . . . degree of (small) permutation
22 *F ADDR_PERM2(<perm>) . . . . . . . absolute address of (small) permutation
23 *F NEW_PERM4(<deg>) . . . . . . . . . . . . make a new (large) permutation
24 *F DEG_PERM4(<perm>) . . . . . . . . . . . . . degree of (large) permutation
25 *F ADDR_PERM4(<perm>) . . . . . . . absolute address of (large) permutation
26 */
SIZEBAG_PERM2(UInt deg)27 EXPORT_INLINE UInt SIZEBAG_PERM2(UInt deg)
28 {
29 return sizeof(Obj) + deg * sizeof(UInt2);
30 }
31
NEW_PERM2(UInt deg)32 EXPORT_INLINE Obj NEW_PERM2(UInt deg)
33 {
34 return NewBag(T_PERM2, SIZEBAG_PERM2(deg));
35 }
36
DEG_PERM2(Obj perm)37 EXPORT_INLINE UInt DEG_PERM2(Obj perm)
38 {
39 return (SIZE_OBJ(perm) - sizeof(Obj)) / sizeof(UInt2);
40 }
41
ADDR_PERM2(Obj perm)42 EXPORT_INLINE UInt2 * ADDR_PERM2(Obj perm)
43 {
44 return (UInt2 *)(ADDR_OBJ(perm) + 1);
45 }
46
CONST_ADDR_PERM2(Obj perm)47 EXPORT_INLINE const UInt2 * CONST_ADDR_PERM2(Obj perm)
48 {
49 return (const UInt2 *)(CONST_ADDR_OBJ(perm) + 1);
50 }
51
SIZEBAG_PERM4(UInt deg)52 EXPORT_INLINE UInt SIZEBAG_PERM4(UInt deg)
53 {
54 return sizeof(Obj) + deg * sizeof(UInt4);
55 }
56
NEW_PERM4(UInt deg)57 EXPORT_INLINE Obj NEW_PERM4(UInt deg)
58 {
59 return NewBag(T_PERM4, SIZEBAG_PERM4(deg));
60 }
61
DEG_PERM4(Obj perm)62 EXPORT_INLINE UInt DEG_PERM4(Obj perm)
63 {
64 return (SIZE_OBJ(perm) - sizeof(Obj)) / sizeof(UInt4);
65 }
66
ADDR_PERM4(Obj perm)67 EXPORT_INLINE UInt4 * ADDR_PERM4(Obj perm)
68 {
69 return (UInt4 *)(ADDR_OBJ(perm) + 1);
70 }
71
CONST_ADDR_PERM4(Obj perm)72 EXPORT_INLINE const UInt4 * CONST_ADDR_PERM4(Obj perm)
73 {
74 return (const UInt4 *)(CONST_ADDR_OBJ(perm) + 1);
75 }
76
STOREDINV_PERM(Obj perm)77 EXPORT_INLINE Obj STOREDINV_PERM(Obj perm)
78 {
79 Obj inv = ADDR_OBJ(perm)[0];
80 /* Check inv has the same TNAM as perm
81 This is checked below in SET_STOREDINV_PERM, but could
82 be invalidated if either perm or inv is changed in-place */
83 GAP_ASSERT(!inv || (TNUM_OBJ(perm) == TNUM_OBJ(inv)));
84 return inv;
85 }
86
87 /* SET_STOREDINV_PERM should only be used in neither perm, nor inv has
88 a stored inverse already. It's OK (although inefficient) if perm and inv
89 are identical */
SET_STOREDINV_PERM(Obj perm,Obj inv)90 EXPORT_INLINE void SET_STOREDINV_PERM(Obj perm, Obj inv)
91 {
92 /* check for the possibility that inv is in a different representation to
93 perm. It could be that perm actually acts on < 2^16 points but is in
94 PERM4 representation and some clever code has represented the inverse
95 as PERM2. It could be that someone introduces a new representation
96 altogether */
97 if (TNUM_OBJ(inv) == TNUM_OBJ(perm)) {
98 GAP_ASSERT(STOREDINV_PERM(perm) == 0 && STOREDINV_PERM(inv) == 0);
99 ADDR_OBJ(perm)[0] = inv;
100 CHANGED_BAG(perm);
101 ADDR_OBJ(inv)[0] = perm;
102 CHANGED_BAG(inv);
103 }
104 }
105
106 /* Clear the stored inverse. This is required if 'perm' changes TNUM.
107 Also clears the stored inverse of the stored inverse (which should be
108 perm). */
CLEAR_STOREDINV_PERM(Obj perm)109 EXPORT_INLINE void CLEAR_STOREDINV_PERM(Obj perm)
110 {
111 Obj inv = ADDR_OBJ(perm)[0];
112 if (inv) {
113 ADDR_OBJ(inv)[0] = 0;
114 ADDR_OBJ(perm)[0] = 0;
115 }
116 }
117
118
119 #define IMAGE(i,pt,dg) (((i) < (dg)) ? (pt)[(i)] : (i))
120
121 enum {
122 MAX_DEG_PERM4 = (1L << (sizeof(UInt) == 8 ? 32 : 28)) - 1
123 };
124
125 #define IS_PERM2(perm) (TNUM_OBJ(perm) == T_PERM2)
126 #define IS_PERM4(perm) (TNUM_OBJ(perm) == T_PERM4)
127
128
IS_PERM(Obj f)129 EXPORT_INLINE int IS_PERM(Obj f)
130 {
131 return (TNUM_OBJ(f) == T_PERM2 || TNUM_OBJ(f) == T_PERM4);
132 }
133
134
135 /****************************************************************************
136 **
137 *V IdentityPerm . . . . . . . . . . . . . . . . . . . identity permutation
138 **
139 ** 'IdentityPerm' is an identity permutation.
140 */
141 extern Obj IdentityPerm;
142
143
144 /****************************************************************************
145 **
146 *F OnTuplesPerm( <tup>, <perm> ) . . . . operations on tuples of points
147 **
148 ** 'OnTuplesPerm' returns the image of the tuple <tup> under the
149 ** permutation <perm>. It is called from 'FuncOnTuples'.
150 */
151 Obj OnTuplesPerm(Obj tup, Obj perm);
152
153
154 /****************************************************************************
155 **
156 *F OnSetsPerm( <set>, <perm> ) . . . . . . . . operations on sets of points
157 **
158 ** 'OnSetsPerm' returns the image of the tuple <set> under the permutation
159 ** <perm>. It is called from 'FuncOnSets'.
160 */
161 Obj OnSetsPerm(Obj set, Obj perm);
162
163
164 /****************************************************************************
165 **
166 *F Array2Perm( <array> ) . . . . . . . . . convert array of cycles into perm
167 **
168 ** This function may be used by C code generated by the GAP compiler.
169 */
170 Obj Array2Perm(Obj array);
171
172 /****************************************************************************
173 **
174 *F LargestMovedPointPerm(perm) . . . . . . . . largest point moved by a perm
175 */
176 UInt LargestMovedPointPerm(Obj perm);
177
178
179 /****************************************************************************
180 **
181 *F TrimPerm( <perm>, <m> ) . . . . . . . trim the permutation to degree <m>
182 **
183 ** Trim <perm> to degree <m> and if possible change it to a T_PERM2 bag.
184 ** No checks are performed, the caller is responsible for ensuring that this
185 ** operation is valid.
186 */
187 void TrimPerm(Obj perm, UInt m);
188
189
190 /****************************************************************************
191 **
192 *F ScanPermCycle( <perm>, <m>, <cycle>, <len>, <readElm> )
193 */
194 UInt ScanPermCycle(
195 Obj perm, UInt m, Obj cycle, UInt cycleLen, Obj (*readElm)(Obj, Int));
196
197
198 /****************************************************************************
199 **
200 *F * * * * * * * * * * * * * initialize module * * * * * * * * * * * * * * *
201 */
202
203 /****************************************************************************
204 **
205 *F InitInfoPermutat() . . . . . . . . . . . . . . . table of init functions
206 */
207 StructInitInfo * InitInfoPermutat ( void );
208
209
210 #endif // GAP_PERMUTAT_H
211