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 declares the functions of the generic list package.
11 **
12 ** This package provides a uniform interface to the functions that access
13 ** lists and their elements for the other packages in the GAP kernel. For
14 ** example, 'ExecFor' can loop over the elements in a list using 'LEN_LIST'
15 ** and 'ELM_LIST' independently of the type of the list.
16 */
17
18 #ifndef GAP_LISTS_H
19 #define GAP_LISTS_H
20
21 #include "error.h"
22 #include "io.h"
23 #include "objects.h"
24
25 /****************************************************************************
26 **
27 *F IS_LIST(<obj>) . . . . . . . . . . . . . . . . . . . is an object a list
28 *V IsListFuncs[<type>] . . . . . . . . . . . . . . . . . table for list test
29 **
30 ** 'IS_LIST' returns a nonzero value if the object <obj> is a list and zero
31 ** otherwise.
32 **
33 ** A package implementing an ordinary list type <type> must set the flag
34 ** 'IsListFlag[<type>]' for this type to '1'. A package implementing a
35 ** vector type must set it to '2'. A package implementing a matrix type
36 ** must set it to '3'.
37 */
38 extern Int (*IsListFuncs [LAST_REAL_TNUM+1]) ( Obj obj );
39
IS_LIST(Obj obj)40 EXPORT_INLINE Int IS_LIST(Obj obj)
41 {
42 return (*IsListFuncs[TNUM_OBJ(obj)])(obj);
43 }
44
45
46 /****************************************************************************
47 **
48 *F IS_SMALL_LIST(<obj>) . . . . . . . . . . . . . is an object a small list
49 *V IsSmallListFuncs[<type>] . . . . . . . . . . .. table for small list test
50 **
51 ** 'IS_SMALL_LIST' returns a nonzero value if the object <obj> is a small
52 ** list (meaning that its length will fit in 28 bits and zero otherwise.
53 ** in particular, it returns zero if <obj> is not a list at all
54 **
55 ** If <obj> is an external object it does not trigger length computation
56 ** in general
57 ** instead it will check if the object HasIsSmallList and IsSmallList, or
58 ** HasLength in which case Length will be checked
59 */
60 extern Int (*IsSmallListFuncs[LAST_REAL_TNUM + 1])(Obj obj);
61
IS_SMALL_LIST(Obj obj)62 EXPORT_INLINE Int IS_SMALL_LIST(Obj obj)
63 {
64 return (*IsSmallListFuncs[TNUM_OBJ(obj)])(obj);
65 }
66
67 /****************************************************************************
68 **
69 *F IS_DENSE_LIST(<list>) . . . . . . . . . . . . . . . test for dense lists
70 *V IsDenseListFuncs[<type>] . . . . . . table of dense list test functions
71 **
72 ** 'IS_DENSE_LIST' returns 1 if the list <list> is a dense list and 0
73 ** otherwise, i.e., if either <list> is not a list, or if it is not dense.
74 **
75 ** A package implementing a list type <type> must provide such a function
76 ** and install it in 'IsDenseListFuncs[<type>]'. This function must loop
77 ** over the list and test for holes, unless the type of the list guarantees
78 ** already that the list is dense (e.g. for sets).
79 */
80
81 extern Int (*IsDenseListFuncs[LAST_REAL_TNUM + 1])(Obj list);
82
IS_DENSE_LIST(Obj list)83 EXPORT_INLINE Int IS_DENSE_LIST(Obj list)
84 {
85 return (*IsDenseListFuncs[TNUM_OBJ(list)])(list);
86 }
87
88 /****************************************************************************
89 **
90 *F IS_HOMOG_LIST(<list>) . . . . . . . . . . . . test for homogeneous lists
91 *V IsHomogListFuncs[<type>] . . . table of homogeneous list test functions
92 **
93 ** 'IS_HOMOG_LIST' returns 1 if the list <list> is a homogeneous list and
94 ** 0 otherwise, i.e., if either <list> is not a list, or if it is not
95 ** homogeneous.
96 **
97 ** A package implementing a list type <type> must provide such a function
98 ** and install it in 'IsHomogListFuncs[<type>]'. This function must loop
99 ** over the list and test whether all elements lie in the same family,
100 ** unless the type of the list guarantees already that the list is
101 ** homogeneous (e.g. for sets).
102 */
103
104 extern Int (*IsHomogListFuncs[LAST_REAL_TNUM + 1])(Obj list);
105
IS_HOMOG_LIST(Obj list)106 EXPORT_INLINE Int IS_HOMOG_LIST(Obj list)
107 {
108 return (*IsHomogListFuncs[TNUM_OBJ(list)])(list);
109 }
110
111 /****************************************************************************
112 **
113 *F IS_POSS_LIST(<list>) . . . . . . . . . . . . . test for positions lists
114 *V IsPossListFuncs[<type>] . . . . . . table of positions list test function
115 **
116 ** 'IS_POSS_LIST' returns 1 if the list <list> is a dense list containing
117 ** only positive integers and 0 otherwise, i.e., if either <list> is not a
118 ** list, or if it is not dense, or if it contains an element that is not a
119 ** positive integer.
120 **
121 ** A package implementing a list type <type> must provide such a function
122 ** and install it in 'IsPossListFuncs[<type>]'. This function must loop
123 ** over the list and test for holes and elements that are not positive
124 ** integers, unless the type of the list guarantees already that the list is
125 ** acceptable (e.g. a range with positive <low> and <high> values).
126 */
127
128 extern Int (*IsPossListFuncs[LAST_REAL_TNUM + 1])(Obj list);
129
IS_POSS_LIST(Obj list)130 EXPORT_INLINE Int IS_POSS_LIST(Obj list)
131 {
132 return (*IsPossListFuncs[TNUM_OBJ(list)])(list);
133 }
134
135 /****************************************************************************
136 **
137 *F LEN_LIST(<list>) . . . . . . . . . . . . . . . . . . . length of a list
138 *V LenListFuncs[<type>] . . . . . . . . . . . . . table of length functions
139 **
140 ** A package implementing a list type <type> must provide such a function
141 ** and install it in 'LenListFuncs[<type>]'.
142 */
143 extern Int (*LenListFuncs[LAST_REAL_TNUM+1]) ( Obj list );
144
LEN_LIST(Obj list)145 EXPORT_INLINE Int LEN_LIST(Obj list)
146 {
147 return (*LenListFuncs[TNUM_OBJ(list)])(list);
148 }
149
150
151 /****************************************************************************
152 **
153 *F LENGTH(<list>) . . . . . . . . . . . . . . . . . . . length of a list
154 *V LengthFuncs[<type>] . . . . . . . . . . . . . table of length functions
155 **
156 ** 'LENGTH' returns the logical length of the list <list> as a GAP object
157 ** An error is signalled if <list> is not a list.
158 **
159 ** A package implementing a list type <type> must provide such a function
160 ** and install it in 'LengthFuncs[<type>]'.
161 */
162 extern Obj (*LengthFuncs[LAST_REAL_TNUM+1]) ( Obj list );
163
LENGTH(Obj list)164 EXPORT_INLINE Obj LENGTH(Obj list)
165 {
166 return (*LengthFuncs[TNUM_OBJ(list)])(list);
167 }
168
169
170 /****************************************************************************
171 **
172 *F ISB_LIST(<list>,<pos>) . . . . . . . . . . test for element from a list
173 *V IsbListFuncs[<type>] . . . . . . . . . . . . . . table of test functions
174 **
175 ** 'ISB_LIST' returns 1 if the list <list> has an entry at position <pos>
176 ** and 0 otherwise. An error is signalled if <list> is not a list. It is
177 ** the responsibility of the caller to ensure that <pos> is a positive
178 ** integer.
179 **
180 ** A package implementing a list type <type> must provide a function for
181 ** 'ISB_LIST' and install it in 'IsbListFuncs[<type>]'.
182 **
183 */
184
185 extern Int (*IsbListFuncs[LAST_REAL_TNUM+1]) ( Obj list, Int pos );
186
ISB_LIST(Obj list,Int pos)187 EXPORT_INLINE Int ISB_LIST(Obj list, Int pos)
188 {
189 return (*IsbListFuncs[TNUM_OBJ(list)])(list, pos);
190 }
191
192 Int ISBB_LIST(Obj list, Obj pos);
193
194 Int ISB_MAT(Obj list, Obj row, Obj col);
195
196
197 /****************************************************************************
198 **
199 *F * * * * * * * * * * * * list access functions * * * * * * * * * * * * * *
200 */
201
202
203 /****************************************************************************
204 **
205 *V Elm0ListFuncs[ <type> ] . . . . . . . . . . table of selection functions
206 **
207 ** A package implementing a list type <type> must provide a function for
208 ** 'ELM0_LIST' and install it in 'Elm0ListFuncs[<type>]'.
209 */
210 extern Obj (*Elm0ListFuncs[LAST_REAL_TNUM+1]) ( Obj list, Int pos );
211
212
213 /****************************************************************************
214 **
215 *F ELM0_LIST( <list>, <pos> ) . . . . . . . . select an element from a list
216 **
217 ** 'ELM0_LIST' returns the element at the position <pos> in the list <list>,
218 ** or 0 if <list> has no assigned object at position <pos>. An error is
219 ** signalled if <list> is not a list. It is the responsibility of the
220 ** caller to ensure that <pos> is a positive integer.
221 */
ELM0_LIST(Obj list,Int pos)222 EXPORT_INLINE Obj ELM0_LIST(Obj list, Int pos)
223 {
224 return (*Elm0ListFuncs[TNUM_OBJ(list)])(list, pos);
225 }
226
227 /****************************************************************************
228 **
229 *V ElmDefListFuncs[ <type> ] . . . . . . . . . table of selection functions
230 **
231 ** A package implementing a list type <type> can provide a function for
232 ** 'ELM_DEFAULT_LIST' and install it in 'ElmDefListFuncs[<type>]', otherwise
233 ** a default implementation is provided.
234 */
235 extern Obj (*ElmDefListFuncs[LAST_REAL_TNUM + 1])(Obj list, Int pos, Obj def);
236
237
238 /****************************************************************************
239 **
240 *F ELM_DEFAULT_LIST( <list>, <pos>, <default> )select an element from a list
241 **
242 ** 'ELM_DEFAULT_LIST' returns the element at the position <pos> in the list
243 ** <list>, or <default> if <list> has no assigned object at position <pos>.
244 ** An error is signalled if <list> is not a list. It is the responsibility
245 ** of the caller to ensure that <pos> is a positive integer.
246 */
ELM_DEFAULT_LIST(Obj list,Int pos,Obj def)247 EXPORT_INLINE Obj ELM_DEFAULT_LIST(Obj list, Int pos, Obj def)
248 {
249 return (*ElmDefListFuncs[TNUM_OBJ(list)])(list, pos, def);
250 }
251
252
253 /****************************************************************************
254 **
255 *V Elmv0ListFuncs[ <type> ] . . . . . . . . . table of selection functions
256 **
257 ** A package implementing a lists type <type> must provide a function for
258 ** 'ELMV0_LIST( <list>, <pos> )' and install it in 'Elmv0ListFuncs[<type>]'.
259 ** This function need not test whether <pos> is less than or equal to the
260 ** length of <list>.
261 */
262 extern Obj (*Elm0vListFuncs[LAST_REAL_TNUM+1]) ( Obj list, Int pos );
263
264
265 /****************************************************************************
266 **
267 *F ELMV0_LIST( <list>, <pos> ) . . . . . . . . select an element from a list
268 **
269 ** 'ELMV0_LIST' does the same as 'ELM0_LIST', but the caller also guarantees
270 ** that <list> is a list and that <pos> is less than or equal to the length
271 ** of <list>.
272 */
ELMV0_LIST(Obj list,Int pos)273 EXPORT_INLINE Obj ELMV0_LIST(Obj list, Int pos)
274 {
275 GAP_ASSERT(pos > 0);
276 GAP_ASSERT(pos <= LEN_LIST(list));
277 return (*Elm0vListFuncs[TNUM_OBJ(list)])(list, pos);
278 }
279
280
281 /****************************************************************************
282 **
283 *V ElmListFuncs[ <type> ] . . . . . . . . . . table of selection functions
284 **
285 ** A package implementing a list type <type> must provide a function for
286 ** 'ELM_LIST( <list>, <pos> )' and install it in 'ElmListFuncs[<type>]'.
287 ** This function must signal an error if <pos> is larger than the length of
288 ** <list> or if <list> has no assigned object at <pos>.
289 */
290 extern Obj (*ElmListFuncs[LAST_REAL_TNUM+1]) ( Obj list, Int pos );
291
292
293 /****************************************************************************
294 **
295 *F ELM_LIST( <list>, <pos> ) . . . . . . . . . select an element from a list
296 *F ELMB_LIST( <list>, <pos> ) . . . . . . . . . select an element from a list
297 **
298 ** 'ELM_LIST' returns the element at the position <pos> in the list <list>.
299 ** An error is signalled if <list> is not a list, if <pos> is larger than
300 ** the length of <list>, or if <list> has no assigned object at <pos>. It
301 ** is the responsibility of the caller to ensure that <pos> is a positive
302 ** integer.
303 **
304 ** The difference between 'ELM_LIST' and 'ELMB_LIST' is that 'ELMB_LIST'
305 ** accepts an object as the second argument.
306 ** It is intended as an interface for access to elements of large external
307 ** lists, on the rare occasions when the kernel needs to do this.
308 */
309 Obj ELMB_LIST(Obj list, Obj pos);
310
ELM_LIST(Obj list,Int pos)311 EXPORT_INLINE Obj ELM_LIST(Obj list, Int pos)
312 {
313 Obj ret = (*ElmListFuncs[TNUM_OBJ(list)])(list, pos);
314 GAP_ASSERT(ret != 0);
315 return ret;
316 }
317
318
319 /****************************************************************************
320 **
321 *F ELM_MAT( <list>, <row>, <col> ) . . . . select an element from a list
322 **
323 ** 'ELM_MAT' implements 'list[row,col]', which for lists of lists is
324 ** defined as 'list[row][col]', and for other kind of objects is handled
325 ** by method dispatch through the GAP operation 'ELM_LIST' with three
326 ** arguments.
327 */
328 Obj ELM_MAT(Obj list, Obj row, Obj col);
329
330
331 /****************************************************************************
332 **
333 *V ElmvListFuncs[ <type> ] . . . . . . . . . . table of selection functions
334 **
335 ** A package implementing a list type <type> must provide a function for
336 ** 'ELMV_LIST' and install it in 'ElmvListFuncs[<type>]'. This function
337 ** need not check that <pos> is less than or equal to the length of <list>,
338 ** but it must signal an error if <list> has no assigned object at <pos>.
339 **
340 */
341 extern Obj (*ElmvListFuncs[LAST_REAL_TNUM+1]) ( Obj list, Int pos );
342
343
344 /****************************************************************************
345 **
346 *F ELMV_LIST( <list>, <pos> ) . . . . . . . . select an element from a list
347 **
348 ** 'ELMV_LIST' does the same as 'ELM_LIST', but the caller also guarantees
349 ** that <list> is a list and that <pos> is less than or equal to the length
350 ** of <list>.
351 */
ELMV_LIST(Obj list,Int pos)352 EXPORT_INLINE Obj ELMV_LIST(Obj list, Int pos)
353 {
354 GAP_ASSERT(pos > 0);
355 GAP_ASSERT(pos <= LEN_LIST(list));
356 return (*ElmvListFuncs[TNUM_OBJ(list)])(list, pos);
357 }
358
359
360 /****************************************************************************
361 **
362 *V ElmwListFuncs[ <type> ] . . . . . . . . . . table of selection functions
363 **
364 ** A package implementing a list type <type> must provide a function for
365 ** 'ELMW_LIST' and install them in 'ElmwListFuncs[<type>]'. This function
366 ** need not check that <pos> is less than or equal to the length of <list>
367 ** or that <list> has an assigned object at <pos>.
368 */
369 extern Obj (*ElmwListFuncs[LAST_REAL_TNUM+1]) ( Obj list, Int pos );
370
371
372 /****************************************************************************
373 **
374 *F ELMW_LIST( <list>, <pos> ) . . . . . . . . select an element from a list
375 **
376 ** 'ELMW_LIST' does the same as 'ELMV_LIST', but the caller also guarantees
377 ** that <list> has an assigned object at the position <pos>.
378 */
ELMW_LIST(Obj list,Int pos)379 EXPORT_INLINE Obj ELMW_LIST(Obj list, Int pos)
380 {
381 GAP_ASSERT(pos > 0);
382 GAP_ASSERT(pos <= LEN_LIST(list));
383 Obj ret = (*ElmwListFuncs[TNUM_OBJ(list)])(list, pos);
384 GAP_ASSERT(ret != 0);
385 return ret;
386 }
387
388
389 /****************************************************************************
390 **
391 *V ElmsListFuncs[ <type> ] . . . . . . . . . . table of selection functions
392 **
393 ** A package implementing a list type <type> must provide such a function
394 ** and install it in 'ElmsListFuncs[<type>]'. This function must signal an
395 ** error if any of the positions is larger than the length of <list> or if
396 ** <list> has no assigned object at any of the positions (and thus it will
397 ** always return a dense list). It *must* create a new list, even if <poss>
398 ** is equal to '[1..Length(<list>)]', 'EvalElmListLevel' depends on this so
399 ** that it can call 'ElmListLevel', which overwrites this new list. If the
400 ** result is a list of lists, then it also *must* create a new list that has
401 ** the same representation as a plain list.
402 */
403 extern Obj (*ElmsListFuncs[LAST_REAL_TNUM+1]) ( Obj list, Obj poss );
404
405
406
407 /****************************************************************************
408 **
409 *F ELMS_LIST(<list>,<poss>) . . . . . . select several elements from a list
410 **
411 ** 'ELMS_LIST' returns a new list containing the elements at the positions
412 ** given in the list <poss> from the list <list>. An error is signalled if
413 ** <list> is not a list, if any of the positions is larger than the length
414 ** of <list>, or if <list> has no assigned object at any of the positions.
415 ** It is the responsibility of the caller to ensure that <poss> is a dense
416 ** list of positive integers.
417 */
ELMS_LIST(Obj list,Obj poss)418 EXPORT_INLINE Obj ELMS_LIST(Obj list, Obj poss)
419 {
420 GAP_ASSERT(IS_POSS_LIST(poss));
421 return (*ElmsListFuncs[TNUM_OBJ(list)])(list, poss);
422 }
423
424
425 /****************************************************************************
426 **
427 *F ElmsListDefault( <list>, <poss> ) . . . default function for 'ELMS_LIST'
428 */
429 Obj ElmsListDefault(Obj list, Obj poss);
430
431
432 /****************************************************************************
433 **
434 *F ElmsListCheck( <list>, <poss> ) . . . . . . . . . 'ELMS_LIST' with check
435 */
436 Obj ElmsListCheck(Obj list, Obj poss);
437
438
439 /****************************************************************************
440 **
441 *F ElmsListLevelCheck( <lists>, <poss>, <level> ) 'ElmsListLevel' with check
442 */
443 void ElmsListLevelCheck(Obj lists, Obj poss, Int level);
444
445
446 /****************************************************************************
447 **
448 *F UNB_LIST(<list>,<pos>) . . . . . . . . . . . unbind element from a list
449 *V UnbListFuncs[<type>] . . . . . . . . . . . . . table of unbind functions
450 **
451 ** 'UNB_LiST' unbinds the element at the position <pos> in the list <list>.
452 ** Note that the unbinding may change the length of the representation of
453 ** <list>. An error is signalled if <list> is not a list. It is the
454 ** responsibility of the caller to ensure that <pos> is a positive integer.
455 **
456 ** A package implementing a list type <type> must provide such a function
457 ** and install it in 'UnbListFuncs[<type>]'. This function must change the
458 ** representation of <list> to that of a plain list if necessary.
459 */
460
461 extern void (*UnbListFuncs[LAST_REAL_TNUM+1]) ( Obj list, Int pos );
462
463 void UNBB_LIST(Obj list, Obj pos);
464
UNB_LIST(Obj list,Int pos)465 EXPORT_INLINE void UNB_LIST(Obj list, Int pos)
466 {
467 GAP_ASSERT(pos > 0);
468 UInt tnum = TNUM_OBJ(list);
469 if (FIRST_LIST_TNUM <= tnum && tnum <= LAST_LIST_TNUM &&
470 (tnum & IMMUTABLE)) {
471 ErrorMayQuit("List Unbind: <list> must be a mutable list", 0, 0);
472 }
473 (*UnbListFuncs[TNUM_OBJ(list)])(list, pos);
474 }
475
476 void UNB_MAT(Obj list, Obj row, Obj col);
477
478
479 /****************************************************************************
480 **
481 *F ASS_LIST(<list>,<pos>,<obj>) . . . . . . . . assign an element to a list
482 *V AssListFuncs[<type>] . . . . . . . . . . . table of assignment functions
483 **
484 ** 'ASS_LIST' assigns the object <obj> to the list <list> at position <pos>.
485 ** Note that the assignment may change the length or the representation of
486 ** <list>. An error is signalled if <list> is not a list. It is the
487 ** responsibility of the caller to ensure that <pos> is a positive integer,
488 ** and that <obj> is not 0.
489 **
490 ** A package implementing a list type <type> must provide such a function
491 ** and install it in 'AssListFuncs[<type>]'. This function must extend
492 ** <list> if <pos> is larger than the length of <list> and must also change
493 ** the representation of <list> to that of a plain list if necessary.
494 */
495
496
497 extern void (*AssListFuncs[LAST_REAL_TNUM+1]) ( Obj list, Int pos, Obj obj );
498
499 void ASSB_LIST(Obj list, Obj pos, Obj obj);
500
ASS_LIST(Obj list,Int pos,Obj obj)501 EXPORT_INLINE void ASS_LIST(Obj list, Int pos, Obj obj)
502 {
503 GAP_ASSERT(pos > 0);
504 GAP_ASSERT(obj != 0);
505 UInt tnum = TNUM_OBJ(list);
506 if (FIRST_LIST_TNUM <= tnum && tnum <= LAST_LIST_TNUM &&
507 (tnum & IMMUTABLE)) {
508 ErrorMayQuit("List Assignment: <list> must be a mutable list", 0, 0);
509 }
510 (*AssListFuncs[TNUM_OBJ(list)])(list, pos, obj);
511 }
512
513
514 /****************************************************************************
515 **
516 *F ASS_MAT( <mat>, <row>, <col>, <obj> )
517 **
518 ** 'ASS_MAT' implements 'mat[row,col]:=obj', which for lists of lists
519 ** is defined as 'mat[row][col]:=obj', and for other kind of objects is
520 ** handled by method dispatch through the GAP operation 'ASS_LIST' with
521 ** three arguments.
522 */
523 void ASS_MAT(Obj list, Obj row, Obj col, Obj obj);
524
525
526 /****************************************************************************
527 **
528 *F ASSS_LIST(<list>,<poss>,<objs>) . . . . assign several elements to a list
529 *V AsssListFuncs[<type>] . . . . . . . . . . . table of assignment function
530 **
531 ** 'ASSS_LIST' assignes the objects from the list <objs> at the positions
532 ** given in the list <poss> to the list <list>. Note that the assignment
533 ** may change the length or the representation of <list>. An error is
534 ** signalled if <list> is not a list. It is the responsibility of the
535 ** caller to ensure that <poss> is a dense list of positive integers and
536 ** that <objs> is a dense list of the same length as <poss>.
537 **
538 ** A package implementing a list type <type> must provide such a function
539 ** and install it in 'AsssListFuncs[<type>]'. This function must extend the
540 ** <list> if any of the positions is larger than the length of <list> and
541 ** must also change the representation of <list> to that of a plain list if
542 ** necessary.
543 */
544 extern void (*AsssListFuncs[LAST_REAL_TNUM+1]) (Obj list, Obj poss, Obj objs);
545
546 void AsssListDefault(Obj list, Obj poss, Obj objs);
547
ASSS_LIST(Obj list,Obj poss,Obj objs)548 EXPORT_INLINE void ASSS_LIST(Obj list, Obj poss, Obj objs)
549 {
550 GAP_ASSERT(IS_POSS_LIST(poss));
551 GAP_ASSERT(IS_DENSE_LIST(objs));
552 GAP_ASSERT(LEN_LIST(poss) == LEN_LIST(objs));
553 UInt tnum = TNUM_OBJ(list);
554 if (FIRST_LIST_TNUM <= tnum && tnum <= LAST_LIST_TNUM &&
555 (tnum & IMMUTABLE)) {
556 ErrorMayQuit("List Assignments: <list> must be a mutable list", 0, 0);
557 }
558 (*AsssListFuncs[TNUM_OBJ(list)])(list, poss, objs);
559 }
560
561 /****************************************************************************
562 **
563 *F AssListObject( <list>, <pos>, <obj> ) . . . . . . . assign to list object
564 */
565 void AssListObject(Obj list, Int pos, Obj obj);
566
567
568 /****************************************************************************
569 **
570 *F IS_TABLE_LIST(<list>) . . . . . . . . . . . . . . . test for table lists
571 *V IsTableListFuncs[<type>] . . . . . . table of table list test functions
572 **
573 ** 'IS_TABLE_LIST' returns 1 if the list <list> is a table, i.e., a
574 ** homogeneous list of homogeneous lists of equal length, and 0 otherwise.
575 **
576 ** A package implementing a list type <type> must provide such a function
577 ** and install it in 'IsTableListFuncs[<type>]'. This function must loop
578 ** over the list and test whether all elements lie in the same family, are
579 ** homogenous lists, and have the same length, unless the type of the list
580 ** guarantees already that the list has this property.
581 */
582
583 extern Int (*IsTableListFuncs[LAST_REAL_TNUM+1]) ( Obj list );
584
IS_TABLE_LIST(Obj list)585 EXPORT_INLINE Int IS_TABLE_LIST(Obj list)
586 {
587 return (*IsTableListFuncs[TNUM_OBJ(list)])(list);
588 }
589
590 /****************************************************************************
591 **
592 *F IS_SSORT_LIST(<list>) . . . . . . . . . . test for strictly sorted lists
593 *V IsSSortListFuncs[<type>] . table of strictly sorted list test functions
594 **
595 ** 'IS_SSORT_LIST' returns 2 if the list <list> is a strictly sorted list
596 ** and 0 otherwise, i.e., if either <list> is not a list, or if it is not
597 ** strictly sorted.
598 **
599 ** A package implementing a list type <type> must provide such a function
600 ** and install it in 'IsSSortListFuncs[<type>]'. This function must loop
601 ** over the list and compare each element with the next one, unless the type
602 ** of the list guarantees already that the list is strictly sorted.
603 */
604
605 extern Int (*IsSSortListFuncs[LAST_REAL_TNUM+1]) ( Obj list );
606
IS_SSORT_LIST(Obj list)607 EXPORT_INLINE Int IS_SSORT_LIST(Obj list)
608 {
609 return (*IsSSortListFuncs[TNUM_OBJ(list)])(list);
610 }
611
612
613 /****************************************************************************
614 **
615 *F POS_LIST(<list>,<obj>,<start>) . . . . . . . . find an element in a list
616 *V PosListFuncs[<type>] . . . . . . . . . . . table of searching functions
617 **
618 ** 'POS_LIST' returns the position of the first occurrence of the object
619 ** <obj>, which may be an object of any type, in the list <list> after the
620 ** position <start> as GAP Integer. Fail is returned if <obj> is not in the
621 ** list after <start>. An error is signalled if <list> is not a list.
622 **
623 ** A package implementing a list type <type> must provide such a function
624 ** and install it in 'PosListFuncs[<type>]'.
625 */
626
627 extern Obj (*PosListFuncs[LAST_REAL_TNUM+1]) (Obj list, Obj obj, Obj start);
628
POS_LIST(Obj list,Obj obj,Obj start)629 EXPORT_INLINE Obj POS_LIST(Obj list, Obj obj, Obj start)
630 {
631 return (*PosListFuncs[TNUM_OBJ(list)])(list, obj, start);
632 }
633
634 /****************************************************************************
635 **
636 *F ElmListLevel(<lists>,<pos>,<level>) . . . . . . . . . . . . . . . . . . .
637 *F . . . . . . . . . . . . . select an element of several lists in parallel
638 **
639 ** 'ElmListLevel' assigns to '<lists>[<p_1>][<p_2>]...[<p_level>]' the value
640 ** '<lists>[<p_1>][<p_2>]...[<p_level>][<pos>]' for all appropriate tuples
641 ** of positions <p_1>,<p_2>,...,<p_level>. An error is signalled if for any
642 ** tuple of positions '<list> = <lists>[<p_1>][<p_2>]...[<p_level>]' is not
643 ** a list, <pos> is larger than the length of <list>, or <list> has no
644 ** assigned object at <pos>. It is the responsibility of the caller to
645 ** ensure that <pos> is a positive integer.
646 **
647 ** It is also the responsibility of the caller to ensure that <lists>,
648 ** '<lists>[<p_1>]', ..., '<lists>[<p_1>][<p_2>]...[<p_level-1>]' are all
649 ** dense lists with the same representation as plain lists. Usually <lists>
650 ** is the result of <level> nested applications of 'ELMS_LIST', so we
651 ** require 'ELMS_LIST' (resp. the functions implementing 'ELMS_LIST') to
652 ** satisfy this requirements.
653 */
654 void ElmListLevel(Obj lists, Obj pos, Int level);
655
656
657 /****************************************************************************
658 **
659 *F ElmsListLevel(<lists>,<poss>,<level>) . . . . . . . . . . . . . . . . . .
660 *F . . . . . . . . . . select several elements of several lists in parallel
661 **
662 ** 'ElmsListLevel' assigns to '<lists>[<p_1>][<p_2>]...[<p_level>]' the
663 ** objects '<lists>[<p_1>][<p_2>]...[<p_level>]{<poss>}' for all appropriate
664 ** tuples of positions <p_1>,<p_2>,...,<p_level>. An error is signalled if
665 ** for any tuple of positions '<list> = <lists>[<p_1>][<p_2>]...[<p_level>]'
666 ** is not a list, any of the positions of <poss> is larger than the length
667 ** of <list>, or <list> has no assigned object at any of the positions. It
668 ** is also the responsibility of the caller to ensure that <poss> is a dense
669 ** list of positive integers.
670 **
671 ** It is also the responsibility of the caller to ensure that <lists>,
672 ** '<lists>[<p_1>]', ..., '<lists>[<p_1>][<p_2>]...[<p_level-1>]' are all
673 ** dense lists with the same representation as plain lists. Usually <lists>
674 ** is the result of <level> nested applications of 'ELMS_LIST', so we
675 ** require 'ELMS_LIST' (resp. the functions implementing 'ELMS_LIST') to
676 ** satisfy this requirements.
677 */
678 void ElmsListLevel(Obj lists, Obj poss, Int level);
679
680
681 /****************************************************************************
682 **
683 *F AssListLevel(<lists>,<pos>,<objs>,<level>) . . . . . . . . . . . . . . .
684 *F . . . . . . . . . . . . . assign an element to several lists in parallel
685 **
686 ** 'AssListLevel' assigns to '<lists>[<p_1>][<p_2>]...[<p_level>][<pos>]'
687 ** the value '<objs>[<p_1>][<p_2>]...[<p_level>]' for all appropriate tuples
688 ** of positions <p_1>,<p_2>,...,<p_level>. An error is signalled if for any
689 ** tuple of positions '<list> = <lists>[<p_1>][<p_2>]...[<p_level>]' is not
690 ** a list, '<obj> = <objs>[<p_1>][<p_2>]...[<p_i-1>]' is not a dense list,
691 ** or <obj> has not the same length as '<list>[<p_1>][<p_2>]...[<p_i-1>]'.
692 ** It is the responsibility of the caller to ensure that <pos> is a positive
693 ** integer.
694 **
695 ** It is also the responsibility of the caller to ensure that <lists>,
696 ** '<lists>[<p_1>]', ..., '<lists>[<p_1>][<p_2>]...[<p_level-1>]' are all
697 ** dense lists with the same representation as plain lists. Usually <lists>
698 ** is the result of <level> nested applications of 'ELMS_LIST', so we
699 ** require 'ELMS_LIST' (resp. the functions implementing 'ELMS_LIST') to
700 ** satisfy this requirements.
701 */
702 void AssListLevel(Obj lists, Obj pos, Obj objs, Int level);
703
704
705 /****************************************************************************
706 **
707 *F AsssListLevel(<lists>,<poss>,<objs>,<level>) . . . . . . . . . . . . . .
708 *F . . . . . . . . . . assign several elements to several lists in parallel
709 **
710 ** 'AsssListLevel' assigns to '<lists>[<p_1>][<p_2>]...[<p_level>]{<poss>}'
711 ** the objects '<objs>[<p_1>][<p_2>]...[<p_level>]' for all appropriate
712 ** tuples of positions <p_1>,<p_2>,...,<p_level>. An error is signalled if
713 ** for any tuple of positions '<list> = <lists>[<p_1>][<p_2>]...[<p_level>]'
714 ** is not a list, '<obj> = <objs>[<p_1>][<p_2>]...[<p_i-1>]' is not a dense
715 ** list, <obj> has not the same length as '<list>[<p_1>][<p_2>]...[<p_i-1>]'
716 ** or '<objs>[<p_1>][<p_2>]...[<p_level>]' is not a dense list of the same
717 ** length as <poss>. It is the responsibility of the caller to ensure that
718 ** <poss> is a dense list of positive integers.
719 **
720 ** It is also the responsibility of the caller to ensure that <lists>,
721 ** '<lists>[<p_1>]', ..., '<lists>[<p_1>][<p_2>]...[<p_level-1>]' are all
722 ** dense lists with the same representation as plain lists. Usually <lists>
723 ** is the result of <level> nested applications of 'ELMS_LIST', so we
724 ** require 'ELMS_LIST' (resp. the functions implementing 'ELMS_LIST') to
725 ** satisfy this requirements.
726 */
727 void AsssListLevel(Obj lists, Obj poss, Obj objs, Int lev);
728
729
730 /****************************************************************************
731 **
732 *F PLAIN_LIST(<list>) . . . . . . . . . . . convert a list to a plain list
733 *V PlainListFuncs[<type>] . . . . . . . . . . table of conversion functions
734 **
735 ** 'PLAIN_LIST' changes the representation of the list <list> to that of a
736 ** plain list. An error is signalled if <list> is not a list.
737 **
738 ** A package implementing a list type <type> must provide such a function
739 ** and install it in 'PlainListFuncs[<type>]'.
740 */
741
742 extern void (*PlainListFuncs[LAST_REAL_TNUM+1]) ( Obj list );
743
PLAIN_LIST(Obj list)744 EXPORT_INLINE void PLAIN_LIST(Obj list)
745 {
746 ((*PlainListFuncs[TNUM_OBJ(list)])(list));
747 }
748
749
750 /****************************************************************************
751 **
752 *F TYPES_LIST_FAM(<fam>) . . . . . . . list of types of lists over a family
753 */
754 Obj TYPES_LIST_FAM(Obj fam);
755
756
757 /****************************************************************************
758 **
759 *F * * * * * * * * * * * * * important filters * * * * * * * * * * * * * * *
760 */
761
762 typedef enum {
763 /** filter number for 'IsSSortedList' */
764 FN_IS_SSORT,
765
766 /** filter number for 'IsNSortedList' */
767 FN_IS_NSORT,
768
769 /** filter number for 'IsDenseList' */
770 FN_IS_DENSE,
771
772 /** filter number for 'IsNDenseList' */
773 FN_IS_NDENSE,
774
775 /** filter number for 'IsHomogeneousList' */
776 FN_IS_HOMOG,
777
778 /** filter number for 'IsNonHomogeneousList' */
779 FN_IS_NHOMOG,
780
781 /** filter number for 'IsTable' */
782 FN_IS_TABLE,
783
784 /** filter number for 'IsRectangularTable' */
785 FN_IS_RECT,
786
787 LAST_FN = FN_IS_RECT
788 } FilterNumber;
789
790
791 /****************************************************************************
792 **
793 *V SetFiltListTNums[ <tnum> ][ <fnum> ] . . . . . new tnum after filter set
794 **
795 ** If a list with type number <tnum> gains the filter with filter number
796 ** <fnum>, then the new type number is stored in:
797 **
798 ** 'SetFiltListTNums[<tnum>][<fnum>]'
799 **
800 ** 'SET_FILT_LIST' is used to set the filter for a list by changing its
801 ** type number.
802 **
803 ** Two values are treated specially:
804 ** 0 : The default. This tnum should not change.
805 ** (UInt)-1 : It is an error to apply this filter (for example,
806 ** marking an empty list as not sorted)
807 */
808 extern UInt SetFiltListTNums [ LAST_REAL_TNUM ] [ LAST_FN + 1 ];
809
810
811 /****************************************************************************
812 **
813 *F SET_FILT_LIST( <list>, <fnum> ) . . . . . . . . . . . . . . set a filter
814 */
SET_FILT_LIST(Obj list,FilterNumber fn)815 EXPORT_INLINE void SET_FILT_LIST(Obj list, FilterNumber fn)
816 {
817 UInt n = SetFiltListTNums[TNUM_OBJ(list)][fn];
818 if (n == 0) {
819 return;
820 }
821 if (n != (UInt)-1)
822 RetypeBagIfWritable(list, n);
823 else {
824 Pr("#E SET_FILT_LIST[%s][%d]\n", (Int)TNAM_OBJ(list), fn);
825 }
826 }
827
828 /****************************************************************************
829 **
830 *F SET_FILTER_LIST( <list>, <filter> ) . . . . . . . . . . . . . set filter
831 */
832 Obj SET_FILTER_LIST(Obj list, Obj filter);
833
834 /****************************************************************************
835 **
836 *V ResetFiltListTNums[ <tnum> ][ <fnum> ] . . . new tnum after filter reset
837 **
838 ** If a list with type number <tnum> loses the filter with filter number
839 ** <fnum>, then the new type number is stored in:
840 **
841 ** 'ResetFiltListTNums[<tnum>][<fnum>]'
842 **
843 ** 'RESET_FILT_LIST' is used to set the filter for a list by changing its
844 ** type number.
845 **
846 ** The same special values are used as SetFiltListTNums.
847 */
848 extern UInt ResetFiltListTNums [ LAST_REAL_TNUM ] [ LAST_FN + 1 ];
849
850
851 /****************************************************************************
852 **
853 *F RESET_FILT_LIST( <list>, <fnum> ) . . . . . . . . . . . . reset a filter
854 */
RESET_FILT_LIST(Obj list,FilterNumber fn)855 EXPORT_INLINE void RESET_FILT_LIST(Obj list, FilterNumber fn)
856 {
857 UInt n = ResetFiltListTNums[TNUM_OBJ(list)][fn];
858 if (n == 0) {
859 return;
860 }
861 if (n != (UInt)-1)
862 RetypeBag(list, n);
863 else {
864 Pr("#E RESET_FILT_LIST[%s][%d]\n", (Int)TNAM_OBJ(list), fn);
865 }
866 }
867
868 /****************************************************************************
869 **
870 *V HasFiltListTNums[ <tnum> ][ <fnum> ] . . . . . . . . . . . . has filter
871 */
872 extern Int HasFiltListTNums [ LAST_REAL_TNUM ] [ LAST_FN + 1 ];
873
874
875 /****************************************************************************
876 **
877 *F HAS_FILT_LIST( <list>, <fnum> ) . . . . . . . . . . . . . . . has filter
878 */
879 #define HAS_FILT_LIST(list,fn) HasFiltListTNums[TNUM_OBJ(list)][fn]
880
881
882 /****************************************************************************
883 **
884 *V ClearFiltsTNums[ <tnum> ] . . . . . . . . . . . . clear all list filters
885 **
886 ** The type number without any known properties of a list of type number
887 ** <tnum> is stored in:
888 **
889 ** 'ClearPropsTNums[<tnum>]'
890 **
891 ** 'CLEAR_PROPS_LIST' is used to clear all properties of a list.
892 */
893 extern UInt ClearFiltsTNums [ LAST_REAL_TNUM ];
894
895
896 /****************************************************************************
897 **
898 *F CLEAR_FILTS_LIST( <list> ) . . . . . . . . . . . . . . clear properties
899 */
CLEAR_FILTS_LIST(Obj list)900 EXPORT_INLINE void CLEAR_FILTS_LIST(Obj list)
901 {
902 UInt n = ClearFiltsTNums[TNUM_OBJ(list)];
903 if (n > 0) {
904 RetypeBag(list, n);
905 }
906 }
907
908
909 /****************************************************************************
910 **
911 *F * * * * * * * * * * * functions with checking * * * * * * * * * * * * * *
912 */
913
914
915 /****************************************************************************
916 **
917 *F AsssListCheck( <list>, <poss>, <rhss> ) . . . . . . . . . . . . ASSS_LIST
918 */
919 void AsssListCheck(Obj list, Obj poss, Obj rhss);
920
921
922 /****************************************************************************
923 **
924 *F AsssListLevelCheck( <lists>, <poss>, <rhss>, <level> ) . . AsssListLevel
925 */
926 void AsssListLevelCheck(Obj lists, Obj poss, Obj rhss, Int level);
927
928
929 /****************************************************************************
930 **
931 *F * * * * * * * * * * * * * initialize module * * * * * * * * * * * * * * *
932 */
933
934
935 /****************************************************************************
936 **
937 *F InitInfoLists() . . . . . . . . . . . . . . . . . table of init functions
938 */
939 StructInitInfo * InitInfoLists ( void );
940
941
942 #endif // GAP_LISTS_H
943