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