home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c017 / 7.ddi / GPPLIB.ZIP / BITSTR.CC < prev    next >
Encoding:
C/C++ Source or Header  |  1988-08-17  |  40.3 KB  |  1,844 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.   BitString class implementation
  25.  */
  26.  
  27. #include <BitString.h>
  28. #include <std.h>
  29. #include "libconfig.h"
  30. #include <Obstack.h>
  31.  
  32. // error handling
  33.  
  34.  
  35. void default_BitString_error_handler(char* msg)
  36. {
  37.   cerr << "Fatal BitString error. " << msg << "\n";
  38.   exit(1);
  39. }
  40.  
  41. one_arg_error_handler_t BitString_error_handler = default_BitString_error_handler;
  42.  
  43. one_arg_error_handler_t set_BitString_error_handler(one_arg_error_handler_t f)
  44. {
  45.   one_arg_error_handler_t old = BitString_error_handler;
  46.   BitString_error_handler = f;
  47.   return old;
  48. }
  49.  
  50. void BitString::error(char* msg)
  51. {
  52.   (*BitString_error_handler)(msg);
  53. }
  54.  
  55. //  globals
  56.  
  57. _BitStringrep    _nil_BitStringrep = {  0, 1, -1, {0} };
  58.  
  59. static BitString _nil_BitString;
  60.  
  61.  
  62. #define MIN_BITSTRING_SIZE  2
  63. #define MAX_BITSTRING_SIZE  (1 << (SHORTBITS - 1) - 1)
  64.  
  65. //static unsigned long ones = ~(0L); // g++/vax bug workaround
  66. #define ONES  ((unsigned long)(~0L))
  67. #define MAXBIT  (1 << (B_SHIFT - 1))
  68.  
  69. /*
  70.  *  bit manipulation utilities
  71. */
  72.  
  73. // break things up into .s indices and positions
  74.  
  75. inline static int word_length(int l)
  76. {
  77.   return (unsigned)(l) / B_SHIFT + 1;
  78. }
  79.  
  80. inline static int word_index(int l)
  81. {
  82.   return (unsigned)(l) / B_SHIFT;
  83. }
  84.  
  85. inline static int bit_position(int l)
  86. {
  87.   return l & (B_SHIFT - 1);
  88. }
  89.  
  90. // mask out low bits
  91.  
  92. static inline unsigned long lmask(int p)
  93. {
  94.   if (p <= 0)
  95.     return ONES;
  96.   else
  97.     return ONES << p;
  98. }
  99.  
  100. // mask out high bits
  101.  
  102. static inline unsigned long rmask(int p)
  103. {
  104.   int s = B_SHIFT - 1 - p;
  105.   if (s <= 0)
  106.     return ONES;
  107.   else
  108.     return ONES >> s;
  109. }
  110.  
  111.  
  112. // mask out unused bits in last word of rep
  113.  
  114. inline static void check_last(_BitStringrep* r)
  115. {
  116.   r->s[r->len / B_SHIFT] &= ONES >> (B_SHIFT - (r->len & (B_SHIFT - 1)));
  117. }
  118.  
  119. // merge bits from next word
  120.  
  121. static inline unsigned long borrow_hi(unsigned long a[], int ind, 
  122.                                       int maxind, int p)
  123. {
  124.   if (ind < maxind)
  125.     return (a[ind] >> p) | (a[ind+1] << (B_SHIFT - p));
  126.   else
  127.     return (a[ind] >> p);
  128. }
  129.  
  130. // merge bits from prev word
  131.  
  132. static inline unsigned long borrow_lo(unsigned long a[], int ind, 
  133.                                       int minind, int p)
  134. {
  135.   if (ind > minind)
  136.     return (a[ind] << (B_SHIFT - 1 - p)) | (a[ind-1] >> (p + 1));
  137.   else
  138.     return (a[ind] << (B_SHIFT - 1 - p));
  139. }
  140.  
  141. // same with bounds check (for masks shorter than patterns)
  142.  
  143. static inline unsigned long safe_borrow_hi(unsigned long a[], int ind, 
  144.                                            int maxind, int p)
  145. {
  146.   if (ind > maxind)
  147.     return 0;
  148.   else if (ind == maxind)
  149.     return(a[ind] >> p);
  150.   else
  151.     return (a[ind] >> p) | (a[ind+1] << (B_SHIFT - p));
  152. }
  153.  
  154.  
  155. static inline unsigned long safe_borrow_lo(unsigned long a[], int ind, 
  156.                                       int minind, int p)
  157. {
  158.   if (ind < minind)
  159.     return 0;
  160.   else if (ind == minind)
  161.     return (a[ind] << (B_SHIFT - 1 - p));
  162.   else
  163.     return (a[ind] << (B_SHIFT - 1 - p)) | (a[ind-1] >> (p + 1));
  164. }
  165.  
  166. // copy bits from a word boundary
  167.  
  168. static inline void bit_copy(unsigned long* ss, unsigned long* ds, int nbits)
  169. {
  170.   if (ss != ds)
  171.   {
  172.     int n = (unsigned)(nbits) / B_SHIFT;
  173.     if (n > 0) bcopy((void*)ss, (void*)ds, n * sizeof(long));
  174.     unsigned long m = ONES << (nbits & (B_SHIFT - 1));
  175.     ds[n] = (ss[n] & ~m) | (ds[n] & m);
  176.   }
  177. }
  178.  
  179. // clear bits from a word boundary
  180.  
  181. static inline void bit_clear(unsigned long* ds, int nbits)
  182. {
  183.   int n = (unsigned)(nbits) / B_SHIFT;
  184.   if (n > 0) bzero((void*)ds, n * sizeof(long));
  185.   ds[n] &= ONES << (nbits & (B_SHIFT - 1));
  186. }
  187.  
  188.  
  189. // allocate a new rep
  190.  
  191. static _BitStringrep*  new_BitStringrep(unsigned long l)
  192. {
  193.   int siz = word_length(l);
  194.   if (siz < MIN_BITSTRING_SIZE)
  195.     siz = MIN_BITSTRING_SIZE;
  196.   else if (siz >= MAX_BITSTRING_SIZE)
  197.     (*BitString_error_handler)("Requested length out of range");
  198.  
  199.   unsigned allocsiz = sizeof(_BitStringrep) + (siz - 1) * sizeof(long);
  200.  
  201.   _BitStringrep* z = (_BitStringrep *) (malloc(allocsiz));
  202.   if (z == 0)
  203.     (*BitString_error_handler)("Out of memory.");
  204.  
  205.   z->len = l;
  206.   z->sz  = siz;
  207.   z->ref = 1;
  208.   return z;
  209. }
  210.  
  211. // expand a rep via realloc
  212.  
  213. static _BitStringrep*  expand_BitStringrep(_BitStringrep* p, unsigned long l)
  214. {
  215.   int siz = word_length(l);
  216.   if (siz < MIN_BITSTRING_SIZE)   
  217.     siz = MIN_BITSTRING_SIZE;
  218.   else if (siz >= MAX_BITSTRING_SIZE)
  219.     (*BitString_error_handler)("Requested length out of range");
  220.  
  221.   unsigned allocsiz = sizeof(_BitStringrep) + (siz - 1) * sizeof(long);
  222.  
  223. #ifdef SHOULD_FREE_TO_REALLOC
  224.   free((void*)p);
  225. #endif
  226.  
  227.   _BitStringrep* z = (_BitStringrep *) (realloc((void*)p, allocsiz));
  228.   if (z == 0)
  229.     (*BitString_error_handler)("Out of memory.");
  230.   z->len = l;
  231.   z->sz  = siz;
  232.   z->ref = 1;
  233.   return z;
  234. }
  235.  
  236.  
  237. // copy ss from starts to lengths-1 into ds starting at startd
  238. // this will work even if ss & ds are the same 
  239. // The g++ optimizer does very good things with the messy shift expressions!
  240.  
  241. static void bit_transfer(unsigned long* ss, int starts, int lengths,
  242.                          unsigned long* ds, int startd)
  243. {
  244.   int ends = lengths - 1;
  245.   if (starts > ends)
  246.     return;
  247.  
  248.   int sind = word_index(starts);
  249.   int spos = bit_position(starts);
  250.   int dind = word_index(startd);
  251.   int dpos = bit_position(startd);
  252.  
  253.   if (spos == 0 && dpos == 0)
  254.   {
  255.     bit_copy(&ss[sind], &ds[dind], ends - starts + 1);
  256.     return;
  257.   }
  258.  
  259.   int endsind = word_index(ends);
  260.   int endspos = bit_position(ends);
  261.   int endd = startd + (ends - starts);
  262.   int enddind = word_index(endd);
  263.   int enddpos = bit_position(endd);
  264.  
  265.   if (dind == enddind)
  266.   {
  267.     if (sind == endsind)
  268.       ds[dind] = (ds[dind] & ((ONES >> (B_SHIFT - dpos)) | 
  269.                               (ONES << (enddpos + 1)))) | 
  270.         (((ss[sind] >> spos) << dpos) & 
  271.          ~((ONES >> (B_SHIFT - dpos)) | (ONES << (enddpos + 1))));
  272.     else
  273.       ds[dind] = (ds[dind] & ((ONES >> (B_SHIFT - dpos)) | 
  274.                               (ONES << (enddpos + 1)))) | 
  275.         ((((ss[sind] >> spos) | (ss[sind+1] << (B_SHIFT - spos))) << dpos) & 
  276.          ~((ONES >> (B_SHIFT - dpos)) | (ONES << (enddpos + 1))));
  277.     return;
  278.   }
  279.   else if (sind == endsind)
  280.   {
  281.     unsigned long saveend = (ds[enddind] & (ONES << (enddpos + 1))) | 
  282.         (((ss[sind] << (B_SHIFT - 1 - endspos)) >> 
  283.           (B_SHIFT - 1 - enddpos)) & ~(ONES << (enddpos + 1)));
  284.     ds[dind] = (ds[dind] & (ONES >> (B_SHIFT - dpos))) |
  285.         (((ss[sind] >> spos) << dpos) & ~(ONES >> (B_SHIFT - dpos)));
  286.     ds[enddind] = saveend;
  287.     return;
  288.   }
  289.  
  290.   unsigned long saveend = (ds[enddind] & (ONES << (enddpos + 1))) | 
  291.     ((((ss[endsind] << (B_SHIFT - 1 - endspos)) |
  292.        (ss[endsind-1] >> (endspos + 1))) >> 
  293.       (B_SHIFT - 1 - enddpos)) & ~(ONES << (enddpos + 1)));
  294.   unsigned long savestart = (ds[dind] & (ONES >> (B_SHIFT - dpos))) |
  295.     ((((ss[sind] >> spos) | (ss[sind+1] << (B_SHIFT - spos))) << dpos) 
  296.      & ~(ONES >> (B_SHIFT - dpos)));
  297.  
  298.  
  299.   if (ds != ss || startd < starts)
  300.   {
  301.     int pos = spos - dpos;
  302.     if (pos < 0)
  303.       pos += B_SHIFT;
  304.     else
  305.       ++sind;
  306.     
  307.     for (;;)                    // lag by one in case of overlaps
  308.     {
  309.       if (dind == enddind - 1)
  310.       {
  311.         ds[dind] = savestart;
  312.         ds[enddind] = saveend;
  313.         return;
  314.       }
  315.       else
  316.       {
  317.         unsigned long tmp = borrow_hi(ss, sind++, endsind, pos);
  318.         ds[dind++] = savestart;
  319.         savestart = tmp;
  320.       }
  321.     }
  322.   }
  323.   else
  324.   {
  325.     int pos = endspos - enddpos;
  326.     if (pos <= 0)
  327.     {
  328.       pos += B_SHIFT - 1;
  329.       --endsind;
  330.     }
  331.     for (;;)
  332.     {
  333.       if (enddind == dind + 1)
  334.       {
  335.         ds[enddind] = saveend;
  336.         ds[dind] = savestart;
  337.         return;
  338.       }
  339.       else
  340.       {
  341.         unsigned long tmp = borrow_lo(ss, endsind--, sind, pos);
  342.         ds[enddind--] = saveend;
  343.         saveend = tmp;
  344.       }
  345.     }
  346.   }
  347. }
  348.   
  349.  
  350. // set up or expand a rep 
  351.  
  352. void BitString::setlength(int newlen, int prefill = 0)
  353. {
  354.   check_last(rep);
  355.   unsigned long oldlen = rep->len;
  356.  
  357.   if (rep->ref != 1)
  358.   {
  359.     if (rep->ref > 0) rep->ref--;
  360.     _BitStringrep* newrep = new_BitStringrep(newlen);
  361.     bit_copy(rep->s, newrep->s, oldlen);
  362.     rep = newrep;
  363.   }
  364.   else if (newlen >= rep->sz * B_SHIFT)
  365.     rep = expand_BitStringrep(rep, newlen);
  366.   else
  367.     rep->len = newlen;
  368.  
  369.   if (prefill && newlen > oldlen)
  370.   {
  371.     int ol = word_length(oldlen);
  372.     int nl = word_length(newlen);
  373.     bzero((void*)&(rep->s[ol]), (nl - ol) * sizeof(long));
  374.     check_last(rep);
  375.   }
  376. }
  377.  
  378.  
  379. // copy one rep to another; expand & dereference as necessary
  380.  
  381. void BitString::copy(unsigned long* news, int startpos, int endp)
  382. {
  383.   int newlen = endp - startpos;
  384.   if (newlen <= 0)
  385.   {
  386.     if (rep->ref > 0 && --rep->ref == 0)
  387.       delete rep;
  388.     rep = &_nil_BitStringrep;
  389.     return;
  390.   }
  391.  
  392.   if (rep->ref != 1)
  393.   {
  394.     if (rep->ref > 0) rep->ref--;
  395.     rep = new_BitStringrep(newlen);
  396.   }
  397.   else if (newlen >= rep->sz * B_SHIFT)
  398.     rep = expand_BitStringrep(rep, newlen);
  399.  
  400.   bit_transfer(news, startpos, endp, rep->s, 0);
  401.   rep->len = newlen;
  402.   check_last(rep);
  403. }
  404.  
  405. int operator == (BitString& x, BitString& y)
  406. {
  407.   return x.rep->len == y.rep->len && 
  408.     bcmp((void*)x.rep->s, (void*)y.rep->s, 
  409.          word_length(x.rep->len) * sizeof(long)) == 0;
  410. }
  411.  
  412. int operator <= (BitString& x, BitString& y)
  413. {
  414.   unsigned long xl = x.rep->len;
  415.   unsigned long yl = y.rep->len;
  416.   if (xl > yl)
  417.     return 0;
  418.  
  419.   unsigned long* xs = x.rep->s;
  420.   unsigned long* ys = y.rep->s;
  421.   unsigned long* topx = &(xs[word_length(xl)]);
  422.  
  423.   while (xs < topx)
  424.   {
  425.     unsigned long a = *xs++;
  426.     unsigned long b = *ys++;
  427.     if ((a | b) != b)
  428.       return 0;
  429.   }
  430.   return 1;
  431. }
  432.  
  433. int operator < (BitString& x, BitString& y)
  434. {
  435.   unsigned long xl = x.rep->len;
  436.   unsigned long yl = y.rep->len;
  437.   if (xl >= yl)
  438.     return 0;
  439.  
  440.   unsigned long* xs = x.rep->s;
  441.   unsigned long* ys = y.rep->s;
  442.   unsigned long* topx = &(xs[word_length(xl)]);
  443.   unsigned long* topy = &(xs[word_length(yl)]);
  444.   int one_diff = 0;
  445.   while (xs < topx)
  446.   {
  447.     unsigned long a = *xs++;
  448.     unsigned long b = *ys++;
  449.     unsigned long c = a | b;
  450.     if (c != b)
  451.       return 0;
  452.     else if (c != a)
  453.       one_diff = 1;
  454.   }
  455.   if (one_diff)
  456.     return 1;
  457.   else
  458.   {
  459.     while (ys < topy)
  460.       if (*ys++ != 0)
  461.         return 1;
  462.     return 0;
  463.   }
  464. }
  465.  
  466. int lcompare(BitString& x, BitString& y)
  467. {
  468.   unsigned long xl = x.rep->len;
  469.   unsigned long yl = y.rep->len;
  470.  
  471.   unsigned long* xs = x.rep->s;
  472.   unsigned long* topx = &(xs[word_length(xl)]);
  473.   unsigned long* ys = y.rep->s;
  474.   unsigned long* topy = &(ys[word_length(yl)]);
  475.  
  476.   while (xs < topx && ys < topy)
  477.   {
  478.     unsigned long a = *xs++;
  479.     unsigned long b = *ys++;
  480.     if (a != b)
  481.     {
  482.       unsigned long mask = 1;
  483.       for (;;)
  484.       {
  485.         unsigned long abit = (a & mask) != 0;
  486.         unsigned long bbit = (b & mask) != 0;
  487.         int diff = abit - bbit;
  488.         if (diff != 0)
  489.           return diff;
  490.         else
  491.           mask <<= 1;
  492.       }
  493.     }
  494.   }
  495.   return xl - yl;
  496. }
  497.  
  498. int BitString::count(int b = 1)
  499. {
  500.   check_last(rep);
  501.   int xwds = word_length(rep->len);
  502.   int xlast = bit_position(rep->len);
  503.   int l = 0;
  504.   unsigned long* s = rep->s;
  505.   unsigned long* tops = &(s[xwds - 1]);
  506.   unsigned long a;
  507.   int i;
  508.   if (b != 0)
  509.   {
  510.     while (s < tops)
  511.     {
  512.       a = *s++;
  513.       for (i = 0; i < B_SHIFT && a != 0; ++i)
  514.       {
  515.         if (a & 1)
  516.           ++l;
  517.         a >>= 1;
  518.       }
  519.     }
  520.     a = *s;
  521.     for (i = 0; i < xlast && a != 0; ++i)
  522.     {
  523.       if (a & 1)
  524.         ++l;
  525.       a >>= 1;
  526.     }
  527.   }
  528.   else
  529.   {
  530.     unsigned long maxbit = 1 << (B_SHIFT - 1);
  531.     while (s < tops)
  532.     {
  533.       a = *s++;
  534.       for (i = 0; i < B_SHIFT; ++i)
  535.       {
  536.         if ((a & maxbit) == 0)
  537.           ++l;
  538.         a <<= 1;
  539.       }
  540.     }
  541.     maxbit = 1 << (xlast - 1);
  542.     a = *s;
  543.     for (i = 0; i < xlast; ++i)
  544.     {
  545.       if ((a & maxbit) == 0)
  546.         ++l;
  547.       a <<= 1;
  548.     }
  549.   }
  550.   return l;
  551. }
  552.  
  553.  
  554. BitString BitString:: operator ~()
  555. {
  556.   BitString r;
  557.   r.setlength(rep->len);
  558.   unsigned long* xs = rep->s;
  559.   unsigned long* rs = r.rep->s;
  560.   unsigned long* topr = &(rs[word_length(rep->len)]);
  561.   while (rs < topr) *rs++ = ~(*xs++);
  562.   check_last(r.rep);
  563.   return r;
  564. }
  565.  
  566.  
  567. BitString& BitString::complement()
  568. {
  569.   make_unique();
  570.   unsigned long* rs = rep->s;
  571.   unsigned long* topr = &(rs[word_length(rep->len)]);
  572.   while (rs < topr)
  573.   {
  574.     unsigned long cmp = ~(*rs);
  575.     *rs++ = cmp;
  576.   }
  577.   check_last(rep);
  578.   return *this;
  579. }
  580.  
  581. void and(BitString& x, BitString& y, BitString& r)
  582. {
  583.   int xrsame = x.rep == r.rep;
  584.   int yrsame = y.rep == r.rep;
  585.  
  586.   unsigned long rl = x.rep->len <? y.rep->len;
  587.   r.setlength(rl);
  588.  
  589.   unsigned long* rs = r.rep->s;
  590.   unsigned long* topr = &(rs[word_length(rl)]);
  591.   unsigned long* xs = (xrsame)? rs : x.rep->s;
  592.   unsigned long* ys = (yrsame)? rs : y.rep->s;
  593.  
  594.   while (rs < topr) *rs++ = *xs++ & *ys++;
  595.   check_last(r.rep);
  596. }
  597.  
  598. void or(BitString& x, BitString& y, BitString& r)
  599. {
  600.   unsigned long xl = x.rep->len;
  601.   unsigned long yl = y.rep->len;
  602.   unsigned long rl = xl >? yl;
  603.   int xrsame = x.rep == r.rep;
  604.   int yrsame = y.rep == r.rep;
  605.  
  606.   r.setlength(rl);
  607.  
  608.   unsigned long* rs = r.rep->s;
  609.   unsigned long* xs = (xrsame)? rs : x.rep->s;
  610.   unsigned long* topx = &(xs[word_length(xl)]);
  611.   unsigned long* ys = (yrsame)? rs : y.rep->s;
  612.   unsigned long* topy = &(ys[word_length(yl)]);
  613.  
  614.   if (xl <= yl)
  615.   {
  616.     while (xs < topx) *rs++ = *xs++ | *ys++;
  617.     if (rs != ys) while (ys < topy) *rs++ = *ys++;
  618.   }
  619.   else
  620.   {
  621.     while (ys < topy) *rs++ = *xs++ | *ys++;
  622.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  623.   }
  624.   check_last(r.rep);
  625. }
  626.  
  627.  
  628. void xor(BitString& x, BitString& y, BitString& r)
  629. {
  630.   unsigned long xl = x.rep->len;
  631.   unsigned long yl = y.rep->len;
  632.   unsigned long rl = xl >? yl;
  633.   int xrsame = x.rep == r.rep;
  634.   int yrsame = y.rep == r.rep;
  635.  
  636.   r.setlength(rl);
  637.  
  638.   unsigned long* rs = r.rep->s;
  639.   unsigned long* xs = (xrsame)? rs : x.rep->s;
  640.   unsigned long* topx = &(xs[word_length(xl)]);
  641.   unsigned long* ys = (yrsame)? rs : y.rep->s;
  642.   unsigned long* topy = &(ys[word_length(yl)]);
  643.  
  644.   if (xl <= yl)
  645.   {
  646.     while (xs < topx) *rs++ = *xs++ ^ *ys++;
  647.     if (rs != ys) while (ys < topy) *rs++ = *ys++;
  648.   }
  649.   else
  650.   {
  651.     while (ys < topy) *rs++ = *xs++ ^ *ys++;
  652.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  653.   }
  654.   check_last(r.rep);
  655. }
  656.  
  657.  
  658. void difference(BitString& x, BitString& y, BitString& r)
  659. {
  660.   unsigned long xl = x.rep->len;
  661.   unsigned long yl = y.rep->len;
  662.   int xrsame = x.rep == y.rep;
  663.   int yrsame = y.rep == r.rep;
  664.  
  665.   r.setlength(xl);
  666.  
  667.   unsigned long* rs = r.rep->s;
  668.   unsigned long* xs = (xrsame)? rs : x.rep->s;
  669.   unsigned long* topx = &(xs[word_length(xl)]);
  670.   unsigned long* ys = (yrsame)? rs : y.rep->s;
  671.   unsigned long* topy = &(ys[word_length(yl)]);
  672.  
  673.   if (xl <= yl)
  674.   {
  675.     while (xs < topx) *rs++ = *xs++ & ~(*ys++);
  676.   }
  677.   else
  678.   {
  679.     while (ys < topy) *rs++ = *xs++ & ~(*ys++);
  680.     if (rs != xs) while (xs < topx) *rs++ = *xs++;
  681.   }
  682.   check_last(r.rep);
  683. }
  684.  
  685.  
  686. void concat(BitString& x, BitString& y, BitString& r)
  687. {
  688.   unsigned long xl = x.rep->len;
  689.   unsigned long yl = y.rep->len;
  690.   unsigned long rl = xl + yl;
  691.   int xrsame = x.rep == r.rep;
  692.   int yrsame = y.rep == r.rep;
  693.  
  694.   if (yrsame)
  695.   {
  696.     BitString tmp = y;
  697.     r.setlength(rl);
  698.     bit_copy(x.rep->s, r.rep->s, xl);
  699.     bit_transfer(tmp.rep->s, 0, yl, r.rep->s, xl);
  700.   }
  701.   else
  702.   {
  703.     r.setlength(rl);
  704.     bit_copy(x.rep->s, r.rep->s, xl);
  705.     bit_transfer(y.rep->s, 0, yl, r.rep->s, xl);
  706.   }
  707.   check_last(r.rep);
  708. }
  709.  
  710. void rshift(BitString& x, int s, BitString& r)
  711. {
  712.   if (s == 0)
  713.   {
  714.     r = x;
  715.     return;
  716.   }
  717.  
  718.   int xl = x.rep->len;
  719.   int rl = xl + s;
  720.   if (rl <= 0)
  721.   {
  722.     r.nullify();
  723.     return;
  724.   }
  725.  
  726.   int xrsame = x.rep == r.rep;
  727.   r.setlength(rl);
  728.   unsigned long* xs = (xrsame)? r.rep->s : x.rep->s;
  729.  
  730.   if (s < 0)
  731.     bit_transfer(xs, -s, xl, r.rep->s, 0);
  732.   else
  733.   {
  734.     bit_transfer(xs, 0, xl, r.rep->s, s);
  735.     bit_clear(r.rep->s, s);
  736.   }
  737.   check_last(r.rep);
  738. }
  739.  
  740.  
  741. void BitString::set(int p)
  742. {
  743.   if (p < 0)
  744.   {
  745.     error("Illegal bit index");
  746.     return;
  747.   }
  748.   
  749.   if (p >= rep->len)
  750.     setlength(p + 1, 1);
  751.   else
  752.     make_unique();
  753.  
  754.   rep->s[word_index(p)] |= (1 << (bit_position(p)));
  755. }
  756.  
  757. void BitString::clear(int p)
  758. {
  759.   if (p < 0)
  760.   {
  761.     error("Illegal bit index");
  762.     return;
  763.   }
  764.   
  765.   if (p >= rep->len)
  766.     setlength(p + 1, 1);
  767.   else
  768.     make_unique();
  769.   
  770.   rep->s[word_index(p)] &= ~(1 << (bit_position(p)));
  771. }
  772.  
  773. void BitString::invert(int p)
  774. {
  775.   if (p < 0)
  776.   {
  777.     error("Illegal bit index");
  778.     return;
  779.   }
  780.  
  781.   if (p >= rep->len)
  782.     setlength(p + 1, 1);
  783.   else
  784.     make_unique();
  785.   
  786.   rep->s[word_index(p)] ^= (1 << (bit_position(p)));
  787. }
  788.  
  789. int BitString::test(int p)
  790. {
  791.   if (p < 0 || p >= rep->len)
  792.     return 0;
  793.   else
  794.     return (rep->s[word_index(p)] & (1 << (bit_position(p)))) != 0;
  795. }
  796.  
  797.  
  798. void BitString::set(int from, int to)
  799. {
  800.   if (from < 0 || from > to)
  801.   {
  802.     error("Illegal bit index");
  803.     return;
  804.   }
  805.  
  806.  
  807.   if (to >= rep->len)
  808.     setlength(to+1, 1);
  809.   else
  810.     make_unique();
  811.  
  812.   int ind1 = word_index(from);
  813.   int pos1 = bit_position(from);
  814.   int ind2 = word_index(to);
  815.   int pos2 = bit_position(to);
  816.   unsigned long* s = &(rep->s[ind1]);
  817.   unsigned long m1 = lmask(pos1);
  818.   unsigned long m2 = rmask(pos2);
  819.   if (ind2 == ind1)
  820.     *s |= m1 & m2;
  821.   else
  822.   {
  823.     *s++ |= m1;
  824.     unsigned long* top = &(rep->s[ind2]);
  825.     *top |= m2;
  826.     while (s < top)
  827.       *s++ = ONES;
  828.   }
  829. }
  830.  
  831. void BitString::clear(int from, int to)
  832. {
  833.   if (from < 0 || from > to)
  834.   {
  835.     error("Illegal bit index");
  836.     return;
  837.   }
  838.  
  839.   if (to >= rep->len)
  840.     setlength(to+1, 1);
  841.   else
  842.     make_unique();
  843.  
  844.   int ind1 = word_index(from);
  845.   int pos1 = bit_position(from);
  846.   int ind2 = word_index(to);
  847.   int pos2 = bit_position(to);
  848.   unsigned long* s = &(rep->s[ind1]);
  849.   unsigned long m1 = lmask(pos1);
  850.   unsigned long m2 = rmask(pos2);
  851.   if (ind2 == ind1)
  852.     *s &= ~(m1 & m2);
  853.   else
  854.   {
  855.     *s++ &= ~m1;
  856.     unsigned long* top = &(rep->s[ind2]);
  857.     *top &= ~m2;
  858.     while (s < top)
  859.       *s++ = 0;
  860.   }
  861. }
  862.  
  863. void BitString::invert(int from, int to)
  864. {
  865.   if (from < 0 || from > to)
  866.   {
  867.     error("Illegal bit index");
  868.     return;
  869.   }
  870.  
  871.   if (to >= rep->len)
  872.     setlength(to+1, 1);
  873.   else
  874.     make_unique();
  875.  
  876.   int ind1 = word_index(from);
  877.   int pos1 = bit_position(from);
  878.   int ind2 = word_index(to);
  879.   int pos2 = bit_position(to);
  880.   unsigned long* s = &(rep->s[ind1]);
  881.   unsigned long m1 = lmask(pos1);
  882.   unsigned long m2 = rmask(pos2);
  883.   if (ind2 == ind1)
  884.     *s ^= m1 & m2;
  885.   else
  886.   {
  887.     *s++ ^= m1;
  888.     unsigned long* top = &(rep->s[ind2]);
  889.     *top ^= m2;
  890.     while (s < top)
  891.     {
  892.       unsigned long cmp = ~(*s);
  893.       *s++ = cmp;
  894.     }
  895.   }
  896. }
  897.  
  898.  
  899. int BitString::test(int from, int to)
  900. {
  901.   if (from < 0 || from > to || from >= rep->len)
  902.     return 0;
  903.  
  904.   int ind1 = word_index(from);
  905.   int pos1 = bit_position(from);
  906.   int ind2 = word_index(to);
  907.   int pos2 = bit_position(to);
  908.  
  909.   if (to >= rep->len)
  910.   {
  911.     ind2 = word_index(rep->len - 1);
  912.     pos2 = bit_position(rep->len - 1);
  913.   }
  914.  
  915.   unsigned long* s = &(rep->s[ind1]);
  916.   unsigned long m1 = lmask(pos1);
  917.   unsigned long m2 = rmask(pos2);
  918.  
  919.   if (ind2 == ind1)
  920.     return (*s & m1 & m2) != 0;
  921.   else
  922.   {
  923.     if (*s++ & m1)
  924.       return 1;
  925.     unsigned long* top = &(rep->s[ind2]);
  926.     if (*top & m2)
  927.       return 1;
  928.     while (s < top)
  929.       if (*s++ != 0) 
  930.         return 1;
  931.     return 0;
  932.   }
  933. }
  934.  
  935. int BitString::next(int p, int b = 1)
  936. {
  937.   if (++p >= rep->len)
  938.     return -1;
  939.  
  940.   int ind = word_index(p);
  941.   int pos = bit_position(p);
  942.   int l = word_length(rep->len);
  943.  
  944.   int j = ind;
  945.   unsigned long* s = rep->s;
  946.   unsigned long a = s[j] >> pos;
  947.   int i = pos;
  948.  
  949.   if (b != 0)
  950.   {
  951.     for (; i < B_SHIFT && a != 0; ++i)
  952.     {
  953.       if (a & 1)
  954.         return j * B_SHIFT + i;
  955.       a >>= 1;
  956.     }
  957.     for (++j; j < l; ++j)
  958.     {
  959.       a = s[j];
  960.       for (i = 0; i < B_SHIFT && a != 0; ++i)
  961.       {
  962.         if (a & 1)
  963.           return j * B_SHIFT + i;
  964.         a >>= 1;
  965.       }
  966.     }
  967.     return -1;
  968.   }
  969.   else
  970.   {
  971.     int last = bit_position(rep->len);
  972.     if (j == l - 1)
  973.     {
  974.       for (; i < last; ++i)
  975.       {
  976.         if ((a & 1) == 0)
  977.           return j * B_SHIFT + i;
  978.         a >>= 1;
  979.       }
  980.       return -1;
  981.     }
  982.  
  983.     for (; i < B_SHIFT; ++i)
  984.     {
  985.       if ((a & 1) == 0)
  986.         return j * B_SHIFT + i;
  987.       a >>= 1;
  988.     }
  989.     for (++j; j < l - 1; ++j)
  990.     {
  991.       a = s[j];
  992.       if (a != ONES)
  993.       {
  994.         for (i = 0; i < B_SHIFT; ++i)
  995.         {
  996.           if ((a & 1) == 0)
  997.             return j * B_SHIFT + i;
  998.           a >>= 1;
  999.         }
  1000.       }
  1001.     }
  1002.     a = s[j];
  1003.     for (i = 0; i < last; ++i)
  1004.     {
  1005.       if ((a & 1) == 0)
  1006.         return j * B_SHIFT + i;
  1007.       a >>= 1;
  1008.     }
  1009.     return -1;
  1010.   }
  1011. }
  1012.  
  1013. int BitString::previous(int p, int b = 1)
  1014. {
  1015.   if (--p < 0)
  1016.     return -1;
  1017.  
  1018.   int ind = word_index(p);
  1019.   int pos = bit_position(p);
  1020.  
  1021.   unsigned long* s = rep->s;
  1022.   int l = word_length(rep->len);
  1023.  
  1024.   if (p >= rep->len)
  1025.   {
  1026.     ind = word_index(rep->len - 1);
  1027.     pos = bit_position(rep->len - 1);
  1028.   }
  1029.  
  1030.   int j = ind;
  1031.   unsigned long a = s[j];
  1032.  
  1033.   int i = pos;
  1034.   unsigned long maxbit = 1 << pos;
  1035.  
  1036.   if (b != 0)
  1037.   {
  1038.     for (; i >= 0 && a != 0; --i)
  1039.     {
  1040.       if (a & maxbit)
  1041.         return j * B_SHIFT + i;
  1042.       a <<= 1;
  1043.     }
  1044.     maxbit = 1 << (B_SHIFT - 1);
  1045.     for (--j; j >= 0; --j)
  1046.     {
  1047.       a = s[j];
  1048.       for (i = B_SHIFT - 1; i >= 0 && a != 0; --i)
  1049.       {
  1050.         if (a & maxbit)
  1051.           return j * B_SHIFT + i;
  1052.         a <<= 1;
  1053.       }
  1054.     }
  1055.     return -1;
  1056.   }
  1057.   else
  1058.   {
  1059.     if (a != ONES)
  1060.     {
  1061.       for (; i >= 0; --i)
  1062.       {
  1063.         if ((a & maxbit) == 0)
  1064.           return j * B_SHIFT + i;
  1065.         a <<= 1;
  1066.       }
  1067.     }
  1068.     maxbit = 1 << (B_SHIFT - 1);
  1069.     for (--j; j >= 0; --j)
  1070.     {
  1071.       a = s[j];
  1072.       if (a != ONES)
  1073.       {
  1074.         for (i = B_SHIFT - 1; i >= 0; --i)
  1075.         {
  1076.           if ((a & maxbit) == 0)
  1077.             return j * B_SHIFT + i;
  1078.           a <<= 1;
  1079.         }
  1080.       }
  1081.     }
  1082.     return -1;
  1083.   }
  1084. }
  1085.  
  1086.  
  1087. int BitString::search(int startx, int lengthx, 
  1088.                       unsigned long* ys, int starty, int lengthy)
  1089. {
  1090.   unsigned long* xs = rep->s;
  1091.   int ylen = lengthy - starty;
  1092.   int righty = lengthy - 1;
  1093.   int leftx, rightx;
  1094.   int rev = startx < 0;
  1095.   if (rev)
  1096.   {
  1097.     leftx = 0;
  1098.     rightx = lengthx + startx;
  1099.     startx = rightx - ylen + 1;
  1100.   }
  1101.   else
  1102.   {
  1103.     leftx = startx;
  1104.     rightx = lengthx - 1;
  1105.   }
  1106.  
  1107.   if (starty < 0 || righty < 0 || startx < 0 || startx >= lengthx)
  1108.     return -1;
  1109.   
  1110.   int xind = word_index(startx);
  1111.   int xpos = bit_position(startx);
  1112.   int yind = word_index(starty);
  1113.   int ypos = bit_position(starty);
  1114.  
  1115.   int rightxind = word_index(rightx);
  1116.   int leftxind = word_index(leftx);
  1117.   unsigned long x = borrow_hi(xs, xind, rightxind, xpos);
  1118.   unsigned long nextx;
  1119.   if (rev)
  1120.     nextx = xs[xind] << (B_SHIFT - xpos);
  1121.   else
  1122.     nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
  1123.   
  1124.   int rightyind = word_index(righty);
  1125.   int rightypos = bit_position(righty);
  1126.   unsigned long y = borrow_hi(ys, yind, rightyind, ypos);
  1127.   unsigned long ymask;
  1128.   if (yind == rightyind)
  1129.     ymask = rmask(rightypos);
  1130.   else if (yind+1 == rightyind)
  1131.     ymask = rmask(ypos + rightypos + 1);
  1132.   else
  1133.     ymask = ONES;
  1134.   
  1135.   int p = startx;
  1136.   for (;;)
  1137.   {
  1138.     if ((x & ymask) == y)
  1139.     {
  1140.       int xi = xind;
  1141.       int yi = yind;
  1142.       for (;;)
  1143.       {
  1144.         if (++yi > rightyind || ++xi > rightxind)
  1145.           return p;
  1146.         unsigned long tx = borrow_hi(xs, xi, rightxind, xpos);
  1147.         unsigned long ty = borrow_hi(ys, yi, rightyind, ypos);
  1148.          if (yi == rightyind)
  1149.           tx &= rmask(rightypos);
  1150.         else if (yi+1 == rightyind)
  1151.           tx &= rmask(ypos + rightypos + 1);
  1152.         if (tx != ty)
  1153.           break;
  1154.       }
  1155.     }
  1156.     if (rev)
  1157.     {
  1158.       if (--p < leftx)
  1159.         return -1;
  1160.       if (--xpos < 0)
  1161.       {
  1162.         xpos = B_SHIFT - 1;
  1163.         x = xs[--xind];
  1164.         nextx = (xind <= leftxind) ? 0 : xs[xind-1];
  1165.       }
  1166.       else
  1167.       {
  1168.         x <<= 1;
  1169.         if (nextx & MAXBIT)
  1170.           x |= 1;
  1171.         nextx <<= 1;
  1172.       }
  1173.     }
  1174.     else
  1175.     {
  1176.       if (++p > rightx)
  1177.         return -1;
  1178.       if (++xpos == B_SHIFT)
  1179.       {
  1180.         xpos = 0;
  1181.         x = xs[++xind];
  1182.         nextx = (xind >= rightxind) ? 0 : xs[xind+1];
  1183.       }
  1184.       else
  1185.       {
  1186.         x >>= 1;
  1187.         if (nextx & 1)
  1188.           x |= MAXBIT;
  1189.         nextx >>= 1;
  1190.       }
  1191.     }
  1192.   }
  1193. }
  1194.  
  1195.  
  1196. int BitPattern::search(unsigned long* xs, int startx, int lengthx)
  1197. {
  1198.   unsigned long* ys = pattern.rep->s;
  1199.   unsigned long* ms = mask.rep->s;
  1200.   int righty = pattern.rep->len - 1;
  1201.   int rightm = mask.rep->len - 1;
  1202.  
  1203.   int leftx, rightx;
  1204.   int rev = startx < 0;
  1205.   if (rev)
  1206.   {
  1207.     leftx = 0;
  1208.     rightx = lengthx + startx;
  1209.     startx = rightx - righty;
  1210.   }
  1211.   else
  1212.   {
  1213.     leftx = startx;
  1214.     rightx = lengthx - 1;
  1215.   }
  1216.  
  1217.   if (righty < 0 || startx < 0 || startx >= lengthx)
  1218.     return -1;
  1219.   
  1220.   int xind = word_index(startx);
  1221.   int xpos = bit_position(startx);
  1222.  
  1223.   int rightxind = word_index(rightx);
  1224.   int leftxind = word_index(leftx);
  1225.   int rightmind = word_index(rightm);
  1226.   int rightyind = word_index(righty);
  1227.  
  1228.   unsigned long x = safe_borrow_hi(xs, xind, rightxind, xpos);
  1229.   unsigned long m = safe_borrow_hi(ms, 0, rightmind, 0);
  1230.   unsigned long y = safe_borrow_hi(ys, 0, rightyind, 0) & m;
  1231.  
  1232.   unsigned long nextx;
  1233.   if (rev)
  1234.     nextx = xs[xind] << (B_SHIFT - xpos);
  1235.   else
  1236.     nextx = (xind >= rightxind) ? 0 : (xs[xind+1] >> xpos);
  1237.  
  1238.   int p = startx;
  1239.   for (;;)
  1240.   {
  1241.     if ((x & m) == y)
  1242.     {
  1243.       int xi = xind;
  1244.       int yi = 0;
  1245.       for (;;)
  1246.       {
  1247.         if (++yi > rightyind || ++xi > rightxind)
  1248.           return p;
  1249.         unsigned long tm = safe_borrow_hi(ms, yi, rightmind, 0);
  1250.         unsigned long ty = safe_borrow_hi(ys, yi, rightyind, 0);
  1251.         unsigned long tx = safe_borrow_hi(xs, xi, rightxind, xpos);
  1252.         if ((tx & tm) != (ty & tm))
  1253.           break;
  1254.       }
  1255.     }
  1256.     if (rev)
  1257.     {
  1258.       if (--p < leftx)
  1259.         return -1;
  1260.       if (--xpos < 0)
  1261.       {
  1262.         xpos = B_SHIFT - 1;
  1263.         x = xs[--xind];
  1264.         nextx = (xind <= leftxind) ? 0 : xs[xind-1];
  1265.       }
  1266.       else
  1267.       {
  1268.         x <<= 1;
  1269.         if (nextx & MAXBIT)
  1270.           x |= 1;
  1271.         nextx <<= 1;
  1272.       }
  1273.     }
  1274.     else
  1275.     {
  1276.       if (++p > rightx)
  1277.         return -1;
  1278.       if (++xpos == B_SHIFT)
  1279.       {
  1280.         xpos = 0;
  1281.         x = xs[++xind];
  1282.         nextx = (xind >= rightxind) ? 0 : xs[xind+1];
  1283.       }
  1284.       else
  1285.       {
  1286.         x >>= 1;
  1287.         if (nextx & 1)
  1288.           x |= MAXBIT;
  1289.         nextx >>= 1;
  1290.       }
  1291.     }
  1292.   }
  1293. }
  1294.  
  1295. int BitString::match(int startx, int lengthx, int exact, 
  1296.                      unsigned long* ys, int starty, int yl)
  1297. {
  1298.   unsigned long* xs = rep->s;
  1299.   int ylen = yl - starty;
  1300.   int righty = yl - 1;
  1301.  
  1302.   int rightx;
  1303.   int rev = startx < 0;
  1304.   if (rev)
  1305.   {
  1306.     rightx = lengthx + startx;
  1307.     startx = rightx - ylen + 1;
  1308.     if (exact && startx != 0)
  1309.       return 0;
  1310.   }
  1311.   else
  1312.   {
  1313.     rightx = lengthx - 1;
  1314.     if (exact && rightx - startx != righty)
  1315.       return 0;
  1316.   }
  1317.  
  1318.   if (righty < 0 || startx < 0 || startx >= lengthx)
  1319.     return 0;
  1320.   
  1321.   int xi   = word_index(startx);
  1322.   int xpos = bit_position(startx);
  1323.   int yi   = word_index(starty);
  1324.   int ypos = bit_position(starty);
  1325.  
  1326.   int rightxind = word_index(rightx);
  1327.   int rightyind = word_index(righty);
  1328.   int rightypos = bit_position(righty);
  1329.  
  1330.   for (;;)
  1331.   {
  1332.     unsigned long x = borrow_hi(xs, xi, rightxind, xpos);
  1333.     unsigned long y = borrow_hi(ys, yi, rightyind, ypos);
  1334.     if (yi == rightyind)
  1335.       x &= rmask(rightypos);
  1336.     else if (yi+1 == rightyind)
  1337.       x &= rmask(ypos + rightypos + 1);
  1338.     if (x != y)
  1339.       return 0;
  1340.     else if (++yi > rightyind || ++xi > rightxind)
  1341.       return 1;
  1342.   }
  1343. }
  1344.  
  1345. int BitPattern::match(unsigned long* xs, int startx, int lengthx, int exact)
  1346. {
  1347.   unsigned long* ys = pattern.rep->s;
  1348.   int righty = pattern.rep->len - 1;
  1349.   unsigned long* ms = mask.rep->s;
  1350.   int rightm = mask.rep->len - 1;
  1351.  
  1352.   int rightx;
  1353.   int rev = startx < 0;
  1354.   if (rev)
  1355.   {
  1356.     rightx = lengthx + startx;
  1357.     startx = rightx - righty;
  1358.     if (exact && startx != 0)
  1359.       return 0;
  1360.   }
  1361.   else
  1362.   {
  1363.     rightx = lengthx - 1;
  1364.     if (exact && rightx - startx != righty)
  1365.       return 0;
  1366.   }
  1367.  
  1368.   if (righty < 0 || startx < 0 || startx >= lengthx)
  1369.     return 0;
  1370.   
  1371.   int xind = word_index(startx);
  1372.   int xpos = bit_position(startx);
  1373.   int yind = 0;
  1374.  
  1375.   int rightxind = word_index(rightx);
  1376.   int rightyind = word_index(righty);
  1377.   int rightmind = word_index(rightm);
  1378.  
  1379.   for(;;)
  1380.   {
  1381.     unsigned long m = safe_borrow_hi(ms, yind, rightmind, 0);
  1382.     unsigned long x = safe_borrow_hi(xs, xind, rightxind, xpos) & m;
  1383.     unsigned long y = safe_borrow_hi(ys, yind, rightyind, 0) & m;
  1384.     if (x != y)
  1385.       return 0;
  1386.     else if (++yind > rightyind || ++xind > rightxind)
  1387.       return 1;
  1388.   }
  1389. }
  1390.  
  1391. BitSubString::BitSubString(BitString* x, int first, int l)
  1392. {
  1393.   if (first < 0 || l <= 0 || first + l > x->rep->len)
  1394.   {
  1395.     S = &_nil_BitString; pos = len = 0;
  1396.   }
  1397.   else
  1398.   {
  1399.     S = x; pos = first; len = l;
  1400.   }
  1401. }
  1402.  
  1403.  
  1404.  
  1405. void BitSubString::operator = (BitString& y)
  1406. {
  1407.   int ylen = y.rep->len;
  1408.   _BitStringrep* targ = S->rep;
  1409.  
  1410.   if (len == 0 || pos >= targ->len)
  1411.     return;
  1412.  
  1413.   int sl = targ->len - len + ylen;
  1414.  
  1415.   if (targ->ref != 1)
  1416.   {
  1417.     if (targ->ref > 0) targ->ref--;
  1418.     _BitStringrep* oldtarg = targ;
  1419.     targ = new_BitStringrep(sl);
  1420.     bit_transfer(oldtarg->s, 0, pos, targ->s, 0);
  1421.     bit_transfer(y.rep->s, 0, ylen, targ->s, pos);
  1422.     bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + ylen);
  1423.   }
  1424.   else if (y.rep == targ || ylen > len)
  1425.   {
  1426.     _BitStringrep* oldtarg = targ;
  1427.     targ = new_BitStringrep(sl);
  1428.     bit_transfer(oldtarg->s, 0, pos, targ->s, 0);
  1429.     bit_transfer(y.rep->s, 0, ylen, targ->s, pos);
  1430.     bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + ylen);
  1431.     delete oldtarg;
  1432.   }
  1433.   else if (len == ylen)
  1434.     bit_transfer(y.rep->s, 0, len, targ->s, pos);
  1435.   else if (ylen < len)
  1436.   {
  1437.     bit_transfer(y.rep->s, 0, ylen, targ->s, pos);
  1438.     bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + ylen);
  1439.     targ->len = sl;
  1440.   }
  1441.   check_last(targ);
  1442.   S->rep = targ;
  1443. }
  1444.  
  1445. void BitSubString::operator = (BitSubString& y)
  1446. {
  1447.   _BitStringrep* targ = S->rep;
  1448.  
  1449.   if (len == 0 || pos >= targ->len)
  1450.     return;
  1451.  
  1452.   int sl = targ->len - len + y.len;
  1453.  
  1454.   if (targ->ref != 1)
  1455.   {
  1456.     if (targ->ref > 0) targ->ref--;
  1457.     _BitStringrep* oldtarg = targ;
  1458.     targ = new_BitStringrep(sl);
  1459.     bit_copy(oldtarg->s, targ->s, pos);
  1460.     bit_transfer(y.S->rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1461.     bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + y.len);
  1462.   }
  1463.   else if (y.S->rep == targ || y.len > len)
  1464.   {
  1465.     _BitStringrep* oldtarg = targ;
  1466.     targ = new_BitStringrep(sl);
  1467.     bit_copy(oldtarg->s, targ->s, pos);
  1468.     bit_transfer(y.S->rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1469.     bit_transfer(oldtarg->s, pos+len, oldtarg->len, targ->s, pos + y.len);
  1470.     delete oldtarg;
  1471.   }
  1472.   else if (len == y.len)
  1473.     bit_transfer(y.S->rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1474.   else if (y.len < len)
  1475.   {
  1476.     bit_transfer(y.S->rep->s, y.pos, y.pos+y.len, targ->s, pos);
  1477.     bit_transfer(targ->s, pos+len, targ->len, targ->s, pos + y.len);
  1478.     targ->len = sl;
  1479.   }
  1480.   check_last(targ);
  1481.   S->rep = targ;
  1482. }
  1483.  
  1484. BitSubString BitString::at(int first, int len)
  1485. {
  1486.   return BitSubString(this, first, len);
  1487. }
  1488.  
  1489. BitSubString BitString::before(int pos)
  1490. {
  1491.   return BitSubString(this, 0, pos);
  1492. }
  1493.  
  1494. BitSubString BitString::after(int pos)
  1495. {
  1496.   return BitSubString(this, pos + 1, rep->len - (pos + 1));
  1497. }
  1498.  
  1499. BitSubString BitString::at(BitString& y, int startpos = 0)
  1500. {
  1501.   int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1502.   return BitSubString(this, first,  y.rep->len);
  1503. }
  1504.  
  1505. BitSubString BitString::before(BitString& y, int startpos = 0)
  1506. {
  1507.   int last = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1508.   return BitSubString(this, 0, last);
  1509. }
  1510.  
  1511. BitSubString BitString::after(BitString& y, int startpos = 0)
  1512. {
  1513.   int first = search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  1514.   return BitSubString(this, first + y.rep->len, rep->len - (first+y.rep->len));
  1515. }
  1516.  
  1517.  
  1518. BitSubString BitString::at(BitSubString& y, int startpos = 0)
  1519. {
  1520.   int first = search(startpos, rep->len, y.S->rep->s, y.pos, y.len);
  1521.   return BitSubString(this, first, y.len);
  1522. }
  1523.  
  1524. BitSubString BitString::before(BitSubString& y, int startpos = 0)
  1525. {
  1526.   int last = search(startpos, rep->len, y.S->rep->s, y.pos, y.len);
  1527.   return BitSubString(this, 0, last);
  1528. }
  1529.  
  1530. BitSubString BitString::after(BitSubString& y, int startpos = 0)
  1531. {
  1532.   int first = search(startpos, rep->len, y.S->rep->s, y.pos, y.len);
  1533.   return BitSubString(this, first + y.len, rep->len - (first + y.len));
  1534. }
  1535.  
  1536. BitSubString BitString::at(BitPattern& r, int startpos = 0)
  1537. {
  1538.   int first = r.search(rep->s, startpos, rep->len);
  1539.   return BitSubString(this, first, r.pattern.rep->len);
  1540. }
  1541.  
  1542.  
  1543. BitSubString BitString::before(BitPattern& r, int startpos = 0)
  1544. {
  1545.   int first = r.search(rep->s, startpos, rep->len);
  1546.   return BitSubString(this, 0, first);
  1547. }
  1548.  
  1549. BitSubString BitString::after(BitPattern& r, int startpos = 0)
  1550. {
  1551.   int first = r.search(rep->s, startpos, rep->len);
  1552.   int last;
  1553.   if (first < 0)
  1554.     last = -1;
  1555.   else
  1556.     last = first + r.pattern.rep->len;
  1557.   return BitSubString(this, last, rep->len - last);
  1558. }
  1559.  
  1560. BitString common_prefix(BitString& x, BitString& y, int startpos = 0)
  1561. {
  1562.   BitString r;
  1563.   unsigned long xl = x.rep->len;
  1564.   unsigned long yl = y.rep->len;
  1565.  
  1566.   int startx, starty;
  1567.   if (startpos < 0)
  1568.   {
  1569.     startx = xl + startpos;
  1570.     starty = yl + startpos;
  1571.   }
  1572.   else
  1573.     startx = starty = startpos;
  1574.  
  1575.   if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
  1576.     return r;
  1577.  
  1578.   unsigned long* xs = &(x.rep->s[word_index(startx)]);
  1579.   unsigned long a = *xs++;
  1580.   int xp = startx;
  1581.  
  1582.   unsigned long* ys = &(y.rep->s[word_index(starty)]);
  1583.   unsigned long b = *ys++;
  1584.   int yp = starty;
  1585.  
  1586.   for(; xp < xl && yp < yl; ++xp, ++yp)
  1587.   {
  1588.     unsigned long xbit = 1 << (bit_position(xp));
  1589.     unsigned long ybit = 1 << (bit_position(yp));
  1590.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1591.       break;
  1592.     if (xbit == MAXBIT)
  1593.       a = *xs++;
  1594.     if (ybit == MAXBIT)
  1595.       b = *ys++;
  1596.   }
  1597.   if (xp > startx)
  1598.     r.copy(x.rep->s, startx, xp);
  1599.   return r;
  1600. }
  1601.  
  1602.  
  1603. BitString common_suffix(BitString& x, BitString& y, int startpos = -1)
  1604. {
  1605.   BitString r;
  1606.   unsigned long xl = x.rep->len;
  1607.   unsigned long yl = y.rep->len;
  1608.  
  1609.   int startx, starty;
  1610.   if (startpos < 0)
  1611.   {
  1612.     startx = xl + startpos;
  1613.     starty = yl + startpos;
  1614.   }
  1615.   else
  1616.     startx = starty = startpos;
  1617.  
  1618.   if (startx < 0 || startx >= xl || starty < 0 || starty >= yl)
  1619.     return r;
  1620.  
  1621.   unsigned long* xs = &(x.rep->s[word_index(startx)]);
  1622.   unsigned long a = *xs--;
  1623.   int xp = startx;
  1624.  
  1625.   unsigned long* ys = &(y.rep->s[word_index(starty)]);
  1626.   unsigned long b = *ys--;
  1627.   int yp = starty;
  1628.  
  1629.   for(; xp >= 0 && yp >= 0; --xp, --yp)
  1630.   {
  1631.     unsigned long xbit = 1 << (bit_position(xp));
  1632.     unsigned long ybit = 1 << (bit_position(yp));
  1633.     if (((a & xbit) == 0) != ((b & ybit) == 0))
  1634.       break;
  1635.     if (xbit == 1)
  1636.       a = *xs--;
  1637.     if (ybit == 1)
  1638.       b = *ys--;
  1639.   }
  1640.   if (xp < startx)
  1641.     r.copy(x.rep->s, xp+1, startx+1);
  1642.   return r;
  1643. }
  1644.  
  1645. BitString reverse(BitString& x)
  1646. {
  1647.   BitString y = x;
  1648.   y.make_unique();
  1649.   unsigned long yl = y.rep->len;
  1650.   if (yl > 0)
  1651.   {
  1652.     int l = 0;
  1653.     int r = yl - 1;
  1654.     unsigned long* ls = y.rep->s;
  1655.     unsigned long* rs = &(ls[word_length(yl) - 1]);
  1656.     unsigned long lm = 1 << (bit_position(l));
  1657.     unsigned long rm = 1 << (bit_position(r));
  1658.     for (; l < r; ++l, --r)
  1659.     {
  1660.       if (((*ls & lm) != 0) != ((*rs & rm) != 0))
  1661.       {
  1662.         *rs ^= rm;
  1663.         *ls ^= lm;
  1664.       }
  1665.       if (lm == MAXBIT)
  1666.       {
  1667.         ++ls;
  1668.         lm = 1;
  1669.       }
  1670.       else
  1671.         lm <<= 1;
  1672.       if (rm == 1)
  1673.       {
  1674.         --rs;
  1675.         rm = MAXBIT;
  1676.       }
  1677.       else
  1678.         rm = (rm >> 1) & ~(MAXBIT);
  1679.     }
  1680.   }
  1681.   return y;
  1682. }
  1683.  
  1684. extern Obstack _libgxx_io_ob;
  1685. extern char* _libgxx_io_oblast;
  1686.  
  1687.  
  1688. const char* BitStringtoa(BitString& x, char f = '0', char t = '1')
  1689. {
  1690.   if (_libgxx_io_oblast)  _libgxx_io_ob.free(_libgxx_io_oblast);
  1691.   unsigned long xl = x.rep->len;
  1692.   unsigned long* s = x.rep->s;
  1693.   unsigned long a;
  1694.  
  1695.   for (unsigned long i = 0; i < xl; ++i)
  1696.   {
  1697.     if (i % B_SHIFT == 0)
  1698.       a = *s++;
  1699.     _libgxx_io_ob.grow((a & 1)? t : f);
  1700.     a >>= 1;
  1701.   }
  1702.  
  1703.   return _libgxx_io_oblast = (char*)(_libgxx_io_ob.finish(0));
  1704. }
  1705.  
  1706. BitString atoBitString(const char* s, char f = '0', char t = '1')
  1707. {
  1708.   BitString r;
  1709.   int sl = strlen(s);
  1710.   if (sl != 0)
  1711.   {
  1712.     unsigned long rl = 0;
  1713.     r.setlength(sl);
  1714.     unsigned long* rs = r.rep->s;
  1715.     unsigned long a = 0;
  1716.     unsigned long m = 1;
  1717.     unsigned long i = 0;
  1718.     for(;;)
  1719.     {
  1720.       char ch = s[i];
  1721.       if (ch != t && ch != f)
  1722.       {
  1723.         *rs = a;
  1724.         break;
  1725.       }
  1726.       ++rl;
  1727.       if (ch == t)
  1728.         a |= m;
  1729.       if (++i == sl)
  1730.       {
  1731.         *rs = a;
  1732.         break;
  1733.       }
  1734.       else if (i % B_SHIFT == 0)
  1735.       {
  1736.         *rs++ = a;
  1737.         a = 0;
  1738.         m = 1;
  1739.       }
  1740.       else
  1741.         m <<= 1;
  1742.     }
  1743.     r.setlength(rl);
  1744.   }
  1745.   return r;
  1746. }
  1747.  
  1748. ostream& operator << (ostream& s, BitString& x)
  1749. {
  1750.   return s << BitStringtoa(x);
  1751. }
  1752.  
  1753.  
  1754. const char* BitPatterntoa(BitPattern& p, char f = '0',char t = '1',char x='X')
  1755. {
  1756.   if (_libgxx_io_oblast)  _libgxx_io_ob.free(_libgxx_io_oblast);
  1757.   unsigned long pl = p.pattern.rep->len;
  1758.   unsigned long ml = p.mask.rep->len;
  1759.   unsigned long l = pl <? ml;
  1760.   unsigned long* ps = p.pattern.rep->s;
  1761.   unsigned long* ms = p.mask.rep->s;
  1762.   unsigned long a;
  1763.   unsigned long m;
  1764.  
  1765.   for (unsigned long i = 0; i < l; ++i)
  1766.   {
  1767.     if (i % B_SHIFT == 0)
  1768.     {
  1769.       a = *ps++;
  1770.       m = *ms++;
  1771.     }
  1772.     if (m & 1)
  1773.       _libgxx_io_ob.grow((a & 1)? t : f);
  1774.     else
  1775.       _libgxx_io_ob.grow(x);
  1776.     a >>= 1;
  1777.     m >>= 1;
  1778.   }
  1779.  
  1780.   return _libgxx_io_oblast = (char*)(_libgxx_io_ob.finish(0));
  1781. }
  1782.  
  1783. BitPattern atoBitPattern(const char* s,char f = '0',char t = '1',char x = 'X')
  1784. {
  1785.   BitPattern r;
  1786.   int sl = strlen(s);
  1787.   if (sl != 0)
  1788.   {
  1789.     unsigned long rl = 0;
  1790.     r.pattern.setlength(sl);
  1791.     r.mask.setlength(sl);
  1792.     unsigned long* rs = r.pattern.rep->s;
  1793.     unsigned long* ms = r.mask.rep->s;
  1794.     unsigned long a = 0;
  1795.     unsigned long b = 0;
  1796.     unsigned long m = 1;
  1797.     unsigned long i = 0;
  1798.     for(;;)
  1799.     {
  1800.       char ch = s[i];
  1801.       if (ch != t && ch != f && ch != x)
  1802.       {
  1803.         *rs = a;
  1804.         *ms = b;
  1805.         break;
  1806.       }
  1807.       ++rl;
  1808.       if (ch == t)
  1809.       {
  1810.         a |= m;
  1811.         b |= m;
  1812.       }
  1813.       else if (ch == f)
  1814.       {
  1815.         b |= m;
  1816.       }
  1817.       if (++i == sl)
  1818.       {
  1819.         *rs = a;
  1820.         *ms = b;
  1821.         break;
  1822.       }
  1823.       else if (i % B_SHIFT == 0)
  1824.       {
  1825.         *rs++ = a;
  1826.         *ms++ = b;
  1827.         a = 0;
  1828.         b = 0;
  1829.         m = 1;
  1830.       }
  1831.       else
  1832.         m <<= 1;
  1833.     }
  1834.     r.pattern.setlength(rl);
  1835.     r.mask.setlength(rl);
  1836.   }
  1837.   return r;
  1838. }
  1839.  
  1840. ostream& operator << (ostream& s, BitPattern& x)
  1841. {
  1842.   return s << BitPatterntoa(x);
  1843. }
  1844.