CoCalc -- blister.c

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
Project: cocalc-sagemath-dev-slelievre
Views: ⁴¹⁸³⁴⁶
1
/****************************************************************************
2
**
3
*W  blister.c                   GAP source                       Frank Celler
4
*W                                                         & Martin Schönert
5
**
6
**
7
*Y  Copyright (C)  1996,  Lehrstuhl D für Mathematik,  RWTH Aachen,  Germany
8
*Y  (C) 1998 School Math and Comp. Sci., University of St Andrews, Scotland
9
*Y  Copyright (C) 2002 The GAP Group
10
**
11
**  This  file contains the functions  that mainly operate  on boolean lists.
12
**  Because boolean lists are  just a special case  of lists many  things are
13
**  done in the list package.
14
**
15
**  A *boolean list* is a list that has no holes and contains only 'true' and
16
**  'false'.  For  the full definition of  boolean list  see chapter "Boolean
17
**  Lists" in the {\GAP} Manual.  Read  also the section "More  about Boolean
18
**  Lists" about the different internal representations of such lists.
19
**
20
**  A list that is known to be a boolean list is represented by a bag of type
21
**  'T_BLIST', which has the following format:
22
**
23
**      +-------+-------+-------+-------+- - - -+-------+
24
**      |logical| block | block | block |       | last  |
25
**      |length |   0   |   1   |   2   |       | block |
26
**      +-------+-------+-------+-------+- - - -+-------+
27
**             /         \
28
**        .---'           `-----------.
29
**       /                             \
30
**      +---+---+---+---+- - - -+---+---+
31
**      |bit|bit|bit|bit|       |bit|bit|
32
**      | 0 | 1 | 2 | 3 |       |n-1| n |
33
**      +---+---+---+---+- - - -+---+---+
34
**
35
**  The  first  entry is  the logical  length of the list,  represented as  a
36
**  {\GAP} immediate integer.  The other entries are blocks, represented as C
37
**  unsigned  long integer.   Each  block corresponds  to  <n>  (usually  32)
38
**  elements of the list.  The <j>-th bit (the bit corresponding to '2\^<j>')
39
**  in  the <i>-th block  is 1 if  the element  '<list>[BIPEB*<i>+<j>+1]'  it
40
**  'true'  and '0' if  it  is 'false'.  If the logical length of the boolean
41
**  list is not a multiple of BIPEB the  last block will contain unused bits,
42
**  which are then zero.
43
**
44
**  Note that a list represented by a bag of type 'T_PLIST'  might still be a
45
**  boolean list.  It is just that the kernel does not known this.
46
**
47
**  This package consists of three parts.
48
**
49
**  The  first  part  consists  of  the  macros  'BIPEB',  'SIZE_PLEN_BLIST',
50
**  'PLEN_SIZE_BLIST',   'LEN_BLIST',   'SET_LEN_BLIST',   'ELM_BLIST',   and
51
**  'SET_ELM_BLIST'.   They  determine the  representation of boolean  lists.
52
**  The  rest  of the {\GAP} kernel  uses those macros  to access and  modify
53
**  boolean lists.
54
**
55
**  The  second  part  consists  of  the  functions  'LenBlist',  'ElmBlist',
56
**  'ElmsBlist',   'AssBlist',    'AsssBlist',   'PosBlist',    'PlainBlist',
57
**  'IsDenseBlist',  'IsPossBlist', 'EqBlist', and  'LtBlist'.  They  are the
58
**  functions required by the  generic lists  package.  Using these functions
59
**  the other parts of  the {\GAP} kernel can access and modify boolean lists
60
**  without actually being aware that they are dealing with a boolean list.
61
**
62
**  The third part consists   of the functions  'IsBlistConv', 'FuncIsBlist',
63
**  'FuncBLIST_LIST', 'FuncLIST_BLIST', 'FuncSIZE_BLIST', 'FuncIS_SUB_BLIST',
64
**  'FuncUNITE_BLIST', 'FuncINTER_BLIST',   and    'FuncSUBTR_BLIST'.   These
65
**  functions make it possible to make  boolean lists, either by converting a
66
**  list to  a boolean list, or by  computing the characteristic boolean list
67
**  of a sublist, or  by computing the  union, intersection or  difference of
68
**  two boolean lists.
69
**
70
*N  1992/12/16 martin should have 'LtBlist'
71
*/
72
#include        "system.h"              /* system dependent part           */
73

74

75
#include        "gasman.h"              /* garbage collector               */
76
#include        "objects.h"             /* objects                         */
77
#include        "scanner.h"             /* scanner                         */
78

79
#include        "gap.h"                 /* error handling, initialisation  */
80

81
#include        "gvars.h"               /* global variables                */
82
#include        "calls.h"               /* generic call mechanism          */
83
#include        "opers.h"               /* generic operations              */
84

85
#include        "ariths.h"              /* basic arithmetic                */
86

87
#include        "bool.h"                /* booleans                        */
88

89
#include        "records.h"             /* generic records                 */
90
#include        "precord.h"             /* plain records                   */
91

92
#include        "lists.h"               /* generic lists                   */
93
#include        "plist.h"               /* plain lists                     */
94
#include        "set.h"                 /* plain sets                      */
95
#include        "blister.h"             /* boolean lists                   */
96
#include        "range.h"               /* ranges                          */
97
#include        "string.h"              /* strings                         */
98

99
#include        "saveload.h"            /* saving and loading              */
100

101
#include	"code.h"		/* coder                           */
102
#include	"thread.h"		/* threads			   */
103
#include	"tls.h"			/* thread-local storage		   */
104

105

106
/****************************************************************************
107
**
108

109
*F  TypeBlist( <list> )  . . . . . . . . . . . . . . . type of a boolean list
110
**
111
**  'TypeBlist' returns the type of a boolean list.
112
**
113
**  'TypeBlist' is the function in 'TypeObjFuncs' for boolean lists.
114
*/
115

116
/* The following are imported from the GAP level, we have one type for
117
 * each blist TNUM. */
118
Obj TYPE_BLIST_MUT;
119
Obj TYPE_BLIST_IMM;
120
Obj TYPE_BLIST_NSORT_MUT;
121
Obj TYPE_BLIST_NSORT_IMM;
122
Obj TYPE_BLIST_SSORT_MUT;
123
Obj TYPE_BLIST_SSORT_IMM;
124
Obj TYPE_BLIST_EMPTY_MUT;
125
Obj TYPE_BLIST_EMPTY_IMM;
126

127
Obj TypeBlistMut (
128
    Obj                 list )
129
{
130
    /* special case for the empty blist                                    */
131
    if ( LEN_BLIST(list) == 0 ) {
132
        return TYPE_BLIST_EMPTY_MUT;
133
    } else {
134
        return TYPE_BLIST_MUT;
135
    }
136
}
137

138
Obj TypeBlistImm (
139
    Obj                 list )
140
{
141
    /* special case for the empty blist                                    */
142
    if ( LEN_BLIST(list) == 0 ) {
143
        return TYPE_BLIST_EMPTY_IMM;
144
    } else {
145
        return TYPE_BLIST_IMM;
146
    }
147
}
148

149
Obj TypeBlistNSortMut (
150
    Obj                 list )
151
{
152
    /* special case for the empty blist                                    */
153
    if ( LEN_BLIST(list) == 0 ) {
154
        return TYPE_BLIST_EMPTY_MUT;
155
    } else {
156
        return TYPE_BLIST_NSORT_MUT;
157
    }
158
}
159

160
Obj TypeBlistNSortImm (
161
    Obj                 list )
162
{
163
    /* special case for the empty blist                                    */
164
    if ( LEN_BLIST(list) == 0 ) {
165
        return TYPE_BLIST_EMPTY_IMM;
166
    } else {
167
        return TYPE_BLIST_NSORT_IMM;
168
    }
169
}
170

171
Obj TypeBlistSSortMut (
172
    Obj                 list )
173
{
174
    /* special case for the empty blist                                    */
175
    if ( LEN_BLIST(list) == 0 ) {
176
        return TYPE_BLIST_EMPTY_MUT;
177
    } else {
178
        return TYPE_BLIST_SSORT_MUT;
179
    }
180
}
181

182
Obj TypeBlistSSortImm (
183
    Obj                 list )
184
{
185
    /* special case for the empty blist                                    */
186
    if ( LEN_BLIST(list) == 0 ) {
187
        return TYPE_BLIST_EMPTY_IMM;
188
    } else {
189
        return TYPE_BLIST_SSORT_IMM;
190
    }
191
}
192

193
/****************************************************************************
194
**
195
*F  SaveBlist( <blist> ) . . . . . . . . . . . . . . . . . . . . save a blist
196
**
197
**   The saving method for the blist tnums
198
*/
199
void SaveBlist (
200
    Obj                 bl )
201
{
202
    UInt                i;
203
    UInt *              ptr;
204

205
    /* logical length                                                      */
206
    SaveSubObj(ADDR_OBJ(bl)[0]);
207
    ptr = BLOCKS_BLIST(bl);
208
    for (i = 1; i <= NUMBER_BLOCKS_BLIST( bl ); i++ )
209
        SaveUInt(*ptr++);
210
    return;
211
}
212

213
/****************************************************************************
214
**
215
*F  LoadBlist( <blist> ) . . . . . . . . . . . . . . . . . . . . load a blist
216
**
217
**   The loading method for the blist tnums
218
*/
219
void LoadBlist (
220
    Obj                 bl )
221
{
222
    UInt                i;
223
    UInt *              ptr;
224
  
225
    /* get the length back, then NUMBER_BLOCKS_BLIST is OK                 */
226
    ADDR_OBJ(bl)[0] = LoadSubObj(); 
227
  
228
    /* Now load the real data                                              */
229
    ptr = (UInt *)BLOCKS_BLIST(bl);
230
    for (i = 1; i <= NUMBER_BLOCKS_BLIST( bl ); i++ )
231
        *ptr++ = LoadUInt();
232
    return;
233
}
234

235

236
/****************************************************************************
237
**
238

239
*F * * * * * * * * * * * * * * copy functions * * * * * * * * * * * * * * * *
240
*/
241

242
/****************************************************************************
243
**
244

245

246
*F  CopyBlist( <list>, <mut> )  . . . . . . . . . . . . . copy a boolean list
247
**
248
**  'CopyBlist' returns a structural (deep) copy  of the boolean list <list>,
249
**  i.e., a recursive copy that preserves the structure.
250
**
251
**  If <list>  has not yet been copied,   it makes a   copy, leaves a forward
252
**  pointer  to the copy in the  first entry of  the  boolean list, where the
253
**  size of the boolean list usually resides, and copies all the entries.  If
254
**  the boolean  list has already been  copied, it returns  the  value of the
255
**  forwarding pointer.
256
**
257
**  'CopyBlist' is the function in 'CopyObjFuncs' for boolean lists.
258
**
259
**  'CleanBlist' removes the mark and the forwarding pointer from the boolean
260
**  list <list>.
261
**
262
**  'CleanBlist' is the function in 'CleanObjFuncs' for boolean lists.
263
*/
264

265
Obj DoCopyBlist(Obj list, Int mut) {
266
  Obj copy;
267
  UInt *l;
268
  UInt *c;
269
    /* make a copy                                                         */
270
    if ( mut ) {
271
      copy = NewBag( MUTABLE_TNUM(TNUM_OBJ(list)), SIZE_OBJ(list) );
272
    }
273
    else {
274
      copy = NewBag( IMMUTABLE_TNUM( TNUM_OBJ(list) ), SIZE_OBJ(list) );
275
    }
276

277

278
    /* copy the subvalues                                                  */
279
    l = (UInt*)(ADDR_OBJ(list));
280
    c = (UInt*)(ADDR_OBJ(copy));
281
    memcpy((void *)c, (void *)l, sizeof(UInt)*(1+NUMBER_BLOCKS_BLIST(list)));
282

283
    /* return the copy                                                     */
284
    return copy;
285
  
286
}
287

288
Obj CopyBlist (
289
    Obj                 list,
290
    Int                 mut )
291
{
292

293
    /* don't change immutable objects                                      */
294
    if ( ! IS_MUTABLE_OBJ(list) ) {
295
        return list;
296
    }
297

298
    return DoCopyBlist(list, mut);
299
}
300

301
Obj ShallowCopyBlist ( Obj list)
302
{
303
  return DoCopyBlist(list, 1);
304
}
305

306

307

308
/****************************************************************************
309
**
310
*F  CopyBlistCopy( <list>, <mut> )  . . . . . . . copy a already copied blist
311
*/
312
Obj CopyBlistCopy (
313
    Obj                 list,
314
    Int                 mut )
315
{
316
    return ADDR_OBJ(list)[0];
317
}
318

319

320
/****************************************************************************
321
**
322
*F  CleanBlist( <list> )  . . . . . . . . . . . . . . clean up a boolean list
323
*/
324
void CleanBlist (
325
    Obj                 list )
326
{
327
}
328

329

330
/****************************************************************************
331
**
332
*F  CleanBlistCopy( <list> )  . . . . . . . . . . . . .  clean a copied blist
333
*/
334
void CleanBlistCopy (
335
    Obj                 list )
336
{
337
    /* remove the forwarding pointer                                       */
338
    ADDR_OBJ(list)[0] = ADDR_OBJ( ADDR_OBJ(list)[0] )[0];
339

340
    /* now it is cleaned                                                   */
341
    UNMARK_LIST( list, COPYING );
342
}
343

344

345
/****************************************************************************
346
**
347

348
*F * * * * * * * * * * * * * * list functions * * * * * * * * * * * * * * * *
349
*/
350

351
/****************************************************************************
352
**
353

354

355
*F  EqBlist( <listL>, <listR> ) . . . . . test if two boolean lists are equal
356
**
357
**  'EqBlist' returns 'true' if the two boolean lists <listL> and <listR> are
358
**  equal and 'false' otherwise.
359
*/
360
Int EqBlist (
361
    Obj                 listL,
362
    Obj                 listR )
363
{
364
    long                lenL;           /* length of the left operand      */
365
    long                lenR;           /* length of the right operand     */
366
    UInt *              ptrL;           /* pointer to the left operand     */
367
    UInt *              ptrR;           /* pointer to the right operand    */
368
    UInt                i;              /* loop variable                   */
369

370
    /* get the lengths of the lists and compare them                       */
371
    lenL = LEN_BLIST( listL );
372
    lenR = LEN_BLIST( listR );
373
    if ( lenL != lenR ) {
374
        return 0L;
375
    }
376

377
    /* test for equality blockwise                                         */
378
    ptrL = BLOCKS_BLIST(listL);
379
    ptrR = BLOCKS_BLIST(listR);
380
    for ( i = (lenL+BIPEB-1)/BIPEB; 0 < i; i-- ) {
381
        if ( *ptrL++ != *ptrR++ )
382
            return 0L;
383
    }
384

385
    /* no differences found, the lists are equal                           */
386
    return 1L;
387
}
388

389

390
/****************************************************************************
391
**
392
*F  LenBlist( <list> )  . . . . . . . . . . . . . .  length of a boolean list
393
**
394
**  'LenBlist' returns the length of the boolean list <list> as a C integer.
395
**
396
**  'LenBlist' is the function in 'LenListFuncs' for boolean lists.
397
*/
398
Int LenBlist (
399
    Obj                 list )
400
{
401
    return LEN_BLIST( list );
402
}
403

404

405
/****************************************************************************
406
**
407
*F  IsbBlist( <list>, <pos> ) . . . . . test for an element of a boolean list
408
**
409
**  'IsbBlist' returns  1 if the boolean list <list> contains an  element  at
410
**  the position <pos> and 0 otherwise.  It  is  the  responsibility  of  the
411
**  caller to ensure that <pos> is a positive integer.
412
**
413
**  'IsbBlist' is the function in 'IsbListFuncs' for boolean lists.
414
*/
415
Int IsbBlist (
416
    Obj                 list,
417
    Int                 pos )
