home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / libg++-2.7.1-bin.lha / lib / g++-include / BitString.h < prev    next >
C/C++ Source or Header  |  1996-10-12  |  20KB  |  764 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17. */
  18.  
  19. #ifndef _BitString_h
  20. #ifdef __GNUG__
  21. #pragma interface
  22. #endif
  23.  
  24. #define _BitString_h 1
  25.  
  26. #include <stream.h>
  27. #include <limits.h>
  28.  
  29. #undef OK
  30.  
  31. #include <bitprims.h>
  32. #define BITSTRBITS  _BS_BITS_PER_WORD
  33.  
  34. struct BitStrRep
  35. {
  36.   unsigned int    len;          // length in bits
  37.   unsigned short  sz;           // allocated slots
  38.   _BS_word        s[1];         // bits start here
  39. };
  40.  
  41. extern BitStrRep*  BStr_alloc(BitStrRep*, const _BS_word*, int, int,int);
  42. extern BitStrRep*  BStr_resize(BitStrRep*, int);
  43. extern BitStrRep*  BStr_copy(BitStrRep*, const BitStrRep*);
  44. extern BitStrRep*  cmpl(const BitStrRep*, BitStrRep*);
  45. extern BitStrRep*  and(const BitStrRep*, const BitStrRep*, BitStrRep*);
  46. extern BitStrRep*  or(const BitStrRep*, const BitStrRep*, BitStrRep*);
  47. extern BitStrRep*  xor(const BitStrRep*, const BitStrRep*, BitStrRep*);
  48. extern BitStrRep*  diff(const BitStrRep*, const BitStrRep*, BitStrRep*);
  49. extern BitStrRep*  cat(const BitStrRep*, const BitStrRep*, BitStrRep*);
  50. extern BitStrRep*  cat(const BitStrRep*, unsigned int, BitStrRep*);
  51. extern BitStrRep*  lshift(const BitStrRep*, int, BitStrRep*);
  52.  
  53.  
  54. class BitString;
  55. class BitPattern;
  56.  
  57. class BitStrBit
  58. {
  59. protected:
  60.   BitString&        src;
  61.   unsigned int      pos;
  62.  
  63.  public:
  64.                     BitStrBit(BitString& v, int p);
  65.                     BitStrBit(const BitStrBit& b);
  66.                    ~BitStrBit();
  67.                     operator unsigned int() const;
  68.   int               operator =  (unsigned int b);
  69. };
  70.  
  71. class BitSubString
  72. {
  73.   friend class      BitString;
  74.   friend class      BitPattern;
  75.  
  76. protected:
  77.  
  78.   BitString&        S;
  79.   unsigned int      pos;
  80.   unsigned int      len;
  81.  
  82.                     BitSubString(BitString& x, int p, int l);
  83.                     BitSubString(const BitSubString& x);
  84. public:
  85.                     ~BitSubString();
  86.  
  87.   BitSubString&     operator =  (const BitString&);
  88.   BitSubString&     operator =  (const BitSubString&);
  89.  
  90.   int               length() const;
  91.   int               empty() const;
  92.  
  93.   int               OK() const;
  94. };
  95.  
  96. class BitString
  97. {
  98.   friend class       BitSubString;
  99.   friend class       BitPattern;
  100. protected:
  101.   BitStrRep*         rep;
  102.  
  103.   int                search(int, int, const _BS_word*, int, int) const;
  104.   int                match(int, int, int, const _BS_word*,int,int) const;
  105.   BitSubString       _substr(int first, int l);
  106.  
  107. public:
  108.  
  109. // constructors
  110.                      BitString();
  111.                      BitString(const BitString&);
  112.                      BitString(const BitSubString& y);
  113.  
  114.                     ~BitString();
  115.  
  116.   BitString&         operator =  (unsigned int bit);
  117.   BitString&         operator =  (const BitString& y);
  118.   BitString&         operator =  (const BitSubString& y);
  119.  
  120. // equality & subset tests
  121.  
  122.   friend int         operator == (const BitString&, const BitString&);
  123.   friend int         operator != (const BitString&, const BitString&);
  124.   friend int         operator <  (const BitString&, const BitString&);
  125.   friend int         operator <= (const BitString&, const BitString&);
  126.   friend int         operator >  (const BitString&, const BitString&);
  127.   friend int         operator >= (const BitString&, const BitString&);
  128.  
  129. // procedural versions of operators
  130.  
  131.  
  132.   friend void        and(const BitString&, const BitString&, BitString&);
  133.   friend void        or(const BitString&, const BitString&, BitString&);
  134.   friend void        xor(const BitString&, const BitString&, BitString&);
  135.   friend void        diff(const BitString&, const BitString&, BitString&);
  136.   friend void        cat(const BitString&, const BitString&, BitString&);
  137.   friend void        cat(const BitString&, unsigned int, BitString&);
  138.   friend void        lshift(const BitString&, int, BitString&);
  139.   friend void        rshift(const BitString&, int, BitString&);
  140.  
  141.   friend void        complement(const BitString&, BitString&);
  142.  
  143.   friend int         lcompare(const BitString&, const BitString&); 
  144.  
  145. // assignment-based operators
  146. // (constuctive versions decalred inline below
  147.  
  148.   BitString&         operator |= (const BitString&);
  149.   BitString&         operator &= (const BitString&);
  150.   BitString&         operator -= (const BitString&);
  151.   BitString&         operator ^= (const BitString&);
  152.   BitString&         operator += (const BitString&);
  153.   BitString&         operator += (unsigned int b);
  154.   BitString&         operator <<=(int s);
  155.   BitString&         operator >>=(int s);
  156.  
  157.   void               complement();
  158.  
  159. // individual bit manipulation
  160.  
  161.   void               set(int pos);
  162.   void               set(int from, int to);
  163.   void               set();
  164.  
  165.   void               clear(int pos);
  166.   void               clear(int from, int to);
  167.   void               clear(); 
  168.  
  169.   void               invert(int pos);
  170.   void               invert(int from, int to);
  171.  
  172.   int                test(int pos) const;
  173.   int                test(int from, int to) const;
  174.  
  175.   void               assign(int p, unsigned int bit);
  176.  
  177. // indexing
  178.  
  179.   BitStrBit          operator [] (int pos);
  180.  
  181. // iterators
  182.  
  183.   int                first(unsigned int bit = 1) const;
  184.   int                last(unsigned int b = 1) const;
  185.  
  186.   int                next(int pos, unsigned int b = 1) const;
  187.   int                prev(int pos, unsigned int b = 1) const;
  188.   int                previous(int pos, unsigned int b = 1) const
  189.     { return prev(pos, b); } /* Obsolete synonym */
  190.  
  191. // searching & matching
  192.  
  193.   int                index(unsigned int bit, int startpos = 0) const ;      
  194.   int                index(const BitString&, int startpos = 0) const;
  195.   int                index(const BitSubString&, int startpos = 0) const;
  196.   int                index(const BitPattern&, int startpos = 0) const;
  197.  
  198.   int                contains(const BitString&) const;
  199.   int                contains(const BitSubString&) const;
  200.   int                contains(const BitPattern&) const;
  201.  
  202.   int                contains(const BitString&, int pos) const;
  203.   int                contains(const BitSubString&, int pos) const;
  204.   int                contains(const BitPattern&, int pos) const;
  205.  
  206.   int                matches(const BitString&, int pos = 0) const;
  207.   int                matches(const BitSubString&, int pos = 0) const;
  208.   int                matches(const BitPattern&, int pos = 0) const;
  209.  
  210. // BitSubString extraction
  211.  
  212.   BitSubString       at(int pos, int len);
  213.   BitSubString       at(const BitString&, int startpos = 0); 
  214.   BitSubString       at(const BitSubString&, int startpos = 0); 
  215.   BitSubString       at(const BitPattern&, int startpos = 0); 
  216.  
  217.   BitSubString       before(int pos);
  218.   BitSubString       before(const BitString&, int startpos = 0);
  219.   BitSubString       before(const BitSubString&, int startpos = 0);
  220.   BitSubString       before(const BitPattern&, int startpos = 0);
  221.  
  222.   BitSubString       after(int pos);
  223.   BitSubString       after(const BitString&, int startpos = 0);
  224.   BitSubString       after(const BitSubString&, int startpos = 0);
  225.   BitSubString       after(const BitPattern&, int startpos = 0);
  226.  
  227. // other friends & utilities
  228.  
  229.   friend BitString   common_prefix(const BitString&, const BitString&, 
  230.                                    int pos = 0);
  231.   friend BitString   common_suffix(const BitString&, const BitString&, 
  232.                                    int pos = -1);
  233.   friend BitString   reverse(const BitString&);
  234.  
  235.   void               right_trim(unsigned int bit);
  236.   void               left_trim(unsigned int bit);
  237.  
  238. // status
  239.  
  240.   int                empty() const ;
  241.   int                count(unsigned int bit = 1) const;
  242.   int                length() const;
  243.  
  244. // convertors & IO
  245.  
  246.   friend BitString   atoBitString(const char* s, char f='0', char t='1');
  247.   // BitStringtoa is deprecated; do not use in new programs!
  248.   friend const char* BitStringtoa(const BitString&, char f='0', char t='1');
  249.   void             printon(ostream&, char f='0', char t='1') const;
  250.  
  251.   friend BitString   shorttoBitString(unsigned short);
  252.   friend BitString   longtoBitString(unsigned long);
  253.  
  254.   friend ostream&    operator << (ostream& s, const BitString&);
  255.  
  256. // misc
  257.  
  258.   void      error(const char* msg) const;
  259.  
  260. // indirect friends
  261.  
  262.   friend BitPattern  atoBitPattern(const char* s,
  263.                                   char f='0',char t='1',char x='X');
  264.   friend const char* BitPatterntoa(const BitPattern& p, 
  265.                                   char f='0',char t='1',char x='X');
  266.   int                OK() const;
  267. };
  268.  
  269.  
  270. class BitPattern
  271. {
  272. public:
  273.   BitString          pattern;
  274.   BitString          mask;
  275.  
  276.                      BitPattern();
  277.                      BitPattern(const BitPattern&);
  278.                      BitPattern(const BitString& p, const BitString& m);
  279.  
  280.                     ~BitPattern();
  281.  
  282.   friend const char* BitPatterntoa(const BitPattern& p, 
  283.                                  char f/*='0'*/,char t/*='1'*/,char x/*='X'*/);
  284.   void             printon(ostream&, char f='0',char t='1',char x='X') const;
  285.   friend BitPattern atoBitPattern(const char* s, char f,char t, char x);
  286.   friend ostream&   operator << (ostream& s, const BitPattern&);
  287.  
  288.   int               search(const _BS_word*, int, int) const;
  289.   int               match(const _BS_word* xs, int, int, int) const;
  290.  
  291.   int               OK() const;
  292. };
  293.  
  294. BitString  operator & (const BitString& x, const BitString& y);
  295. BitString  operator | (const BitString& x, const BitString& y);
  296. BitString  operator ^ (const BitString& x, const BitString& y);
  297. BitString  operator << (const BitString& x, int y);
  298. BitString  operator >> (const BitString& x, int y);
  299. BitString  operator - (const BitString& x, const BitString& y);
  300. BitString  operator + (const BitString& x, const BitString& y);
  301. BitString  operator + (const BitString& x, unsigned int y);
  302. BitString  operator ~ (const BitString& x);
  303. int operator != (const BitString& x, const BitString& y);
  304. int operator>(const BitString& x, const BitString& y);
  305. int operator>=(const BitString& x, const BitString& y);
  306.  
  307. extern BitStrRep    _nilBitStrRep;
  308. extern BitString    _nil_BitString;
  309.  
  310. // primitive bit extraction
  311.  
  312. // These must be inlined regardless of optimization.
  313.  
  314. inline int BitStr_index(int l) { return (unsigned)(l) / BITSTRBITS; }
  315.  
  316. inline int BitStr_pos(int l) { return l & (BITSTRBITS - 1); }
  317.  
  318.  
  319. // constructors & assignment
  320.  
  321. inline BitString::BitString() :rep(&_nilBitStrRep) {}
  322.  
  323. inline BitString::BitString(const BitString& x) :rep(BStr_copy(0, x.rep)) {}
  324.  
  325. inline BitString::BitString(const BitSubString& y) 
  326.    :rep (BStr_alloc(0, y.S.rep->s, y.pos, y.pos+y.len, y.len)) {}
  327.  
  328. inline BitString::~BitString()
  329. { 
  330.   if (rep != &_nilBitStrRep) delete rep;
  331. }
  332.  
  333. inline BitString shorttoBitString(unsigned short w) 
  334. { 
  335.   BitString r;
  336.   _BS_word ww = w;
  337. #if _BS_BIGENDIAN
  338.   abort();
  339. #endif
  340.   r.rep = BStr_alloc(0, &ww, 0, 8 * sizeof(short), 8 * sizeof(short));
  341.   return r;
  342. }
  343.  
  344. inline BitString longtoBitString(unsigned long w) 
  345. { 
  346.   BitString r;
  347. #if 1
  348.   _BS_word u = w;
  349.   r.rep = BStr_alloc(0, &u, 0, BITSTRBITS, BITSTRBITS);
  350. #else
  351.   unsigned short u[2];
  352.   u[0] = w & ((unsigned short)(~(0)));
  353.   u[1] = w >> BITSTRBITS;
  354.   r.rep = BStr_alloc(0, &u[0], 0, 2*BITSTRBITS, 2*BITSTRBITS);
  355. #endif
  356.   return r;
  357. }
  358.  
  359. inline BitString& BitString::operator =  (const BitString& y)
  360. { 
  361.   rep = BStr_copy(rep, y.rep);
  362.   return *this;
  363. }
  364.  
  365. inline BitString& BitString::operator = (unsigned int b)
  366. { 
  367.   _BS_word bit = b;
  368.   rep = BStr_alloc(rep, &bit, 0, 1, 1);
  369.   return *this;
  370. }
  371.  
  372. inline BitString&  BitString::operator=(const BitSubString&  y)
  373. {
  374.   rep = BStr_alloc(rep, y.S.rep->s, y.pos, y.pos+y.len, y.len);
  375.   return *this;
  376. }
  377.  
  378. inline BitSubString::BitSubString(const BitSubString& x) 
  379.     :S(x.S), pos(x.pos), len(x.len) {}
  380.  
  381. inline BitSubString::BitSubString(BitString& x, int p, int l)
  382.      : S(x), pos(p), len(l) {}
  383.  
  384. inline BitSubString::~BitSubString() {}
  385.  
  386. inline BitPattern::BitPattern(const BitString& p, const BitString& m)
  387.     :pattern(p), mask(m) {}
  388.  
  389. inline BitPattern::BitPattern(const BitPattern& b)
  390.     :pattern(b.pattern), mask(b.mask) {}
  391.  
  392. inline BitPattern::BitPattern() {}
  393. inline BitPattern::~BitPattern() {}
  394.  
  395.  
  396. // procedural versions of operators
  397.  
  398. inline void and(const BitString& x, const BitString& y, BitString& r)
  399. {
  400.   r.rep = and(x.rep, y.rep, r.rep);
  401. }
  402.  
  403. inline void or(const BitString& x, const BitString& y, BitString& r)
  404. {
  405.   r.rep = or(x.rep, y.rep, r.rep);
  406. }
  407.  
  408. inline void xor(const BitString& x, const BitString& y, BitString& r)
  409. {
  410.   r.rep = xor(x.rep, y.rep, r.rep);
  411. }
  412.  
  413. inline void diff(const BitString& x, const BitString& y, BitString& r)
  414. {
  415.   r.rep = diff(x.rep, y.rep, r.rep);
  416. }
  417.  
  418. inline void cat(const BitString& x, const BitString& y, BitString& r)
  419. {
  420.   r.rep = cat(x.rep, y.rep, r.rep);
  421. }
  422.  
  423. inline void cat(const BitString& x, unsigned int y, BitString& r)
  424. {
  425.   r.rep = cat(x.rep, y, r.rep);
  426. }
  427.  
  428. inline void rshift(const BitString& x, int y, BitString& r)
  429. {
  430.   r.rep = lshift(x.rep, -y, r.rep);
  431. }
  432.  
  433. inline void lshift(const BitString& x, int y, BitString& r)
  434. {
  435.   r.rep = lshift(x.rep, y, r.rep);
  436. }
  437.  
  438. inline void complement(const BitString& x, BitString& r)
  439. {
  440.   r.rep = cmpl(x.rep, r.rep);
  441. }
  442.  
  443. // operators
  444.  
  445.  
  446. inline BitString& BitString::operator &= (const BitString& y)
  447. {
  448.   and(*this, y, *this);
  449.   return *this;
  450. }
  451.  
  452.  
  453. inline BitString& BitString::operator |= (const BitString& y)
  454. {
  455.   or(*this, y, *this);
  456.   return *this;
  457. }
  458.  
  459. inline BitString& BitString::operator ^= (const BitString& y)
  460. {
  461.   xor(*this, y, *this);
  462.   return *this;
  463. }
  464.  
  465. inline BitString& BitString::operator <<= (int y)
  466. {
  467.   lshift(*this, y, *this);
  468.   return *this;
  469. }
  470.  
  471. inline BitString& BitString::operator >>= (int y)
  472. {
  473.   rshift(*this, y, *this);
  474.   return *this;
  475. }
  476.  
  477. inline BitString& BitString::operator -= (const BitString& y)
  478. {
  479.   diff(*this, y, *this);
  480.   return *this;
  481. }
  482.  
  483. inline BitString& BitString::operator += (const BitString& y)
  484. {
  485.   cat(*this, y, *this);
  486.   return *this;
  487. }
  488.  
  489. inline BitString& BitString::operator += (unsigned int y)
  490. {
  491.   cat(*this, y, *this);
  492.   return *this;
  493. }
  494.  
  495. inline void BitString::complement()
  496. {
  497.   ::complement(*this, *this);
  498. }
  499.  
  500. #if defined(__GNUG__) && !defined(_G_NO_NRV)
  501.  
  502. inline BitString  operator & (const BitString& x, const BitString& y) return r
  503. {
  504.   and(x, y, r);
  505. }
  506.  
  507. inline BitString  operator | (const BitString& x, const BitString& y) return r
  508. {
  509.   or(x, y, r);
  510. }
  511.  
  512. inline BitString  operator ^ (const BitString& x, const BitString& y) return r
  513. {
  514.   xor(x, y, r);
  515. }
  516.  
  517. inline BitString  operator << (const BitString& x, int y) return r
  518. {
  519.   lshift(x, y, r);
  520. }
  521.  
  522. inline BitString  operator >> (const BitString& x, int y) return r
  523. {
  524.   rshift(x, y, r);
  525. }
  526.  
  527. inline BitString  operator - (const BitString& x, const BitString& y) return r
  528. {
  529.   diff(x, y, r);
  530. }
  531.  
  532. inline BitString  operator + (const BitString& x, const BitString& y) return r
  533. {
  534.   cat(x, y, r);
  535. }
  536.  
  537. inline BitString  operator + (const BitString& x, unsigned int y) return r
  538. {
  539.   cat(x, y, r);
  540. }
  541.  
  542. inline BitString  operator ~ (const BitString& x) return r
  543. {
  544.   complement(x, r);
  545. }
  546.  
  547. #else /* NO_NRV */
  548.  
  549. inline BitString  operator & (const BitString& x, const BitString& y) 
  550. {
  551.   BitString r; and(x, y, r); return r;
  552. }
  553.  
  554. inline BitString  operator | (const BitString& x, const BitString& y) 
  555. {
  556.   BitString r; or(x, y, r); return r;
  557. }
  558.  
  559. inline BitString  operator ^ (const BitString& x, const BitString& y) 
  560. {
  561.   BitString r; xor(x, y, r); return r;
  562. }
  563.  
  564. inline BitString  operator << (const BitString& x, int y) 
  565. {
  566.   BitString r; lshift(x, y, r); return r;
  567. }
  568.  
  569. inline BitString  operator >> (const BitString& x, int y) 
  570. {
  571.   BitString r; rshift(x, y, r); return r;
  572. }
  573.  
  574. inline BitString  operator - (const BitString& x, const BitString& y) 
  575. {
  576.   BitString r; diff(x, y, r); return r;
  577. }
  578.  
  579. inline BitString  operator + (const BitString& x, const BitString& y) 
  580. {
  581.   BitString r; cat(x, y, r); return r;
  582. }
  583.  
  584. inline BitString  operator + (const BitString& x, unsigned int y) 
  585. {
  586.   BitString r; cat(x, y, r); return r;
  587. }
  588.  
  589. inline BitString  operator ~ (const BitString& x) 
  590. {
  591.   BitString r; complement(x, r); return r;
  592. }
  593.  
  594. #endif
  595.  
  596. // status, matching
  597.  
  598. inline int BitString::length() const
  599. { 
  600.   return rep->len;
  601. }
  602.  
  603. inline int BitString::empty() const
  604. { 
  605.   return rep->len == 0;
  606. }
  607.  
  608. inline int BitString::index(const BitString& y, int startpos) const
  609. {   
  610.   return search(startpos, rep->len, y.rep->s, 0, y.rep->len);
  611. }
  612.  
  613. inline int BitString::index(const BitSubString& y, int startpos) const
  614. {   
  615.   return search(startpos, rep->len, y.S.rep->s, y.pos, y.pos+y.len);
  616. }
  617.  
  618. inline int BitString::contains(const BitString& y) const
  619. {   
  620.   return search(0, rep->len, y.rep->s, 0, y.rep->len) >= 0;
  621. }
  622.  
  623. inline int BitString::contains(const BitSubString& y) const
  624. {   
  625.   return search(0, rep->len, y.S.rep->s, y.pos, y.pos+y.len) >= 0;
  626. }
  627.  
  628. inline int BitString::contains(const BitString& y, int p) const
  629. {
  630.   return match(p, rep->len, 0, y.rep->s, 0, y.rep->len);
  631. }
  632.  
  633. inline int BitString::matches(const BitString& y, int p) const
  634. {
  635.   return match(p, rep->len, 1, y.rep->s, 0, y.rep->len);
  636. }
  637.  
  638. inline int BitString::contains(const BitSubString& y, int p) const
  639. {
  640.   return match(p, rep->len, 0, y.S.rep->s, y.pos, y.pos+y.len);
  641. }
  642.  
  643. inline int BitString::matches(const BitSubString& y, int p) const
  644. {
  645.   return match(p, rep->len, 1, y.S.rep->s, y.pos, y.pos+y.len);
  646. }
  647.  
  648. inline int BitString::contains(const BitPattern& r) const
  649. {
  650.   return r.search(rep->s, 0, rep->len) >= 0;
  651. }
  652.  
  653. inline int BitString::contains(const BitPattern& r, int p) const
  654. {
  655.   return r.match(rep->s, p, rep->len, 0);
  656. }
  657.  
  658. inline int BitString::matches(const BitPattern& r, int p) const
  659. {
  660.   return r.match(rep->s, p, rep->len, 1);
  661. }
  662.  
  663. inline int BitString::index(const BitPattern& r, int startpos) const
  664. {
  665.   return r.search(rep->s, startpos, rep->len);
  666. }
  667.  
  668. inline  int BitSubString::length() const
  669. { 
  670.   return len;
  671. }
  672.  
  673. inline  int BitSubString::empty() const
  674. { 
  675.   return len == 0;
  676. }
  677.  
  678. inline int operator != (const BitString& x, const BitString& y)
  679. {
  680.   return !(x == y);
  681. }
  682.  
  683. inline int operator>(const BitString& x, const BitString& y)
  684. {
  685.   return y < x;
  686. }
  687.  
  688. inline int operator>=(const BitString& x, const BitString& y)
  689. {
  690.   return y <= x;
  691. }
  692.  
  693. inline int BitString::first(unsigned int b) const
  694. {
  695.   return next(-1, b);
  696. }
  697.  
  698. inline int BitString::last(unsigned int b) const
  699. {
  700.   return prev(rep->len, b);
  701. }
  702.  
  703. inline int BitString::index(unsigned int bit, int startpos) const
  704. {
  705.   if (startpos >= 0)
  706.     return next(startpos - 1, bit);
  707.   else
  708.     return prev(rep->len + startpos + 1, bit);
  709. }
  710.  
  711. inline void BitString::right_trim(unsigned int b) 
  712. {
  713.   int nb = (b == 0)? 1 : 0;
  714.   rep = BStr_resize(rep, prev(rep->len, nb) + 1);
  715. }
  716.  
  717. inline void BitString::left_trim(unsigned int b)
  718. {
  719.   int nb = (b == 0)? 1 : 0;
  720.   int p = next(-1, nb);
  721.   rep = BStr_alloc(rep, rep->s, p, rep->len, rep->len - p);
  722. }
  723.  
  724. inline int BitString::test(int i) const
  725. {
  726.   return ((unsigned)(i) >= rep->len)? 0 : 
  727.          ((rep->s[BitStr_index(i)] & (1 << (BitStr_pos(i)))) != 0);
  728. }
  729.  
  730.  
  731. // subscripting
  732.  
  733. inline BitStrBit::BitStrBit(const BitStrBit& b) :src(b.src), pos(b.pos) {}
  734.  
  735. inline BitStrBit::BitStrBit(BitString& v, int p) :src(v), pos(p) {}
  736.  
  737. inline BitStrBit::~BitStrBit() {}
  738.  
  739. inline BitStrBit::operator unsigned int() const
  740. {
  741.   return src.test(pos);
  742. }
  743.  
  744. inline int BitStrBit::operator = (unsigned int b)
  745. {
  746.   src.assign(pos, b); return b;
  747. }
  748.  
  749. inline BitStrBit BitString::operator [] (int i)
  750. {
  751.   if ((unsigned)(i) >= rep->len) error("illegal bit index");
  752.   return BitStrBit(*this, i);
  753. }
  754.  
  755. inline BitSubString BitString::_substr(int first, int l)
  756. {
  757.   if (first < 0 || l <= 0 || (unsigned)(first + l) > rep->len)
  758.     return BitSubString(_nil_BitString, 0, 0) ;
  759.   else 
  760.     return BitSubString(*this, first, l);
  761. }
  762.  
  763. #endif
  764.