home *** CD-ROM | disk | FTP | other *** search
/ NeXTSTEP 3.3 (Developer) / NeXT_Developer-3.3.iso / NextDeveloper / Headers / g++ / BitString.h < prev    next >
Encoding:
C/C++ Source or Header  |  1995-02-06  |  19.8 KB  |  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, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifndef _BitString_h
  20. #ifdef __GNUG__
  21. #pragma interface
  22. #pragma cplusplus
  23. #endif
  24.  
  25. #define _BitString_h 1
  26.  
  27. #include <stream.h>
  28. #ifdef __cplusplus
  29. extern "C" {
  30. #endif
  31. #include <limits.h>
  32. #ifdef __cplusplus
  33. }
  34. #endif
  35. #define BITSTRBITS  (sizeof(short) * CHAR_BIT)
  36.  
  37. struct BitStrRep
  38. {
  39.   unsigned int    len;          // length in bits
  40.   unsigned short  sz;           // allocated slots
  41.   unsigned short  s[1];         // bits start here
  42. };
  43.  
  44. extern BitStrRep*  BStr_alloc(BitStrRep*, const unsigned short*, int, int,int);
  45. extern BitStrRep*  BStr_resize(BitStrRep*, int);
  46. extern BitStrRep*  BStr_copy(BitStrRep*, const BitStrRep*);
  47. extern BitStrRep*  cmpl(const BitStrRep*, BitStrRep*);
  48. extern BitStrRep*  and(const BitStrRep*, const BitStrRep*, BitStrRep*);
  49. extern BitStrRep*  or(const BitStrRep*, const BitStrRep*, BitStrRep*);
  50. extern BitStrRep*  xor(const BitStrRep*, const BitStrRep*, BitStrRep*);
  51. extern BitStrRep*  diff(const BitStrRep*, const BitStrRep*, BitStrRep*);
  52. extern BitStrRep*  cat(const BitStrRep*, const BitStrRep*, BitStrRep*);
  53. extern BitStrRep*  cat(const BitStrRep*, unsigned int, BitStrRep*);
  54. extern BitStrRep*  lshift(const BitStrRep*, int, BitStrRep*);
  55.  
  56.  
  57. class BitString;
  58. class BitPattern;
  59.  
  60. class BitStrBit
  61. {
  62. protected:
  63.   BitString&        src;
  64.   unsigned int      pos;
  65.  
  66.  public:
  67.                     BitStrBit(BitString& v, int p);
  68.                     BitStrBit(const BitStrBit& b);
  69.                    ~BitStrBit();
  70.                     operator unsigned int() const;
  71.   int               operator =  (unsigned int b);
  72. };
  73.  
  74. class BitSubString
  75. {
  76.   friend class      BitString;
  77.   friend class      BitPattern;
  78.  
  79. protected:
  80.  
  81.   BitString&        S;
  82.   unsigned int      pos;
  83.   unsigned int      len;
  84.  
  85.                     BitSubString(BitString& x, int p, int l);
  86.                     BitSubString(const BitSubString& x);
  87. public:
  88.                     ~BitSubString();
  89.  
  90.   void              operator =  (const BitString&);
  91.   void              operator =  (const BitSubString&);
  92.  
  93.   int               length() const;
  94.   int               empty() const;
  95.  
  96.   int               OK() const;
  97. };
  98.  
  99. class BitString
  100. {
  101.   friend class       BitSubString;
  102.   friend class       BitPattern;
  103. protected:
  104.   BitStrRep*         rep;
  105.  
  106.   int                search(int, int, const unsigned short*, int, int) const;
  107.   int                match(int, int, int, const unsigned short*,int,int) const;
  108.   BitSubString       _substr(int first, int l);
  109.  
  110. public:
  111.  
  112. // constructors
  113.                      BitString();
  114.                      BitString(const BitString&);
  115.                      BitString(const BitSubString& y);
  116.  
  117.                     ~BitString();
  118.  
  119.   void               operator =  (unsigned int bit);
  120.   void               operator =  (const BitString& y);
  121.   void               operator =  (const BitSubString& y);
  122.  
  123. // equality & subset tests
  124.  
  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.   friend int         operator <= (const BitString&, const BitString&);
  129.   friend int         operator >  (const BitString&, const BitString&);
  130.   friend int         operator >= (const BitString&, const BitString&);
  131.  
  132. // procedural versions of operators
  133.  
  134.  
  135.   friend void        and(const BitString&, const BitString&, BitString&);
  136.   friend void        or(const BitString&, const BitString&, BitString&);
  137.   friend void        xor(const BitString&, const BitString&, BitString&);
  138.   friend void        diff(const BitString&, const BitString&, BitString&);
  139.   friend void        cat(const BitString&, const BitString&, BitString&);
  140.   friend void        cat(const BitString&, unsigned int, BitString&);
  141.   friend void        lshift(const BitString&, int, BitString&);
  142.   friend void        rshift(const BitString&, int, BitString&);
  143.  
  144.   friend void        complement(const BitString&, BitString&);
  145.  
  146.   friend int         lcompare(const BitString&, const BitString&); 
  147.  
  148. // assignment-based operators
  149. // (constuctive versions decalred inline below
  150.  
  151.   void               operator |= (const BitString&);
  152.   void               operator &= (const BitString&);
  153.   void               operator -= (const BitString&);
  154.   void               operator ^= (const BitString&);
  155.   void               operator += (const BitString&);
  156.   void               operator += (unsigned int b);
  157.   void               operator <<=(int s);
  158.   void               operator >>=(int s);
  159.  
  160.   void               complement();
  161.  
  162. // individual bit manipulation
  163.  
  164.   void               set(int pos);
  165.   void               set(int from, int to);
  166.   void               set();
  167.  
  168.   void               clear(int pos);
  169.   void               clear(int from, int to);
  170.   void               clear(); 
  171.  
  172.   void               invert(int pos);
  173.   void               invert(int from, int to);
  174.  
  175.   int                test(int pos) const;
  176.   int                test(int from, int to) const;
  177.  
  178.   void               assign(int p, unsigned int bit);
  179.  
  180. // indexing
  181.  
  182.   BitStrBit          operator [] (int pos);
  183.  
  184. // iterators
  185.  
  186.   int                first(unsigned int bit = 1) const;
  187.   int                last(unsigned int b = 1) const;
  188.  
  189.   int                next(int pos, unsigned int b = 1) const;
  190.   int                prev(int pos, unsigned int b = 1) const;
  191.   int                previous(int pos, unsigned int b = 1) const
  192.     { return prev(pos, b); } /* Obsolete synonym */
  193.  
  194. // searching & matching
  195.  
  196.   int                index(unsigned int bit, int startpos = 0) const ;      
  197.   int                index(const BitString&, int startpos = 0) const;
  198.   int                index(const BitSubString&, int startpos = 0) const;
  199.   int                index(const BitPattern&, int startpos = 0) const;
  200.  
  201.   int                contains(const BitString&) const;
  202.   int                contains(const BitSubString&) const;
  203.   int                contains(const BitPattern&) const;
  204.  
  205.   int                contains(const BitString&, int pos) const;
  206.   int                contains(const BitSubString&, int pos) const;
  207.   int                contains(const BitPattern&, int pos) const;
  208.  
  209.   int                matches(const BitString&, int pos = 0) const;
  210.   int                matches(const BitSubString&, int pos = 0) const;
  211.   int                matches(const BitPattern&, int pos = 0) const;
  212.  
  213. // BitSubString extraction
  214.  
  215.   BitSubString       at(int pos, int len);
  216.   BitSubString       at(const BitString&, int startpos = 0); 
  217.   BitSubString       at(const BitSubString&, int startpos = 0); 
  218.   BitSubString       at(const BitPattern&, int startpos = 0); 
  219.  
  220.   BitSubString       before(int pos);
  221.   BitSubString       before(const BitString&, int startpos = 0);
  222.   BitSubString       before(const BitSubString&, int startpos = 0);
  223.   BitSubString       before(const BitPattern&, int startpos = 0);
  224.  
  225.   BitSubString       after(int pos);
  226.   BitSubString       after(const BitString&, int startpos = 0);
  227.   BitSubString       after(const BitSubString&, int startpos = 0);
  228.   BitSubString       after(const BitPattern&, int startpos = 0);
  229.  
  230. // other friends & utilities
  231.  
  232.   friend BitString   common_prefix(const BitString&, const BitString&, 
  233.                                    int pos = 0);
  234.   friend BitString   common_suffix(const BitString&, const BitString&, 
  235.                                    int pos = -1);
  236.   friend BitString   reverse(const BitString&);
  237.  
  238.   void               right_trim(unsigned int bit);
  239.   void               left_trim(unsigned int bit);
  240.  
  241. // status
  242.  
  243.   int                empty() const ;
  244.   int                count(unsigned int bit = 1) const;
  245.   int                length() const;
  246.  
  247. // convertors & IO
  248.  
  249.   friend BitString   atoBitString(const char* s, char f='0', char t='1');
  250.   // BitStringtoa is deprecated; do not use in new programs!
  251.   friend const char* BitStringtoa(const BitString&, char f='0', char t='1');
  252.   void             printon(ostream&, char f='0', char t='1') const;
  253.  
  254.   friend BitString   shorttoBitString(unsigned short);
  255.   friend BitString   longtoBitString(unsigned long);
  256.  
  257.   friend ostream&    operator << (ostream& s, const BitString&);
  258.  
  259. // misc
  260.  
  261.   void      error(const char* msg) const;
  262.  
  263. // indirect friends
  264.  
  265.   friend BitPattern  atoBitPattern(const char* s,
  266.                                   char f='0',char t='1',char x='X');
  267.   friend const char* BitPatterntoa(const BitPattern& p, 
  268.                                   char f='0',char t='1',char x='X');
  269.   int                OK() const;
  270. };
  271.  
  272.  
  273. class BitPattern
  274. {
  275. public:
  276.   BitString          pattern;
  277.   BitString          mask;
  278.  
  279.                      BitPattern();
  280.                      BitPattern(const BitPattern&);
  281.                      BitPattern(const BitString& p, const BitString& m);
  282.  
  283.                     ~BitPattern();
  284.  
  285.   friend const char* BitPatterntoa(const BitPattern& p, 
  286.                                  char f/*='0'*/,char t/*='1'*/,char x/*='X'*/);
  287.   void             printon(ostream&, char f='0',char t='1',char x='X') const;
  288.   friend BitPattern atoBitPattern(const char* s, char f,char t, char x);
  289.   friend ostream&   operator << (ostream& s, const BitPattern&);
  290.  
  291.   int               search(const unsigned short*, int, int) const;
  292.   int               match(const unsigned short* xs, int, int, int) const;
  293.  
  294.   int               OK() const;
  295. };
  296.  
  297. BitString  operator & (const BitString& x, const BitString& y);
  298. BitString  operator | (const BitString& x, const BitString& y);
  299. BitString  operator ^ (const BitString& x, const BitString& y);
  300. BitString  operator << (const BitString& x, int y);
  301. BitString  operator >> (const BitString& x, int y);
  302. BitString  operator - (const BitString& x, const BitString& y);
  303. BitString  operator + (const BitString& x, const BitString& y);
  304. BitString  operator + (const BitString& x, unsigned int y);
  305. BitString  operator ~ (const BitString& x);
  306. int operator != (const BitString& x, const BitString& y);
  307. int operator>(const BitString& x, const BitString& y);
  308. int operator>=(const BitString& x, const BitString& y);
  309.  
  310. extern BitStrRep    _nilBitStrRep;
  311. extern BitString    _nil_BitString;
  312.  
  313. // primitive bit extraction
  314.  
  315. // These must be inlined regardless of optimization.
  316.  
  317. inline int BitStr_index(int l) { return (unsigned)(l) / BITSTRBITS; }
  318.  
  319. inline int BitStr_pos(int l) { return l & (BITSTRBITS - 1); }
  320.  
  321.  
  322. // constructors & assignment
  323.  
  324. inline BitString::BitString() :rep(&_nilBitStrRep) {}
  325.  
  326. inline BitString::BitString(const BitString& x) :rep(BStr_copy(0, x.rep)) {}
  327.  
  328. inline BitString::BitString(const BitSubString& y) 
  329.    :rep (BStr_alloc(0, y.S.rep->s, y.pos, y.pos+y.len, y.len)) {}
  330.  
  331. inline BitString::~BitString()
  332. { 
  333.   if (rep != &_nilBitStrRep) delete rep;
  334. }
  335.  
  336. #if defined(__GNUG__) && !defined(NO_NRV)
  337.  
  338. inline BitString shorttoBitString(unsigned short w) return r
  339. { 
  340.   r.rep = BStr_alloc(0, &w, 0, BITSTRBITS, BITSTRBITS);
  341. }
  342.  
  343. inline BitString longtoBitString(unsigned long w) return r
  344. { 
  345.   unsigned short u[2];
  346.   u[0] = w & ((unsigned short)(~(0)));
  347.   u[1] = w >> BITSTRBITS;
  348.   r.rep = BStr_alloc(0, &u[0], 0, 2*BITSTRBITS, 2*BITSTRBITS);
  349. }
  350.  
  351. #else
  352.  
  353. inline BitString shorttoBitString(unsigned short w) 
  354. { 
  355.   BitString r; r.rep = BStr_alloc(0, &w, 0, BITSTRBITS, BITSTRBITS); return r;
  356. }
  357.  
  358. inline BitString longtoBitString(unsigned long w) 
  359. { 
  360.   BitString r;
  361.   unsigned short u[2];
  362.   u[0] = w & ((unsigned short)(~(0)));
  363.   u[1] = w >> BITSTRBITS;
  364.   r.rep = BStr_alloc(0, &u[0], 0, 2*BITSTRBITS, 2*BITSTRBITS);
  365.   return r;
  366. }
  367.  
  368. #endif
  369.  
  370. inline void BitString::operator =  (const BitString& y)
  371. { 
  372.   rep = BStr_copy(rep, y.rep);
  373. }
  374.  
  375. inline void BitString::operator = (unsigned int b)
  376. { 
  377.   unsigned short bit = b;
  378.   rep = BStr_alloc(rep, &bit, 0, 1, 1);
  379. }
  380.  
  381. inline void BitString::operator=(const BitSubString&  y)
  382. {
  383.   rep = BStr_alloc(rep, y.S.rep->s, y.pos, y.pos+y.len, y.len);
  384. }
  385.  
  386. inline BitSubString::BitSubString(const BitSubString& x) 
  387.     :S(x.S), pos(x.pos), len(x.len) {}
  388.  
  389. inline BitSubString::BitSubString(BitString& x, int p, int l)
  390.      : S(x), pos(p), len(l) {}
  391.  
  392. inline BitSubString::~BitSubString() {}
  393.  
  394. inline BitPattern::BitPattern(const BitString& p, const BitString& m)
  395.     :pattern(p), mask(m) {}
  396.  
  397. inline BitPattern::BitPattern(const BitPattern& b)
  398.     :pattern(b.pattern), mask(b.mask) {}
  399.  
  400. inline BitPattern::BitPattern() {}
  401. inline BitPattern::~BitPattern() {}
  402.  
  403.  
  404. // procedural versions of operators
  405.  
  406. inline void and(const BitString& x, const BitString& y, BitString& r)
  407. {
  408.   r.rep = and(x.rep, y.rep, r.rep);
  409. }
  410.  
  411. inline void or(const BitString& x, const BitString& y, BitString& r)
  412. {
  413.   r.rep = or(x.rep, y.rep, r.rep);
  414. }
  415.  
  416. inline void xor(const BitString& x, const BitString& y, BitString& r)
  417. {
  418.   r.rep = xor(x.rep, y.rep, r.rep);
  419. }
  420.  
  421. inline void diff(const BitString& x, const BitString& y, BitString& r)
  422. {
  423.   r.rep = diff(x.rep, y.rep, r.rep);
  424. }
  425.  
  426. inline void cat(const BitString& x, const BitString& y, BitString& r)
  427. {
  428.   r.rep = cat(x.rep, y.rep, r.rep);
  429. }
  430.  
  431. inline void cat(const BitString& x, unsigned int y, BitString& r)
  432. {
  433.   r.rep = cat(x.rep, y, r.rep);
  434. }
  435.  
  436. inline void rshift(const BitString& x, int y, BitString& r)
  437. {
  438.   r.rep = lshift(x.rep, -y, r.rep);
  439. }
  440.  
  441. inline void lshift(const BitString& x, int y, BitString& r)
  442. {
  443.   r.rep = lshift(x.rep, y, r.rep);
  444. }
  445.  
  446. inline void complement(const BitString& x, BitString& r)
  447. {
  448.   r.rep = cmpl(x.rep, r.rep);
  449. }
  450.  
  451. // operators
  452.  
  453.  
  454. inline void BitString::operator &= (const BitString& y)
  455. {
  456.   and(*this, y, *this);
  457. }
  458.  
  459.  
  460. inline void BitString::operator |= (const BitString& y)
  461. {
  462.   or(*this, y, *this);
  463. }
  464.  
  465. inline void BitString::operator ^= (const BitString& y)
  466. {
  467.   xor(*this, y, *this);
  468. }
  469.  
  470. inline void BitString::operator <<= (int y)
  471. {
  472.   lshift(*this, y, *this);
  473. }
  474.  
  475. inline void BitString::operator >>= (int y)
  476. {
  477.   rshift(*this, y, *this);
  478. }
  479.  
  480. inline void BitString::operator -= (const BitString& y)
  481. {
  482.   diff(*this, y, *this);
  483. }
  484.  
  485. inline void BitString::operator += (const BitString& y)
  486. {
  487.   cat(*this, y, *this);
  488. }
  489.  
  490. inline void BitString::operator += (unsigned int y)
  491. {
  492.   cat(*this, y, *this);
  493. }
  494.  
  495. inline void BitString::complement()
  496. {
  497.   ::complement(*this, *this);
  498. }
  499.  
  500. #if defined(__GNUG__) && !defined(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.