418
{
419
    return (pos <= LEN_BLIST(list));
420
}
421

422

423
/****************************************************************************
424
**
425
*F  IsbvBlist( <list>, <pos> )  . . . . test for an element of a boolean list
426
*/
427
Int IsbvBlist (
428
    Obj                 list,
429
    Int                 pos )
430
{
431
    return 1L;
432
}
433

434

435
/****************************************************************************
436
**
437

438
*F  Elm0Blist( <list>, <pos> )  . . . . . select an element of a boolean list
439
**
440
**  'Elm0Blist' returns the element at the position <pos> of the boolean list
441
**  <list>, or 0 if  <list>  has no  assigned object  at  <pos>.  It  is  the
442
**  responsibility of the caller to ensure that <pos> is a positive integer.
443
*/
444
Obj Elm0Blist (
445
    Obj                 list,
446
    Int                 pos )
447
{
448
    if ( pos <= LEN_BLIST( list ) ) {
449
        return ELM_BLIST( list, pos );
450
    }
451
    else {
452
        return 0;
453
    }
454
}
455

456

457
/****************************************************************************
458
**
459
*F  Elm0vBlist( <list>, <pos> ) . . . . . select an element of a boolean list
460
**
461
**  'Elm0vPlist' does the same thing than 'Elm0List', but need not check that
462
**  <pos>  is less  than or  equal   to the length   of  <list>, this is  the
463
**  responsibility of the caller.
464
*/
465
Obj Elm0vBlist (
466
    Obj                 list,
467
    Int                 pos )
468
{
469
    return ELM_BLIST( list, pos );
470
}
471

472

473
/****************************************************************************
474
**
475
*F  ElmBlist( <list>, <pos> ) . . . . . . select an element of a boolean list
476
**
477
**  'ElmBlist' selects  the  element at  position <pos> of  the  boolean list
478
**  <list>.  It is the responsibility of the caller to ensure that <pos> is a
479
**  positive integer.   An  error is signalled   if <pos> is larger  than the
480
**  length of <list>.
481
**
482
**  'ElmBlist'   is  the  function  in    'ElmListFuncs'  for boolean  lists.
483
**  'ElmvBlist' is the function in 'ElmvListFuncs' for boolean lists.
484
*/
485
Obj ElmBlist (
486
    Obj                 list,
487
    Int                 pos )
488
{
489

490
    /* check the position                                                  */
491
    if ( LEN_BLIST( list ) < pos ) {
492
        ErrorReturnVoid(
493
            "List Element: <list>[%d] must have an assigned value",
494
            pos, 0L,
495
            "you can assign a value and 'return;'" );
496
        return ELM_LIST( list, pos );
497
    }
498

499
    /* select and return the element                                       */
500
    return ELM_BLIST( list, pos );
501
}
502

503
/****************************************************************************
504
**
505
*F  ElmvBlist( <list>, <pos> )  . . . . . select an element of a boolean list
506
**
507
**  'ElmvBlist' does the same thing than  'ElmBlist', but need not check that
508
**  <pos>   is less than   or equal  to the  length  of  <list>,  this is the
509
**  responsibility of the caller.
510
**
511
*/
512
Obj ElmvBlist (
513
    Obj                 list,
514
    Int                 pos )
515
{
516
    /* select and return the element                                       */
517
    return ELM_BLIST( list, pos );
518
}
519

520

521
/****************************************************************************
522
**
523
*F  ElmsBlist( <list>, <poss> ) . . . .  select a sublist from a boolean list
524
**
525
**  'ElmsBlist' returns a new list  containing the elements at the  positions
526
**  given in the   list  <poss> from  the boolean   list <list>.   It  is the
527
**  responsibility of the caller to ensure  that <poss> is dense and contains
528
**  only positive integers.  An error is signalled if an element of <poss> is
529
**  larger than the length of <list>.
530
**
531
**  'ElmsBlist' is the function in 'ElmsListFuncs' for boolean lists.
532
*/
533
Obj ElmsBlist (
534
    Obj                 list,
535
    Obj                 poss )
536
{
537
    Obj                 elms;           /* selected sublist, result        */
538
    Int                 lenList;        /* length of <list>                */
539
    Obj                 elm;            /* one element from <list>         */
540
    Int                 lenPoss;        /* length of <positions>           */
541
    Int                 pos;            /* <position> as integer           */
542
    Int                 inc;            /* increment in a range            */
543
    UInt                block;          /* one block of <elms>             */
544
    UInt                bit;            /* one bit of a block              */
545
    UInt                i;              /* loop variable                   */
546

547
    /* general code                                                        */
548
    if ( ! IS_RANGE(poss) ) {
549

550
        /* get the length of <list>                                        */
551
        lenList = LEN_BLIST( list );
552

553
        /* get the length of <positions>                                   */
554
        lenPoss = LEN_LIST( poss );
555

556
        /* make the result list                                            */
557
        elms = NewBag( T_BLIST, SIZE_PLEN_BLIST( lenPoss ) );
558
        SET_LEN_BLIST( elms, lenPoss );
559

560
        /* loop over the entries of <positions> and select                 */
561
        block = 0;  bit = 1;
562
        for ( i = 1; i <= lenPoss; i++ ) {
563

564
            /* get <position>                                              */
565
            pos = INT_INTOBJ( ELMW_LIST( poss, (Int)i ) );
566
            if ( lenList < pos ) {
567
                ErrorReturnVoid(
568
                    "List Elements: <list>[%d] must have an assigned value",
569
                    pos, 0L,
570
                    "you can assign a value and 'return;'" );
571
                return ELMS_LIST( list, poss );
572
            }
573

574
            /* select the element                                          */
575
            elm = ELM_BLIST( list, pos );
576

577
            /* assign the element into <elms>                              */
578
            if ( elm == True )
579
                block |= bit;
580
            bit <<= 1;
581
            if ( bit == 0 || i == lenPoss ) {
582
                BLOCK_ELM_BLIST( elms, i) =  block;
583
                block = 0;
584
                bit = 1;
585
            }
586

587
        }
588

589
    }
590

591
    /* special code for ranges                                             */
592
    /*N 1992/12/15 martin special code for ranges with increment 1         */
593
    else {
594

595
        /* get the length of <list>                                        */
596
        lenList = LEN_PLIST( list );
597

598
        /* get the length of <positions>, the first elements, and the inc. */
599
        lenPoss = GET_LEN_RANGE( poss );
600
        pos = GET_LOW_RANGE( poss );
601
        inc = GET_INC_RANGE( poss );
602

603
        /* check that no <position> is larger than 'LEN_LIST(<list>)'      */
604
        if ( lenList < pos ) {
605
            ErrorReturnVoid(
606
                "List Elements: <list>[%d] must have an assigned value",
607
                pos, 0L,
608
                "you can assign a value and 'return;'" );
609
            return ELMS_LIST( list, poss );
610
        }
611
        if ( lenList < pos + (lenPoss-1) * inc ) {
612
            ErrorReturnVoid(
613
                "List Elements: <list>[%d] must have an assigned value",
614
                pos+(lenPoss-1)*inc, 0L,
615
                "you can assign a value and 'return;'" );
616
            return ELMS_LIST( list, poss );
617
        }
618

619
        /* make the result list                                            */
620
        elms = NewBag( T_BLIST, SIZE_PLEN_BLIST( lenPoss ) );
621
        SET_LEN_BLIST( elms, lenPoss );
622

623
        /* loop over the entries of <positions> and select                 */
624
        block = 0;  bit = 1;
625
        for ( i = 1; i <= lenPoss; i++, pos += inc ) {
626

627
            /* select the element                                          */
628
            elm = ELM_BLIST( list, pos );
629

630
            /* assign the element to <elms>                                */
631
            if ( elm == True )
632
                block |= bit;
633
            bit <<= 1;
634
            if ( bit == 0 || i == lenPoss ) {
635
                BLOCK_ELM_BLIST(elms, i) =  block;
636
                block = 0;
637
                bit = 1;
638
            }
639

640
        }
641

642
    }
643

644
    /* return the result                                                   */
645
    return elms;
646
}
647

648

649
/****************************************************************************
650
**
651

652
*F  AssBlist( <list>, <pos>, <val> )  . . . . . . .  assign to a boolean list
653
**
654
**  'AssBlist' assigns the   value <val> to  the  boolean list <list> at  the
655
**  position <pos>.   It is the responsibility  of the caller to  ensure that
656
**  <pos> is positive, and that <val> is not 0.
657
**
658
**  'AssBlist' is the function in 'AssListFuncs' for boolean lists.
659
**
660
**  If <pos> is less than or equal to the logical length  of the boolean list
661
**  and <val> is 'true' or   'false' the assignment  is  done by setting  the
662
**  corresponding bit.  If <pos>  is one more  than the logical length of the
663
**  boolean list  the assignment is  done by   resizing  the boolean list  if
664
**  necessary, setting the   corresponding bit and  incrementing  the logical
665
**  length  by one.  Otherwise  the boolean list is  converted to an ordinary
666
**  list and the assignment is performed the ordinary way.
667
*/
668
void AssBlist (
669
    Obj                 list,
670
    Int                 pos,
671
    Obj                 val )
672
{
673
    /* if <pos> is less than the logical length and <elm> is 'true'        */
674
    if      ( pos <= LEN_BLIST(list) && val == True ) {
675
        SET_ELM_BLIST( list, pos, True );
676
        CLEAR_FILTS_LIST(list);
677
    }
678

679
    /* if <i> is less than the logical length and <elm> is 'false'         */
680
    else if ( pos <= LEN_BLIST(list) && val == False ) {
681
        SET_ELM_BLIST( list, pos, False );
682
        CLEAR_FILTS_LIST(list);
683
    }
684

685
    /* if <i> is one more than the logical length and <elm> is 'true'      */
686
    else if ( pos == LEN_BLIST(list)+1 && val == True ) {
687
        if ( SIZE_OBJ(list) < SIZE_PLEN_BLIST(pos) )
688
            ResizeBag( list, SIZE_PLEN_BLIST(pos) );
689
        SET_LEN_BLIST( list, pos );
690
        SET_ELM_BLIST( list, pos, True );
691
        CLEAR_FILTS_LIST(list);
692
    }
693

694
    /* if <i> is one more than the logical length and <elm> is 'false'     */
695
    else if ( pos == LEN_BLIST(list)+1 && val == False ) {
696
        if ( SIZE_OBJ(list) < SIZE_PLEN_BLIST(pos) )
697
            ResizeBag( list, SIZE_PLEN_BLIST(pos) );
698
        SET_LEN_BLIST( list, pos );
699
        SET_ELM_BLIST( list, pos, False );
700
        CLEAR_FILTS_LIST(list);
701
    }
702

703
    /* otherwise convert to ordinary list and assign as in 'AssList'       */
704
    else {
705
        PLAIN_LIST(list);
706
        CLEAR_FILTS_LIST(list);
707
        if ( LEN_PLIST(list) < pos ) {
708
            GROW_PLIST( list, (UInt)pos );
709
            SET_LEN_PLIST( list, pos );
710
        }
711
        SET_ELM_PLIST( list, pos, val );
712
        CHANGED_BAG( list );
713
    }
714
}
715

716

717
/****************************************************************************
718
**
719
*F  AssBlistImm( <list>, <pos>, <val> ) . assign to an immutable boolean list
720
*/
721
void AssBlistImm (
722
    Obj                 list,
723
    Int                 pos,
724
    Obj                 val )
725
{
726
    ErrorReturnVoid(
727
        "Lists Assignment: <list> must be a mutable list",
728
        0L, 0L,
729
        "you can 'return;' and ignore the assignment" );
730
}
731

732

733
/****************************************************************************
734
**
735
*F  AsssBlist( <list>, <poss>, <vals> ) .  assign several elements to a blist
736
**
737
**  'AsssBlist' assignes the values  from  the list  <vals> at the  positions
738
**  given  in the  list  <poss>  to the   boolean  list  <list>.  It is   the
739
**  responsibility of the caller to ensure that  <poss> is dense and contains
740
**  only positive integers, that <poss> and <vals>  have the same length, and
741
**  that <vals> is dense.
742
**
743
**  'AsssBlist' is intended as function in 'AsssListFuncs' for boolean lists.
744
**  Note that currently, we use AsssListDefault instead. This ensures 
745
**  automatically that <list> remains a blist if possible.
746
**
747
*/
748
void AsssBlist (     /*  currently not used */
749
    Obj                 list,
750
    Obj                 poss,
751
    Obj                 vals )
752
{
753
   Int   i, len, pos;
754
   Obj   val;
755

756
   len = LEN_LIST(poss);
757
   for (i=1; i <= len; i++) {
758
      /* use generic macros because list might be unpacked */
759
      pos = INT_INTOBJ(ELMW_LIST(poss, i));
760
      val = ELMW_LIST(vals, i);
761
      ASS_LIST( list, pos, val);
762
    }
763
}
764

765

766
/****************************************************************************
767
**
768
*F  AsssBlistImm( <list>, <poss>, <vals> )  . .  assign to an immutable blist
769
*/
770
void AsssBlistImm (
771
    Obj                 list,
772
    Obj                 poss,
773
    Obj                 val )
774
{
775
    ErrorReturnVoid(
776
        "Lists Assignments: <list> must be a mutable list",
777
        0L, 0L,
778
        "you can 'return;' and ignore the assignment" );
779
}
780

781

782
/****************************************************************************
783
**
784

785
*F  PosBlist( <list>, <val>, <start> )   position of an elm in a boolean list
786
**
787
**  'PosBlist' returns the   position of  the first  occurrence  of the  value
788
**  <val>, which may be  an  object of  arbitrary  type, in the boolean  list
789
**  <list> after <start> as a C  integer.  If <val> does  not occur in <list>
790
**  after <start>, then 0 is returned.
791
**
792
**  'PosBlist' is the function in 'PosListFuncs' for boolean lists.
793
*/
794
Obj PosBlist (
795
    Obj                 list,
796
    Obj                 val,
797
    Obj                 start )
