home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / gnu / djgpp / src / libgplus.5 / libgplus / src / bitset.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-11-13  |  20.2 KB  |  1,005 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 the GNU C++ Library.  This library is free
  6. software; you can redistribute it and/or modify it under the terms of
  7. the GNU Library General Public License as published by the Free
  8. Software Foundation; either version 2 of the License, or (at your
  9. option) any later version.  This library is distributed in the hope
  10. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  11. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  12. PURPOSE.  See the GNU Library General Public License for more details.
  13. You should have received a copy of the GNU Library General Public
  14. License along with this library; if not, write to the Free Software
  15. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  16. */
  17.  
  18. /* 
  19.   BitSet class implementation
  20.  */
  21.  
  22. #ifdef __GNUG__
  23. #pragma implementation
  24. #endif
  25. #include <BitSet.h>
  26. #include <std.h>
  27. #include <limits.h>
  28. #ifdef __MSDOS__
  29. #include <_Obstack.h>
  30. #else
  31. #include <Obstack.h>
  32. #endif
  33. #include <AllocRing.h>
  34. #include <new.h>
  35. #include <builtin.h>
  36. #include <string.h>
  37. #include <strstream.h>
  38.  
  39. void BitSet::error(const char* msg) const
  40. {
  41.   (*lib_error_handler)("BitSet", msg);
  42. }
  43.  
  44. //  globals & constants
  45.  
  46. BitSetRep  _nilBitSetRep = { 0, 1, 0, {0} }; // nil BitSets point here
  47.  
  48. #define ONES               ((unsigned short)(~0L))
  49. #define MAXBitSetRep_SIZE  ((1 << (sizeof(short)*CHAR_BIT - 1)) - 1)
  50. #define MINBitSetRep_SIZE  16
  51.  
  52. #ifndef MALLOC_MIN_OVERHEAD
  53. #define MALLOC_MIN_OVERHEAD     4
  54. #endif
  55.  
  56. // break things up into .s indices and positions
  57.  
  58.  
  59. // mask out bits from left
  60.  
  61. static inline unsigned short lmask(int p)
  62. {
  63.   return ONES << p;
  64. }
  65.  
  66. // mask out high bits
  67.  
  68. static inline unsigned short rmask(int p)
  69. {
  70.   return ONES >> (BITSETBITS - 1 - p);
  71. }
  72.  
  73.  
  74. inline static BitSetRep* BSnew(int newlen)
  75. {
  76.   unsigned int siz = sizeof(BitSetRep) + newlen * sizeof(short) 
  77.     + MALLOC_MIN_OVERHEAD;
  78.   unsigned int allocsiz = MINBitSetRep_SIZE;;
  79.   while (allocsiz < siz) allocsiz <<= 1;
  80.   allocsiz -= MALLOC_MIN_OVERHEAD;
  81.   if (allocsiz >= MAXBitSetRep_SIZE * sizeof(short))
  82.     (*lib_error_handler)("BitSet", "Requested length out of range");
  83.     
  84.   BitSetRep* rep = (BitSetRep *) new char[allocsiz];
  85.   memset(rep, 0, allocsiz);
  86.   rep->sz = (allocsiz - sizeof(BitSetRep) + sizeof(short)) / sizeof(short);
  87.   return rep;
  88. }
  89.  
  90. BitSetRep* BitSetalloc(BitSetRep* old, const unsigned short* src, int srclen,
  91.                 int newvirt, int newlen)
  92. {
  93.   if (old == &_nilBitSetRep) old = 0;
  94.   BitSetRep* rep;
  95.   if (old == 0 || newlen >= old->sz)
  96.     rep = BSnew(newlen);
  97.   else
  98.     rep = old;
  99.  
  100.   rep->len = newlen;
  101.   rep->virt = newvirt;
  102.  
  103.   if (srclen != 0 && src != rep->s)
  104.     memcpy(rep->s, src, srclen * sizeof(short));
  105.   // BUG fix: extend virtual bit! 20 Oct 1992 Kevin Karplus
  106.   if (rep->virt)
  107.       memset(&rep->s[srclen], ONES, (newlen - srclen) * sizeof(short));
  108.   if (old != rep && old != 0) delete old;
  109.   return rep;
  110. }
  111.  
  112. BitSetRep* BitSetresize(BitSetRep* old, int newlen)
  113. {
  114.   BitSetRep* rep;
  115.   if (old == 0 || old == &_nilBitSetRep)
  116.   {
  117.     rep = BSnew(newlen);
  118.     rep->virt = 0;
  119.   }
  120.   else if (newlen >= old->sz)
  121.   {
  122.     rep = BSnew(newlen);
  123.     memcpy(rep->s, old->s, old->len * sizeof(short));
  124.     rep->virt = old->virt;
  125.     // BUG fix: extend virtual bit!  20 Oct 1992 Kevin Karplus
  126.     if (rep->virt)
  127.     memset(&rep->s[old->len], ONES, (newlen - old->len) * sizeof(short));
  128.     delete old;
  129.   }
  130.   else
  131.     rep = old;
  132.  
  133.   rep->len = newlen;
  134.  
  135.   return rep;
  136. }
  137.  
  138. // same, for straight copy
  139.  
  140. BitSetRep* BitSetcopy(BitSetRep* old, const BitSetRep* src)
  141. {
  142.   BitSetRep* rep;
  143.   if (old == &_nilBitSetRep) old = 0;
  144.   if (src == 0 || src == &_nilBitSetRep)
  145.   {
  146.     if (old == 0)
  147.       rep = BSnew(0);
  148.     else
  149.       rep = old;
  150.     rep->len = 0;
  151.     rep->virt = 0;
  152.   }
  153.   else if (old == src) 
  154.     return old; 
  155.   else 
  156.   {
  157.     int newlen = src->len;
  158.     if (old == 0 || newlen > old->sz)
  159.     {
  160.       rep = BSnew(newlen);
  161.       if (old != 0) delete old;
  162.     }
  163.     else
  164.       rep = old;
  165.  
  166.     memcpy(rep->s, src->s, newlen * sizeof(short));
  167.     rep->len = newlen;
  168.     rep->virt = src->virt;
  169.   }
  170.   return rep;
  171. }
  172.  
  173.  
  174. // remove unneeded top bits
  175.  
  176. inline static void trim(BitSetRep* rep)
  177. {
  178.   int l = rep->len;
  179.   unsigned short* s = &(rep->s[l - 1]);
  180.  
  181.   if (rep->virt == 0)
  182.     while (l > 0 && *s-- == 0) --l;
  183.   else
  184.     while (l > 0 && *s-- == ONES) --l;
  185.   rep->len = l;
  186. }
  187.  
  188. int operator == (const BitSet& x, const BitSet& y)
  189. {
  190.   if (x.rep->virt != y.rep->virt)
  191.     return 0;
  192.   int xl = x.rep->len;
  193.   int yl = y.rep->len;
  194.  
  195.   unsigned short* xs = x.rep->s;
  196.   unsigned short* ys = y.rep->s;
  197.   if (xl<=yl)
  198.     {
  199.       if (memcmp((void*)xs, (void*)ys, xl * sizeof(short)))
  200.       return 0;
  201.       for (register int i=xl; i<yl; i++)
  202.         if (ys[i])
  203.       return 0;
  204.       return 1;
  205.     }
  206.   else
  207.     {
  208.       if (memcmp((void*)xs, (void*)ys, yl * sizeof(short)))
  209.       return 0;
  210.       for (register int i=yl; i<xl; i++)
  211.         if (xs[i]) 
  212.       return 0;
  213.       return 1;
  214.     }
  215. }
  216.  
  217. int operator <= (const BitSet& x, const BitSet& y)
  218. {
  219.   if (x.rep->virt > y.rep->virt)
  220.     return 0;
  221.  
  222.   int xl = x.rep->len;
  223.   int yl = y.rep->len; 
  224.  
  225.   unsigned short* xs = x.rep->s;
  226.   unsigned short* ys = y.rep->s;
  227.   unsigned short* topx = &(xs[xl]);
  228.   unsigned short* topy = &(ys[yl]);
  229.  
  230.   while (xs < topx && ys < topy)
  231.   {
  232.     unsigned short a = *xs++;
  233.     unsigned short b = *ys++;
  234.     if ((a | b) != b)
  235.       return 0;
  236.   }
  237.   if (xl == yl)
  238.     return x.rep->virt <= y.rep->virt;
  239.   else if (xl < yl)
  240.     return !x.rep->virt;
  241.   else
  242.     return y.rep->virt;
  243. }
  244.  
  245.  
  246. int operator < (const BitSet& x, const BitSet& y)
  247. {
  248.   if (x.rep->virt > y.rep->virt)
  249.     return 0;
  250.  
  251.   int xl = x.rep->len;
  252.   int yl = y.rep->len;
  253.  
  254.   unsigned short* xs = x.rep->s;
  255.   unsigned short* ys = y.rep->s;
  256.   unsigned short* topx = &(xs[xl]);
  257.   unsigned short* topy = &(ys[yl]);
  258.   int one_diff = 0;
  259.   while (xs < topx && ys < topy)
  260.   {
  261.     unsigned short a = *xs++;
  262.     unsigned short b = *ys++;
  263.     unsigned short c = a | b;
  264.     if (c != b)
  265.       return 0;
  266.     else if (c != a)
  267.       one_diff = 1;
  268.   }
  269.   if (xl == yl)
  270.     return x.rep->virt < y.rep->virt || 
  271.       (one_diff && x.rep->virt == y.rep->virt);
  272.   else if (xl < yl)
  273.     return !x.rep->virt;
  274.   else
  275.     return y.rep->virt;
  276. }
  277.  
  278.  
  279.  
  280. int BitSet::empty() const
  281. {
  282.   if (rep->virt == 1)
  283.     return 0;
  284.  
  285.   unsigned short* bots = rep->s;
  286.   unsigned short* s = &(bots[rep->len - 1]);
  287.   while (s >= bots) if (*s-- != 0) return 0;
  288.   return 1;
  289. }
  290.  
  291.  
  292. int BitSet::count(int b) const
  293. {
  294.   if (b == rep->virt)
  295.     return -1;
  296.   int l = 0;
  297.   unsigned short* s = rep->s;
  298.   unsigned short* tops = &(s[rep->len]);
  299.   if (b == 1)
  300.   {
  301.     while (s < tops)
  302.     {
  303.       unsigned short a = *s++;
  304.       for (int i = 0; i < BITSETBITS && a != 0; ++i)
  305.       {
  306.         if (a & 1)
  307.           ++l;
  308.         a >>= 1;
  309.       }
  310.     }
  311.   }
  312.   else
  313.   {
  314.     unsigned short maxbit = 1 << (BITSETBITS - 1);
  315.     while (s < tops)
  316.     {
  317.       unsigned short a = *s++;
  318.       for (int i = 0; i < BITSETBITS; ++i)
  319.       {
  320.         if ((a & maxbit) == 0)
  321.           ++l;
  322.         a <<= 1;
  323.       }
  324.     }
  325.   }
  326.   return l;
  327. }
  328.  
  329. BitSetRep* BitSetcmpl(const BitSetRep* src, BitSetRep* r)
  330. {
  331.   r = BitSetcopy(r, src);
  332.   r->virt = !src->virt;
  333.   unsigned short* rs = r->s;
  334.   unsigned short* topr = &(rs[r->len]);
  335.   if (r->len == 0)
  336.     *rs = ONES;
  337.   else
  338.   {
  339.     while (rs < topr)
  340.     {
  341.       unsigned short cmp = ~(*rs);
  342.       *rs++ = cmp;
  343.     }
  344.   }
  345.   trim(r);
  346.   return r;
  347. }
  348.  
  349.  
  350. BitSetRep* BitSetop(const BitSetRep* x, const BitSetRep* y, 
  351.                     BitSetRep* r, char op)
  352. {
  353.   int xrsame = x == r;
  354.   int yrsame = y == r;
  355.   int xv = x->virt;
  356.   int yv = y->virt;
  357.   int xl = x->len;
  358.   int yl = y->len;
  359.   int rl = (xl >= yl)? xl : yl;
  360.  
  361.   r = BitSetresize(r, rl);
  362.   unsigned short* rs = r->s;
  363.   unsigned short* topr = &(rs[rl]);
  364.  
  365.   int av, bv;
  366.   const unsigned short* as;
  367.   const unsigned short* topa;
  368.   const unsigned short* bs;
  369.   const unsigned short* topb;
  370.   
  371.   if (xl <= yl)
  372.   {
  373.     as = (xrsame)? r->s : x->s;
  374.     av = xv;
  375.     topa = &(as[xl]);
  376.     bs = (yrsame)? r->s : y->s;
  377.     bv = yv;
  378.     topb = &(bs[yl]);
  379.   }
  380.   else
  381.   {
  382.     as = (yrsame)? r->s : y->s;
  383.     av = yv;
  384.     topa = &(as[yl]);
  385.     bs = (xrsame)? r->s : x->s;
  386.     bv = xv;
  387.     topb = &(bs[xl]);
  388.     if (op == '-')              // reverse sense of difference
  389.       op = 'D';
  390.   }
  391.  
  392.   switch (op)
  393.   {
  394.   case '&':
  395.     r->virt = av & bv;
  396.     while (as < topa) *rs++ = *as++ & *bs++;
  397.     if (av)
  398.       while (rs < topr) *rs++ = *bs++;
  399.     else
  400.       while (rs < topr) *rs++ = 0;
  401.     break;
  402.   case '|':
  403.     r->virt = av | bv;
  404.     while (as < topa) *rs++ = *as++ | *bs++;
  405.     if (av)
  406.       while (rs < topr) *rs++ = ONES;
  407.     else
  408.       while (rs < topr) *rs++ = *bs++;
  409.     break;
  410.   case '^':
  411.     r->virt = av ^ bv;
  412.     while (as < topa) *rs++ = *as++ ^ *bs++;
  413.     if (av)
  414.       while (rs < topr) *rs++ = ~(*bs++);
  415.     else
  416.       while (rs < topr) *rs++ = *bs++;
  417.     break;
  418.   case '-':
  419.     r->virt = av & ~(bv);
  420.     while (as < topa) *rs++ = *as++ & ~(*bs++);
  421.     if (av)
  422.       while (rs < topr) *rs++ = ~(*bs++);
  423.     else
  424.       while (rs < topr) *rs++ = 0;
  425.     break;
  426.   case 'D':
  427.     r->virt = ~(av) & (bv);
  428.     while (as < topa) *rs++ = ~(*as++) & (*bs++);
  429.     if (av)
  430.       while (rs < topr) *rs++ = 0;
  431.     else
  432.       while (rs < topr) *rs++ = *bs++;
  433.     break;
  434.   }
  435.   trim(r);
  436.   return r;
  437. }
  438.  
  439.  
  440. void BitSet::set(int p)
  441. {
  442.   if (p < 0) error("Illegal bit index");
  443.  
  444.   int index = BitSet_index(p);
  445.   int pos   = BitSet_pos(p);
  446.  
  447.   if (index >= rep->len)
  448.   {
  449.     if (rep->virt)
  450.       return;
  451.     else
  452.       rep = BitSetresize(rep, index+1);
  453.   }
  454.  
  455.   rep->s[index] |= (1 << pos);
  456. }
  457.  
  458. void BitSet::clear()
  459. {
  460.   if (rep->len > 0) memset(rep->s, 0, rep->sz * sizeof(short));
  461.   rep->len = rep->virt = 0;
  462. }
  463.  
  464. void BitSet::clear(int p)
  465. {
  466.   if (p < 0) error("Illegal bit index");
  467.   int index = BitSet_index(p);
  468.   if (index >= rep->len)
  469.   {
  470.     if (rep->virt == 0)
  471.       return;
  472.     else
  473.       rep = BitSetresize(rep, index+1);
  474.   }
  475.   rep->s[index] &= ~(1 << BitSet_pos(p));
  476. }
  477.  
  478. void BitSet::invert(int p)
  479. {
  480.   if (p < 0) error("Illegal bit index");
  481.   int index = BitSet_index(p);
  482.   if (index >= rep->len) rep = BitSetresize(rep, index+1);
  483.   rep->s[index] ^= (1 << BitSet_pos(p));
  484. }
  485.  
  486. void BitSet::set(int from, int to)
  487. {
  488.   if (from < 0 || from > to) error("Illegal bit index");
  489.  
  490.   int index1 = BitSet_index(from);
  491.   int pos1   = BitSet_pos(from);
  492.   
  493.   if (rep->virt && index1 >= rep->len)
  494.     return;
  495.  
  496.   int index2 = BitSet_index(to);
  497.   int pos2   = BitSet_pos(to);
  498.  
  499.   if (index2 >= rep->len)
  500.     rep = BitSetresize(rep, index2+1);
  501.  
  502.   unsigned short* s = &(rep->s[index1]);
  503.   unsigned short m1 = lmask(pos1);
  504.   unsigned short m2 = rmask(pos2);
  505.   if (index2 == index1)
  506.     *s |= m1 & m2;
  507.   else
  508.   {
  509.     *s++ |= m1;
  510.     unsigned short* top = &(rep->s[index2]);
  511.     *top |= m2;
  512.     while (s < top)
  513.       *s++ = ONES;
  514.   }
  515. }
  516.  
  517. void BitSet::clear(int from, int to)
  518. {
  519.   if (from < 0 || from > to) error("Illegal bit index");
  520.  
  521.   int index1 = BitSet_index(from);
  522.   int pos1   = BitSet_pos(from);
  523.   
  524.   if (!rep->virt && index1 >= rep->len)
  525.     return;
  526.  
  527.   int index2 = BitSet_index(to);
  528.   int pos2   = BitSet_pos(to);
  529.  
  530.   if (index2 >= rep->len)
  531.     rep = BitSetresize(rep, index2+1);
  532.  
  533.   unsigned short* s = &(rep->s[index1]);
  534.   unsigned short m1 = lmask(pos1);
  535.   unsigned short m2 = rmask(pos2);
  536.   if (index2 == index1)
  537.     *s &= ~(m1 & m2);
  538.   else
  539.   {
  540.     *s++ &= ~m1;
  541.     unsigned short* top = &(rep->s[index2]);
  542.     *top &= ~m2;
  543.     while (s < top)
  544.       *s++ = 0;
  545.   }
  546. }
  547.  
  548. void BitSet::invert(int from, int to)
  549. {
  550.   if (from < 0 || from > to) error("Illegal bit index");
  551.  
  552.   int index1 = BitSet_index(from);
  553.   int pos1   = BitSet_pos(from);
  554.   int index2 = BitSet_index(to);
  555.   int pos2   = BitSet_pos(to);
  556.  
  557.   if (index2 >= rep->len)
  558.     rep = BitSetresize(rep, index2+1);
  559.  
  560.   unsigned short* s = &(rep->s[index1]);
  561.   unsigned short m1 = lmask(pos1);
  562.   unsigned short m2 = rmask(pos2);
  563.   if (index2 == index1)
  564.     *s ^= m1 & m2;
  565.   else
  566.   {
  567.     *s++ ^= m1;
  568.     unsigned short* top = &(rep->s[index2]);
  569.     *top ^= m2;
  570.     while (s < top)
  571.     {
  572.       unsigned short cmp = ~(*s);
  573.       *s++ = cmp;
  574.     }
  575.   }
  576. }
  577.  
  578.  
  579. int BitSet::test(int from, int to) const
  580. {
  581.   if (from < 0 || from > to) return 0;
  582.  
  583.   int index1 = BitSet_index(from);
  584.   int pos1   = BitSet_pos(from);
  585.   
  586.   if (index1 >= rep->len)
  587.     return rep->virt;
  588.  
  589.   int index2 = BitSet_index(to);
  590.   int pos2   = BitSet_pos(to);
  591.  
  592.   if (index2 >= rep->len)
  593.   {
  594.     if (rep->virt)
  595.       return 1;
  596.     else 
  597.     {
  598.       index2 = rep->len - 1;
  599.       pos2 = BITSETBITS - 1;
  600.     }
  601.   }
  602.  
  603.   unsigned short* s = &(rep->s[index1]);
  604.   unsigned short m1 = lmask(pos1);
  605.   unsigned short m2 = rmask(pos2);
  606.  
  607.   if (index2 == index1)
  608.     return (*s & m1 & m2) != 0;
  609.   else
  610.   {
  611.     if (*s++ & m1)
  612.       return 1;
  613.     unsigned short* top = &(rep->s[index2]);
  614.     if (*top & m2)
  615.       return 1;
  616.     while (s < top)
  617.       if (*s++ != 0) 
  618.         return 1;
  619.     return 0;
  620.   }
  621. }
  622.  
  623. int BitSet::next(int p, int b) const
  624. {
  625.   ++p;
  626.   int index = BitSet_index(p);
  627.   int pos   = BitSet_pos(p);
  628.  
  629.   int l = rep->len;
  630.   
  631.   if (index >= l)
  632.   {
  633.     if (rep->virt == b)
  634.       return p;
  635.     else
  636.       return -1;
  637.   }
  638.   int j = index;
  639.   unsigned short* s = rep->s;
  640.   unsigned short a = s[j] >> pos;
  641.   int i = pos;
  642.  
  643.   if (b == 1)
  644.   {
  645.     for (; i < BITSETBITS && a != 0; ++i)
  646.     {
  647.       if (a & 1)
  648.         return j * BITSETBITS + i;
  649.       a >>= 1;
  650.     }
  651.     for (++j; j < l; ++j)
  652.     {
  653.       a = s[j];
  654.       for (i = 0; i < BITSETBITS && a != 0; ++i)
  655.       {
  656.         if (a & 1)
  657.           return j * BITSETBITS + i;
  658.         a >>= 1;
  659.       }
  660.     }
  661.     if (rep->virt)
  662.       return j * BITSETBITS;
  663.     else
  664.       return -1;
  665.   }
  666.   else
  667.   {
  668.     for (; i < BITSETBITS; ++i)
  669.     {
  670.       if ((a & 1) == 0)
  671.         return j * BITSETBITS + i;
  672.       a >>= 1;
  673.     }
  674.     for (++j; j < l; ++j)
  675.     {
  676.       a = s[j];
  677.       if (a != ONES)
  678.       {
  679.         for (i = 0; i < BITSETBITS; ++i)
  680.         {
  681.           if ((a & 1) == 0)
  682.             return j * BITSETBITS + i;
  683.           a >>= 1;
  684.         }
  685.       }
  686.     }
  687.     if (!rep->virt)
  688.       return j * BITSETBITS;
  689.     else
  690.       return -1;
  691.   }
  692. }
  693.  
  694. int BitSet::prev(int p, int b) const
  695. {
  696.   if (--p < 0)
  697.     return -1;
  698.  
  699.   int index = BitSet_index(p);
  700.   int pos   = BitSet_pos(p);
  701.  
  702.   unsigned short* s = rep->s;
  703.   int l = rep->len;
  704.  
  705.   if (index >= l)
  706.   {
  707.     if (rep->virt == b)
  708.       return p;
  709.     else
  710.     {
  711.       index = l - 1;
  712.       pos = BITSETBITS - 1;
  713.     }
  714.   }
  715.  
  716.   int j = index;
  717.   unsigned short a = s[j];
  718.  
  719.   int i = pos;
  720.   unsigned short maxbit = 1 << pos;
  721.  
  722.   if (b == 1)
  723.   {
  724.     for (; i >= 0 && a != 0; --i)
  725.     {
  726.       if (a & maxbit)
  727.         return j * BITSETBITS + i;
  728.       a <<= 1;
  729.     }
  730.     maxbit = 1 << (BITSETBITS - 1);
  731.     for (--j; j >= 0; --j)
  732.     {
  733.       a = s[j];
  734.       for (i = BITSETBITS - 1; i >= 0 && a != 0; --i)
  735.       {
  736.         if (a & maxbit)
  737.           return j * BITSETBITS + i;
  738.         a <<= 1;
  739.       }
  740.     }
  741.     return -1;
  742.   }
  743.   else
  744.   {
  745.     if (a != ONES)
  746.     {
  747.       for (; i >= 0; --i)
  748.       {
  749.         if ((a & maxbit) == 0)
  750.           return j * BITSETBITS + i;
  751.         a <<= 1;
  752.       }
  753.     }
  754.     maxbit = 1 << (BITSETBITS - 1);
  755.     for (--j; j >= 0; --j)
  756.     {
  757.       a = s[j];
  758.       if (a != ONES)
  759.       {
  760.         for (i = BITSETBITS - 1; i >= 0; --i)
  761.         {
  762.           if ((a & maxbit) == 0)
  763.             return j * BITSETBITS + i;
  764.           a <<= 1;
  765.         }
  766.       }
  767.     }
  768.     return -1;
  769.   }
  770. }
  771.  
  772. int BitSet::last(int b) const
  773. {
  774.   if (b == rep->virt)
  775.     return -1;
  776.   else
  777.     return prev((rep->len) * BITSETBITS, b);
  778. }
  779.  
  780.  
  781. extern AllocRing _libgxx_fmtq;
  782.  
  783. const char* BitSettoa(const BitSet& x, char f, char t, char star)
  784. {
  785.   trim(x.rep);
  786.   int wrksiz = (x.rep->len + 1) * BITSETBITS + 2;
  787.   char* fmtbase = (char *) _libgxx_fmtq.alloc(wrksiz);
  788.   ostrstream stream(fmtbase, wrksiz);
  789.   
  790.   x.printon(stream, f, t, star);
  791.   stream << ends;
  792.   return fmtbase;
  793. }
  794.  
  795. #if defined(__GNUG__) && !defined(NO_NRV)
  796.  
  797. BitSet shorttoBitSet(unsigned short w) return r
  798. {
  799.   r.rep = BitSetalloc(0, &w, 1, 0, 2);  trim(r.rep);
  800. }
  801.  
  802. BitSet longtoBitSet(unsigned long w) return r;
  803. {
  804.   unsigned short u[2];
  805.   u[0] = w & ((unsigned short)(~(0)));
  806.   u[1] = w >> BITSETBITS;
  807.   r.rep = BitSetalloc(0, &u[0], 2, 0, 3);
  808.   trim(r.rep);
  809. }
  810.  
  811. BitSet atoBitSet(const char* s, char f, char t, char star) return r
  812. {
  813.   int sl = strlen(s);
  814.   if (sl != 0)
  815.   {
  816.     r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1);
  817.     unsigned short* rs = r.rep->s;
  818.     unsigned short a = 0;
  819.     unsigned short m = 1;
  820.     char lastch = 0;
  821.     unsigned int i = 0;
  822.     unsigned int l = 1;
  823.     for(;;)
  824.     {
  825.       char ch = s[i];
  826.       if (ch == t)
  827.         a |= m;
  828.       else if (ch == star)
  829.       {
  830.         if (r.rep->virt = lastch == t)
  831.           *rs = a | ~(m - 1);
  832.         else
  833.           *rs = a;
  834.         break;
  835.       }
  836.       else if (ch != f)
  837.       {
  838.         *rs = a;
  839.         break;
  840.       }
  841.       lastch = ch;
  842.       if (++i == sl)
  843.       {
  844.         *rs = a;
  845.         break;
  846.       }
  847.       else if (i % BITSETBITS == 0)
  848.       {
  849.         *rs++ = a;
  850.         a = 0;
  851.         m = 1;
  852.         ++l;
  853.       }
  854.       else
  855.         m <<= 1;
  856.     }
  857.     r.rep->len = l;
  858.     trim(r.rep);
  859.   }
  860.   return;
  861. }
  862.  
  863. #else
  864.  
  865. BitSet shorttoBitSet(unsigned short w) 
  866. {
  867.   BitSet r;
  868.   r.rep = BitSetalloc(0, &w, 1, 0, 2);  trim(r.rep);
  869.   return r;
  870. }
  871.  
  872. BitSet longtoBitSet(unsigned long w)
  873. {
  874.   BitSet r;
  875.   unsigned short u[2];
  876.   u[0] = w & ((unsigned short)(~(0)));
  877.   u[1] = w >> BITSETBITS;
  878.   r.rep = BitSetalloc(0, &u[0], 2, 0, 3);
  879.   trim(r.rep);
  880.   return r;
  881. }
  882.  
  883. BitSet atoBitSet(const char* s, char f, char t, char star) 
  884. {
  885.   BitSet r;
  886.   int sl = strlen(s);
  887.   if (sl != 0)
  888.   {
  889.     r.rep = BitSetresize(r.rep, sl / BITSETBITS + 1);
  890.     unsigned short* rs = r.rep->s;
  891.     unsigned short a = 0;
  892.     unsigned short m = 1;
  893.     char lastch = 0;
  894.     unsigned int i = 0;
  895.     unsigned int l = 1;
  896.     for(;;)
  897.     {
  898.       char ch = s[i];
  899.       if (ch == t)
  900.         a |= m;
  901.       else if (ch == star)
  902.       {
  903.         if (r.rep->virt = lastch == t)
  904.           *rs = a | ~(m - 1);
  905.         else
  906.           *rs = a;
  907.         break;
  908.       }
  909.       else if (ch != f)
  910.       {
  911.         *rs = a;
  912.         break;
  913.       }
  914.       lastch = ch;
  915.       if (++i == sl)
  916.       {
  917.         *rs = a;
  918.         break;
  919.       }
  920.       else if (i % BITSETBITS == 0)
  921.       {
  922.         *rs++ = a;
  923.         a = 0;
  924.         m = 1;
  925.         ++l;
  926.       }
  927.       else
  928.         m <<= 1;
  929.     }
  930.     r.rep->len = l;
  931.     trim(r.rep);
  932.   }
  933.   return r;
  934. }
  935.  
  936. #endif
  937.  
  938. ostream& operator << (ostream& s, const BitSet& x)
  939. {
  940.   if (s.opfx())
  941.     x.printon(s);
  942.   return s;
  943. }
  944.  
  945. void BitSet::printon(ostream& os, char f, char t, char star) const
  946. // FIXME:  Does not respect s.width()!
  947. {
  948.   trim(rep);
  949.   register streambuf* sb = os.rdbuf();
  950.   const unsigned short* s = rep->s;
  951.   const unsigned short* top = &(s[rep->len - 1]);
  952.  
  953.   while (s < top)
  954.   {
  955.     unsigned short a = *s++;
  956.     for (int j = 0; j < BITSETBITS; ++j)
  957.     {
  958.       sb->sputc((a & 1)? t : f);
  959.       a >>= 1;
  960.     }
  961.   }
  962.  
  963.   if (!rep->virt)
  964.   {
  965.     unsigned short a = *s;
  966.     if (rep->len != 0)
  967.     {
  968.       for (int j = 0; j < BITSETBITS && a != 0; ++j)
  969.       {
  970.         sb->sputc((a & 1)? t : f);
  971.         a >>= 1;
  972.       }
  973.     }
  974.     sb->sputc(f);
  975.   }
  976.   else
  977.   {
  978.     unsigned short a = *s;
  979.     unsigned short mask = ONES;
  980.     unsigned short himask = (1 << (BITSETBITS - 1)) - 1;
  981.     if (rep->len != 0)
  982.     {
  983.       for (int j = 0; j < BITSETBITS && a != mask; ++j)
  984.       {
  985.         sb->sputc((a & 1)? t : f);
  986.         a = (a >> 1) & himask;
  987.         mask = (mask >> 1) & himask;
  988.       }
  989.     }
  990.     sb->sputc(t);
  991.   }
  992.  
  993.   sb->sputc(star);
  994. }
  995.  
  996. int BitSet::OK() const
  997. {
  998.   int v = rep != 0;             // have a rep
  999.   v &= rep->len <= rep->sz;     // within bounds
  1000.   v &= rep->virt == 0 || rep->virt == 1; // valid virtual bit
  1001.   if (!v) error("invariant failure");
  1002.   return v;
  1003. }
  1004.  
  1005.