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 contains the functions that deal with ranges.
11 **
12 ** A *range* is a list without holes consisting of consecutive integers.
13 ** For the full definition of ranges see chapter "Ranges" in the GAP Manual.
14 ** Read also "More about Ranges" about the different representation of
15 ** ranges.
16 **
17 ** A list that is known to be a range is represented by a bag of type
18 ** 'T_RANGE', which has the following format:
19 **
20 ** +-------+-------+-------+
21 ** |logical| first | incr- |
22 ** | length|element| ement |
23 ** +-------+-------+-------+
24 **
25 ** The first entry is the handle of the logical length. The second entry is
26 ** the first element of the range. The last entry is the increment. All
27 ** three are represented as immediate GAP integers.
28 **
29 ** The element at position <pos> is thus simply <first> + (<pos>-1) * <inc>.
30 **
31 ** Note that a list represented by a bag of type 'T_PLIST' might still be a
32 ** range. It is just that the kernel does not know this.
33 **
34 ** This package consists of three parts.
35 **
36 ** The first part consists of the macros 'NEW_RANGE', 'IS_RANGE',
37 ** 'SET_LEN_RANGE', 'GET_LEN_RANGE', 'SET_LOW_RANGE', 'GET_LOW_RANGE',
38 ** 'SET_INC_RANGE', 'GET_INC_RANGE', and 'GET_ELM_RANGE'. They determine
39 ** the representation of ranges. Everything else in this file and the rest
40 ** of the {\GAP} kernel uses those macros to access and modify ranges.
41 **
42 ** The second part consists of the functions 'LenRange', 'ElmRange',
43 ** 'ElmsRange', 'AssRange', 'AsssRange', 'PosRange', 'PlainRange',
44 ** 'IsPossRange', 'PrintRange', 'EqRange', and 'LtRange'.
45 ** They are the functions required by the generic lists package. Using
46 ** these functions the other parts of the {\GAP} kernel can access or modify
47 ** ranges without actually being aware that they are dealing with a range.
48 **
49 ** The third part consists ...
50 */
51
52 #include "range.h"
53
54 #include "ariths.h"
55 #include "bool.h"
56 #include "error.h"
57 #include "gaputils.h"
58 #include "io.h"
59 #include "lists.h"
60 #include "modules.h"
61 #include "opers.h"
62 #include "plist.h"
63 #include "saveload.h"
64
65
66 /****************************************************************************
67 **
68 *F TypeRangeNSort( <range> ) . . . . . . . . . . . . . . . . type of a range
69 **
70 ** 'TypeRangeNSort' is the function in 'TypeObjFuncs' for ranges which are
71 ** not strictly sorted.
72 */
73 static Obj TYPE_RANGE_NSORT_IMMUTABLE;
74 static Obj TYPE_RANGE_NSORT_MUTABLE;
75
TypeRangeNSort(Obj list)76 static Obj TypeRangeNSort(Obj list)
77 {
78 return IS_MUTABLE_OBJ(list) ? TYPE_RANGE_NSORT_MUTABLE
79 : TYPE_RANGE_NSORT_IMMUTABLE;
80 }
81
82
83 /****************************************************************************
84 **
85 *F TypeRangeSSort( <range> ) . . . . . . . . . . . . . . . . type of a range
86 **
87 ** 'TypeRangeSSort' is the function in 'TypeObjFuncs' for ranges which are
88 ** strictly sorted.
89 */
90 static Obj TYPE_RANGE_SSORT_IMMUTABLE;
91 static Obj TYPE_RANGE_SSORT_MUTABLE;
92
TypeRangeSSort(Obj list)93 static Obj TypeRangeSSort(Obj list)
94 {
95 return IS_MUTABLE_OBJ(list) ? TYPE_RANGE_SSORT_MUTABLE
96 : TYPE_RANGE_SSORT_IMMUTABLE;
97 }
98
99
100 #if !defined(USE_THREADSAFE_COPYING)
101
102 /****************************************************************************
103 **
104 *F CopyRange( <list>, <mut> ) . . . . . . . . . . . . . . . . copy a range
105 **
106 ** 'CopyRange' returns a structural (deep) copy of the range <list>, i.e., a
107 ** recursive copy that preserves the structure.
108 **
109 ** If <list> has not yet been copied, it makes a copy, leaves a forward
110 ** pointer to the copy in the first entry of the range, where the size of
111 ** the range usually resides, and copies the other entries. If the range
112 ** has already been copied, it returns the value of the forwarding pointer.
113 **
114 ** 'CopyRange' is the function in 'CopyObjFuncs' for ranges.
115 */
CopyRange(Obj list,Int mut)116 static Obj CopyRange(Obj list, Int mut)
117 {
118 Obj copy; /* copy, result */
119
120 // immutable input is handled by COPY_OBJ
121 GAP_ASSERT(IS_MUTABLE_OBJ(list));
122
123 /* make a copy */
124 copy = NewBag(TNUM_OBJ(list), SIZE_OBJ(list));
125 if (!mut)
126 MakeImmutableNoRecurse(copy);
127 ADDR_OBJ(copy)[0] = CONST_ADDR_OBJ(list)[0];
128
129 /* leave a forwarding pointer */
130 PrepareCopy(list, copy);
131
132 /* copy the subvalues */
133 ADDR_OBJ(copy)[1] = CONST_ADDR_OBJ(list)[1];
134 ADDR_OBJ(copy)[2] = CONST_ADDR_OBJ(list)[2];
135
136 /* return the copy */
137 return copy;
138 }
139
140 #endif // !defined(USE_THREADSAFE_COPYING)
141
142
143 /****************************************************************************
144 **
145 *F PrintRange(<list>) . . . . . . . . . . . . . . . . . . . . print a range
146 **
147 ** 'PrintRange' prints the range <list>.
148 **
149 ** 'PrintRange' handles bags of type 'T_RANGE'.
150 */
PrintRange(Obj list)151 static void PrintRange(Obj list)
152 {
153 Pr( "%2>[ %2>%d",
154 GET_LOW_RANGE(list), 0L );
155 if ( GET_INC_RANGE(list) != 1 ) {
156 Pr( "%<,%< %2>%d",
157 GET_LOW_RANGE(list)+GET_INC_RANGE(list), 0L );
158 }
159 Pr( "%2< .. %2>%d%4< ]",
160 GET_LOW_RANGE(list)+(GET_LEN_RANGE(list)-1)*GET_INC_RANGE(list), 0L );
161 }
162
163
164 /****************************************************************************
165 **
166 *F EqRange(<listL>,<listR>) . . . . . . . . . test if two ranges are equal
167 **
168 ** 'EqRange' returns 'true' if the two ranges <listL> and <listR> are equal
169 ** and 'false' otherwise.
170 */
EqRange(Obj listL,Obj listR)171 static Int EqRange(Obj listL, Obj listR)
172 {
173 return ( GET_LEN_RANGE(listL) == GET_LEN_RANGE(listR)
174 && GET_LOW_RANGE(listL) == GET_LOW_RANGE(listR)
175 && GET_INC_RANGE(listL) == GET_INC_RANGE(listR) );
176 }
177
178
179 /****************************************************************************
180 **
181 *F LtRange(<listL>,<listR>) . . . . . . . . . test if two ranges are equal
182 **
183 ** 'LtRange' returns 'true' if the range <listL> is less than the range
184 ** <listR> and 'false' otherwise.
185 */
LtRange(Obj listL,Obj listR)186 static Int LtRange(Obj listL, Obj listR)
187 {
188 /* first compare the first elements */
189 if ( GET_LOW_RANGE(listL) < GET_LOW_RANGE(listR) )
190 return 1L;
191 else if ( GET_LOW_RANGE(listR) < GET_LOW_RANGE(listL) )
192 return 0L;
193
194 /* next compare the increments (or the second elements) */
195 if ( GET_INC_RANGE(listL) < GET_INC_RANGE(listR) )
196 return 1L;
197 else if ( GET_INC_RANGE(listR) < GET_INC_RANGE(listL) )
198 return 0L;
199
200 /* finally compare the lengths */
201 if ( GET_LEN_RANGE(listL) < GET_LEN_RANGE(listR) )
202 return 1L;
203 else if ( GET_LEN_RANGE(listR) < GET_LEN_RANGE(listL) )
204 return 0L;
205
206 /* the two ranges are equal */
207 return 0L;
208 }
209
210
211 /****************************************************************************
212 **
213 *F LenRange(<list>) . . . . . . . . . . . . . . . . . . . length of a range
214 **
215 ** 'LenRange' returns the length of the range <list> as a C integer.
216 **
217 ** 'LenRange' is the function in 'LenListFuncs' for ranges.
218 */
LenRange(Obj list)219 static Int LenRange(Obj list)
220 {
221 return GET_LEN_RANGE( list );
222 }
223
224
225 /****************************************************************************
226 **
227 *F IsbRange(<list>,<pos>) . . . . . . . . test for an element from a range
228 **
229 ** 'IsbRange' returns 1 if the range has an element at the position <pos>
230 ** and 0 otherwise. It is the responsibility of the caller to ensure that
231 ** <pos> is a positive integer.
232 **
233 ** 'IsbRange' is the function in 'IsbListFuncs' for ranges.
234 */
IsbRange(Obj list,Int pos)235 static Int IsbRange(Obj list, Int pos)
236 {
237 return (pos <= GET_LEN_RANGE(list));
238 }
239
240
241 /****************************************************************************
242 **
243 *F Elm0Range(<list>,<pos>) . . . . . . . . . . select an element of a range
244 *F Elm0vRange(<list>,<pos>) . . . . . . . . . select an element of a range
245 **
246 ** 'Elm0Range' returns the element at the position <pos> of the range
247 ** <list>, or 0 if <list> has no assigned object at <pos>. It is the
248 ** responsibility of the caller to ensure that <pos> is a positive integer.
249 **
250 ** 'Elm0vRange' does the same thing than 'Elm0Range', but need not check
251 ** that <pos> is less than or equal to the length of <list>, this is the
252 ** responsibility of the caller.
253 */
Elm0Range(Obj list,Int pos)254 static Obj Elm0Range(Obj list, Int pos)
255 {
256 if ( pos <= GET_LEN_RANGE( list ) ) {
257 return GET_ELM_RANGE( list, pos );
258 }
259 else {
260 return 0;
261 }
262 }
263
Elm0vRange(Obj list,Int pos)264 static Obj Elm0vRange(Obj list, Int pos)
265 {
266 return GET_ELM_RANGE( list, pos );
267 }
268
269
270 /****************************************************************************
271 **
272 *F ElmRange(<list>,<pos>) . . . . . . . . . . select an element of a range
273 **
274 ** 'ElmRange' selects the element at position <pos> of the range <list>. It
275 ** is the responsibility of the caller to ensure that <pos> is a positive
276 ** integer. An error is signaller if <pos> is larger than the length of
277 ** <list>.
278 **
279 ** 'ElmvRange' does the same thing than 'ElmRange', but need not check that
280 ** <pos> is less than or equal to the length of <list>, this is the
281 ** responsibility of the caller.
282 **
283 ** 'ElmRange' is the function in 'ElmListFuncs' for ranges. 'ElmvRange' is
284 ** the function in 'ElmvListFuncs' for ranges.
285 */
ElmRange(Obj list,Int pos)286 static Obj ElmRange(Obj list, Int pos)
287 {
288 /* check the position */
289 if ( GET_LEN_RANGE( list ) < pos ) {
290 ErrorMayQuit("List Element: <list>[%d] must have an assigned value",
291 (Int)pos, 0);
292 }
293
294 /* return the selected element */
295 return GET_ELM_RANGE( list, pos );
296 }
297
ElmvRange(Obj list,Int pos)298 static Obj ElmvRange(Obj list, Int pos)
299 {
300 return GET_ELM_RANGE( list, pos );
301 }
302
303
304 /****************************************************************************
305 **
306 *F ElmsRange(<list>,<poss>) . . . . . . . . . select a sublist from a range
307 **
308 ** 'ElmsRange' returns a new list containing the elements at the positions
309 ** given in the list <poss> from the range <list>. It is the responsibility
310 ** of the caller to ensure that <poss> is dense and contains only positive
311 ** integers. An error is signalled if an element of <poss> is larger than
312 ** the length of <list>.
313 **
314 ** 'ElmsRange' is the function in 'ElmsListFuncs' for ranges.
315 */
ElmsRange(Obj list,Obj poss)316 static Obj ElmsRange(Obj list, Obj poss)
317 {
318 Obj elms; /* selected sublist, result */
319 Int lenList; /* length of <list> */
320 Obj elm; /* one element from <list> */
321 Int lenPoss; /* length of <positions> */
322 Int pos; /* <position> as integer */
323 Int inc; /* increment in a range */
324 Int i; /* loop variable */
325
326 /* general code */
327 if ( ! IS_RANGE(poss) ) {
328
329 /* get the length of <list> */
330 lenList = GET_LEN_RANGE( list );
331
332 /* get the length of <positions> */
333 lenPoss = LEN_LIST( poss );
334
335 /* make the result list */
336 elms = NEW_PLIST( T_PLIST, lenPoss );
337 SET_LEN_PLIST( elms, lenPoss );
338
339 /* loop over the entries of <positions> and select */
340 for ( i = 1; i <= lenPoss; i++ ) {
341
342 /* get <position> */
343 Obj p = ELMW_LIST(poss, i);
344 if (!IS_INTOBJ(p)) {
345 ErrorMayQuit("List Elements: position is too large for "
346 "this type of list",
347 0, 0);
348 }
349 pos = INT_INTOBJ(p);
350
351 /* select the element */
352 if ( lenList < pos ) {
353 ErrorMayQuit(
354 "List Elements: <list>[%d] must have an assigned value",
355 (Int)pos, 0);
356 }
357
358 /* select the element */
359 elm = GET_ELM_RANGE( list, pos );
360
361 /* assign the element into <elms> */
362 SET_ELM_PLIST( elms, i, elm );
363
364 }
365
366 }
367
368 /* special code for ranges */
369 else {
370
371 /* get the length of <list> */
372 lenList = GET_LEN_RANGE( list );
373
374 /* get the length of <positions>, the first elements, and the inc. */
375 lenPoss = GET_LEN_RANGE( poss );
376 pos = GET_LOW_RANGE( poss );
377 inc = GET_INC_RANGE( poss );
378
379 /* check that no <position> is larger than 'LEN_LIST(<list>)' */
380 if ( lenList < pos ) {
381 ErrorMayQuit(
382 "List Elements: <list>[%d] must have an assigned value",
383 (Int)pos, 0);
384 }
385 if ( lenList < pos + (lenPoss-1) * inc ) {
386 ErrorMayQuit(
387 "List Elements: <list>[%d] must have an assigned value",
388 (Int)(pos + (lenPoss - 1) * inc), 0);
389 }
390
391 /* make the result range */
392 if ( 0 < inc * GET_INC_RANGE(list) )
393 elms = NEW_RANGE_SSORT();
394 else
395 elms = NEW_RANGE_NSORT();
396 SET_LEN_RANGE( elms, lenPoss );
397 SET_LOW_RANGE( elms, INT_INTOBJ( GET_ELM_RANGE( list, pos ) ) );
398 SET_INC_RANGE( elms, inc * GET_INC_RANGE( list ) );
399
400 }
401
402 /* return the result */
403 return elms;
404 }
405
406
407 /****************************************************************************
408 **
409 *F UnbRange( <list>, <pos> ) . . . . unbind an element from a range
410 **
411 ** This is to avoid unpacking of the range to a plain list when <pos> is
412 ** larger or equal to the length of <list>.
413 */
UnbRange(Obj list,Int pos)414 static void UnbRange(Obj list, Int pos)
415 {
416 GAP_ASSERT(IS_MUTABLE_OBJ(list));
417 const Int len = GET_LEN_RANGE(list);
418 if (len == pos && len > 2) {
419 SET_LEN_RANGE(list, len - 1);
420 }
421 else if (pos <= len) {
422 PLAIN_LIST(list);
423 UNB_LIST(list, pos);
424 }
425 }
426
427
428 /****************************************************************************
429 **
430 *F AssRange(<list>,<pos>,<val>) . . . . . . . . . . . . . assign to a range
431 **
432 ** 'AssRange' assigns the value <val> to the range <list> at the position
433 ** <pos>. It is the responsibility of the caller to ensure that <pos> is
434 ** positive, and that <val> is not 0.
435 **
436 ** 'AssRange' is the function in 'AssListFuncs' for ranges.
437 **
438 ** 'AssRange' simply converts the range into a plain list, and then does the
439 ** same stuff as 'AssPlist'. This is because a range is not very likely to
440 ** stay a range after the assignment.
441 */
AssRange(Obj list,Int pos,Obj val)442 static void AssRange(Obj list, Int pos, Obj val)
443 {
444 /* convert the range into a plain list */
445 PLAIN_LIST( list );
446 RetypeBag( list, T_PLIST );
447
448 /* resize the list if necessary */
449 if ( LEN_PLIST( list ) < pos ) {
450 GROW_PLIST( list, pos );
451 SET_LEN_PLIST( list, pos );
452 }
453
454 /* now perform the assignment and return the assigned value */
455 SET_ELM_PLIST( list, pos, val );
456 CHANGED_BAG( list );
457 }
458
459
460 /****************************************************************************
461 **
462 *F AsssRange(<list>,<poss>,<vals>) . . . assign several elements to a range
463 **
464 ** 'AsssRange' assignes the values from the list <vals> at the positions
465 ** given in the list <poss> to the range <list>. It is the responsibility
466 ** of the caller to ensure that <poss> is dense and contains only positive
467 ** integers, that <poss> and <vals> have the same length, and that <vals> is
468 ** dense.
469 **
470 ** 'AsssRange' is the function in 'AsssListFuncs' for ranges.
471 **
472 ** 'AsssRange' simply converts the range to a plain list and then does the
473 ** same stuff as 'AsssPlist'. This is because a range is not very likely to
474 ** stay a range after the assignment.
475 */
AsssRange(Obj list,Obj poss,Obj vals)476 static void AsssRange(Obj list, Obj poss, Obj vals)
477 {
478 /* convert <list> to a plain list */
479 PLAIN_LIST( list );
480 RetypeBag( list, T_PLIST );
481
482 /* and delegate */
483 ASSS_LIST( list, poss, vals );
484 }
485
486
487 /****************************************************************************
488 **
489 *F IsPossRange(<list>) . . . . . . . positions list test function for ranges
490 **
491 ** 'IsPossRange' returns 1 if the range <list> is a dense list containing
492 ** only positive integers, and 0 otherwise.
493 **
494 ** 'IsPossRange' is the function in 'IsPossListFuncs' for ranges.
495 */
IsPossRange(Obj list)496 static Int IsPossRange(Obj list)
497 {
498 /* test if the first element is positive */
499 if ( GET_LOW_RANGE( list ) <= 0 )
500 return 0;
501
502 /* test if the last element is positive */
503 if ( INT_INTOBJ( GET_ELM_RANGE( list, GET_LEN_RANGE(list) ) ) <= 0 )
504 return 0;
505
506 /* otherwise <list> is a positions list */
507 return 1;
508 }
509
510
511 /****************************************************************************
512 **
513 *F PosRange(<list>,<val>,<start>) . . . . position of an element in a range
514 **
515 ** 'PosRange' returns the position of the value <val> in the range <list>
516 ** after the first position <start> as a GAP integer. Fail is returned if <val>
517 ** is not in the list.
518 **
519 ** 'PosRange' is the function in 'PosListFuncs' for ranges.
520 */
PosRange(Obj list,Obj val,Obj start)521 Obj PosRange (
522 Obj list,
523 Obj val,
524 Obj start )
525 {
526 Int k; /* position, result */
527 Int lenList; /* length of <list> */
528 Int low; /* first element of <list> */
529 Int inc; /* increment of <list> */
530 Int v; /* numerical value of <val> */
531 Int istart;
532
533 /* if the starting position is too big to be a small int
534 then there can't be anything to find */
535 if (!IS_INTOBJ(start))
536 return Fail;
537
538 istart = INT_INTOBJ(start);
539 /* get the length, the first element, and the increment of <list> */
540 lenList = GET_LEN_RANGE(list);
541 low = GET_LOW_RANGE(list);
542 inc = GET_INC_RANGE(list);
543
544 // look for an integer, and not beyond the list end
545 if ( IS_INTOBJ(val) && istart < lenList ) {
546 v = INT_INTOBJ(val);
547 if ( 0 < inc
548 && low + istart * inc <= v && v <= low + (lenList-1) * inc
549 && (v - low) % inc == 0 ) {
550 k = (v - low) / inc + 1;
551 }
552 else if ( inc < 0
553 && low + (lenList-1) * inc <= v && v <= low + istart * inc
554 && (v - low) % inc == 0 ) {
555 k = (v - low) / inc + 1;
556 }
557 else {
558 k = 0;
559 }
560 }
561
562 /* otherwise it can not be an element of the range */
563 else {
564 k = 0;
565 }
566
567 /* return the position */
568 return k == 0 ? Fail : INTOBJ_INT(k);
569 }
570
571
572 /****************************************************************************
573 **
574 *F PlainRange(<list>) . . . . . . . . . . . convert a range to a plain list
575 **
576 ** 'PlainRange' converts the range <list> to a plain list.
577 **
578 ** 'PlainRange' is the function in 'PlainListFuncs' for ranges.
579 */
PlainRange(Obj list)580 static void PlainRange(Obj list)
581 {
582 Int lenList; /* length of <list> */
583 Int low; /* first element of <list> */
584 Int inc; /* increment of <list> */
585 Int i; /* loop variable */
586
587 /* get the length, the first element, and the increment of <list> */
588 lenList = GET_LEN_RANGE( list );
589 low = GET_LOW_RANGE( list );
590 inc = GET_INC_RANGE( list );
591
592 /* change the type of the list, and allocate enough space */
593 RetypeBagSM( list, T_PLIST );
594 GROW_PLIST( list, lenList );
595 SET_LEN_PLIST( list, lenList );
596
597 /* enter the values in <list> */
598 for ( i = 1; i <= lenList; i++ ) {
599 SET_ELM_PLIST( list, i, INTOBJ_INT( low + (i-1) * inc ) );
600 }
601 }
602
603
604 /****************************************************************************
605 **
606 *F IsRange(<list>) . . . . . . . . . . . . . . . . test if a list is a range
607 **
608 ** 'IsRange' returns 1 if the list with the handle <list> is a range and 0
609 ** otherwise. As a side effect 'IsRange' converts proper ranges represented
610 ** the ordinary way to the compact representation.
611 */
612 static Obj IsRangeFilt;
613
IsRange(Obj list)614 static Int IsRange(Obj list)
615 {
616 Int isRange; /* result of the test */
617 Int len; /* logical length of list */
618 Int low; /* value of first element of range */
619 Int inc; /* increment */
620 Int i; /* loop variable */
621
622 /* if <list> is represented as a range, it is of course a range */
623 if ( TNUM_OBJ(list) == T_RANGE_NSORT
624 || TNUM_OBJ(list) == T_RANGE_SSORT ) {
625 isRange = 1;
626 }
627
628 /* if <list> is not a list, it is not a range at the moment */
629 else if ( ! IS_SMALL_LIST( list ) ) {
630 /* isRange = 0; */
631 isRange = (DoFilter(IsRangeFilt, list) == True);
632 }
633
634 /* if <list> is the empty list, it is a range by definition */
635 else if ( LEN_LIST(list) == 0 ) {
636 isRange = 1;
637 }
638
639 /* if <list> is a list with just one integer, it is also a range */
640 else if ( LEN_LIST(list)==1 && IS_INTOBJ(ELMW_LIST(list,1)) ) {
641 isRange = 1;
642 }
643
644 /* if the first element is not an integer, it is not a range */
645 else if ( ELMV0_LIST(list,1)==0 || !IS_INTOBJ(ELMW_LIST(list,1)) ) {
646 isRange = 0;
647 }
648
649 /* if the second element is not an integer, it is not a range */
650 else if ( ELMV0_LIST(list,2)==0 || !IS_INTOBJ(ELMW_LIST(list,2)) ) {
651 isRange = 0;
652 }
653
654 /* if the first and the second element are equal it is also not a range*/
655 else if ( ELMW_LIST(list,1) == ELMW_LIST(list,2) ) {
656 isRange = 0;
657 }
658
659 /* otherwise, test if the elements are consecutive integers */
660 else {
661
662 /* get the logical length of the list */
663 len = LEN_LIST(list);
664 low = INT_INTOBJ( ELMW_LIST( list, 1 ) );
665 inc = INT_INTOBJ( ELMW_LIST( list, 2 ) ) - low;
666
667 /* test all entries against the first one */
668 for ( i = 3; i <= len; i++ ) {
669 if ( ELMV0_LIST(list,i) != INTOBJ_INT( low + (i-1) * inc ) )
670 break;
671 }
672
673 /* if <list> is a range, convert to the compact representation */
674 isRange = (len < i);
675 if ( isRange ) {
676 RetypeBagSM( list, (0 < inc ? T_RANGE_SSORT : T_RANGE_NSORT) );
677 ResizeBag( list, 3 * sizeof(Obj) );
678 SET_LEN_RANGE( list, len );
679 SET_LOW_RANGE( list, low );
680 SET_INC_RANGE( list, inc );
681 }
682
683 }
684
685 /* return the result of the test */
686 return isRange;
687 }
688
689
690 /****************************************************************************
691 **
692 *F FuncIsRange(<self>,<obj>) . . . . . . . . . . . . . . . test for a range
693 **
694 ** 'FuncIsRange' implements the internal function 'IsRange'.
695 **
696 ** 'IsRange( <obj> )'
697 **
698 ** 'IsRange' returns 'true' if <obj>, which may be an object of any type, is
699 ** a range and 'false' otherwise. A range is a list without holes such that
700 ** the elements are consecutive integers.
701 */
FiltIS_RANGE(Obj self,Obj obj)702 static Obj FiltIS_RANGE(Obj self, Obj obj)
703 {
704 /* let 'IsRange' do the work for lists */
705 return IsRange(obj) ? True : False;
706 }
707
708
709 /****************************************************************************
710 **
711 *F SaveRange( <range> )
712 **
713 */
714
SaveRange(Obj range)715 static void SaveRange(Obj range)
716 {
717 SaveSubObj(CONST_ADDR_OBJ(range)[0]); /* length */
718 SaveSubObj(CONST_ADDR_OBJ(range)[1]); /* base */
719 SaveSubObj(CONST_ADDR_OBJ(range)[2]); /* increment */
720 }
721
722 /****************************************************************************
723 **
724 *F LoadRange( <range> )
725 **
726 */
727
LoadRange(Obj range)728 static void LoadRange(Obj range)
729 {
730 ADDR_OBJ(range)[0] = LoadSubObj(); /* length */
731 ADDR_OBJ(range)[1] = LoadSubObj(); /* base */
732 ADDR_OBJ(range)[2] = LoadSubObj(); /* increment */
733 }
734
735
736 /****************************************************************************
737 **
738 *F Range2Check( <first>, <last> ) . . . . . . . . . . . . . construct range
739 */
Range2Check(Obj first,Obj last)740 Obj Range2Check (
741 Obj first,
742 Obj last )
743 {
744 Obj range;
745 Int f, l;
746 f = GetSmallInt("Range", first);
747 l = GetSmallInt("Range", last);
748 if ( f > l ) {
749 range = NEW_PLIST( T_PLIST, 0 );
750 }
751 else if ( f == l ) {
752 range = NEW_PLIST( T_PLIST, 1 );
753 SET_LEN_PLIST( range, 1 );
754 SET_ELM_PLIST( range, 1, first );
755 }
756 else {
757 range = NEW_RANGE_SSORT();
758 SET_LEN_RANGE( range, (l-f) + 1 );
759 SET_LOW_RANGE( range, f );
760 SET_INC_RANGE( range, 1 );
761 }
762 return range;
763 }
764
765
766 /****************************************************************************
767 **
768 *F Range3Check( <first>, <second>, <last> ) . . . . . . . . construct range
769 */
Range3Check(Obj first,Obj second,Obj last)770 Obj Range3Check (
771 Obj first,
772 Obj second,
773 Obj last )
774 {
775 Obj range;
776 if ( first == second ) {
777 ErrorQuit(
778 "Range: <second> must not be equal to <first> (%d)",
779 (Int)INT_INTOBJ(first), 0L );
780 }
781 Int f = GetSmallInt("Range", first);
782 Int i = GetSmallInt("Range", second) - f;
783 Int l = GetSmallInt("Range", last);
784 if ( (l - f) % i != 0 ) {
785 ErrorQuit(
786 "Range: <last>-<first> (%d) must be divisible by <inc> (%d)",
787 (Int)(l - f), (Int)i );
788 }
789 if ( (0 < i && f > l) || (i < 0 && f < l) ) {
790 range = NEW_PLIST( T_PLIST, 0 );
791 }
792 else if ( f == l ) {
793 range = NEW_PLIST( T_PLIST, 1 );
794 SET_LEN_PLIST( range, 1 );
795 SET_ELM_PLIST( range, 1, first );
796 }
797 else {
798 if ( 0 < i )
799 range = NEW_RANGE_SSORT();
800 else
801 range = NEW_RANGE_NSORT();
802 SET_LEN_RANGE( range, (l - f) / i + 1 );
803 SET_LOW_RANGE( range, f );
804 SET_INC_RANGE( range, i );
805 }
806 return range;
807 }
808
809
810 /****************************************************************************
811 **
812 *F * * * * * * * * * * * * * * GAP level functions * * * * * * * * * * * * *
813 */
814
815 /****************************************************************************
816 **
817 *F FiltIS_RANGE_REP( <self>, <obj> ) . . . . . test if value is in range rep
818 */
819 static Obj IsRangeRepFilt;
820
FiltIS_RANGE_REP(Obj self,Obj obj)821 static Obj FiltIS_RANGE_REP(Obj self, Obj obj)
822 {
823 return (IS_RANGE( obj ) ? True : False);
824 }
825
826 /****************************************************************************
827 **
828 *F MakeImmutableRange( <range> )
829 **
830 */
831
MakeImmutableRange(Obj range)832 static void MakeImmutableRange(Obj range)
833 {
834 MakeImmutableNoRecurse(range);
835 }
836
837 /****************************************************************************
838 **
839 *F FuncINTER_RANGE( <range1>, <range2> )
840 **
841 */
842
egcd(Int a,Int b,Int * lastx,Int * lasty)843 static Int egcd (Int a, Int b, Int *lastx, Int *lasty)
844 {
845 Int x = 0, y = 1;
846 *lastx = 1; *lasty = 0;
847
848 while (b != 0) {
849 Int t, q;
850 t = b; q = a / b; b = a % b; a = t;
851 if (lastx) { t = x; x = *lastx - q*x; *lastx = t; }
852 if (lasty) { t = y; y = *lasty - q*y; *lasty = t; }
853 }
854 return a;
855 } /* returns g=gcd(a,b), with lastx*a+lasty*b = g */
856
FuncINTER_RANGE(Obj self,Obj r1,Obj r2)857 static Obj FuncINTER_RANGE(Obj self, Obj r1, Obj r2)
858 {
859 Int low1, low2, inc1, inc2, lowi, inci, g, x, y;
860 UInt len1, len2, leni;
861
862 if (!IS_RANGE(r1) || !IS_MUTABLE_OBJ(r1))
863 RequireArgumentEx("INTER_RANGE", r1, "<range1>",
864 "must be a mutable range");
865 if (!IS_RANGE(r2))
866 RequireArgumentEx("INTER_RANGE", r2, "<range2>", "must be a range");
867
868 low1 = GET_LOW_RANGE(r1);
869 low2 = GET_LOW_RANGE(r2);
870 inc1 = GET_INC_RANGE(r1);
871 inc2 = GET_INC_RANGE(r2);
872 len1 = GET_LEN_RANGE(r1);
873 len2 = GET_LEN_RANGE(r2);
874
875 if (inc1 < 0)
876 {
877 low1 = low1 + (len1-1)*inc1;
878 inc1 = -inc1;
879 }
880 if (inc2 < 0)
881 {
882 low2 = low2 + (len2-1)*inc2;
883 inc2 = -inc2;
884 }
885
886 if (low1 > low2)
887 {
888 Int t;
889 UInt ut;
890 t = low1; low1 = low2; low2 = t;
891 t = inc1; inc1 = inc2; inc2 = t;
892 ut = len1; len1 = len2; len2 = ut;
893 }
894
895 g = egcd(inc1, inc2, &x, &y);
896
897 inci = (inc1 / g) * inc2;
898
899 if (inci / inc2 != inc1 / g) /* overflow */
900 goto empty_range;
901
902 if ((low2 - low1) % g) /* ranges are disjoint */
903 goto empty_range;
904
905 x = (-y * ((low2 - low1) / g)) % (inc1 / g);
906 if (x < 0)
907 x += inc1/g;
908 lowi = low2 + inc2 * x;
909
910 x = (low1 + (len1-1)*inc1 - lowi);
911 y = (low2 + (len2-1)*inc2 - lowi);
912 if (x < 0 || y < 0)
913 goto empty_range;
914 if (x > y)
915 leni = 1 + y / inci;
916 else
917 leni = 1 + x / inci;
918
919 SET_LOW_RANGE(r1,lowi);
920 SET_LEN_RANGE(r1,leni);
921 SET_INC_RANGE(r1,inci);
922 return (Obj)0;
923
924 empty_range:
925 RetypeBag(r1, T_PLIST_EMPTY);
926 ResizeBag(r1,sizeof(Obj));
927 SET_LEN_PLIST(r1, 0L);
928 return (Obj) 0;
929 }
930
931
932 /****************************************************************************
933 **
934 *F * * * * * * * * * * * * * initialize module * * * * * * * * * * * * * * *
935 */
936
937
938 /****************************************************************************
939 **
940 *V BagNames . . . . . . . . . . . . . . . . . . . . . . . list of bag names
941 */
942 static StructBagNames BagNames[] = {
943 { T_RANGE_NSORT, "list (range,nsort)" },
944 { T_RANGE_NSORT +IMMUTABLE, "list (range,nsort,imm)" },
945 { T_RANGE_SSORT, "list (range,ssort)" },
946 { T_RANGE_SSORT +IMMUTABLE, "list (range,ssort,imm)" },
947 { -1, "" }
948 };
949
950
951 /****************************************************************************
952 **
953 *V ClearFiltsTab . . . . . . . . . . . . . . . . . . . . clear filter tnums
954 */
955 static Int ClearFiltsTab [] = {
956 T_RANGE_NSORT, T_RANGE_NSORT,
957 T_RANGE_SSORT, T_RANGE_SSORT,
958 -1, -1
959 };
960
961
962 /****************************************************************************
963 **
964 *V HasFiltTab . . . . . . . . . . . . . . . . . . . . . tester filter tnum
965 */
966 static Int HasFiltTab [] = {
967
968 // nsort range
969 T_RANGE_NSORT, FN_IS_DENSE, 1,
970 T_RANGE_NSORT, FN_IS_NDENSE, 0,
971 T_RANGE_NSORT, FN_IS_HOMOG, 1,
972 T_RANGE_NSORT, FN_IS_NHOMOG, 0,
973 T_RANGE_NSORT, FN_IS_TABLE, 0,
974 T_RANGE_NSORT, FN_IS_RECT, 0,
975 T_RANGE_NSORT, FN_IS_SSORT, 0,
976 T_RANGE_NSORT, FN_IS_NSORT, 1,
977
978 // ssort range
979 T_RANGE_SSORT, FN_IS_DENSE, 1,
980 T_RANGE_SSORT, FN_IS_NDENSE, 0,
981 T_RANGE_SSORT, FN_IS_HOMOG, 1,
982 T_RANGE_SSORT, FN_IS_NHOMOG, 0,
983 T_RANGE_SSORT, FN_IS_TABLE, 0,
984 T_RANGE_SSORT, FN_IS_RECT, 0,
985 T_RANGE_SSORT, FN_IS_SSORT, 1,
986 T_RANGE_SSORT, FN_IS_NSORT, 0,
987
988 -1, -1, -1
989 };
990
991
992 /****************************************************************************
993 **
994 *V SetFiltTab . . . . . . . . . . . . . . . . . . . . . setter filter tnum
995 */
996 static Int SetFiltTab [] = {
997
998 // nsort range
999 T_RANGE_NSORT, FN_IS_DENSE, T_RANGE_NSORT,
1000 T_RANGE_NSORT, FN_IS_NDENSE, -1,
1001 T_RANGE_NSORT, FN_IS_HOMOG, T_RANGE_NSORT,
1002 T_RANGE_NSORT, FN_IS_NHOMOG, -1,
1003 T_RANGE_NSORT, FN_IS_TABLE, -1,
1004 T_RANGE_NSORT, FN_IS_RECT, -1,
1005 T_RANGE_NSORT, FN_IS_SSORT, -1,
1006 T_RANGE_NSORT, FN_IS_NSORT, T_RANGE_NSORT,
1007
1008 // ssort range
1009 T_RANGE_SSORT, FN_IS_DENSE, T_RANGE_SSORT,
1010 T_RANGE_SSORT, FN_IS_NDENSE, -1,
1011 T_RANGE_SSORT, FN_IS_HOMOG, T_RANGE_SSORT,
1012 T_RANGE_SSORT, FN_IS_NHOMOG, -1,
1013 T_RANGE_SSORT, FN_IS_TABLE, -1,
1014 T_RANGE_SSORT, FN_IS_RECT, -1,
1015 T_RANGE_SSORT, FN_IS_SSORT, T_RANGE_SSORT,
1016 T_RANGE_SSORT, FN_IS_NSORT, -1,
1017
1018 -1, -1, -1
1019
1020 };
1021
1022
1023 /****************************************************************************
1024 **
1025 *V ResetFiltTab . . . . . . . . . . . . . . . . . . . unsetter filter tnum
1026 */
1027 static Int ResetFiltTab [] = {
1028
1029 // nsort range
1030 T_RANGE_NSORT, FN_IS_DENSE, T_RANGE_NSORT,
1031 T_RANGE_NSORT, FN_IS_NDENSE, T_RANGE_NSORT,
1032 T_RANGE_NSORT, FN_IS_HOMOG, T_RANGE_NSORT,
1033 T_RANGE_NSORT, FN_IS_NHOMOG, T_RANGE_NSORT,
1034 T_RANGE_NSORT, FN_IS_TABLE, T_RANGE_NSORT,
1035 T_RANGE_NSORT, FN_IS_RECT, T_RANGE_NSORT,
1036 T_RANGE_NSORT, FN_IS_SSORT, T_RANGE_NSORT,
1037 T_RANGE_NSORT, FN_IS_NSORT, T_RANGE_NSORT,
1038
1039 // ssort range
1040 T_RANGE_SSORT, FN_IS_DENSE, T_RANGE_SSORT,
1041 T_RANGE_SSORT, FN_IS_NDENSE, T_RANGE_SSORT,
1042 T_RANGE_SSORT, FN_IS_HOMOG, T_RANGE_SSORT,
1043 T_RANGE_SSORT, FN_IS_NHOMOG, T_RANGE_SSORT,
1044 T_RANGE_SSORT, FN_IS_TABLE, T_RANGE_SSORT,
1045 T_RANGE_SSORT, FN_IS_RECT, T_RANGE_SSORT,
1046 T_RANGE_SSORT, FN_IS_SSORT, T_RANGE_SSORT,
1047 T_RANGE_SSORT, FN_IS_NSORT, T_RANGE_SSORT,
1048
1049 -1, -1, -1
1050
1051 };
1052
1053
1054 /****************************************************************************
1055 **
1056 *V GVarFilts . . . . . . . . . . . . . . . . . . . list of filters to export
1057 */
1058 static StructGVarFilt GVarFilts [] = {
1059
1060 GVAR_FILT(IS_RANGE, "obj", &IsRangeFilt),
1061 GVAR_FILT(IS_RANGE_REP, "obj", &IsRangeRepFilt),
1062 { 0, 0, 0, 0, 0 }
1063
1064 };
1065
1066 /****************************************************************************
1067 **
1068 *V GVarFuncs . . . . . . . . . . . . . . . . . . . list of filters to export
1069 */
1070 static StructGVarFunc GVarFuncs [] = {
1071
1072 GVAR_FUNC(INTER_RANGE, 2, "range1, range2"),
1073 { 0, 0, 0, 0, 0 }
1074
1075 };
1076
1077
1078 /****************************************************************************
1079 **
1080 *F InitKernel( <module> ) . . . . . . . . initialise kernel data structures
1081 */
InitKernel(StructInitInfo * module)1082 static Int InitKernel (
1083 StructInitInfo * module )
1084 {
1085 /* GASMAN marking functions and GASMAN names */
1086 InitBagNamesFromTable( BagNames );
1087
1088 InitMarkFuncBags( T_RANGE_NSORT , MarkAllSubBags );
1089 InitMarkFuncBags( T_RANGE_NSORT +IMMUTABLE , MarkAllSubBags );
1090 InitMarkFuncBags( T_RANGE_SSORT , MarkAllSubBags );
1091 InitMarkFuncBags( T_RANGE_SSORT +IMMUTABLE , MarkAllSubBags );
1092
1093 #ifdef HPCGAP
1094 /* Make immutable bags public */
1095 MakeBagTypePublic( T_RANGE_NSORT + IMMUTABLE );
1096 MakeBagTypePublic( T_RANGE_SSORT + IMMUTABLE );
1097 #endif
1098
1099 /* install the type function */
1100 ImportGVarFromLibrary( "TYPE_RANGE_NSORT_MUTABLE",
1101 &TYPE_RANGE_NSORT_MUTABLE );
1102
1103 ImportGVarFromLibrary( "TYPE_RANGE_SSORT_MUTABLE",
1104 &TYPE_RANGE_SSORT_MUTABLE );
1105
1106 ImportGVarFromLibrary( "TYPE_RANGE_NSORT_IMMUTABLE",
1107 &TYPE_RANGE_NSORT_IMMUTABLE );
1108
1109 ImportGVarFromLibrary( "TYPE_RANGE_SSORT_IMMUTABLE",
1110 &TYPE_RANGE_SSORT_IMMUTABLE );
1111
1112 TypeObjFuncs[ T_RANGE_NSORT ] = TypeRangeNSort;
1113 TypeObjFuncs[ T_RANGE_NSORT +IMMUTABLE ] = TypeRangeNSort;
1114 TypeObjFuncs[ T_RANGE_SSORT ] = TypeRangeSSort;
1115 TypeObjFuncs[ T_RANGE_SSORT +IMMUTABLE ] = TypeRangeSSort;
1116
1117 /* init filters and functions */
1118 InitHdlrFiltsFromTable( GVarFilts );
1119 InitHdlrFuncsFromTable( GVarFuncs );
1120
1121 /* Saving functions */
1122 SaveObjFuncs[T_RANGE_NSORT ] = SaveRange;
1123 SaveObjFuncs[T_RANGE_NSORT +IMMUTABLE ] = SaveRange;
1124 SaveObjFuncs[T_RANGE_SSORT ] = SaveRange;
1125 SaveObjFuncs[T_RANGE_SSORT +IMMUTABLE ] = SaveRange;
1126 LoadObjFuncs[T_RANGE_NSORT ] = LoadRange;
1127 LoadObjFuncs[T_RANGE_NSORT +IMMUTABLE ] = LoadRange;
1128 LoadObjFuncs[T_RANGE_SSORT ] = LoadRange;
1129 LoadObjFuncs[T_RANGE_SSORT +IMMUTABLE ] = LoadRange;
1130
1131 #if !defined(USE_THREADSAFE_COPYING)
1132 /* install the copy methods */
1133 CopyObjFuncs [ T_RANGE_NSORT ] = CopyRange;
1134 CopyObjFuncs [ T_RANGE_NSORT +IMMUTABLE ] = CopyRange;
1135 CopyObjFuncs [ T_RANGE_SSORT ] = CopyRange;
1136 CopyObjFuncs [ T_RANGE_SSORT +IMMUTABLE ] = CopyRange;
1137 CleanObjFuncs[ T_RANGE_NSORT ] = 0;
1138 CleanObjFuncs[ T_RANGE_NSORT +IMMUTABLE ] = 0;
1139 CleanObjFuncs[ T_RANGE_SSORT ] = 0;
1140 CleanObjFuncs[ T_RANGE_SSORT +IMMUTABLE ] = 0;
1141 #endif
1142
1143 /* Make immutable methods */
1144 MakeImmutableObjFuncs[ T_RANGE_NSORT ] = MakeImmutableRange;
1145 MakeImmutableObjFuncs[ T_RANGE_SSORT ] = MakeImmutableRange;
1146
1147 /* install the print method */
1148 PrintObjFuncs[ T_RANGE_NSORT ] = PrintRange;
1149 PrintObjFuncs[ T_RANGE_NSORT +IMMUTABLE ] = PrintRange;
1150 PrintObjFuncs[ T_RANGE_SSORT ] = PrintRange;
1151 PrintObjFuncs[ T_RANGE_SSORT +IMMUTABLE ] = PrintRange;
1152
1153 /* initialise list tables */
1154 InitClearFiltsTNumsFromTable ( ClearFiltsTab );
1155 InitHasFiltListTNumsFromTable ( HasFiltTab );
1156 InitSetFiltListTNumsFromTable ( SetFiltTab );
1157 InitResetFiltListTNumsFromTable( ResetFiltTab );
1158
1159 /* install the comparison methods */
1160 EqFuncs[ T_RANGE_NSORT ][ T_RANGE_NSORT ] = EqRange;
1161 EqFuncs[ T_RANGE_NSORT ][ T_RANGE_SSORT ] = EqRange;
1162 EqFuncs[ T_RANGE_SSORT ][ T_RANGE_NSORT ] = EqRange;
1163 EqFuncs[ T_RANGE_SSORT ][ T_RANGE_SSORT ] = EqRange;
1164 LtFuncs[ T_RANGE_NSORT ][ T_RANGE_NSORT ] = LtRange;
1165 LtFuncs[ T_RANGE_NSORT ][ T_RANGE_SSORT ] = LtRange;
1166 LtFuncs[ T_RANGE_SSORT ][ T_RANGE_NSORT ] = LtRange;
1167 LtFuncs[ T_RANGE_SSORT ][ T_RANGE_SSORT ] = LtRange;
1168
1169 /* install the list functions in the tables */
1170 LenListFuncs [ T_RANGE_NSORT ] = LenRange;
1171 LenListFuncs [ T_RANGE_NSORT +IMMUTABLE ] = LenRange;
1172 LenListFuncs [ T_RANGE_SSORT ] = LenRange;
1173 LenListFuncs [ T_RANGE_SSORT +IMMUTABLE ] = LenRange;
1174 IsbListFuncs [ T_RANGE_NSORT ] = IsbRange;
1175 IsbListFuncs [ T_RANGE_NSORT +IMMUTABLE ] = IsbRange;
1176 IsbListFuncs [ T_RANGE_SSORT ] = IsbRange;
1177 IsbListFuncs [ T_RANGE_SSORT +IMMUTABLE ] = IsbRange;
1178 Elm0ListFuncs [ T_RANGE_NSORT ] = Elm0Range;
1179 Elm0ListFuncs [ T_RANGE_NSORT +IMMUTABLE ] = Elm0Range;
1180 Elm0ListFuncs [ T_RANGE_SSORT ] = Elm0Range;
1181 Elm0ListFuncs [ T_RANGE_SSORT +IMMUTABLE ] = Elm0Range;
1182 Elm0vListFuncs [ T_RANGE_NSORT ] = Elm0vRange;
1183 Elm0vListFuncs [ T_RANGE_NSORT +IMMUTABLE ] = Elm0vRange;
1184 Elm0vListFuncs [ T_RANGE_SSORT ] = Elm0vRange;
1185 Elm0vListFuncs [ T_RANGE_SSORT +IMMUTABLE ] = Elm0vRange;
1186 ElmListFuncs [ T_RANGE_NSORT ] = ElmRange;
1187 ElmListFuncs [ T_RANGE_NSORT +IMMUTABLE ] = ElmRange;
1188 ElmListFuncs [ T_RANGE_SSORT ] = ElmRange;
1189 ElmListFuncs [ T_RANGE_SSORT +IMMUTABLE ] = ElmRange;
1190 ElmvListFuncs [ T_RANGE_NSORT ] = ElmvRange;
1191 ElmvListFuncs [ T_RANGE_NSORT +IMMUTABLE ] = ElmvRange;
1192 ElmvListFuncs [ T_RANGE_SSORT ] = ElmvRange;
1193 ElmvListFuncs [ T_RANGE_SSORT +IMMUTABLE ] = ElmvRange;
1194 ElmwListFuncs [ T_RANGE_NSORT ] = ElmvRange;
1195 ElmwListFuncs [ T_RANGE_NSORT +IMMUTABLE ] = ElmvRange;
1196 ElmwListFuncs [ T_RANGE_SSORT ] = ElmvRange;
1197 ElmwListFuncs [ T_RANGE_SSORT +IMMUTABLE ] = ElmvRange;
1198 ElmsListFuncs [ T_RANGE_NSORT ] = ElmsRange;
1199 ElmsListFuncs [ T_RANGE_NSORT +IMMUTABLE ] = ElmsRange;
1200 ElmsListFuncs [ T_RANGE_SSORT ] = ElmsRange;
1201 ElmsListFuncs [ T_RANGE_SSORT +IMMUTABLE ] = ElmsRange;
1202 UnbListFuncs [ T_RANGE_NSORT ] = UnbRange;
1203 UnbListFuncs [ T_RANGE_SSORT ] = UnbRange;
1204 AssListFuncs [ T_RANGE_NSORT ] = AssRange;
1205 AssListFuncs [ T_RANGE_SSORT ] = AssRange;
1206 AsssListFuncs [ T_RANGE_NSORT ] = AsssRange;
1207 AsssListFuncs [ T_RANGE_SSORT ] = AsssRange;
1208 IsDenseListFuncs[ T_RANGE_NSORT ] = AlwaysYes;
1209 IsDenseListFuncs[ T_RANGE_NSORT +IMMUTABLE ] = AlwaysYes;
1210 IsDenseListFuncs[ T_RANGE_SSORT ] = AlwaysYes;
1211 IsDenseListFuncs[ T_RANGE_SSORT +IMMUTABLE ] = AlwaysYes;
1212 IsHomogListFuncs[ T_RANGE_NSORT ] = AlwaysYes;
1213 IsHomogListFuncs[ T_RANGE_NSORT +IMMUTABLE ] = AlwaysYes;
1214 IsHomogListFuncs[ T_RANGE_SSORT ] = AlwaysYes;
1215 IsHomogListFuncs[ T_RANGE_SSORT +IMMUTABLE ] = AlwaysYes;
1216 IsTableListFuncs[ T_RANGE_NSORT ] = AlwaysNo;
1217 IsTableListFuncs[ T_RANGE_NSORT +IMMUTABLE ] = AlwaysNo;
1218 IsTableListFuncs[ T_RANGE_SSORT ] = AlwaysNo;
1219 IsTableListFuncs[ T_RANGE_SSORT +IMMUTABLE ] = AlwaysNo;
1220 IsSSortListFuncs[ T_RANGE_NSORT ] = AlwaysNo;
1221 IsSSortListFuncs[ T_RANGE_NSORT +IMMUTABLE ] = AlwaysNo;
1222 IsSSortListFuncs[ T_RANGE_SSORT ] = AlwaysYes;
1223 IsSSortListFuncs[ T_RANGE_SSORT +IMMUTABLE ] = AlwaysYes;
1224 IsPossListFuncs [ T_RANGE_NSORT ] = IsPossRange;
1225 IsPossListFuncs [ T_RANGE_NSORT +IMMUTABLE ] = IsPossRange;
1226 IsPossListFuncs [ T_RANGE_SSORT ] = IsPossRange;
1227 IsPossListFuncs [ T_RANGE_SSORT +IMMUTABLE ] = IsPossRange;
1228 PosListFuncs [ T_RANGE_NSORT ] = PosRange;
1229 PosListFuncs [ T_RANGE_NSORT +IMMUTABLE ] = PosRange;
1230 PosListFuncs [ T_RANGE_SSORT ] = PosRange;
1231 PosListFuncs [ T_RANGE_SSORT +IMMUTABLE ] = PosRange;
1232 PlainListFuncs [ T_RANGE_NSORT ] = PlainRange;
1233 PlainListFuncs [ T_RANGE_NSORT +IMMUTABLE ] = PlainRange;
1234 PlainListFuncs [ T_RANGE_SSORT ] = PlainRange;
1235 PlainListFuncs [ T_RANGE_SSORT +IMMUTABLE ] = PlainRange;
1236
1237 /* return success */
1238 return 0;
1239 }
1240
1241
1242 /****************************************************************************
1243 **
1244 *F InitLibrary( <module> ) . . . . . . . initialise library data structures
1245 */
InitLibrary(StructInitInfo * module)1246 static Int InitLibrary (
1247 StructInitInfo * module )
1248 {
1249 /* init filters and functions */
1250 InitGVarFiltsFromTable( GVarFilts );
1251 InitGVarFuncsFromTable( GVarFuncs );
1252
1253 /* return success */
1254 return 0;
1255 }
1256
1257
1258 /****************************************************************************
1259 **
1260 *F InitInfoRange() . . . . . . . . . . . . . . . . . table of init functions
1261 */
1262 static StructInitInfo module = {
1263 // init struct using C99 designated initializers; for a full list of
1264 // fields, please refer to the definition of StructInitInfo
1265 .type = MODULE_BUILTIN,
1266 .name = "range",
1267 .initKernel = InitKernel,
1268 .initLibrary = InitLibrary,
1269 };
1270
InitInfoRange(void)1271 StructInitInfo * InitInfoRange ( void )
1272 {
1273 return &module;
1274 }
1275