798
{
799
    Int                 len;            /* logical length of the list      */
800
    UInt *              ptr;            /* pointer to the blocks           */
801
    UInt                i,  j;          /* loop variables                  */
802
    UInt                istart;
803
    UInt                firstblock, lastblock;
804
    UInt                firstoffset, lastoffset;
805
    UInt                x;
806

807
    if (!IS_INTOBJ(start))
808
      return Fail;
809
    
810
    istart = INT_INTOBJ(start);
811

812
    len = LEN_BLIST(list);
813

814
    /* look just beyond end                                                */
815
    if ( len == istart ) {
816
      return Fail;
817
    }
818

819
    ptr = BLOCKS_BLIST(list);
820
    firstblock = istart/BIPEB;
821
    lastblock = (len-1)/BIPEB;
822
    firstoffset = istart%BIPEB;
823
    lastoffset = (len-1)%BIPEB;
824

825
    /* look for 'true'                                                     */
826
     if ( val == True ) {
827

828
       x = ptr[firstblock];
829
       if (firstblock == lastblock) 
830
         {
831
           if (x != 0)
832
             for (j = firstoffset; j <= lastoffset; j++)
833
               if ((x & (1UL << j)) != 0)
834
                 return INTOBJ_INT(BIPEB*firstblock + j + 1);
835
           return Fail;
836
         }
837
       if (x != 0)
838
         for (j = firstoffset; j < BIPEB; j++)
839
           if ((x & (1UL << j)) != 0)
840
             return INTOBJ_INT(BIPEB*firstblock + j + 1);
841
       for (i  = firstblock + 1; i < lastblock; i++)
842
         {
843
           x = ptr[i];
844
           if (x != 0)
845
             for (j = 0; j < BIPEB; j++)
846
               if ((x & (1UL << j)) != 0)
847
                 return INTOBJ_INT(BIPEB*i + j + 1);
848
         }
849
       x = ptr[lastblock];
850
       if (x != 0)
851
         for (j = 0; j <= lastoffset; j++)
852
           if ((x & (1UL << j)) != 0)
853
             return INTOBJ_INT(BIPEB*lastblock + j + 1);
854
       return Fail;
855
    }
856

857
    /* look for 'false'                                                    */
858
    else if ( val == False ) {
859
      x = ptr[firstblock];
860
      if (firstblock == lastblock) 
861
        {
862
          if (x != ~0UL)
863
            for (j = firstoffset; j <= lastoffset; j++)
864
              if ((x & (1UL << j)) == 0)
865
                return INTOBJ_INT(BIPEB*firstblock + j + 1);
866
           return Fail;
867
         }
868
       if (x != ~0UL)
869
         for (j = firstoffset; j < BIPEB; j++)
870
           if ((x & (1UL << j)) == 0)
871
             return INTOBJ_INT(BIPEB*firstblock + j + 1);
872
       for (i  = firstblock + 1; i < lastblock; i++)
873
         {
874
           x = ptr[i];
875
           if (x != ~0UL)
876
             for (j = 0; j < BIPEB; j++)
877
               if ((x & (1UL << j)) == 0)
878
                 return INTOBJ_INT(BIPEB*i + j + 1);
879
         }
880
       x = ptr[lastblock];
881
       if (x != ~0UL)
882
         for (j = 0; j <= lastoffset; j++)
883
           if ((x & (1UL << j)) == 0)
884
             return INTOBJ_INT(BIPEB*lastblock + j + 1);
885
       return Fail;
886
    }
887

888
    /* look for something else                                             */
889
    else {
890
      return Fail;
891
    }
892

893
}
894

895

896
/****************************************************************************
897
**
898
*F  PlainBlist( <list> )  . . .  convert a boolean list into an ordinary list
899
**
900
**  'PlainBlist' converts the boolean list <list> to a plain list.
901
**
902
**  'PlainBlist' is the function in 'PlainListFuncs' for boolean lists.
903
*/
904
void PlainBlist (
905
    Obj                 list )
906
{
907
    Int                 len;            /* length of <list>                */
908
    UInt                i;              /* loop variable                   */
909

910
    /* resize the list and retype it, in this order                        */
911
    len = LEN_BLIST(list);
912
    RetypeBag( list, IS_MUTABLE_OBJ(list) ? T_PLIST : T_PLIST+IMMUTABLE );
913
    GROW_PLIST( list, (UInt)len );
914
    SET_LEN_PLIST( list, len );
915

916
    /* replace the bits by 'True' or 'False' as the case may be            */
917
    /* this must of course be done from the end of the list backwards      */
918
    for ( i = len; 0 < i; i-- )
919
        SET_ELM_PLIST( list, i, ELM_BLIST( list, i ) );
920

921
    /* 'CHANGED_BAG' not needed, 'True' and 'False' are safe           */
922
}
923

924

925

926
/****************************************************************************
927
**
928
*F  IsPossBlist( <list> ) . .  positions list test function for boolean lists
929
**
930
**  'IsPossBlist' returns  1 if  <list> is  empty, and 0 otherwise, since a
931
**  boolean list is a positions list if and only if it is empty.
932
*/
933
Int IsPossBlist (
934
    Obj                 list )
935
{
936
    return LEN_BLIST(list) == 0;
937
}
938

939

940
/****************************************************************************
941
**
942

943
*F  IsDenseBlist( <list> )  . . .  dense list test function for boolean lists
944
**
945
**  'IsDenseBlist' returns 1, since boolean lists are always dense.
946
**
947
**  'IsDenseBlist' is the function in 'IsDenseBlistFuncs' for boolean lists.
948
*/
949
Int IsDenseBlist (
950
    Obj                 list )
951
{
952
    return 1L;
953
}
954

955

956
/****************************************************************************
957
**
958
*F  IsHomogBlist( <list> )  . . . . . . . . . . check if <list> is homogenous
959
*/
960
Int IsHomogBlist (
961
    Obj                 list )
962
{
963
    return (0 < LEN_BLIST(list));
964
}
965

966

967
/****************************************************************************
968
**
969
*F  IsSSortBlist( <list> )  . . . . . . .  check if <list> is strictly sorted
970
*/
971
Int IsSSortBlist (
972
    Obj                 list )
973
{
974
    Int                 isSort;
975

976
    if ( LEN_BLIST(list) <= 1 ) {
977
        isSort = 1;
978
    }
979
    else if ( LEN_BLIST(list) == 2 ) {
980
        isSort = (ELM_BLIST(list,1) == True && ELM_BLIST(list,2) == False);
981
    }
982
    else {
983
        isSort = 0;
984
    }
985
    SET_FILT_LIST( list, (isSort ? FN_IS_SSORT : FN_IS_NSORT) );
986

987
    return isSort;
988
}
989

990

991
/****************************************************************************
992
**
993
*F  IsSSortBlistNot( <list> ) . . . . . . . . . . . . . unsorted boolean list
994
*/
995
Int IsSSortBlistNot (
996
    Obj                 list )
997
{
998
    return 0L;
999
}
1000

1001

1002
/****************************************************************************
1003
**
1004
*F  IsSSortBlistYes( <list> ) . . . . . . . . . . . . . . sorted boolean list
1005
*/
1006
Int IsSSortBlistYes (
1007
    Obj                 list )
1008
{
1009
    return 1L;
1010
}
1011

1012

1013
/****************************************************************************
1014
**
1015

1016
*F  ConvBlist( <list> ) . . . . . . . . .  convert a list into a boolean list
1017
**
1018
**  `ConvBlist' changes the representation of boolean  lists into the compact
1019
**  representation of type 'T_BLIST' described above.
1020
*/
1021
void ConvBlist (
1022
    Obj                 list )
1023
{
1024
    Int                 len;            /* logical length of the list      */
1025
    UInt                block;          /* one block of the boolean list   */
1026
    UInt                bit;            /* one bit of a block              */
1027
    UInt                i;              /* loop variable                   */
1028

1029
    /* if <list> is known to be a boolean list, it is very easy            */
1030
    if ( IS_BLIST_REP(list) ) {
1031
        return;
1032
    }
1033

1034
    /* change its representation                                           */
1035
    block = 0;
1036
    bit = 1;
1037
    len = LEN_LIST( list );
1038
    for ( i = 1; i <= len; i++ ) {
1039
        if ( ELMW_LIST( list, (Int)i ) == True )
1040
            block |= bit;
1041
        bit = bit << 1;
1042
        if ( bit == 0 || i == len ) {
1043
            BLOCK_ELM_BLIST(list,i) = block;
1044
            block = 0;
1045
            bit = 1;
1046
        }
1047
    }
1048
    RetypeBag( list, IS_MUTABLE_OBJ(list) ? T_BLIST : T_BLIST+IMMUTABLE );
1049
    ResizeBag( list, SIZE_PLEN_BLIST(len) );
1050
    SET_LEN_BLIST( list, len );
1051
}
1052

1053

1054
/****************************************************************************
1055
**
1056
*F  IsBlist( <list> ) . . . . . . . . . test whether a list is a boolean list
1057
**
1058
**  'IsBlist' returns  1  if  the  list  <list> is  a  boolean list, i.e.,  a
1059
**  list that   has no holes  and contains  only  'true' and  'false',  and 0
1060
**  otherwise.
1061
*/
1062
Int IsBlist (
1063
    Obj                 list )
1064
{
1065
    UInt                isBlist;        /* result of the test              */
1066
    Int                 len;            /* logical length of the list      */
1067
    UInt                i;              /* loop variable                   */
1068

1069
    /* if <list> is known to be a boolean list, it is very easy            */
1070
    if ( IS_BLIST_REP(list) ) {
1071
        isBlist = 1;
1072
    }
1073

1074
    /* if <list> is not a small list, its not a boolean list (convert to list)   */
1075
    else if ( ! IS_SMALL_LIST( list ) ) {
1076
        isBlist = 0;
1077
    }
1078

1079
    /* otherwise test if there are holes and if all elements are boolean   */
1080
    else {
1081

1082
        /* test that all elements are bound and either 'true' or 'false'   */
1083
        len = LEN_LIST( list );
1084
        for ( i = 1; i <= len; i++ ) {
1085
            if ( ELMV0_LIST( list, (Int)i ) == 0
1086
              || (ELMW_LIST( list, (Int)i ) != True
1087
               && ELMW_LIST( list, (Int)i ) != False) ) {
1088
                break;
1089
            }
1090
        }
1091

1092
        isBlist = (len < i);
1093
    }
1094

1095
    /* return the result                                                   */
1096
    return isBlist;
1097
}
1098

1099

1100
/****************************************************************************
1101
**
1102
*F  IsBlistConv( <list> ) . test whether a list is a boolean list and convert
1103
**
1104
**  'IsBlistConv' returns 1 if  the list <list> is  a  boolean list, i.e.,  a
1105
**  list that   has no holes  and contains  only  'true' and  'false',  and 0
1106
**  otherwise.  As a  side effect 'IsBlistConv' changes the representation  of
1107
**  boolean lists into the compact representation of type 'T_BLIST' described
1108
**  above.
1109
*/
1110
Int IsBlistConv (
1111
    Obj                 list )
1112
{
1113
    UInt                isBlist;        /* result of the test              */
1114
    Int                 len;            /* logical length of the list      */
1115
    UInt                i;              /* loop variable                   */
1116

1117
    /* if <list> is known to be a boolean list, it is very easy            */
1118
    if ( IS_BLIST_REP(list) ) {
1119
        isBlist = 1;
1120
    }
1121

1122
    /* if <list> is not a list, its not a boolean list (convert to list)   */
1123
    else if ( ! IS_SMALL_LIST(list) ) {
1124
        isBlist = 0;
1125
    }
1126

1127
    /* otherwise test if there are holes and if all elements are boolean   */
1128
    else {
1129

1130
        /* test that all elements are bound and either 'true' or 'false'   */
1131
        len = LEN_LIST( list );
1132
        for ( i = 1;  i <= len;  i++ ) {
1133
            if ( ELMV0_LIST( list, (Int)i ) == 0
1134
              || (ELMW_LIST( list, (Int)i ) != True
1135
               && ELMW_LIST( list, (Int)i ) != False) ) {
1136
                break;
1137
            }
1138
        }
1139

1140
        /* if <list> is a boolean list, change its representation        */
1141
        isBlist = (len < i);
1142
        if ( isBlist ) {
1143
            ConvBlist(list);
1144
        }
1145
    }
1146

1147
    /* return the result                                                   */
1148
    return isBlist;
1149
}
1150

1151

1152
/****************************************************************************
1153
**
1154
*F  SizeBlist( <blist> )  . . . .  number of 'true' entries in a boolean list
1155
**
1156
**  'SizeBlist' returns   the number of  entries of  the boolean list <blist>
1157
**  that are 'true'.
1158
**
1159
**  The sequence to compute the  number of bits in  a block is quite  clever.
1160
**  The idea is that after the <i>-th instruction each subblock of $2^i$ bits
1161
**  holds the number of   bits of this  subblock  in the original block  <m>.
1162
**  This is illustrated in the example below for a block of with 8 bits:
1163
**
1164
**       // a b c d e f g h
1165
**      m = (m & 0x55)       +  ((m >> 1) & 0x55);
1166
**       // . b . d . f . h  +  . a . c . e . g   =  a+b c+d e+f g+h
1167
**      m = (m & 0x33)       +  ((m >> 2) & 0x33);
1168
**       // . . c+d . . g+h  +  . . a+b . . e+f   =  a+b+c+d e+f+g+h
1169
**      m = (m & 0x0f)       +  ((m >> 4) & 0x0f);
1170
**       // . . . . e+f+g+h  +  . . . . a+b+c+d   =  a+b+c+d+e+f+g+h
1171
**
1172
**  In the actual  code  some unnecessary mask  have  been removed, improving
1173
**  performance quite a bit,  because masks are 32  bit immediate values  for
1174
**  which most RISC  processors need two  instructions to load them.  Talking
1175
**  about performance.  The code is  close to optimal,  it should compile  to
1176
**  only about  22 MIPS  or SPARC instructions.   Dividing the  block into  4
1177
**  bytes and looking up the number of bits  of a byte in a  table may be 10%
1178
**  faster, but only if the table lives in the data cache.
1179
**
1180
*N  1992/12/15 martin this depends on 'BIPEB' being 32 
1181
*N  1996/11/12 Steve  altered to handle 64 bit also
1182
**
1183
**  Introduced the SizeBlist function for kernel use, and the 
1184
**  COUNT_TRUES_BLOCK( <var> ) macro which replaces a block of bits in <var> 
1185
**  by the number of ones it contains. It will fail horribly if <var> is not 
1186
**  a variable.
1187
*/
1188
UInt SizeBlist (
1189
    Obj                 blist )
1190
{
1191
    UInt *              ptr;            /* pointer to blist                */
1192
    UInt                nrb;            /* number of blocks in blist       */
1193
    UInt                m;              /* number of bits in a block       */
1194
    UInt                n;              /* number of bits in blist         */
1195
    UInt                i;              /* loop variable                   */
1196

1197
    /* get the number of blocks and a pointer                              */
1198
    nrb = NUMBER_BLOCKS_BLIST(blist);
1199
    ptr = BLOCKS_BLIST( blist );
1200

1201
    /* loop over the blocks, adding the number of bits of each one         */
1202
    n = 0;
1203
    for ( i = 1; i <= nrb; i++ ) {
1204
        m = *ptr++;
1205
        COUNT_TRUES_BLOCK(m);
1206
        n += m;
1207
    }
1208

1209
    /* return the number of bits                                           */
1210
    return n;
1211
}
1212

1213

1214
/****************************************************************************
1215
**
1216

1217
*F * * * * * * * * * * * * * * GAP level functions  * * * * * * * * * * * * *
1218
*/
1219

1220
/****************************************************************************
1221
**
1222

1223

1224
*F  FuncIS_BLIST( <self>, <val> ) . . . . . test if a value is a boolean list
1225
**
1226
**  'FuncIS_BLIST' handles the internal function 'IsBlist'.
1227
**
1228
**  'IsBlist( <val> )'
1229
**
1230
**  'IsBlist' returns 'true' if the value <val> is a boolean list and 'false'
1231
**  otherwise.  A value is a   boolean list if  it is  a lists without  holes
1232
**  containing only  'true' and 'false'.
1233
*/
1234
Obj IsBlistFilt;
1235

1236
Obj FuncIS_BLIST (
1237
    Obj                 self,
1238
    Obj                 val )
1239
{
1240
    /* let 'IsBlist' do the work                                           */
1241
    return IsBlist( val ) ? True : False;
1242
}
1243

1244

1245
/****************************************************************************
1246
**
1247
*F  FuncIS_BLIST_CONV( <self>, <val> )  . . test if a value is a boolean list
1248
**
1249
**  'FuncIS_BLIST_CONV' handles the internal function 'IsBlist'.
1250
**
1251
**  'IsBlistConv( <val> )'
1252
**
1253
**  'IsBlist' returns 'true' if the value <val> is a boolean list and 'false'
1254
**  otherwise.  A value is a   boolean list if  it is  a lists without  holes
1255
**  containing only  'true' and 'false'.
1256
*/
1257
Obj IsBlistFilt;
1258

1259
Obj FuncIS_BLIST_CONV (
1260
    Obj                 self,
1261
    Obj                 val )
1262
{
1263
    /* let 'IsBlist' do the work                                           */
1264
    return IsBlistConv( val ) ? True : False;
1265
}
1266

1267

