home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__lib / bitset.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-23  |  16.5 KB  |  865 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of GNU CC.
  6.  
  7. GNU CC is distributed in the hope that it will be useful,
  8. but WITHOUT ANY WARRANTY.  No author or distributor
  9. accepts responsibility to anyone for the consequences of using it
  10. or for whether it serves any particular purpose or works at all,
  11. unless he says so in writing.  Refer to the GNU CC General Public
  12. License for full details.
  13.  
  14. Everyone is granted permission to copy, modify and redistribute
  15. GNU CC, but only under the conditions described in the
  16. GNU CC General Public License.   A copy of this license is
  17. supposed to have been given to you along with GNU CC so you
  18. can know your rights and responsibilities.  It should be in a
  19. file named COPYING.  Among other things, the copyright notice
  20. and this notice must be preserved on all copies.  
  21. */
  22.  
  23. /* 
  24.   BitSet class implementation
  25.  */
  26.  
  27. #include <BitSet.h>
  28. #include <std.h>
  29. #include "libconfig.h"
  30. #include <Obstack.h>
  31.  
  32.  
  33.  
  34. void BitSet::error(char* msg)
  35. {
  36.   (*lib_error_handler)("BitSet", msg);
  37. }
  38.  
  39. //  globals & constants
  40.  
  41. BitSetRep  _nilBitSetRep = { 0, 1, 0, {0} }; // nil BitSets point here
  42.  
  43. #define ONES               ((unsigned short)(~0L))
  44. #define MINBitSetRep_SIZE  16
  45. #define MAXBitSetRep_SIZE  (1 << (SHORTBITS - 1) - 1)
  46. #define MALLOC_OVERHEAD     4
  47.  
  48. // break things up into .s indices and positions
  49.  
  50.  
  51. // mask out bits from left
  52.  
  53. static inline unsigned short lmask(int p)
  54. {
  55.   return ONES << p;
  56. }
  57.  
  58. // mask out high bits
  59.  
  60. static inline unsigned short rmask(int p)
  61. {
  62.   return ONES >> (BITSETBITS - 1 - p);
  63. }
  64.  
  65.  
  66. inline static BitSetRep* BSnew(int newlen)
  67. {
  68.   unsigned int siz = sizeof(BitSetRep) + newlen * sizeof(short) 
  69.     + MALLOC_OVERHEAD;
  70.   unsigned int allocsiz = MINBitSetRep_SIZE;;
  71.   while (allocsiz < siz) allocsiz <<= 1;
  72.   allocsiz -= MALLOC_OVERHEAD;
  73.   if (allocsiz >= MAXBitSetRep_SIZE * sizeof(short))
  74.     (*lib_error_handler)("BitSet", "Requested length out of range");
  75.     
  76.   BitSetRep* rep = (BitSetRep *) new char[allocsiz];
  77.   bzero(rep, allocsiz);
  78.   rep->sz = (allocsiz - sizeof(BitSetRep) + sizeof(short)) / sizeof(short);
  79.   return rep;
  80. }
  81.  
  82. BitSetRep* BitSetalloc(BitSetRep* old, unsigned short* src, int srclen, 
  83.                 int newvirt, int newlen)
  84. {
  85.   if (old == &_nilBitSetRep) old = 0; 
  86.   BitSetRep* rep;
  87.   if (old == 0 || newlen >= old->sz)
  88.     rep = BSnew(newlen);
  89.   else
  90.     rep = old;
  91.  
  92.   rep->len = newlen;
  93.   rep->virt = newvirt;
  94.  
  95.   if (srclen != 0 && src != rep->s)
  96.     bcopy(src, rep->s, srclen * sizeof(short));
  97.  
  98.   if (old != rep && old != 0) delete old;
  99.   return rep;
  100. }
  101.  
  102. BitSetRep* BitSetresize(BitSetRep* old, int newlen)
  103. {
  104.   BitSetRep* rep;
  105.   if (old == 0 || old == &_nilBitSetRep)
  106.   {
  107.     rep = BSnew(newlen);
  108.     rep->virt = 0;
  109.   }
  110.   else if (newlen >= old->sz)
  111.   {
  112.     rep = BSnew(newlen);
  113.     bcopy(old->s, rep->s, old->len * sizeof(short));
  114.     rep->virt = old->virt;
  115.     delete old;
  116.   }
  117.   else
  118.     rep = old;
  119.  
  120.   rep->len = newlen;
  121.  
  122.   return rep;
  123. }
  124.  
  125. // same, for straight copy
  126.  
  127. BitSetRep* BitSetcopy(BitSetRep* old, BitSetRep* src)
  128. {
  129.   BitSetRep* rep;
  130.   if (old == src) return old; 
  131.   if (old == &_nilBitSetRep) old = 0;
  132.   if (src == &_nilBitSetRep) src = 0;
  133.   if (src == 0)
  134.   {
  135.     if (old == 0)
  136.       rep = BSnew(0);
  137.     rep->len = 0;
  138.     rep->virt = 0;
  139.   }
  140.   else 
  141.   {
  142.     int newlen = src->len;
  143.     if (old == 0 || newlen > old->sz)
  144.     {
  145.       rep = BSnew(newlen);
  146.       if (old != 0) delete old;
  147.     }
  148.     else
  149.       rep = old;
  150.  
  151.     bcopy(src->s, rep->s, newlen * sizeof(short));
  152.     rep->len = newlen;
  153.     rep->virt = src->virt;
  154.   }
  155.   return rep;
  156. }
  157.  
  158.  
  159. // remove unneeded top bits
  160.  
  161. inline static void trim(BitSetRep* rep)
  162. {
  163.   int l = rep->len;
  164.   unsigned short* s = &(rep->s[l - 1]);
  165.  
  166.   if (rep->virt == 0)
  167.     while (l > 0 && *s-- == 0) --l;
  168.   else
  169.     while (l > 0 && *s-- == ONES) --l;
  170.   rep->len = l;
  171. }
  172.  
  173. int operator == (BitSet& x, BitSet& y)
  174. {
  175.   return x.rep->len == y.rep->len && x.rep->virt == y.rep->virt &&
  176.     bcmp((void*)x.rep->s, (void*)y.rep->s, 
  177.          x.rep->len * sizeof(short)) == 0;
  178. }
  179.  
  180.  
  181. int operator <= (BitSet& x, BitSet& y)
  182. {
  183.   if (x.rep->virt > y.rep->virt)
  184.     return 0;
  185.  
  186.   int xl = x.rep->len;
  187.   int yl = y.rep->len; 
  188.  
  189.   unsigned short* xs = x.rep->s;
  190.   unsigned short* ys = y.rep->s;
  191.   unsigned short* topx = &(xs[xl]);
  192.   unsigned short* topy = &(ys[yl]);
  193.  
  194.   while (xs < topx && ys < topy)
  195.   {
  196.     unsigned short a = *xs++;
  197.     unsigned short b = *ys++;
  198.     if ((a | b) != b)
  199.       return 0;
  200.   }
  201.   if (xl == yl)
  202.     return x.rep->virt <= y.rep->virt;
  203.   else if (xl < yl)
  204.     return !x.rep->virt;
  205.   else
  206.     return y.rep->virt;
  207. }
  208.  
  209.  
  210. int operator < (BitSet& x, BitSet& y)
  211. {
  212.   if (x.rep->virt > y.rep->virt)
  213.     return 0;
  214.  
  215.   int xl = x.rep->len;
  216.   int yl = y.rep->len;
  217.  
  218.   unsigned short* xs = x.rep->s;
  219.   unsigned short* ys = y.rep->s;
  220.   unsigned short* topx = &(xs[xl]);
  221.   unsigned short* topy = &(ys[yl]);
  222.   int one_diff = 0;
  223.   while (xs < topx && ys < topy)
  224.   {
  225.     unsigned short a = *xs++;
  226.     unsigned short b = *ys++;
  227.     unsigned short c = a | b;
  228.     if (c != b)
  229.       return 0;
  230.     else if (c != a)
  231.       one_diff = 1;
  232.   }
  233.   if (xl == yl)
  234.     return x.rep->virt < y.rep->virt || 
  235.       (one_diff && x.rep->virt == y.rep->virt);
  236.   else if (xl < yl)
  237.     return !x.rep->virt;
  238.   else
  239.     return y.rep->virt;
  240. }
  241.  
  242. BitSetTmp shorttoBitSet(unsigned short w)
  243. {
  244.   BitSetRep* r = BitSetalloc(0, &w, 1, 0, 2);
  245.   trim(r);
  246.   return r;
  247. }
  248.  
  249. BitSetTmp longtoBitSet(unsigned long w)
  250. {
  251.   unsigned short u[2];
  252.   u[0] = w & ((unsigned short)(~(0)));
  253.   u[1] = w >> BITSETBITS;
  254.   BitSetRep* r = BitSetalloc(0, &u[0], 2, 0, 3);
  255.   trim(r);
  256.   return r;
  257. }
  258.  
  259.  
  260. int BitSet::empty()
  261. {
  262.   if (rep->virt == 1)
  263.     return 0;
  264.  
  265.   unsigned short* bots = rep->s;
  266.   unsigned short* s = &(bots[rep->len - 1]);
  267.   while (s >= bots) if (*s-- != 0) return 0;
  268.   return 1;
  269. }
  270.  
  271.  
  272. int BitSet::count(int b = 1)
  273. {
  274.   if (b == rep->virt)
  275.     return -1;
  276.   int l = 0;
  277.   unsigned short* s = rep->s;
  278.   unsigned short* tops = &(s[rep->len]);
  279.   if (b == 1)
  280.   {
  281.     while (s < tops)
  282.     {
  283.       unsigned short a = *s++;
  284.       for (int i = 0; i < BITSETBITS && a != 0; ++i)
  285.       {
  286.         if (a & 1)
  287.           ++l;
  288.         a >>= 1;
  289.       }
  290.     }
  291.   }
  292.   else
  293.   {
  294.     unsigned short maxbit = 1 << (BITSETBITS - 1);
  295.     while (s < tops)
  296.     {
  297.       unsigned short a = *s++;
  298.       for (int i = 0; i < BITSETBITS; ++i)
  299.       {
  300.         if ((a & maxbit) == 0)
  301.           ++l;
  302.         a <<= 1;
  303.       }
  304.     }
  305.   }
  306.   return l;
  307. }
  308.  
  309. BitSetRep* BitSetcmpl(BitSetRep* src, BitSetRep* r)
  310. {
  311.   r = BitSetcopy(r, src);
  312.   r->virt = !src->virt;
  313.   unsigned short* rs = r->s;
  314.   unsigned short* topr = &(rs[r->len]);
  315.   while (rs < topr)
  316.   {
  317.     unsigned short cmp = ~(*rs);
  318.     *rs++ = cmp;
  319.   }
  320.   trim(r);
  321.   return r;
  322. }
  323.  
  324.  
  325. BitSetRep* BitSetop(BitSetRep* x, BitSetRep* y, BitSetRep* r, char op)
  326. {
  327.   int xrsame = x == r;
  328.   int yrsame = y == r;
  329.  
  330.   int xl = x->len;
  331.   int yl = y->len;
  332.   int rl = (xl >= yl)? xl : yl;
  333.  
  334.   r = BitSetresize(r, rl);
  335.   unsigned short* rs = r->s;
  336.   unsigned short* topr = &(rs[rl]);
  337.  
  338.   int av, bv;
  339.   unsigned short* as;
  340.   unsigned short* topa;
  341.   unsigned short* bs;
  342.   unsigned short* topb;
  343.   
  344.   if (xl <= yl)
  345.   {
  346.     as = (xrsame)? r->s : x->s;
  347.     topa = &(as[xl]);
  348.     av = x->virt;
  349.     bs = (yrsame)? r->s : y->s;
  350.     topb = &(bs[yl]);
  351.     bv = y->virt;
  352.   }
  353.   else
  354.   {
  355.     as = (yrsame)? r->s : y->s;
  356.     topa = &(as[yl]);
  357.     av = y->virt;
  358.     bs = (xrsame)? r->s : x->s;
  359.     topb = &(bs[xl]);
  360.     bv = x->virt;
  361.     if (op == '-')              // reverse sense of difference
  362.       op = 'D';
  363.   }
  364.  
  365.   switch (op)
  366.   {
  367.   case '&':
  368.     r->virt = av & bv;
  369.     while (as < topa) *rs++ = *as++ & *bs++;
  370.     if (av)
  371.       while (rs < topr) *rs++ = *bs++;
  372.     else
  373.       while (rs < topr) *rs++ = 0;
  374.     break;
  375.   case '|':
  376.     r->virt = av | bv;
  377.     while (as < topa) *rs++ = *as++ | *bs++;
  378.     if (av)
  379.       while (rs < topr) *rs++ = ONES;
  380.     else
  381.       while (rs < topr) *rs++ = *bs++;
  382.     break;
  383.   case '^':
  384.     r->virt = av ^ bv;
  385.     while (as < topa) *rs++ = *as++ ^ *bs++;
  386.     if (av)
  387.       while (rs < topr) *rs++ = ~(*bs++);
  388.     else
  389.       while (rs < topr) *rs++ = *bs++;
  390.     break;
  391.   case '-':
  392.     r->virt = av & ~(bv);
  393.     while (as < topa) *rs++ = *as++ & ~(*bs++);
  394.     if (av)
  395.       while (rs < topr) *rs++ = ~(*bs++);
  396.     else
  397.       while (rs < topr) *rs++ = 0;
  398.     break;
  399.   case 'D':
  400.     r->virt = ~(av) & (bv);
  401.     while (as < topa) *rs++ = ~(*as++) & (*bs++);
  402.     if (av)
  403.       while (rs < topr) *rs++ = 0;
  404.     else
  405.       while (rs < topr) *rs++ = *bs++;
  406.     break;
  407.   }
  408.   trim(r);
  409.   return r;
  410. }
  411.  
  412.  
  413. void BitSet::set(int p)
  414. {
  415.   if (p < 0) error("Illegal bit index");
  416.  
  417.   int index = BitSet_index(p);
  418.   int pos   = BitSet_pos(p);
  419.  
  420.   if (index >= rep->len)
  421.   {
  422.     if (rep->virt)
  423.       return;
  424.     else
  425.       rep = BitSetresize(rep, index+1);
  426.   }
  427.  
  428.   rep->s[index] |= (1 << pos);
  429. }
  430.  
  431. void BitSet::clear(int p)
  432. {
  433.   if (p < 0) error("Illegal bit index");
  434.   int index = BitSet_index(p);
  435.   if (index >= rep->len)
  436.   {
  437.     if (rep->virt == 0)
  438.       return;
  439.     else
  440.       rep = BitSetresize(rep, index+1);
  441.   }
  442.   rep->s[index] &= ~(1 << BitSet_pos(p));
  443. }
  444.  
  445. void BitSet::invert(int p)
  446. {
  447.   if (p < 0) error("Illegal bit index");
  448.   int index = BitSet_index(p);
  449.   if (index >= rep->len) rep = BitSetresize(rep, index+1);
  450.   rep->s[index] ^= (1 << BitSet_pos(p));
  451. }
  452.  
  453. void BitSet::set(int from, int to)
  454. {
  455.   if (from < 0 || from > to) error("Illegal bit index");
  456.  
  457.   int index1 = BitSet_index(from);
  458.   int pos1   = BitSet_pos(from);
  459.   
  460.   if (rep->virt && index1 >= rep->len)
  461.     return;
  462.  
  463.   int index2 = BitSet_index(to);
  464.   int pos2   = BitSet_pos(to);
  465.  
  466.   if (index2 >= rep->len)
  467.     rep = BitSetresize(rep, index2+1);
  468.  
  469.   unsigned short* s = &(rep->s[index1]);
  470.   unsigned short m1 = lmask(pos1);
  471.   unsigned short m2 = rmask(pos2);
  472.   if (index2 == index1)
  473.     *s |= m1 & m2;
  474.   else
  475.   {
  476.     *s++ |= m1;
  477.     unsigned short* top = &(rep->s[index2]);
  478.     *top |= m2;
  479.     while (s < top)
  480.       *s++ = ONES;
  481.   }
  482. }
  483.  
  484. void BitSet::clear(int from, int to)
  485. {
  486.   if (from < 0 || from > to) error("Illegal bit index");
  487.  
  488.   int index1 = BitSet_index(from);
  489.   int pos1   = BitSet_pos(from);
  490.   
  491.   if (!rep->virt && index1 >= rep->len)
  492.     return;
  493.  
  494.   int index2 = BitSet_index(to);
  495.   int pos2   = BitSet_pos(to);
  496.  
  497.   if (index2 >= rep->len)
  498.     rep = BitSetresize(rep, index2+1);
  499.  
  500.   unsigned short* s = &(rep->s[index1]);
  501.   unsigned short m1 = lmask(pos1);
  502.   unsigned short m2 = rmask(pos2);
  503.   if (index2 == index1)
  504.     *s &= ~(m1 & m2);
  505.   else
  506.   {
  507.     *s++ &= ~m1;
  508.     unsigned short* top = &(rep->s[index2]);
  509.     *top &= ~m2;
  510.     while (s < top)
  511.       *s++ = 0;
  512.   }
  513. }
  514.  
  515. void BitSet::invert(int from, int to)
  516. {
  517.   if (from < 0 || from > to) error("Illegal bit index");
  518.  
  519.   int index1 = BitSet_index(from);
  520.   int pos1   = BitSet_pos(from);
  521.   int index2 = BitSet_index(to);
  522.   int pos2   = BitSet_pos(to);
  523.  
  524.   if (index2 >= rep->len)
  525.     rep = BitSetresize(rep, index2+1);
  526.  
  527.   unsigned short* s = &(rep->s[index1]);
  528.   unsigned short m1 = lmask(pos1);
  529.   unsigned short m2 = rmask(pos2);
  530.   if (index2 == index1)
  531.     *s ^= m1 & m2;
  532.   else
  533.   {
  534.     *s++ ^= m1;
  535.     unsigned short* top = &(rep->s[index2]);
  536.     *top ^= m2;
  537.     while (s < top)
  538.     {
  539.       unsigned short cmp = ~(*s);
  540.       *s++ = cmp;
  541.     }
  542.   }
  543. }
  544.  
  545.  
  546. int BitSet::test(int from, int to)
  547. {
  548.   if (from < 0 || from > to) return 0;
  549.  
  550.   int index1 = BitSet_index(from);
  551.   int pos1   = BitSet_pos(from);
  552.   
  553.   if (index1 >= rep->len)
  554.     return rep->virt;
  555.  
  556.   int index2 = BitSet_index(to);
  557.   int pos2   = BitSet_pos(to);
  558.  
  559.   if (index2 >= rep->len)
  560.   {
  561.     if (rep->virt)
  562.       return 1;
  563.     else 
  564.     {
  565.       index2 = rep->len - 1;
  566.       pos2 = BITSETBITS - 1;
  567.     }
  568.   }
  569.  
  570.   unsigned short* s = &(rep->s[index1]);
  571.   unsigned short m1 = lmask(pos1);
  572.   unsigned short m2 = rmask(pos2);
  573.  
  574.   if (index2 == index1)
  575.     return (*s & m1 & m2) != 0;
  576.   else
  577.   {
  578.     if (*s++ & m1)
  579.       return 1;
  580.     unsigned short* top = &(rep->s[index2]);
  581.     if (*top & m2)
  582.       return 1;
  583.     while (s < top)
  584.       if (*s++ != 0) 
  585.         return 1;
  586.     return 0;
  587.   }
  588. }
  589.  
  590. int BitSet::next(int p, int b = 1)
  591. {
  592.   ++p;
  593.   int index = BitSet_index(p);
  594.   int pos   = BitSet_pos(p);
  595.  
  596.   int l = rep->len;
  597.   
  598.   if (index >= l)
  599.   {
  600.     if (rep->virt == b)
  601.       return p;
  602.     else
  603.       return -1;
  604.   }
  605.   int j = index;
  606.   unsigned short* s = rep->s;
  607.   unsigned short a = s[j] >> pos;
  608.   int i = pos;
  609.  
  610.   if (b == 1)
  611.   {
  612.     for (; i < BITSETBITS && a != 0; ++i)
  613.     {
  614.       if (a & 1)
  615.         return j * BITSETBITS + i;
  616.       a >>= 1;
  617.     }
  618.     for (++j; j < l; ++j)
  619.     {
  620.       a = s[j];
  621.       for (i = 0; i < BITSETBITS && a != 0; ++i)
  622.       {
  623.         if (a & 1)
  624.           return j * BITSETBITS + i;
  625.         a >>= 1;
  626.       }
  627.     }
  628.     if (rep->virt)
  629.       return j * BITSETBITS;
  630.     else
  631.       return -1;
  632.   }
  633.   else
  634.   {
  635.     for (; i < BITSETBITS; ++i)
  636.     {
  637.       if ((a & 1) == 0)
  638.         return j * BITSETBITS + i;
  639.       a >>= 1;
  640.     }
  641.     for (++j; j < l; ++j)
  642.     {
  643.       a = s[j];
  644.       if (a != ONES)
  645.       {
  646.         for (i = 0; i < BITSETBITS; ++i)
  647.         {
  648.           if ((a & 1) == 0)
  649.             return j * BITSETBITS + i;
  650.           a >>= 1;
  651.         }
  652.       }
  653.     }
  654.     if (!rep->virt)
  655.       return j * BITSETBITS;
  656.     else
  657.       return -1;
  658.   }
  659. }
  660.  
  661. int BitSet::previous(int p, int b = 1)
  662. {
  663.   if (--p < 0)
  664.     return -1;
  665.  
  666.   int index = BitSet_index(p);
  667.   int pos   = BitSet_pos(p);
  668.  
  669.   unsigned short* s = rep->s;
  670.   int l = rep->len;
  671.  
  672.   if (index >= l)
  673.   {
  674.     if (rep->virt == b)
  675.       return p;
  676.     else
  677.     {
  678.       index = l - 1;
  679.       pos = BITSETBITS - 1;
  680.     }
  681.   }
  682.  
  683.   int j = index;
  684.   unsigned short a = s[j];
  685.  
  686.   int i = pos;
  687.   unsigned short maxbit = 1 << pos;
  688.  
  689.   if (b == 1)
  690.   {
  691.     for (; i >= 0 && a != 0; --i)
  692.     {
  693.       if (a & maxbit)
  694.         return j * BITSETBITS + i;
  695.       a <<= 1;
  696.     }
  697.     maxbit = 1 << (BITSETBITS - 1);
  698.     for (--j; j >= 0; --j)
  699.     {
  700.       a = s[j];
  701.       for (i = BITSETBITS - 1; i >= 0 && a != 0; --i)
  702.       {
  703.         if (a & maxbit)
  704.           return j * BITSETBITS + i;
  705.         a <<= 1;
  706.       }
  707.     }
  708.     return -1;
  709.   }
  710.   else
  711.   {
  712.     if (a != ONES)
  713.     {
  714.       for (; i >= 0; --i)
  715.       {
  716.         if ((a & maxbit) == 0)
  717.           return j * BITSETBITS + i;
  718.         a <<= 1;
  719.       }
  720.     }
  721.     maxbit = 1 << (BITSETBITS - 1);
  722.     for (--j; j >= 0; --j)
  723.     {
  724.       a = s[j];
  725.       if (a != ONES)
  726.       {
  727.         for (i = BITSETBITS - 1; i >= 0; --i)
  728.         {
  729.           if ((a & maxbit) == 0)
  730.             return j * BITSETBITS + i;
  731.           a <<= 1;
  732.         }
  733.       }
  734.     }
  735.     return -1;
  736.   }
  737. }
  738.  
  739. int BitSet::last(int b = 1)
  740. {
  741.   if (b == rep->virt)
  742.     return -1;
  743.   else
  744.     return previous((rep->len) * BITSETBITS, b);
  745. }
  746.  
  747. extern Obstack _libgxx_io_ob;
  748. extern char* _libgxx_io_oblast;
  749.  
  750. const char* BitSettoa(BitSet& x, char f = '0', char t = '1', char star = '*')
  751. {
  752.   if (_libgxx_io_oblast) _libgxx_io_ob.free(_libgxx_io_oblast);
  753.  
  754.   trim(x.rep);
  755.  
  756.   unsigned short* s = x.rep->s;
  757.   unsigned short* top = &(s[x.rep->len - 1]);
  758.  
  759.   while (s < top)
  760.   {
  761.     unsigned short a = *s++;
  762.     for (int j = 0; j < BITSETBITS; ++j)
  763.     {
  764.       _libgxx_io_ob.grow((a & 1)? t : f);
  765.       a >>= 1;
  766.     }
  767.   }
  768.  
  769.   if (!x.rep->virt)
  770.   {
  771.     unsigned short a = *s;
  772.     for (int j = 0; j < BITSETBITS && a != 0; ++j)
  773.     {
  774.       _libgxx_io_ob.grow((a & 1)? t : f);
  775.       a >>= 1;
  776.     }
  777.     _libgxx_io_ob.grow(f);
  778.   }
  779.   else
  780.   {
  781.     unsigned short a = *s;
  782.     unsigned short mask = ONES;
  783.     unsigned short himask = (1 << (BITSETBITS - 1)) - 1;
  784.     for (int j = 0; j < BITSETBITS && a != mask; ++j)
  785.     {
  786.       _libgxx_io_ob.grow((a & 1)? t : f);
  787.       a = (a >> 1) & himask;
  788.       mask = (mask >> 1) & himask;
  789.     }
  790.     _libgxx_io_ob.grow(t);
  791.   }
  792.  
  793.   _libgxx_io_ob.grow(star);
  794.  
  795.   return _libgxx_io_oblast = (char*)(_libgxx_io_ob.finish(0));
  796. }
  797.  
  798. BitSetTmp atoBitSet(const char* s, char f = '0', char t = '1', char star = '*')
  799. {
  800.   BitSet r;
  801.   int sl = strlen(s);
  802.   if (sl != 0)
  803.   {
  804.     r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1);
  805.     unsigned short* rs = r.rep->s;
  806.     unsigned short a = 0;
  807.     unsigned short m = 1;
  808.     char lastch = 0;
  809.     unsigned int i = 0;
  810.     unsigned int l = 1;
  811.     for(;;)
  812.     {
  813.       char ch = s[i];
  814.       if (ch == t)
  815.         a |= m;
  816.       else if (ch == star)
  817.       {
  818.         if (r.rep->virt = lastch == t)
  819.           *rs = a | ~(m - 1);
  820.         else
  821.           *rs = a;
  822.         break;
  823.       }
  824.       else if (ch != f)
  825.       {
  826.         *rs = a;
  827.         break;
  828.       }
  829.       lastch = ch;
  830.       if (++i == sl)
  831.       {
  832.         *rs = a;
  833.         break;
  834.       }
  835.       else if (i % BITSETBITS == 0)
  836.       {
  837.         *rs++ = a;
  838.         a = 0;
  839.         m = 1;
  840.         ++l;
  841.       }
  842.       else
  843.         m <<= 1;
  844.     }
  845.     r.rep->len = l;
  846.     trim(r.rep);
  847.   }
  848.   return r;
  849. }
  850.  
  851. ostream& operator << (ostream& s, BitSet& x)
  852. {
  853.   return s << BitSettoa(x);
  854. }
  855.  
  856. int BitSet::OK()
  857. {
  858.   int v = rep != 0;             // have a rep
  859.   v &= rep->len <= rep->sz;     // within bounds
  860.   v &= rep->virt == 0 || rep->virt == 1; // valid virtual bit
  861.   if (!v) error("invariant failure");
  862.   return v;
  863. }
  864.  
  865.