1268
/****************************************************************************
1269
**
1270
*F  FuncCONV_BLIST( <self>, <blist> ) . . . . convert into a boolean list rep
1271
*/
1272
Obj FuncCONV_BLIST (
1273
    Obj                 self,
1274
    Obj                 blist )
1275
{
1276
    /* check whether <blist> is a boolean list                             */
1277
    while ( ! IsBlistConv(blist) ) {
1278
        blist = ErrorReturnObj(
1279
            "CONV_BLIST: <blist> must be a boolean list (not a %s)",
1280
            (Int)TNAM_OBJ(blist), 0L,
1281
            "you can replace <blist> via 'return <blist>;'" );
1282
    }
1283

1284
    /* return nothing                                                      */
1285
    return 0;
1286
}
1287

1288
/****************************************************************************
1289
**
1290
**
1291
*F  FuncIS_BLIST_REP( <self>, <obj> ) . . test if value is a boolean list rep
1292
*/
1293
Obj IsBlistRepFilt;
1294

1295
Obj FuncIS_BLIST_REP (
1296
    Obj                 self,
1297
    Obj                 obj )
1298
{
1299
    return (IS_BLIST_REP( obj ) ? True : False);
1300
}
1301

1302

1303
/****************************************************************************
1304
**
1305

1306
*F  FuncSIZE_BLIST( <self>, <blist> ) . . number of 'true' entries in <blist>
1307
**
1308
**  'FuncSIZE_BLIST' implements the internal function 'SizeBlist'
1309
*/
1310
Obj FuncSIZE_BLIST (
1311
    Obj                 self,
1312
    Obj                 blist )
1313
{
1314
    /* get and check the argument                                          */
1315
    while ( ! IsBlistConv(blist) ) {
1316
        blist = ErrorReturnObj(
1317
            "SizeBlist: <blist> must be a boolean list (not a %s)",
1318
            (Int)TNAM_OBJ(blist), 0L,
1319
            "you can replace <blist> via 'return <blist>;'" );
1320
    }
1321
  
1322
    return INTOBJ_INT(SizeBlist(blist));
1323
}
1324

1325

1326

1327
/****************************************************************************
1328
**
1329
*F  FuncBLIST_LIST( <self>, <list>, <sub> )  make boolean list from a sublist
1330
**
1331
**  'FuncBLIST_LIST' implements the internal function 'BlistList'.
1332
**
1333
**  'BlistList( <list>, <sub> )'
1334
**
1335
**  'BlistList'  creates a boolean  list   that describes the  list <sub>  as
1336
**  sublist  of the list  <list>.  The result  is a new boolean list <blist>,
1337
**  which has the same length  as <list>, such  that '<blist>[<i>]' is 'true'
1338
**  if '<list>[<i>]' is an element of <sub> and 'false' otherwise.
1339
**
1340
**  'BlistList' is most effective if <list> is a set, but can be used with an
1341
**  arbitrary list that has no holes.
1342
*/
1343
Obj FuncBLIST_LIST (
1344
    Obj                 self,
1345
    Obj                 list,
1346
    Obj                 sub )
1347
{
1348
    Obj                 blist;          /* boolean list, result            */
1349
    UInt  *             ptrBlist;       /* pointer to the boolean list     */
1350
    UInt                block;          /* one block of boolean list       */
1351
    UInt                bit;            /* one bit of block                */
1352
    Int                 lenList;        /* logical length of the list      */
1353
    Obj *               ptrSub;         /* pointer to the sublist          */
1354
    UInt                lenSub;         /* logical length of sublist       */
1355
    UInt                i, j, k = 0, l;     /* loop variables                  */
1356
    long                s, t;           /* elements of a range             */
1357

1358
    /* get and check the arguments                                         */
1359
    while ( ! IS_SMALL_LIST(list) ) {
1360
        list = ErrorReturnObj(
1361
            "BlistList: <list> must be a small list (not a %s)",
1362
            (Int)TNAM_OBJ(list), 0L,
1363
            "you can replace <list> via 'return <list>;'" );
1364
    }
1365
    while ( ! IS_SMALL_LIST(sub) ) {
1366
        sub = ErrorReturnObj(
1367
            "BlistList: <sub> must be a small list (not a %s)",
1368
            (Int)TNAM_OBJ(sub), 0L,
1369
            "you can replace <sub> via 'return <sub>;'" );
1370
    }
1371

1372
    /* for a range as subset of a range, it is extremely easy               */
1373
    if ( IS_RANGE(list) && IS_RANGE(sub) && GET_INC_RANGE( list ) == 1
1374
          && GET_INC_RANGE( sub ) == 1) {
1375

1376
        /* allocate the boolean list and get pointer                       */
1377
        lenList  = GET_LEN_RANGE( list );
1378
        lenSub   = GET_LEN_RANGE( sub );
1379
        blist = NewBag( T_BLIST, SIZE_PLEN_BLIST( lenList ) );
1380
        ADDR_OBJ(blist)[0] = INTOBJ_INT(lenList);
1381
        ptrBlist = BLOCKS_BLIST(blist);
1382

1383
        /* get the bounds of the subset with respect to the boolean list   */
1384
        s = INT_INTOBJ( GET_ELM_RANGE( list, 1 ) );
1385
        t = INT_INTOBJ( GET_ELM_RANGE( sub, 1 ) );
1386
        if ( s <= t )  i = t - s + 1;
1387
        else           i = 1;
1388

1389
        if ( i + lenSub - 1 <= lenList )  j = i + lenSub - 1;
1390
        else                              j = lenList;
1391

1392
        /* set the corresponding entries to 'true'                         */
1393
        for ( k = i; k <= j && (k-1)%BIPEB != 0; k++ )
1394
            ptrBlist[(k-1)/BIPEB] |= (1UL << (k-1)%BIPEB);
1395
        for ( ; k+BIPEB <= j; k += BIPEB )
1396
            ptrBlist[(k-1)/BIPEB] = ~(UInt)0;
1397
        for ( ; k <= j; k++ )
1398
            ptrBlist[(k-1)/BIPEB] |= (1UL << (k-1)%BIPEB);
1399

1400
    }
1401

1402
    /* for a list as subset of a range, we need basically no search        */
1403
    else if ( IS_RANGE(list) && GET_INC_RANGE( list) == 1
1404
          && IS_PLIST(sub) ) {
1405

1406
        /* allocate the boolean list and get pointer                       */
1407
        lenList  = GET_LEN_RANGE( list );
1408
        lenSub   = LEN_LIST( sub );
1409
        blist = NewBag( T_BLIST, SIZE_PLEN_BLIST( lenList ) );
1410
        ADDR_OBJ(blist)[0] = INTOBJ_INT(lenList);
1411
        ptrBlist = BLOCKS_BLIST(blist);
1412
        ptrSub = ADDR_OBJ(sub);
1413

1414
        /* loop over <sub> and set the corresponding entries to 'true'     */
1415
        s = INT_INTOBJ( GET_ELM_RANGE( list, 1 ) );
1416
        for ( l = 1; l <= LEN_LIST(sub); l++ ) {
1417
            if ( ptrSub[l] != 0 ) {
1418

1419
                /* if <sub>[<l>] is an integer it is very easy             */
1420
                if ( TNUM_OBJ( ptrSub[l] ) == T_INT ) {
1421
                    t = INT_INTOBJ( ptrSub[l] ) - s + 1;
1422
                    if ( 0 < t && t <= lenList )
1423
                        ptrBlist[(t-1)/BIPEB] |= (1UL << (t-1)%BIPEB);
1424
                }
1425

1426
     /* Nobody seems to remember what the code below is good for,
1427
      * we will now just assume that non-immediate integers are
1428
      * never in a range. I'll leave the old code in a comment
1429
      * for a while, the third arg for PosRange is wrong anyway.
1430
      * FL  */
1431
                /* otherwise it may be a record, let 'PosRange' handle it  */
1432
              /*  else {
1433
                    Obj pos;
1434
                    pos = PosRange( list, ptrSub[l], 0L );
1435
                    if (pos != Fail) {
1436
                      k = INT_INTOBJ(pos);
1437
                      ptrBlist[(k-1)/BIPEB] |= (1UL << (k-1)%BIPEB);
1438
                    }  
1439
                } */
1440

1441
            }
1442
        }
1443

1444
    }
1445

1446
    /* if <list> is a set we have two possibilities                        */
1447
    else if ( IsSet( list ) ) {
1448

1449
        /* get the length of <list> and its logarithm                      */
1450
        lenList = LEN_PLIST( list );
1451
        for ( i = lenList, l = 0; i != 0; i >>= 1, l++ ) ;
1452
        PLAIN_LIST( sub );
1453
        lenSub = LEN_LIST( sub );
1454

1455
        /* if <sub> is small, we loop over <sub> and use binary search     */
1456
        if ( l * lenSub < 2 * lenList ) {
1457

1458
            /* allocate the boolean list and get pointer                   */
1459
            blist = NewBag( T_BLIST, SIZE_PLEN_BLIST( lenList ) );
1460
            ADDR_OBJ(blist)[0] = INTOBJ_INT(lenList);
1461

1462
            /* run over the elements of <sub> and search for the elements  */
1463
            for ( l = 1; l <= LEN_LIST(sub); l++ ) {
1464
                if ( ADDR_OBJ(sub)[l] != 0 ) {
1465

1466
                    /* perform the binary search to find the position      */
1467
                    i = 0;  k = lenList+1;
1468
                    while ( i+1 < k ) {
1469
                        j = (i + k) / 2;
1470
                        if ( LT(ADDR_OBJ(list)[j],ADDR_OBJ(sub)[l]) )
1471
                            i = j;
1472
                        else
1473
                            k = j;
1474
                    }
1475

1476
                    /* set bit if <sub>[<l>] was found at position k       */
1477
                    if ( k <= lenList
1478
                      && EQ( ADDR_OBJ(list)[k], ADDR_OBJ(sub)[l] ) )
1479
                      SET_ELM_BLIST( blist, k, True);
1480
                }
1481
            }
1482

1483
        }
1484

1485
        /* if <sub> is large, run over both list in parallel               */
1486
        else {
1487

1488
            /* turn the <sub> into a set for faster searching              */
1489
            if ( ! IsSet( sub ) ) {
1490
                sub = SetList( sub );
1491
                lenSub = LEN_LIST( sub );
1492
            }
1493

1494
            /* allocate the boolean list and get pointer                   */
1495
            blist = NewBag( T_BLIST, SIZE_PLEN_BLIST( lenList ) );
1496
            ADDR_OBJ(blist)[0] = INTOBJ_INT(lenList);
1497

1498
            /* run over the elements of <list>                             */
1499
            k = 1;
1500
            block = 0;
1501
            bit   = 1;
1502
            for ( l = 1; l <= lenList; l++ ) {
1503

1504
                /* test if <list>[<l>] is in <sub>                         */
1505
                while ( k <= lenSub
1506
                     && LT(ADDR_OBJ(sub)[k],ADDR_OBJ(list)[l]) )
1507
                    k++;
1508

1509
                /* if <list>[<k>] is in <sub> set the current bit in block */
1510
                if ( k <= lenSub
1511
                  && EQ(ADDR_OBJ(sub)[k],ADDR_OBJ(list)[l]) ) {
1512
                    block |= bit;
1513
                    k++;
1514
                }
1515

1516
                /* if block is full add it to boolean list and start next  */
1517
                bit = bit << 1;
1518
                if ( bit == 0 || l == lenList ) {
1519
                  BLOCK_ELM_BLIST( blist, l) = block;
1520
                  block = 0;
1521
                  bit   = 1;
1522
                }
1523

1524
            }
1525
        }
1526

1527
    }
1528

1529
    /* if <list> is not a set, we have to use brute force                  */
1530
    else {
1531

1532
        /* convert left argument to an ordinary list, ignore return value  */
1533
        PLAIN_LIST( list );
1534

1535
        /* turn <sub> into a set for faster searching                      */
1536
        if ( ! IsSet( sub ) )  sub = SetList( sub );
1537

1538
        /* allocate the boolean list and get pointer                       */
1539
        lenList  = LEN_LIST( list );
1540
        lenSub   = LEN_PLIST( sub );
1541
        blist = NewBag( T_BLIST, SIZE_PLEN_BLIST( lenList ) );
1542
        ADDR_OBJ(blist)[0] = INTOBJ_INT(lenList);
1543

1544
        /* run over the elements of <list>                                 */
1545
        k = 1;
1546
        block = 0;
1547
        bit   = 1;
1548
        for ( l = 1; l <= lenList; l++ ) {
1549

1550
            /* test if <list>[<l>] is in <sub>                             */
1551
            if ( l == 1 || LT(ADDR_OBJ(list)[l-1],ADDR_OBJ(list)[l]) ){
1552
                while ( k <= lenSub
1553
                     && LT(ADDR_OBJ(sub)[k],ADDR_OBJ(list)[l]) )
1554
                    k++;
1555
            }
1556
            else {
1557
                i = 0;  k = LEN_PLIST(sub) + 1;
1558
                while ( i+1 < k ) {
1559
                    j = (i + k) / 2;
1560
                    if ( LT( ADDR_OBJ(sub)[j], ADDR_OBJ(list)[l] ) )
1561
                        i = j;
1562
                    else
1563
                        k = j;
1564
                }
1565
            }
1566

1567
            /* if <list>[<k>] is in <sub> set the current bit in the block */
1568
            if ( k <= lenSub
1569
              && EQ( ADDR_OBJ(sub)[k], ADDR_OBJ(list)[l] ) ) {
1570
                block |= bit;
1571
                k++;
1572
            }
1573

1574
            /* if block is full add it to the boolean list and start next  */
1575
            bit = bit << 1;
1576
            if ( bit == 0 || l == lenList ) {
1577
                BLOCK_ELM_BLIST( blist, l) =  block;
1578
                block = 0;
1579
                bit   = 1;
1580
            }
1581
        }
1582

1583
    }
1584

1585
    /* return the boolean list                                             */
1586
    return blist;
1587
}
1588

1589

1590

1591
/****************************************************************************
1592
**
1593
*F  FuncLIST_BLIST( <self>, <list>, <blist> ) . make a sublist from a <blist>
1594
**
1595
**  'FuncListBlist' implements the internal function 'ListBlist'.
1596
**
1597
**  'ListBlist( <list>, <blist> )'
1598
**
1599
**  'ListBlist' returns the  sublist of the  elements of the list  <list> for
1600
**  which the boolean list   <blist>, which must   have  the same  length  as
1601
**  <list>, contains 'true'.  The order of the elements in the result is  the
1602
**  same as in <list>.
1603
**
1604
*/
1605
Obj FuncLIST_BLIST (
1606
    Obj                 self,
1607
    Obj                 list,
1608
    Obj                 blist )
1609
{
1610
    Obj                 sub;            /* handle of the result            */
1611
    Int                 len;            /* logical length of the list      */
1612
    UInt                n;              /* number of bits in blist         */
1613
    UInt                nn;
1614
    UInt                i;              /* loop variable                   */
1615

1616
    /* get and check the first argument                                    */
1617
    while ( ! IS_SMALL_LIST( list ) ) {
1618
        list = ErrorReturnObj(
1619
            "ListBlist: <list> must be a small list (not a %s)",
1620
            (Int)TNAM_OBJ(list), 0L,
1621
            "you can replace <list> via 'return <list>;'" );
1622
    }
1623
    /* get and check the second argument                                   */
1624
    while ( ! IsBlistConv( blist ) ) {
1625
        blist = ErrorReturnObj(
1626
            "ListBlist: <blist> must be a boolean list (not a %s)",
1627
            (Int)TNAM_OBJ(blist), 0L,
1628
            "you can replace <blist> via 'return <blist>;'" );
1629
    }
1630
    while ( LEN_LIST( list ) != LEN_BLIST( blist ) ) {
1631
        blist = ErrorReturnObj(
1632
            "ListBlist: <blist> must have the same length as <list> (%d)",
1633
            LEN_PLIST( list ), 0L,
1634
            "you can replace <blist> via 'return <blist>;'" );
1635
    }
1636

1637
    /* compute the number of 'true'-s                                      */
1638
    n = SizeBlist(blist);
1639

1640
    /* make the sublist (we now know its size exactly)                    */
1641
    sub = NEW_PLIST( IS_MUTABLE_OBJ(list) ? T_PLIST : T_PLIST+IMMUTABLE, n );
1642
    SET_LEN_PLIST( sub, n );
1643

1644
    /* loop over the boolean list and stuff elements into <sub>            */
1645
    len = LEN_LIST( list );
1646
    nn  = 1;
1647
    for ( i = 1;  nn <= n && i <= len;  i++  ) {
1648
        if ( ELM_BLIST( blist, i ) == True ) {
1649
            SET_ELM_PLIST( sub, (Int)nn, ELMW_LIST( list, (Int)i ) );
1650
            CHANGED_BAG( sub );
1651
            nn++;
1652
        }
1653
    }
1654

1655
    /* return the sublist                                                  */
1656
    return sub;
1657
}
1658

1659

1660
/****************************************************************************
1661
**
1662

1663
*F  FuncPositionsTrueBlist( <self>, <blist> ) . . . true positions in a blist
1664
**
1665
*N  1992/12/15 martin this depends on 'BIPEB' being 32
1666
*N  Fix up for 64 bit SL
1667
*/
1668
Obj FuncPositionsTrueBlist (
1669
    Obj                 self,
1670
    Obj                 blist )
1671
{
1672
    Obj                 sub;            /* handle of the result            */
1673
    Int                 len;            /* logical length of the list      */
1674
    UInt  *             ptr;            /* pointer to blist                */
1675
    UInt                nrb;            /* number of blocks in blist       */
1676
    UInt                m;              /* number of bits in a block       */
1677
    UInt                n;              /* number of bits in blist         */
1678
    UInt                nn;
1679
    UInt                i;              /* loop variable                   */
1680

1681
    /* get and check the first argument                                    */
1682
    while ( ! IsBlistConv( blist ) ) {
1683
        blist = ErrorReturnObj(
1684
            "ListBlist: <blist> must be a boolean list (not a %s)",
1685
            (Int)TNAM_OBJ(blist), 0L,
1686
            "you can replace <blist> via 'return <blist>;'" );
1687
    }
1688

1689
    /* compute the number of 'true'-s just as in 'FuncSIZE_BLIST'            */
1690
    nrb = NUMBER_BLOCKS_BLIST( blist);
1691
    ptr = BLOCKS_BLIST( blist );
1692
    n = 0;
1693
    for ( i = 1; i <= nrb; i++ ) {
1694
        m = *ptr++;
1695
        COUNT_TRUES_BLOCK(m);
1696
        n += m;
1697
    }
1698

1699
    /* make the sublist (we now know its size exactly)                    */
1700
    sub = NEW_PLIST( T_PLIST, n );
1701
    SET_LEN_PLIST( sub, n );
1702

1703
    /* loop over the boolean list and stuff elements into <sub>            */
1704
    /* This could be a bit quicker for sparse blists by skipping whole empty
1705
       blocks as we go past                  SL  9/1/97                    */
1706
    len = LEN_BLIST( blist );
1707
    nn  = 1;
1708
    for ( i = 1; nn <= n && i <= len;  i++ ) {
1709
        if ( ELM_BLIST( blist, i ) == True ) {
1710
            SET_ELM_PLIST( sub, nn, INTOBJ_INT(i) );
1711
            nn++;
1712
        }
1713
    }
1714
    CHANGED_BAG(sub);
1715

1716
    /* return the sublist                                                  */
1717
    return sub;
1718
}
1719

1720

1721
/****************************************************************************
1722
**
1723
*F  FuncPositionNthTrueBlist( <self>, <blist>, <Nth> )  . . . find true value
1724
**
1725
*N  1992/12/15 martin this depends on 'BIPEB' being 32
1726
*N  Fixed up for 64 SL
1727
*/
1728
Obj FuncPositionNthTrueBlist (
1729

1730
    Obj                 self,
1731
    Obj                 blist,
1732
    Obj                 Nth )
1733
{
1734
    UInt                nrb;
1735
    Int                 nth,  pos,  i;
1736
    UInt                m,  mask;
1737
    UInt  *             ptr;
1738

1739
    /* Check the arguments. */    
1740
    while ( ! IsBlistConv( blist ) ) {
1741
        blist = ErrorReturnObj(
1742
            "ListBlist: <blist> must be a boolean list (not a %s)",
1743
            (Int)TNAM_OBJ(blist), 0L,
1744
            "you can replace <blist> via 'return <blist>;'" );
1745
    }
1746
    while ( ! IS_INTOBJ(Nth) || INT_INTOBJ(Nth) <= 0 ) {
1747
        Nth = ErrorReturnObj(
1748
            "Position: <nth> must be a positive integer (not a %s)",
1749
            (Int)TNAM_OBJ(Nth), 0L,
1750
            "you can replace <nth> via 'return <nth>;'" );
1751
    }
1752
    
1753
    nrb = NUMBER_BLOCKS_BLIST(blist);
1754
    if ( ! nrb )  return Fail;
1755
    nth = INT_INTOBJ( Nth );
1756
    pos = 0;
1757
    ptr = BLOCKS_BLIST( blist );
1758
    i = 1;
1759
    m = *ptr;
1760
    COUNT_TRUES_BLOCK(m);
1761
    while ( nth > m ) {
1762
        if ( ++i > nrb )  return Fail;
1763
        nth -= m;
1764
        pos += BIPEB;
1765
        ptr++;
1766
        m = *ptr;
1767
        COUNT_TRUES_BLOCK(m);
1768
    }
1769
    m = *ptr;
1770
    mask = 0x1;
1771
    while ( nth > 0 ) {
1772
        pos++;
1773
        if ( m & mask )  nth--;
1774
        mask <<= 1;
1775
    }
1776
    return INTOBJ_INT( pos );
1777
}
1778

1779

1780
/****************************************************************************
1781
**
1782
*F  FuncIsSubsetBlist( <self>, <list1>, <list2> ) . . . . . . . . subset test
1783
**
1784
**  'FuncIsSubsetBlist' implements the internal function 'IsSubsetBlist'.
1785
**
1786
**  'IsSubsetBlist( <list1>, <list2> )'
1787
**
1788
**  'IsSubsetBlist' returns 'true' if the boolean list <list2> is a subset of
1789
**  the  boolean  list <list1>, which must  have  equal length.  <list2> is a
1790
**  subset if <list1> if '<list2>[<i>] >= <list1>[<i>]' for all <i>.
1791
*/
1792
Obj FuncIS_SUB_BLIST (
1793
    Obj                 self,
1794
    Obj                 list1,
1795
    Obj                 list2 )
1796
{
1797
    UInt *              ptr1;           /* pointer to the first argument   */
1798
    UInt *              ptr2;           /* pointer to the second argument  */
1799
    UInt                i;              /* loop variable                   */
1800

1801
    /* get and check the arguments                                         */
1802
    while ( ! IsBlistConv( list1 ) ) {
1803
        list1 = ErrorReturnObj(
1804
            "IsSubsetBlist: <blist1> must be a boolean list (not a %s)",
1805
            (Int)TNAM_OBJ(list1), 0L,
1806
            "you can replace <blist1> via 'return <blist1>;'" );
1807
    }
1808
    while ( ! IsBlistConv( list2 ) ) {
1809
        list2 = ErrorReturnObj(
1810
            "IsSubsetBlist: <blist2> must be a boolean list (not a %s)",
1811
            (Int)TNAM_OBJ(list2), 0L,
1812
            "you can replace <blist2> via 'return <blist2>;'" );
1813
    }
1814
    while ( LEN_BLIST(list1) != LEN_BLIST(list2) ) {
1815
        list2 = ErrorReturnObj(
1816
        "IsSubsetBlist: <blist2> must have the same length as <blist1> (%d)",
1817
            LEN_BLIST(list1), 0L,
1818
            "you can replace <blist2> via 'return <blist2>;'" );
1819
    }
1820

1821
    /* test for subset property blockwise                                  */
1822
    ptr1 = BLOCKS_BLIST(list1);
1823
    ptr2 = BLOCKS_BLIST(list2);
1824

1825
    for ( i = NUMBER_BLOCKS_BLIST(list1); 0 < i; i-- ) {
1826
        if ( *ptr1 != (*ptr1 | *ptr2) )
1827
            break;
1828
        ptr1++;  ptr2++;
1829
    }
1830

1831
    /* if no counterexample was found, <blist2> is a subset of <blist1>    */
1832
    return (i == 0) ? True : False;
1833
}
1834

1835

1836
/****************************************************************************
1837
**
1838
*F  FuncUNITE_BLIST( <self>, <list1>, <list2> ) . unite one list with another
1839
**
1840
**  'FuncUNITE_BLIST' implements the internal function 'UniteBlist'.
1841
**
1842
**  'UniteBlist( <blist1>, <blist2> )'
1843
**
1844
**  'UniteBlist'  unites  the  boolean list  <blist1>  with  the boolean list
1845
**  <blist2>,  which  must  have the   same  length.  This  is  equivalent to
1846
**  assigning '<blist1>[<i>] := <blist1>[<i>] or <blist2>[<i>]' for all <i>.
1847
*/
1848
Obj FuncUNITE_BLIST (
1849
    Obj                 self,
1850
    Obj                 list1,
1851
    Obj                 list2 )
1852
{
1853
    UInt *              ptr1;           /* pointer to the first argument   */
1854
    UInt *              ptr2;           /* pointer to the second argument  */
1855
    UInt                i;              /* loop variable                   */
1856

1857
    /* get and check the arguments                                         */
1858
    while ( ! IsBlistConv( list1 ) ) {
1859
        list1 = ErrorReturnObj(
1860
            "UniteBlist: <blist1> must be a boolean list (not a %s)",
1861
            (Int)TNAM_OBJ(list1), 0L,
1862
            "you can replace <blist1> via 'return <blist1>;'" );
1863
    }
1864
    while ( ! IsBlistConv( list2 ) ) {
1865
        list2 = ErrorReturnObj(
1866
            "UniteBlist: <blist2> must be a boolean list (not a %s)",
1867
            (Int)TNAM_OBJ(list2), 0L,
1868
            "you can replace <blist2> via 'return <blist2>;'" );
1869
    }
1870
    while ( LEN_BLIST(list1) != LEN_BLIST(list2) ) {
1871
        list2 = ErrorReturnObj(
1872
           "UniteBlist: <blist2> must have the same length as <blist1> (%d)",
1873
            LEN_BLIST(list1), 0L,
1874
            "you can replace <blist2> via 'return <blist2>;'" );
1875
    }
1876

1877
    /* compute the union by *or*-ing blockwise                             */
1878
    ptr1 = BLOCKS_BLIST(list1);
1879
    ptr2 = BLOCKS_BLIST(list2);
1880
    for ( i = (LEN_BLIST(list1)+BIPEB-1)/BIPEB; 0 < i; i-- ) {
1881
        *ptr1++ |= *ptr2++;
1882
    }
1883

1884
    /* return nothing, this function is a procedure                        */
1885
    return 0;
1886
}
1887

1888

1889
/****************************************************************************
1890
**
1891
*F  FuncUNITE_BLIST_LIST( <self>, <list>,<blist>, <sub> )
1892
**
1893
**  'FuncUNITE_BLIST_LIST' implements the internal function 'BlistList'.
1894
**
1895
**  'UniteBlistList( <list>,<blist>, <sub> )'
1896
**
1897
**  'UniteBlistList'  works like `BlistList', but adds the entries to the
1898
**  existing <blist>.
1899
*/
1900
Obj FuncUNITE_BLIST_LIST (
1901
    Obj                 self,
1902
    Obj                 list,
1903
    Obj                 blist,
1904
    Obj                 sub )
1905
{
1906
    UInt  *             ptrBlist;       /* pointer to the boolean list     */
1907
    UInt                block;          /* one block of boolean list       */
1908
    UInt                bit;            /* one bit of block                */
1909
    Int                 lenList;        /* logical length of the list      */
1910
    Obj *               ptrSub;         /* pointer to the sublist          */
1911
    UInt                lenSub;         /* logical length of sublist       */
1912
    UInt                i, j, k = 0, l;     /* loop variables                  */
1913
    long                s, t;           /* elements of a range             */
1914

1915
    /* get and check the arguments                                         */
1916
    while ( ! IS_SMALL_LIST(list) ) {
1917
        list = ErrorReturnObj(
1918
            "UniteBlistList: <list> must be a small list (not a %s)",
1919
            (Int)TNAM_OBJ(list), 0L,
1920
            "you can replace <list> via 'return <list>;'" );
1921
    }
1922
    while ( ! IsBlistConv( blist ) ) {
1923
        blist = ErrorReturnObj(
1924
            "UniteBlistList: <blist> must be a boolean list (not a %s)",
1925
            (Int)TNAM_OBJ(blist), 0L,
1926
            "you can replace <blist> via 'return <blist>;'" );
1927
    }
1928
    while ( ! IS_SMALL_LIST(sub) ) {
1929
        sub = ErrorReturnObj(
1930
            "UniteBlistList: <sub> must be a small list (not a %s)",
1931
            (Int)TNAM_OBJ(sub), 0L,
1932
            "you can replace <sub> via 'return <sub>;'" );
1933
    }
1934

1935
    /* for a range as subset of a range, it is extremely easy               */
1936
    if ( IS_RANGE(list) && IS_RANGE(sub) && GET_INC_RANGE( list ) == 1
1937
          && GET_INC_RANGE( sub ) == 1) {
1938

1939
        /* allocate the boolean list and get pointer                       */
1940
        lenList  = GET_LEN_RANGE( list );
1941

1942
        /* check length */
1943
        while ( LEN_BLIST(blist) != lenList ) {
1944
            blist = ErrorReturnObj(
1945
              "UniteBlistList: <blist> must have the same length as <list> (%d)",
1946
                lenList, 0L,
1947
                "you can replace <blist> via 'return <blist>;'" );
1948
        }
1949

1950
        lenSub   = GET_LEN_RANGE( sub );
1951
        ptrBlist = BLOCKS_BLIST(blist);
1952

1953
        /* get the bounds of the subset with respect to the boolean list   */
1954
        s = INT_INTOBJ( GET_ELM_RANGE( list, 1 ) );
1955
        t = INT_INTOBJ( GET_ELM_RANGE( sub, 1 ) );
1956
        if ( s <= t )  i = t - s + 1;
1957
        else           i = 1;
1958

1959
        if ( i + lenSub - 1 <= lenList )  j = i + lenSub - 1;
1960
        else                              j = lenList;
1961

1962
        /* set the corresponding entries to 'true'                         */
1963
        for ( k = i; k <= j && (k-1)%BIPEB != 0; k++ )
1964
            ptrBlist[(k-1)/BIPEB] |= (1UL << (k-1)%BIPEB);
1965
        for ( ; k+BIPEB <= j; k += BIPEB )
1966
            ptrBlist[(k-1)/BIPEB] = ~(UInt)0;
1967
        for ( ; k <= j; k++ )
1968
            ptrBlist[(k-1)/BIPEB] |= (1UL << (k-1)%BIPEB);
1969

1970
    }
1971

1972
    /* for a list as subset of a range, we need basically no search        */
1973
    else if ( IS_RANGE(list) && GET_INC_RANGE( list) == 1
1974
          && IS_PLIST(sub) ) {
1975

1976
        /* allocate the boolean list and get pointer                       */
1977
        lenList  = GET_LEN_RANGE( list );
1978

1979
        /* check length */
1980
        while ( LEN_BLIST(blist) != lenList ) {
1981
            blist = ErrorReturnObj(
1982
              "UniteBlistList: <blist> must have the same length as <list> (%d)",
1983
                lenList, 0L,
1984
                "you can replace <blist> via 'return <blist>;'" );
1985
        }
1986

1987
        lenSub   = LEN_LIST( sub );
1988
        ptrBlist = BLOCKS_BLIST(blist);
1989
        ptrSub = ADDR_OBJ(sub);
1990

1991
        /* loop over <sub> and set the corresponding entries to 'true'     */
1992
        s = INT_INTOBJ( GET_ELM_RANGE( list, 1 ) );
1993
        for ( l = 1; l <= LEN_LIST(sub); l++ ) {
1994
            if ( ptrSub[l] != 0 ) {
1995

1996
                /* if <sub>[<l>] is an integer it is very easy             */
1997
                if ( TNUM_OBJ( ptrSub[l] ) == T_INT ) {
1998
                    t = INT_INTOBJ( ptrSub[l] ) - s + 1;
1999
                    if ( 0 < t && t <= lenList )
2000
                        ptrBlist[(t-1)/BIPEB] |= (1UL << (t-1)%BIPEB);
2001
                }
2002

2003
       /* see comment where PosRange was used above   FL */         
2004
                /* otherwise it may be a record, let 'PosRange' handle it  */
2005
              /*  else {
2006
                  Obj pos;
2007
                    pos = PosRange( list, ptrSub[l], 0L );
2008
                    if (pos != Fail)
2009
                      k = INT_INTOBJ(pos);
2010
                    ptrBlist[(k-1)/BIPEB] |= (1UL << (k-1)%BIPEB);
2011
                }    */
2012

2013
            }
2014
        }
2015

2016
    }
2017

2018
    /* if <list> is a set we have two possibilities                        */
2019
    else if ( IsSet( list ) ) {
2020

2021
        /* get the length of <list> and its logarithm                      */
2022
        lenList = LEN_PLIST( list );
2023

2024
        /* check length */
2025
        while ( LEN_BLIST(blist) != lenList ) {
2026
            blist = ErrorReturnObj(
2027
              "UniteBlistList: <blist> must have the same length as <list> (%d)",
2028
                lenList, 0L,
2029
                "you can replace <blist> via 'return <blist>;'" );
2030
        }
2031

2032
        for ( i = lenList, l = 0; i != 0; i >>= 1, l++ ) ;
2033
        PLAIN_LIST( sub );
2034
        lenSub = LEN_LIST( sub );
2035

2036
        /* if <sub> is small, we loop over <sub> and use binary search     */
2037
        if ( l * lenSub < 2 * lenList ) {
2038

2039
            /* allocate the boolean list and get pointer                   */
2040

2041
            /* run over the elements of <sub> and search for the elements  */
2042
            for ( l = 1; l <= LEN_LIST(sub); l++ ) {
2043
                if ( ADDR_OBJ(sub)[l] != 0 ) {
2044

2045
                    /* perform the binary search to find the position      */
2046
                    i = 0;  k = lenList+1;
2047
                    while ( i+1 < k ) {
2048
                        j = (i + k) / 2;
2049
                        if ( LT(ADDR_OBJ(list)[j],ADDR_OBJ(sub)[l]) )
2050
                            i = j;
2051
                        else
2052
                            k = j;
2053
                    }
2054

2055
                    /* set bit if <sub>[<l>] was found at position k       */
2056
                    if ( k <= lenList
2057
                      && EQ( ADDR_OBJ(list)[k], ADDR_OBJ(sub)[l] ) )
2058
                      SET_ELM_BLIST( blist, k, True);
2059
                }
2060
            }
2061

2062
        }
2063

2064
        /* if <sub> is large, run over both list in parallel               */
2065
        else {
2066

2067
            /* turn the <sub> into a set for faster searching              */
2068
            if ( ! IsSet( sub ) ) {
2069
                sub = SetList( sub );
2070
                lenSub = LEN_LIST( sub );
2071
            }
2072

2073
            /* run over the elements of <list>                             */
2074
            k = 1;
2075
            block = 0;
2076
            bit   = 1;
2077
            for ( l = 1; l <= lenList; l++ ) {
2078

2079
                /* test if <list>[<l>] is in <sub>                         */
2080
                while ( k <= lenSub
2081
                     && LT(ADDR_OBJ(sub)[k],ADDR_OBJ(list)[l]) )
2082
                    k++;
2083

2084
                /* if <list>[<k>] is in <sub> set the current bit in block */
2085
                if ( k <= lenSub
2086
                  && EQ(ADDR_OBJ(sub)[k],ADDR_OBJ(list)[l]) ) {
2087
                    block |= bit;
2088
                    k++;
2089
                }
2090

2091
                /* if block is full add it to boolean list and start next  */
2092
                bit = bit << 1;
2093
                if ( bit == 0 || l == lenList ) {
2094
                  BLOCK_ELM_BLIST( blist, l) |= block;
2095
                  block = 0;
2096
                  bit   = 1;
2097
                }
2098

2099
            }
2100
        }
2101

2102
    }
2103

2104
    /* if <list> is not a set, we have to use brute force                  */
2105
    else {
2106

2107
        /* convert left argument to an ordinary list, ignore return value  */
2108
        PLAIN_LIST( list );
2109

2110
        /* turn <sub> into a set for faster searching                      */
2111
        if ( ! IsSet( sub ) )  sub = SetList( sub );
2112

2113
        /* allocate the boolean list and get pointer                       */
2114
        lenList  = LEN_LIST( list );
2115

2116
        /* check length */
2117
        while ( LEN_BLIST(blist) != lenList ) {
2118
            blist = ErrorReturnObj(
2119
              "UniteBlistList: <blist> must have the same length as <list> (%d)",
2120
                lenList, 0L,
2121
                "you can replace <blist> via 'return <blist>;'" );
2122
        }
2123

2124
        lenSub   = LEN_PLIST( sub );
2125

2126
        /* run over the elements of <list>                                 */
2127
        k = 1;
2128
        block = 0;
2129
        bit   = 1;
2130
        for ( l = 1; l <= lenList; l++ ) {
2131

2132
            /* test if <list>[<l>] is in <sub>                             */
2133
            if ( l == 1 || LT(ADDR_OBJ(list)[l-1],ADDR_OBJ(list)[l]) ){
2134
                while ( k <= lenSub
2135
                     && LT(ADDR_OBJ(sub)[k],ADDR_OBJ(list)[l]) )
2136
                    k++;
2137
            }
2138
            else {
2139
                i = 0;  k = LEN_PLIST(sub) + 1;
2140
                while ( i+1 < k ) {
2141
                    j = (i + k) / 2;
2142
                    if ( LT( ADDR_OBJ(sub)[j], ADDR_OBJ(list)[l] ) )
2143
                        i = j;
2144
                    else
2145
                        k = j;
2146
                }
2147
            }
2148

2149
            /* if <list>[<k>] is in <sub> set the current bit in the block */
2150
            if ( k <= lenSub
2151
              && EQ( ADDR_OBJ(sub)[k], ADDR_OBJ(list)[l] ) ) {
2152
                block |= bit;
2153
                k++;
2154
            }
2155

2156
            /* if block is full add it to the boolean list and start next  */
2157
            bit = bit << 1;
2158
            if ( bit == 0 || l == lenList ) {
2159
                BLOCK_ELM_BLIST( blist,l) |= block;
2160
                block = 0;
2161
                bit   = 1;
2162
            }
2163
        }
2164

2165
    }
2166

2167
    /* return */
2168
    return 0;
2169
}
2170

2171

2172
/****************************************************************************
2173
**
2174
*F  FuncINTER_BLIST( <self>, <list1>, <list2> ) .  <list1> intersection <list2>
2175
**
2176
**  'FuncINTER_BLIST' implements the function 'IntersectBlist'.
2177
**
2178
**  'IntersectBlist( <list1>, <list2> )'
2179
**
2180
**  'IntersectBlist' intersects the   boolean list <list1> with  the  boolean
2181
**  list <list2>, which  must have the  same length.   This is equivalent  to
2182
**  assigning '<list1>[<i>] := <list1>[<i>] and <list2>[<i>]' for all <i>.
2183
*/
2184
Obj FuncINTER_BLIST (
2185
    Obj                 self,
2186
    Obj                 list1,
2187
    Obj                 list2 )
2188
{
2189
    UInt  *             ptr1;           /* pointer to the first argument   */
2190
    UInt  *             ptr2;           /* pointer to the second argument  */
2191
    UInt                i;              /* loop variable                   */
2192

2193
    /* get and check the arguments                                         */
2194
    while ( ! IsBlistConv( list1 ) ) {
2195
        list1 = ErrorReturnObj(
2196
            "IntersectBlist: <blist1> must be a boolean list (not a %s)",
2197
            (Int)TNAM_OBJ(list1), 0L,
2198
            "you can replace <blist1> via 'return <blist1>;'" );
2199
    }
2200
    while ( ! IsBlistConv( list2 ) ) {
2201
        list2 = ErrorReturnObj(
2202
            "IntersectBlist: <blist2> must be a boolean list (not a %s)",
2203
            (Int)TNAM_OBJ(list2), 0L,
2204
            "you can replace <blist2> via 'return <blist2>;'" );
2205
    }
2206
    while ( LEN_BLIST(list1) != LEN_BLIST(list2) ) {
2207
        list2 = ErrorReturnObj(
2208
       "IntersectBlist: <blist2> must have the same length as <blist1> (%d)",
2209
            LEN_BLIST(list1), 0L,
2210
            "you can replace <blist2> via 'return <blist2>;'" );
2211
    }
2212

2213
    /* compute the intersection by *and*-ing blockwise                     */
2214
    ptr1 = BLOCKS_BLIST(list1);
2215
    ptr2 = BLOCKS_BLIST(list2);
2216
    for ( i = NUMBER_BLOCKS_BLIST(list1); 0 < i; i-- ) {
2217
        *ptr1++ &= *ptr2++;
2218
    }
2219

2220
    /* return nothing, this function is a procedure                        */
2221
    return 0;
2222
}
2223

2224

2225
/****************************************************************************
2226
**
2227
*F  FuncSUBTR_BLIST( <self>, <list1>, <list2> ) . . . . . . <list1> - <list2>
2228
**
2229
**  'FuncSUBTR_BLIST' implements the internal function 'SubtractBlist'.
2230
**
2231
**  'SubtractBlist( <list1>, <list2> )'
2232
**
2233
**  'SubtractBlist' subtracts the boolean  list <list2> from the boolean list
2234
**  <list1>, which  must have the  same length.  This is equivalent assigning
2235
**  '<list1>[<i>] := <list1>[<i>] and not <list2>[<i>]' for all <i>.
2236
*/
2237
Obj FuncSUBTR_BLIST (
2238
    Obj                 self,
2239
    Obj                 list1,
2240
    Obj                 list2 )
2241
{
2242
    UInt *              ptr1;           /* pointer to the first argument   */
2243
    UInt *              ptr2;           /* pointer to the second argument  */
2244
    UInt                i;              /* loop variable                   */
2245

2246
    /* get and check the arguments                                         */
2247
    while ( ! IsBlistConv( list1 ) ) {
2248
        list1 = ErrorReturnObj(
2249
            "SubtractBlist: <blist1> must be a boolean list (not a %s)",
2250
            (Int)TNAM_OBJ(list1), 0L,
2251
            "you can replace <blist1> via 'return <blist1>;'" );
2252
    }
2253
    while ( ! IsBlistConv( list2 ) ) {
2254
        list2 = ErrorReturnObj(
2255
            "SubtractBlist: <blist2> must be a boolean list (not a %s)",
2256
            (Int)TNAM_OBJ(list2), 0L,
2257
            "you can replace <blist2> via 'return <blist2>;'" );
2258
    }
2259
    while ( LEN_BLIST(list1) != LEN_BLIST(list2) ) {
2260
        list2 = ErrorReturnObj(
2261
        "SubtractBlist: <blist2> must have the same length as <blist1> (%d)",
2262
            LEN_BLIST(list1), 0L,
2263
            "you can replace <blist2> via 'return <blist2>;'" );
2264
    }
2265

2266
    /* compute the difference by operating blockwise                       */
2267
    ptr1 = BLOCKS_BLIST(list1);
2268
    ptr2 = BLOCKS_BLIST(list2); 
2269
    for ( i = NUMBER_BLOCKS_BLIST(list1); 0 < i; i-- ) 
2270
      { 
2271
        *ptr1++ &= ~ *ptr2++; 
2272
      }
2273

2274
    /* return nothing, this function is a procedure */ return 0; }
2275

2276
/****************************************************************************
2277
**
2278
*F  FuncMEET_BLIST( <self>, <list1>, <list2> ) . . . 
2279
**
2280
**  'FuncSUBTR_BLIST' implements the internal function 'MeetBlist'.
2281
**
2282
**  'MeetBlist( <list1>, <list2> )'
2283
**
2284
**  'MeetBlist' returns true if list1 and list2 have true in the same
2285
**  position and false otherwise. It is equivalent to, but faster than
2286
**  SizeBlist(IntersectionBlist(list1, list2)) <> 0
2287
**  The lists must have the same length.
2288
*/
2289

2290
Obj FuncMEET_BLIST (
2291
    Obj                 self,
2292
    Obj                 list1,
2293
    Obj                 list2 )
2294
{
2295
    UInt *              ptr1;           /* pointer to the first argument   */
2296
    UInt *              ptr2;           /* pointer to the second argument  */
2297
    UInt                i;              /* loop variable                   */
2298

2299
    /* get and check the arguments                                         */
2300
    while ( ! IsBlistConv( list1 ) ) {
2301
        list1 = ErrorReturnObj(
2302
            "MeetBlist: <blist1> must be a boolean list (not a %s)",
2303
            (Int)TNAM_OBJ(list1), 0L,
2304
            "you can replace <blist1> via 'return <blist1>;'" );
2305
    }
2306
    while ( ! IsBlistConv( list2 ) ) {
2307
        list2 = ErrorReturnObj(
2308
            "MeetBlist: <blist2> must be a boolean list (not a %s)",
2309
            (Int)TNAM_OBJ(list2), 0L,
2310
            "you can replace <blist2> via 'return <blist2>;'" );
2311
    }
2312
    while ( LEN_BLIST(list1) != LEN_BLIST(list2) ) {
2313
        list2 = ErrorReturnObj(
2314
        "MeetBlist: <blist2> must have the same length as <blist1> (%d)",
2315
            LEN_BLIST(list1), 0L,
2316
            "you can replace <blist2> via 'return <blist2>;'" );
2317
    }
2318

2319
    /* compute the difference by operating blockwise                       */
2320
    ptr1 = BLOCKS_BLIST(list1);
2321
    ptr2 = BLOCKS_BLIST(list2); 
2322
    for ( i = NUMBER_BLOCKS_BLIST(list1); 0 < i; i-- ) 
2323
      { 
2324
	if (*ptr1++ & *ptr2++) return True;
2325
      }
2326

2327
    return False;
2328
}
2329

2330

2331
/****************************************************************************
2332
**
2333
**
2334
*F  MakeImmutableBlist( <blist> )
2335
*/
2336

2337
void MakeImmutableBlist( Obj blist )
2338
{
2339
  RetypeBag(blist, IMMUTABLE_TNUM(TNUM_OBJ(blist)));
2340
}
2341

2342
/****************************************************************************
2343
**
2344
**
2345
*F * * * * * * * * * * * * * initialize package * * * * * * * * * * * * * * *
2346
*/
2347

2348

2349
/****************************************************************************
2350
**
2351

2352
*V  BagNames  . . . . . . . . . . . . . . . . . . . . . . . list of bag names
2353
*/
2354
static StructBagNames BagNames[] = {
2355
  { T_BLIST,                           "list (boolean)"                  },
2356
  { T_BLIST       +IMMUTABLE,          "list (boolean,imm)"              },
2357
  { T_BLIST                  +COPYING, "list (boolean,copied)"           },
2358
  { T_BLIST       +IMMUTABLE +COPYING, "list (boolean,imm,copied)"       },
2359
  { T_BLIST_NSORT,                     "list (boolean,nsort)"            },
2360
  { T_BLIST_NSORT +IMMUTABLE,          "list (boolean,nsort,imm)"        },
2361
  { T_BLIST_NSORT            +COPYING, "list (boolean,nsort,copied)"     },
2362
  { T_BLIST_NSORT +IMMUTABLE +COPYING, "list (boolean,nsort,imm,copied)" },
2363
  { T_BLIST_SSORT,                     "list (boolean,ssort)"            },
2364
  { T_BLIST_SSORT +IMMUTABLE,          "list (boolean,ssort,imm)"        },
2365
  { T_BLIST_SSORT            +COPYING, "list (boolean,ssort,copied)"     },
2366
  { T_BLIST_SSORT +IMMUTABLE +COPYING, "list (boolean,ssort,imm,copied)" },
2367
  { -1,                                ""                                }
2368
};
2369

2370

2371
/****************************************************************************
2372
**
2373
*V  ClearFiltsTab . . . . . . . . . . . . . . . . . . . .  clear filter tnums
2374
*/
2375
static Int ClearFiltsTab [] = {
2376
    T_BLIST,                 T_BLIST,
2377
    T_BLIST      +IMMUTABLE, T_BLIST+IMMUTABLE,
2378
    T_BLIST_NSORT,           T_BLIST,
2379
    T_BLIST_NSORT+IMMUTABLE, T_BLIST+IMMUTABLE,
2380
    T_BLIST_SSORT,           T_BLIST,
2381
    T_BLIST_SSORT+IMMUTABLE, T_BLIST+IMMUTABLE,
2382
    -1,                      -1
2383
};
2384

2385

2386
/****************************************************************************
2387
**
2388
*V  HasFiltTab  . . . . . . . . . . . . . . . . . . . . .  tester filter tnum
2389
*/
2390
static Int HasFiltTab [] = {
2391

2392
    /* mutable boolean list                                                */
2393
    T_BLIST,                    FN_IS_MUTABLE,  1,
2394
    T_BLIST,                    FN_IS_EMPTY,    0,
2395
    T_BLIST,                    FN_IS_DENSE,    1,
2396
    T_BLIST,                    FN_IS_NDENSE,   0,
2397
    T_BLIST,                    FN_IS_HOMOG,    1,
2398
    T_BLIST,                    FN_IS_NHOMOG,   0,
2399
    T_BLIST,                    FN_IS_TABLE,    0,
2400
    T_BLIST,                    FN_IS_SSORT,    0,
2401
    T_BLIST,                    FN_IS_NSORT,    0,
2402

2403
    /* immutable boolean list                                               */
2404
    T_BLIST      +IMMUTABLE,    FN_IS_MUTABLE,  0,
2405
    T_BLIST      +IMMUTABLE,    FN_IS_EMPTY,    0,
2406
    T_BLIST      +IMMUTABLE,    FN_IS_DENSE,    1,
2407
    T_BLIST      +IMMUTABLE,    FN_IS_NDENSE,   0,
2408
    T_BLIST      +IMMUTABLE,    FN_IS_HOMOG,    1,
2409
    T_BLIST      +IMMUTABLE,    FN_IS_NHOMOG,   0,
2410
    T_BLIST      +IMMUTABLE,    FN_IS_TABLE,    0,
2411
    T_BLIST      +IMMUTABLE,    FN_IS_SSORT,    0,
2412
    T_BLIST      +IMMUTABLE,    FN_IS_NSORT,    0,
2413

2414
    /* nsort mutable boolean list                                          */
2415
    T_BLIST_NSORT,              FN_IS_MUTABLE,  1,
2416
    T_BLIST_NSORT,              FN_IS_EMPTY,    0,
2417
    T_BLIST_NSORT,              FN_IS_DENSE,    1,
2418
    T_BLIST_NSORT,              FN_IS_NDENSE,   0,
2419
    T_BLIST_NSORT,              FN_IS_HOMOG,    1,
2420
    T_BLIST_NSORT,              FN_IS_NHOMOG,   0,
2421
    T_BLIST_NSORT,              FN_IS_TABLE,    0,
2422
    T_BLIST_NSORT,              FN_IS_SSORT,    0,
2423
    T_BLIST_NSORT,              FN_IS_NSORT,    1,
2424

2425
    /* nsort immutable boolean list                                        */
2426
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_MUTABLE,  0,
2427
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_EMPTY,    0,
2428
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_DENSE,    1,
2429
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_NDENSE,   0,
2430
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_HOMOG,    1,
2431
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_NHOMOG,   0,
2432
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_TABLE,    0,
2433
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_SSORT,    0,
2434
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_NSORT,    1,
2435

2436
    /* ssort mutable boolean list                                          */
2437
    T_BLIST_SSORT,              FN_IS_MUTABLE,  1,
2438
    T_BLIST_SSORT,              FN_IS_EMPTY,    0,
2439
    T_BLIST_SSORT,              FN_IS_DENSE,    1,
2440
    T_BLIST_SSORT,              FN_IS_NDENSE,   0,
2441
    T_BLIST_SSORT,              FN_IS_HOMOG,    1,
2442
    T_BLIST_SSORT,              FN_IS_NHOMOG,   0,
2443
    T_BLIST_SSORT,              FN_IS_TABLE,    0,
2444
    T_BLIST_SSORT,              FN_IS_SSORT,    1,
2445
    T_BLIST_SSORT,              FN_IS_NSORT,    0,
2446

2447
    /* ssort immutable boolean list                                        */
2448
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_MUTABLE,  0,
2449
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_EMPTY,    0,
2450
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_DENSE,    1,
2451
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_NDENSE,   0,
2452
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_HOMOG,    1,
2453
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_NHOMOG,   0,
2454
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_TABLE,    0,
2455
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_SSORT,    1,
2456
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_NSORT,    0,
2457

2458
    -1,                         -1,             -1
2459
};
2460

2461

2462
/****************************************************************************
2463
**
2464
*V  SetFiltTab  . . . . . . . . . . . . . . . . . . . . .  setter filter tnum
2465
*/
2466
static Int SetFiltTab [] = {
2467

2468
    /* mutable boolean list                                                */
2469
    T_BLIST,                    FN_IS_MUTABLE,  T_BLIST,
2470
    T_BLIST,                    FN_IS_EMPTY,    T_BLIST_SSORT,
2471
    T_BLIST,                    FN_IS_DENSE,    T_BLIST,
2472
    T_BLIST,                    FN_IS_NDENSE,   -1,
2473
    T_BLIST,                    FN_IS_HOMOG,    T_BLIST,
2474
    T_BLIST,                    FN_IS_NHOMOG,   -1,
2475
    T_BLIST,                    FN_IS_TABLE,    -1,
2476
    T_BLIST,                    FN_IS_SSORT,    T_BLIST_SSORT,
2477
    T_BLIST,                    FN_IS_NSORT,    T_BLIST_NSORT,
2478

2479
    /* immutable boolean list                                              */
2480
    T_BLIST      +IMMUTABLE,    FN_IS_MUTABLE,  T_BLIST,
2481
    T_BLIST      +IMMUTABLE,    FN_IS_EMPTY,    T_BLIST_SSORT+IMMUTABLE,
2482
    T_BLIST      +IMMUTABLE,    FN_IS_DENSE,    T_BLIST      +IMMUTABLE,
2483
    T_BLIST      +IMMUTABLE,    FN_IS_NDENSE,   -1,
2484
    T_BLIST      +IMMUTABLE,    FN_IS_HOMOG,    T_BLIST      +IMMUTABLE,
2485
    T_BLIST      +IMMUTABLE,    FN_IS_NHOMOG,   -1,
2486
    T_BLIST      +IMMUTABLE,    FN_IS_TABLE,    -1,
2487
    T_BLIST      +IMMUTABLE,    FN_IS_SSORT,    T_BLIST_SSORT+IMMUTABLE,
2488
    T_BLIST      +IMMUTABLE,    FN_IS_NSORT,    T_BLIST_NSORT+IMMUTABLE,
2489

2490
    /* nsort mutable boolean list                                          */
2491
    T_BLIST_NSORT,              FN_IS_MUTABLE,  T_BLIST_NSORT,
2492
    T_BLIST_NSORT,              FN_IS_EMPTY,    -1,
2493
    T_BLIST_NSORT,              FN_IS_DENSE,    T_BLIST_NSORT,
2494
    T_BLIST_NSORT,              FN_IS_NDENSE,   -1,
2495
    T_BLIST_NSORT,              FN_IS_HOMOG,    T_BLIST_NSORT,
2496
    T_BLIST_NSORT,              FN_IS_NHOMOG,   -1,
2497
    T_BLIST_NSORT,              FN_IS_TABLE,    -1,
2498
    T_BLIST_NSORT,              FN_IS_SSORT,    -1,
2499
    T_BLIST_NSORT,              FN_IS_NSORT,    T_BLIST_NSORT,
2500

2501
    /* nsort immutable boolean list                                        */
2502
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_MUTABLE,  T_BLIST_NSORT,
2503
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_EMPTY,    -1,
2504
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_DENSE,    T_BLIST_NSORT+IMMUTABLE,
2505
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_NDENSE,   -1,
2506
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_HOMOG,    T_BLIST_NSORT+IMMUTABLE,
2507
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_NHOMOG,   -1,
2508
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_TABLE,    -1,
2509
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_SSORT,    -1,
2510
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_NSORT,    T_BLIST_NSORT+IMMUTABLE,
2511

2512
    /* ssort mutable boolean list                                          */
2513
    T_BLIST_SSORT,              FN_IS_MUTABLE,  T_BLIST_SSORT,
2514
    T_BLIST_SSORT,              FN_IS_EMPTY,    T_BLIST_SSORT,
2515
    T_BLIST_SSORT,              FN_IS_DENSE,    T_BLIST_SSORT,
2516
    T_BLIST_SSORT,              FN_IS_NDENSE,   -1,
2517
    T_BLIST_SSORT,              FN_IS_HOMOG,    T_BLIST_SSORT,
2518
    T_BLIST_SSORT,              FN_IS_NHOMOG,   -1,
2519
    T_BLIST_SSORT,              FN_IS_TABLE,    -1,
2520
    T_BLIST_SSORT,              FN_IS_SSORT,    T_BLIST_SSORT,
2521
    T_BLIST_SSORT,              FN_IS_NSORT,    -1,
2522

2523
    /* ssort immutable boolean list                                        */
2524
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_MUTABLE,  T_BLIST_SSORT,
2525
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_EMPTY,    T_BLIST_SSORT+IMMUTABLE,
2526
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_DENSE,    T_BLIST_SSORT+IMMUTABLE,
2527
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_NDENSE,   -1,
2528
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_HOMOG,    T_BLIST_SSORT+IMMUTABLE,
2529
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_NHOMOG,   -1,
2530
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_TABLE,    -1,
2531
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_SSORT,    T_BLIST_SSORT+IMMUTABLE,
2532
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_NSORT,    -1,
2533

2534
    -1,                         -1,             -1
2535

2536
};
2537

2538

2539
/****************************************************************************
2540
**
2541
*V  ResetFiltTab  . . . . . . . . . . . . . . . . . . .  unsetter filter tnum
2542
*/
2543
static Int ResetFiltTab [] = {
2544

2545
    /* mutable boolean list                                                */
2546
    T_BLIST,                    FN_IS_MUTABLE,  T_BLIST      +IMMUTABLE,
2547
    T_BLIST,                    FN_IS_EMPTY,    T_BLIST,
2548
    T_BLIST,                    FN_IS_DENSE,    T_BLIST,
2549
    T_BLIST,                    FN_IS_NDENSE,   T_BLIST,
2550
    T_BLIST,                    FN_IS_HOMOG,    T_BLIST,
2551
    T_BLIST,                    FN_IS_NHOMOG,   T_BLIST,
2552
    T_BLIST,                    FN_IS_TABLE,    T_BLIST,
2553
    T_BLIST,                    FN_IS_SSORT,    T_BLIST,
2554
    T_BLIST,                    FN_IS_NSORT,    T_BLIST,
2555

2556
    /* immutable boolean list                                               */
2557
    T_BLIST      +IMMUTABLE,    FN_IS_MUTABLE,  T_BLIST      +IMMUTABLE,
2558
    T_BLIST      +IMMUTABLE,    FN_IS_EMPTY,    T_BLIST      +IMMUTABLE,
2559
    T_BLIST      +IMMUTABLE,    FN_IS_DENSE,    T_BLIST      +IMMUTABLE,
2560
    T_BLIST      +IMMUTABLE,    FN_IS_NDENSE,   T_BLIST      +IMMUTABLE,
2561
    T_BLIST      +IMMUTABLE,    FN_IS_HOMOG,    T_BLIST      +IMMUTABLE,
2562
    T_BLIST      +IMMUTABLE,    FN_IS_NHOMOG,   T_BLIST      +IMMUTABLE,
2563
    T_BLIST      +IMMUTABLE,    FN_IS_NSORT,    T_BLIST      +IMMUTABLE,
2564
    T_BLIST      +IMMUTABLE,    FN_IS_SSORT,    T_BLIST      +IMMUTABLE,
2565
    T_BLIST      +IMMUTABLE,    FN_IS_TABLE,    T_BLIST      +IMMUTABLE,
2566

2567
    /* nsort mutable boolean list                                          */
2568
    T_BLIST_NSORT,              FN_IS_MUTABLE,  T_BLIST_NSORT+IMMUTABLE,
2569
    T_BLIST_NSORT,              FN_IS_EMPTY,    T_BLIST_NSORT,
2570
    T_BLIST_NSORT,              FN_IS_DENSE,    T_BLIST_NSORT,
2571
    T_BLIST_NSORT,              FN_IS_NDENSE,   T_BLIST_NSORT,
2572
    T_BLIST_NSORT,              FN_IS_HOMOG,    T_BLIST_NSORT,
2573
    T_BLIST_NSORT,              FN_IS_NHOMOG,   T_BLIST_NSORT,
2574
    T_BLIST_NSORT,              FN_IS_TABLE,    T_BLIST_NSORT,
2575
    T_BLIST_NSORT,              FN_IS_SSORT,    T_BLIST_NSORT,
2576
    T_BLIST_NSORT,              FN_IS_NSORT,    T_BLIST,
2577

2578
    /* nsort immutable boolean list                                        */
2579
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_MUTABLE,  T_BLIST_NSORT+IMMUTABLE,
2580
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_EMPTY,    T_BLIST_NSORT+IMMUTABLE,
2581
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_DENSE,    T_BLIST_NSORT+IMMUTABLE,
2582
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_NDENSE,   T_BLIST_NSORT+IMMUTABLE,
2583
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_HOMOG,    T_BLIST_NSORT+IMMUTABLE,
2584
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_NHOMOG,   T_BLIST_NSORT+IMMUTABLE,
2585
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_TABLE,    T_BLIST_NSORT+IMMUTABLE,
2586
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_SSORT,    T_BLIST_NSORT+IMMUTABLE,
2587
    T_BLIST_NSORT+IMMUTABLE,    FN_IS_NSORT,    T_BLIST      +IMMUTABLE,
2588

2589
    /* ssort mutable boolean list                                          */
2590
    T_BLIST_SSORT,              FN_IS_MUTABLE,  T_BLIST_SSORT+IMMUTABLE,
2591
    T_BLIST_SSORT,              FN_IS_EMPTY,    T_BLIST_SSORT,
2592
    T_BLIST_SSORT,              FN_IS_DENSE,    T_BLIST_SSORT,
2593
    T_BLIST_SSORT,              FN_IS_NDENSE,   T_BLIST_SSORT,
2594
    T_BLIST_SSORT,              FN_IS_HOMOG,    T_BLIST_SSORT,
2595
    T_BLIST_SSORT,              FN_IS_NHOMOG,   T_BLIST_SSORT,
2596
    T_BLIST_SSORT,              FN_IS_TABLE,    T_BLIST_SSORT,
2597
    T_BLIST_SSORT,              FN_IS_SSORT,    T_BLIST,
2598
    T_BLIST_SSORT,              FN_IS_NSORT,    T_BLIST_SSORT,
2599

2600
    /* ssort immutable boolean list                                        */
2601
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_MUTABLE,  T_BLIST_SSORT+IMMUTABLE,
2602
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_EMPTY,    T_BLIST_SSORT+IMMUTABLE,
2603
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_DENSE,    T_BLIST_SSORT+IMMUTABLE,
2604
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_NDENSE,   T_BLIST_SSORT+IMMUTABLE,
2605
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_HOMOG,    T_BLIST_SSORT+IMMUTABLE,
2606
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_NHOMOG,   T_BLIST_SSORT+IMMUTABLE,
2607
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_TABLE,    T_BLIST_SSORT+IMMUTABLE,
2608
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_SSORT,    T_BLIST      +IMMUTABLE,
2609
    T_BLIST_SSORT+IMMUTABLE,    FN_IS_NSORT,    T_BLIST_SSORT+IMMUTABLE,
2610

2611
    -1,                         -1,             -1
2612

2613
};
2614

2615

2616
/****************************************************************************
2617
**
2618
*V  GVarFilts . . . . . . . . . . . . . . . . . . . list of filters to export
2619
*/
2620
static StructGVarFilt GVarFilts [] = {
2621

2622
    { "IS_BLIST", "obj", &IsBlistFilt, 
2623
      FuncIS_BLIST, "src/blister.c:IS_BLIST" },
2624

2625
    { "IS_BLIST_REP", "obj", &IsBlistRepFilt, 
2626
      FuncIS_BLIST_REP, "src/blister.c:IS_BLIST_REP" },
2627

2628
    { 0 }
2629

2630
};
2631

2632

2633
/****************************************************************************
2634
**
2635
*V  GVarFuncs . . . . . . . . . . . . . . . . . . list of functions to export
2636
*/
2637
static StructGVarFunc GVarFuncs [] = {
2638

2639
    { "IS_BLIST_CONV", 1, "obj", 
2640
      FuncIS_BLIST_CONV, "src/blister.c:IS_BLIST_CONV" },
2641

2642
    { "CONV_BLIST", 1, "blist",
2643
      FuncCONV_BLIST, "src/blister.c:CONV_BLIST" },
2644

2645
    { "BLIST_LIST", 2, "list, sub",
2646
      FuncBLIST_LIST, "src/blister.c:BLIST_LIST" },
2647

2648
    { "LIST_BLIST", 2, "list, blist",
2649
      FuncLIST_BLIST, "src/blister.c:LIST_BLIST" },
2650

2651
    { "SIZE_BLIST", 1, "blist",
2652
      FuncSIZE_BLIST, "src/blister.c:SIZE_BLIST" },
2653

2654
    { "IS_SUB_BLIST", 2, "blist1, blist2",
2655
      FuncIS_SUB_BLIST, "src/blister.c:IS_SUB_BLIST" },
2656

2657
    { "UNITE_BLIST", 2, "blist1, blist2",
2658
      FuncUNITE_BLIST, "src/blister.c:UNITE_BLIST" },
2659

2660
    { "UNITE_BLIST_LIST", 3, "list, blist, sub",
2661
      FuncUNITE_BLIST_LIST, "src/blister.c:UNITE_BLIST_LIST" },
2662

2663
    { "INTER_BLIST", 2, "blist1, blist2",
2664
      FuncINTER_BLIST, "src/blister.c:INTER_BLIST" },
2665

2666
    { "SUBTR_BLIST", 2, "blist1, blist2",
2667
      FuncSUBTR_BLIST, "src/blister.c:SUBTR_BLIST" },
2668

2669
    { "MEET_BLIST", 2, "blist1, blist2",
2670
      FuncMEET_BLIST, "src/blister.c:MEET_BLIST" },
2671

2672
    { "PositionNthTrueBlist", 2, "blist, nth",
2673
      FuncPositionNthTrueBlist, "src/blister.c:PositionNthTrueBlist" },
2674

2675
    { "PositionsTrueBlist", 1, "blist",
2676
      FuncPositionsTrueBlist, "src/blister.c:PositionsTrueBlist" },
2677

2678
    { 0 }
2679

2680
};
2681

2682

2683
/****************************************************************************
2684
**
2685

2686
*F  InitKernel( <module> )  . . . . . . . . initialise kernel data structures
2687
*/
2688
static Int InitKernel (
2689
    StructInitInfo *    module )
2690
{
2691
    UInt                t1;
2692
    UInt                t2;
2693

2694
    /* check dependencies                                                  */
2695
    RequireModule( module, "lists", 403600000UL );
2696

2697
    /* init filters and functions                                          */
2698
    InitHdlrFiltsFromTable( GVarFilts );
2699
    InitHdlrFuncsFromTable( GVarFuncs );
2700

2701
    /* GASMAN marking functions and GASMAN names                           */
2702
    InitBagNamesFromTable( BagNames );
2703

2704
    for ( t1 = T_BLIST;  t1 <= T_BLIST_SSORT;  t1 += 2 ) {
2705
        InitMarkFuncBags( t1,                      MarkNoSubBags  );
2706
        InitMarkFuncBags( t1 +IMMUTABLE,           MarkNoSubBags  );
2707
        InitMarkFuncBags( t1            +COPYING , MarkOneSubBags );
2708
        InitMarkFuncBags( t1 +IMMUTABLE +COPYING , MarkOneSubBags );
2709
    }
2710

2711
    /* Make immutable blists public					   */
2712
    for ( t1 = T_BLIST; t1 <= T_BLIST_SSORT; t1 += 2 ) {
2713
        MakeBagTypePublic( t1 + IMMUTABLE );
2714
    }
2715

2716
    /* install the type methods                                            */
2717
    TypeObjFuncs[ T_BLIST ] = TypeBlistMut;
2718
    TypeObjFuncs[ T_BLIST +IMMUTABLE ] = TypeBlistImm;
2719
    TypeObjFuncs[ T_BLIST_NSORT ] = TypeBlistNSortMut;
2720
    TypeObjFuncs[ T_BLIST_NSORT +IMMUTABLE ] = TypeBlistNSortImm;
2721
    TypeObjFuncs[ T_BLIST_SSORT ] = TypeBlistSSortMut;
2722
    TypeObjFuncs[ T_BLIST_SSORT +IMMUTABLE ] = TypeBlistSSortImm;
2723

2724
    /* initialise list tables                                              */
2725
    InitClearFiltsTNumsFromTable   ( ClearFiltsTab );
2726
    InitHasFiltListTNumsFromTable  ( HasFiltTab    );
2727
    InitSetFiltListTNumsFromTable  ( SetFiltTab    );
2728
    InitResetFiltListTNumsFromTable( ResetFiltTab  );
2729

2730
    /* Install the saving functions -- cannot save while copying           */
2731
    for ( t1 = T_BLIST;  t1 <= T_BLIST_SSORT;  t1 += 2 ) {
2732
        SaveObjFuncs[ t1            ] = SaveBlist;
2733
        SaveObjFuncs[ t1 +IMMUTABLE ] = SaveBlist;
2734
        LoadObjFuncs[ t1            ] = LoadBlist;
2735
        LoadObjFuncs[ t1 +IMMUTABLE ] = LoadBlist;
2736
    }
2737

2738
    /* install the copy functions                                          */
2739
    for ( t1 = T_BLIST; t1 <= T_BLIST_SSORT; t1 += 2 ) {
2740
        CopyObjFuncs [ t1                     ] = CopyBlist;
2741
        CopyObjFuncs [ t1 +IMMUTABLE          ] = CopyBlist;
2742
        CopyObjFuncs [ t1            +COPYING ] = CopyBlistCopy;
2743
        CopyObjFuncs [ t1 +IMMUTABLE +COPYING ] = CopyBlistCopy;
2744
        CleanObjFuncs[ t1                     ] = CleanBlist;
2745
        CleanObjFuncs[ t1 +IMMUTABLE          ] = CleanBlist;
2746
        CleanObjFuncs[ t1            +COPYING ] = CleanBlistCopy;
2747
        CleanObjFuncs[ t1 +IMMUTABLE +COPYING ] = CleanBlistCopy;
2748
	ShallowCopyObjFuncs[ t1 ] = ShallowCopyBlist;
2749
	ShallowCopyObjFuncs[ t1 +IMMUTABLE ] = ShallowCopyBlist;
2750
    }
2751

2752
    /* install the comparison methods                                      */
2753
    for ( t1 = T_BLIST;  t1 <= T_BLIST_SSORT+IMMUTABLE;  t1++ ) {
2754
        for ( t2 = T_BLIST;  t2 <= T_BLIST_SSORT+IMMUTABLE;  t2++ ) {
2755
            EqFuncs[ t1 ][ t2 ] = EqBlist;
2756
        }
2757
    }
2758

2759
    /* install the list functions in the tables                            */
2760
    for ( t1 = T_BLIST; t1 <= T_BLIST_SSORT; t1 += 2 ) {
2761
        LenListFuncs    [ t1            ] = LenBlist;
2762
        LenListFuncs    [ t1 +IMMUTABLE ] = LenBlist;
2763
        IsbListFuncs    [ t1            ] = IsbBlist;
2764
        IsbListFuncs    [ t1 +IMMUTABLE ] = IsbBlist;
2765
        IsbvListFuncs   [ t1            ] = IsbvBlist;
2766
        IsbvListFuncs   [ t1 +IMMUTABLE ] = IsbvBlist;
2767
        Elm0ListFuncs   [ t1            ] = Elm0Blist;
2768
        Elm0ListFuncs   [ t1 +IMMUTABLE ] = Elm0Blist;
2769
        Elm0vListFuncs  [ t1            ] = Elm0vBlist;
2770
        Elm0vListFuncs  [ t1 +IMMUTABLE ] = Elm0vBlist;
2771
        ElmListFuncs    [ t1            ] = ElmBlist;
2772
        ElmListFuncs    [ t1 +IMMUTABLE ] = ElmBlist;
2773
        ElmvListFuncs   [ t1            ] = ElmvBlist;
2774
        ElmvListFuncs   [ t1 +IMMUTABLE ] = ElmvBlist;
2775
        ElmwListFuncs   [ t1            ] = ElmvBlist;
2776
        ElmwListFuncs   [ t1 +IMMUTABLE ] = ElmvBlist;
2777
        ElmsListFuncs   [ t1            ] = ElmsBlist;
2778
        ElmsListFuncs   [ t1 +IMMUTABLE ] = ElmsBlist;
2779
        AssListFuncs    [ t1            ] = AssBlist;
2780
        AssListFuncs    [ t1 +IMMUTABLE ] = AssBlistImm;
2781
        AsssListFuncs   [ t1            ] = AsssListDefault;
2782
        AsssListFuncs   [ t1 +IMMUTABLE ] = AsssBlistImm;
2783
        IsDenseListFuncs[ t1            ] = IsDenseBlist;
2784
        IsDenseListFuncs[ t1 +IMMUTABLE ] = IsDenseBlist;
2785
        IsHomogListFuncs[ t1            ] = IsHomogBlist;
2786
        IsHomogListFuncs[ t1 +IMMUTABLE ] = IsHomogBlist;
2787
        IsSSortListFuncs[ t1            ] = IsSSortBlist;
2788
        IsSSortListFuncs[ t1 +IMMUTABLE ] = IsSSortBlist;
2789
        IsPossListFuncs [ t1            ] = IsPossBlist;
2790
        IsPossListFuncs [ t1 +IMMUTABLE ] = IsPossBlist;
2791
        PosListFuncs    [ t1            ] = PosBlist;
2792
        PosListFuncs    [ t1 +IMMUTABLE ] = PosBlist;
2793
        PlainListFuncs  [ t1            ] = PlainBlist;
2794
        PlainListFuncs  [ t1 +IMMUTABLE ] = PlainBlist;
2795
        MakeImmutableObjFuncs [ t1      ] = MakeImmutableBlist;
2796
    }
2797
    IsSSortListFuncs[ T_BLIST_NSORT            ] = IsSSortBlistNot;
2798
    IsSSortListFuncs[ T_BLIST_NSORT +IMMUTABLE ] = IsSSortBlistNot;
2799
    IsSSortListFuncs[ T_BLIST_SSORT            ] = IsSSortBlistYes;
2800
    IsSSortListFuncs[ T_BLIST_SSORT +IMMUTABLE ] = IsSSortBlistYes;
2801

2802
    /* Import the types of blists: */
2803
    ImportGVarFromLibrary( "TYPE_BLIST_MUT", &TYPE_BLIST_MUT );
2804
    ImportGVarFromLibrary( "TYPE_BLIST_IMM", &TYPE_BLIST_IMM );
2805
    ImportGVarFromLibrary( "TYPE_BLIST_NSORT_MUT", &TYPE_BLIST_NSORT_MUT );
2806
    ImportGVarFromLibrary( "TYPE_BLIST_NSORT_IMM", &TYPE_BLIST_NSORT_IMM );
2807
    ImportGVarFromLibrary( "TYPE_BLIST_SSORT_MUT", &TYPE_BLIST_SSORT_MUT );
2808
    ImportGVarFromLibrary( "TYPE_BLIST_SSORT_IMM", &TYPE_BLIST_SSORT_IMM );
2809
    ImportGVarFromLibrary( "TYPE_BLIST_EMPTY_MUT", &TYPE_BLIST_EMPTY_MUT );
2810
    ImportGVarFromLibrary( "TYPE_BLIST_EMPTY_IMM", &TYPE_BLIST_EMPTY_IMM );
2811

2812
    /* return success                                                      */
2813
    return 0;
2814
}
2815

2816

2817
/****************************************************************************
2818
**
2819
*F  InitLibrary( <module> ) . . . . . . .  initialise library data structures
2820
*/
2821
static Int InitLibrary (
2822
    StructInitInfo *    module )
2823
{
2824
    /* init filters and functions                                          */
2825
    InitGVarFiltsFromTable( GVarFilts );
2826
    InitGVarFuncsFromTable( GVarFuncs );
2827

2828
    /* return success                                                      */
2829
    return 0;
2830
}
2831

2832

2833
/****************************************************************************
2834
**
2835
*F  InitInfoBlist() . . . . . . . . . . . . . . . . . table of init functions
2836
*/
2837
static StructInitInfo module = {
2838
    MODULE_BUILTIN,                     /* type                           */
2839
    "blister",                          /* name                           */
2840
    0,                                  /* revision entry of c file       */
2841
    0,                                  /* revision entry of h file       */
2842
    0,                                  /* version                        */
2843
    0,                                  /* crc                            */
2844
    InitKernel,                         /* initKernel                     */
2845
    InitLibrary,                        /* initLibrary                    */
2846
    0,                                  /* checkInit                      */
2847
    0,                                  /* preSave                        */
2848
    0,                                  /* postSave                       */
2849
    0                                   /* postRestore                    */
2850
};
2851

2852
StructInitInfo * InitInfoBlist ( void )
2853
{
2854
    return &module;
2855
}
2856

2857

2858
/****************************************************************************
2859
**
2860

2861
*E  blister.c . . . . . . . . . . . . . . . . . . . . . . . . . . . ends here
2862
*/
2863

2864
Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

Product

Resources

Company

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more, all in one place.

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
