bitset.hxx

Go to the documentation of this file.
00001 // bitset.hxx: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
00016 //
00017 #ifndef VCSN_MISC_BITSET_HXX
00018 # define VCSN_MISC_BITSET_HXX
00019 
00027 # include <vaucanson/misc/bitset.hh>
00028 # include <vaucanson/misc/contract.hh>
00029 
00030 # include <cstdlib>
00031 
00032 namespace vcsn
00033 {
00034   namespace misc
00035   {
00036 
00037   /*-------.
00038   | Bitset |
00039   `-------*/
00040 
00041     // Default contructors.
00042     inline
00043     Bitset::Bitset (size_type max) : data_size_  (get_data_size (max)),
00044                                      data_       (new data_type[data_size_]),
00045                                      max_size_   (max),
00046                                      size_       (0),
00047                                      end_        (bit_iterator (get_index (max_size_),
00048                                                                 get_bitnum (max_size_)))
00049     {
00050       bzero (data_, data_size_ * sizeof (data_type));
00051     }
00052 
00053     inline
00054     Bitset::Bitset (size_type max, const data_type* data)
00055       : data_size_      (get_data_size (max)),
00056         data_           (new data_type[data_size_]),
00057         max_size_       (max),
00058         size_           (invalid_size),
00059         end_            (bit_iterator (get_index (max_size_),
00060                                        get_bitnum (max_size_)))
00061     {
00062       memcpy (data_, data, data_size_ * sizeof (data_type));
00063     }
00064 
00065     // Copy constructor.
00066     inline
00067     Bitset::Bitset (const Bitset& bs) : data_size_      (bs.data_size_),
00068                                         data_           (new data_type[data_size_]),
00069                                         max_size_       (bs.max_size_),
00070                                         size_           (bs.size_),
00071                                         end_            (bs.end_)
00072     {
00073       memcpy (data_, bs.data_, data_size_ * sizeof (data_type));
00074     }
00075 
00076     // Constructor from iterators.
00077     template <class InputIterator>
00078     Bitset::Bitset (InputIterator first, InputIterator last)
00079     {
00080       value_type max = 0;
00081 
00082       for (InputIterator i = first; i != last; ++i)
00083       {
00084         assertion (*i >= 0);
00085         if (*i > max)
00086           max = *i;
00087       }
00088       data_size_ = get_data_size (max + 1);
00089       data_ = new data_type[data_size_];
00090       bzero (data_, data_size_ * sizeof (data_type));
00091       max_size_ = max + 1;
00092       size_ = 0;
00093       end_ = bit_iterator (get_index (max_size_), get_bitnum (max_size_));
00094       insert (first, last);
00095     }
00096 
00097     // Destructor.
00098     inline
00099     Bitset::~Bitset ()
00100     {
00101       delete[] data_;
00102     }
00103 
00104     // Assignment.
00105     inline
00106     Bitset&
00107     Bitset::operator= (const Bitset& rhs)
00108     {
00109       if (this != &rhs)
00110       {
00111         data_size_ = rhs.data_size_;
00112         delete[] data_;
00113         data_ = new data_type[data_size_];
00114         memcpy (data_, rhs.data_, data_size_ * sizeof (data_type));
00115         max_size_ = rhs.max_size_;
00116         size_ = rhs.size_;
00117         end_ = rhs.end_;
00118       }
00119       postcondition (*this == rhs);
00120       return *this;
00121     }
00122 
00123   /*------------.
00124   | Iterators.  |
00125   `------------*/
00126 
00127     // begin
00128     inline
00129     Bitset::iterator
00130     Bitset::begin ()
00131     {
00132       return iterator (this);
00133     }
00134 
00135     inline
00136     Bitset::const_iterator
00137     Bitset::begin () const
00138     {
00139       return const_iterator (this);
00140     }
00141 
00142     // end
00143     inline
00144     Bitset::iterator
00145     Bitset::end ()
00146     {
00147       return iterator (this, end_);
00148     }
00149 
00150     inline
00151     Bitset::const_iterator
00152     Bitset::end () const
00153     {
00154       return const_iterator (this, end_);
00155     }
00156 
00157   /*--------------------.
00158   | Reverse Iterators.  |
00159   `--------------------*/
00160 
00161     // rbegin
00162     inline
00163     Bitset::reverse_iterator
00164     Bitset::rbegin ()
00165     {
00166       return reverse_iterator (end ());
00167     }
00168 
00169     inline
00170     Bitset::const_reverse_iterator
00171     Bitset::rbegin () const
00172     {
00173       return const_reverse_iterator (end ());
00174     }
00175 
00176     // rend
00177     inline
00178     Bitset::reverse_iterator
00179     Bitset::rend ()
00180     {
00181       return reverse_iterator (begin ());
00182     }
00183 
00184     inline
00185     Bitset::const_reverse_iterator
00186     Bitset::rend () const
00187     {
00188       return const_reverse_iterator (begin ());
00189     }
00190 
00191   /*------------------.
00192   | Misc. functions.  |
00193   `------------------*/
00194 
00195     // empty
00196     inline
00197     bool
00198     Bitset::empty () const
00199     {
00200       return size_ == 0;
00201     }
00202 
00203     // size
00204     inline
00205     Bitset::size_type
00206     Bitset::size () const
00207     {
00208       return size_ == invalid_size ? compute_size () : size_;
00209     }
00210 
00211     // max_size
00212     inline
00213     Bitset::size_type
00214     Bitset::max_size () const
00215     {
00216       return max_size_;
00217     }
00218 
00219   /*-------------.
00220   | Insertions.  |
00221   `-------------*/
00222 
00223     inline
00224     std::pair<Bitset::iterator, bool>
00225     Bitset::insert (const value_type& x)
00226     {
00227       precondition (static_cast<size_type> (x) < max_size_);
00228 
00229       size_type idx = get_index (x);
00230       size_type bnm = get_bitnum (x);
00231 
00232       if (get_bit (idx, bnm))
00233         return std::make_pair (end (), false);
00234       else
00235       {
00236         data_[idx] |= (1 << bnm);
00237         if (size_ != invalid_size)
00238           size_++;
00239         return std::make_pair (iterator (this, bit_iterator (idx, bnm)), true);
00240       }
00241     }
00242 
00243     inline
00244     Bitset::iterator
00245     Bitset::insert (iterator, const value_type& x)
00246     {
00247       return insert (x).first;
00248     }
00249 
00250     template <class InputIterator>
00251     void
00252     Bitset::insert (InputIterator first, InputIterator last)
00253     {
00254       while (first != last)
00255       {
00256         insert (*first);
00257         ++first;
00258       }
00259     }
00260 
00261   /*------.
00262   | Erase |
00263   `------*/
00264 
00265     inline
00266     void
00267     Bitset::erase (iterator position)
00268     {
00269       precondition (static_cast<size_type> (*position) < max_size_);
00270 
00271       erase (*position);
00272     }
00273 
00274     inline
00275     Bitset::size_type
00276     Bitset::erase (const key_type& x)
00277     {
00278       precondition (static_cast<size_type> (x) < max_size_);
00279 
00280       size_type idx = get_index (x);
00281       size_type bnm = get_bitnum (x);
00282 
00283       if (get_bit (idx, bnm))
00284       {
00285         data_[idx] &= ~ (1 << bnm);
00286         if (size_ != invalid_size)
00287           --size_;
00288         return 1;
00289       }
00290       else
00291         return 0;
00292     }
00293 
00294     inline
00295     void
00296     Bitset::erase (iterator first, iterator last)
00297     {
00298       while (first != last)
00299       {
00300         erase (*first);
00301         ++first;
00302       }
00303     }
00304 
00305   /*------------------.
00306   | Misc. functions.  |
00307   `------------------*/
00308 
00309     // swap
00310     inline
00311     void
00312     Bitset::swap (Bitset& other)
00313     {
00314       std::swap (data_size_, other.data_size_);
00315       std::swap (data_, other.data_);
00316       std::swap (max_size_, other.max_size_);
00317       std::swap (size_, other.size_);
00318       std::swap (end_, other.end_);
00319     }
00320 
00321     // clear
00322     inline
00323     void
00324     Bitset::clear ()
00325     {
00326       bzero (data_, data_size_ * sizeof (data_type));
00327       size_ = 0;
00328     }
00329 
00330     // key_compare
00331     inline
00332     Bitset::key_compare
00333     Bitset::key_comp () const
00334     {
00335       return key_compare ();
00336     }
00337 
00338     // value_compare
00339     inline
00340     Bitset::value_compare
00341     Bitset::value_comp () const
00342     {
00343       return value_compare ();
00344     }
00345 
00346     // find
00347     inline
00348     Bitset::iterator
00349     Bitset::find (const key_type& x) const
00350     {
00351       precondition (static_cast<size_type> (x) < max_size_);
00352 
00353       bit_iterator it (get_index (x), get_bitnum (x));
00354       if (get_bit (it))
00355         return iterator (this, it);
00356       else
00357         return iterator (this, end_);
00358     }
00359 
00360     // count
00361     inline
00362     Bitset::size_type
00363     Bitset::count (const key_type& x) const
00364     {
00365       precondition (static_cast<size_type> (x) < max_size_);
00366 
00367       return get_bit (get_index (x), get_bitnum (x)) ? 1 : 0;
00368     }
00369 
00370     // lower_bound
00371     inline
00372     Bitset::iterator
00373     Bitset::lower_bound (const key_type& x) const
00374     {
00375       precondition (static_cast<size_type> (x) < max_size_);
00376 
00377       bit_iterator it (get_index (x), get_bitnum (x));
00378 
00379       while ( (it != bit_end ()) && !get_bit (it))
00380         ++it;
00381       return iterator (this, it);
00382     }
00383 
00384     // upper_bound
00385     inline
00386     Bitset::iterator
00387     Bitset::upper_bound (const key_type& x) const
00388     {
00389       precondition (static_cast<size_type> (x) < max_size_);
00390 
00391       bit_iterator it (get_index (x), get_bitnum (x));
00392 
00393       if (it == bit_begin ())
00394         return iterator (this, end_);
00395       else
00396       {
00397         do
00398         {
00399           --it;
00400         }
00401         while ( (it != bit_begin ()) && !get_bit (it));
00402         return iterator (this, get_bit (it) ? it : end_);
00403       }
00404     }
00405 
00406     // equal_range
00407     inline
00408     std::pair<Bitset::iterator, Bitset::iterator>
00409     Bitset::equal_range (const key_type& x) const
00410     {
00411       // FIXME: Could be optimized.
00412       return std::make_pair (lower_bound (x), upper_bound (x));
00413     }
00414 
00415   /*------------.
00416   | Operators.  |
00417   `------------*/
00418 
00419     inline
00420     bool
00421     Bitset::operator== (const Bitset& rhs) const
00422     {
00423       if (rhs.data_size_ < data_size_)
00424         return rhs.operator== (*this);
00425       else
00426       {
00427         for (size_type i = 0; i < data_size_; ++i)
00428           if (data_[i] != rhs.data_[i])
00429             return false;
00430         for (size_type i = data_size_; i < rhs.data_size_; ++i)
00431           if (rhs.data_[i])
00432             return false;
00433         return true;
00434       }
00435     }
00436 
00437     inline
00438     bool
00439     Bitset::operator< (const Bitset& rhs) const
00440     {
00441       // Case 1: rhs is longer than *this.
00442       for (size_type i = rhs.data_size_ - 1; i >= data_size_; ++i)
00443         if (rhs.data_[i])
00444           return true;
00445       // Case 2: *this is longer than rhs.
00446       for (size_type i = data_size_ - 1; i >= rhs.data_size_; ++i)
00447         if (data_[i])
00448           return false;
00449       // Common case: compare the bits rhs and *this have in common.
00450       for (int i = std::min (data_size_, rhs.data_size_) - 1; i >= 0; ++i)
00451         if (rhs.data_[i] != data_[i])
00452           return rhs.data_[i] > data_[i];
00453       // If we get out from the previous loop, then the bitsets are equals.
00454       return false;
00455     }
00456 
00457     inline
00458     bool
00459     Bitset::operator!= (const Bitset& rhs) const
00460     {
00461       return ! (*this == rhs);
00462     }
00463 
00464     inline
00465     bool
00466     Bitset::operator> (const Bitset& rhs) const
00467     {
00468       return rhs < *this;
00469     }
00470 
00471     inline
00472     bool
00473     Bitset::operator<= (const Bitset& rhs) const
00474     {
00475       return ! (*this > rhs);
00476     }
00477 
00478     inline
00479     bool
00480     Bitset::operator>= (const Bitset& rhs) const
00481     {
00482       return ! (*this < rhs);
00483     }
00484 
00485     inline
00486     Bitset
00487     Bitset::operator& (const Bitset& rhs) const
00488     {
00489       const size_type r_data_size = std::min (data_size_, rhs.data_size_);
00490       const size_type r_max_size = std::min (max_size_, rhs.max_size_);
00491       Bitset result (r_max_size);
00492 
00493       for (size_type i = 0; i < r_data_size; ++i)
00494       {
00495         result.data_[i] = data_[i] & rhs.data_[i];
00496         if (result.data_[i])
00497           result.size_ = invalid_size;
00498       }
00499       return result;
00500     }
00501 
00502     inline
00503     Bitset
00504     Bitset::operator| (const Bitset& rhs) const
00505     {
00506       if (rhs.data_size_ < data_size_)
00507         return rhs.operator| (*this);
00508       else
00509       {
00510         Bitset result (rhs.max_size_);
00511 
00512         for (size_type i = 0; i < data_size_; ++i)
00513         {
00514           result.data_[i] = data_[i] | rhs.data_[i];
00515           if (result.data_[i])
00516             result.size_ = invalid_size;
00517         }
00518         for (size_type i = data_size_; i < rhs.data_size_; ++i)
00519         {
00520           result.data_[i] = rhs.data_[i];
00521           if (result.data_[i])
00522             result.size_ = invalid_size;
00523         }
00524         return result;
00525       }
00526     }
00527 
00528     inline
00529     bool
00530     Bitset::operator[] (const key_type& x) const
00531     {
00532       return count (x);
00533     }
00534 
00535   /*------------------------------.
00536   | Projection and Unprojection.  |
00537   `------------------------------*/
00538 
00539     inline
00540     Bitset
00541     Bitset::project (const Bitset& b) const
00542     {
00543       BitActionCount<int, -1, 1> bit_counter;
00544       Bitset result (b.size ());
00545 
00546       for (bit_iterator it = bit_begin (), b_it = b.bit_begin ();
00547            it != bit_end () && b_it != b.bit_end ();
00548            ++it, ++b_it)
00549       {
00550         if (b.do_on_bit (bit_counter, b_it) && get_bit (it))
00551           result.insert (bit_counter.value);
00552       }
00553       return result;
00554     }
00555 
00556     inline
00557     Bitset
00558     Bitset::unproject (const Bitset& b) const
00559     {
00560       BitActionCount<int, 0, 1> bit_counter;
00561       Bitset result (b.max_size ());
00562       bit_iterator b_it = b.bit_begin ();
00563 
00564       while (b_it != b.bit_end () 
00565              && !b.get_bit (b_it))
00566         ++b_it;
00567       for (bit_iterator it = bit_begin (); it != bit_end (); ++it)
00568         if (get_bit (it))
00569         {
00570           while ( (b_it != b.bit_end ()) && (bit_counter.value < *it))
00571             b.do_on_bit (bit_counter, ++b_it);
00572           assertion (bit_counter.value == *it);
00573           result.insert (*b_it);
00574         }
00575       return result;
00576     }
00577 
00578   /*--------.
00579   | Casts.  |
00580   `--------*/
00581 
00582     inline
00583     unsigned
00584     Bitset::to_unsigned () const
00585     {
00586       return cast<unsigned> ();
00587     }
00588 
00589     template <class Type>
00590     const Type
00591     Bitset::cast () const
00592     {
00593       const Type* ptr = reinterpret_cast<const Type*> (data_);
00594       return *ptr;
00595     }
00596 
00597   /*--------.
00598   | Print.  |
00599   `--------*/
00600 
00601     inline
00602     std::ostream&
00603     Bitset::print (std::ostream& ostr) const
00604     {
00605       ostr << "{ ";
00606       for (Bitset::bit_iterator it = bit_begin (); it != bit_end (); ++it)
00607         if (get_bit (it))
00608           ostr << *it << ' ';
00609       return ostr << "}";
00610     }
00611 
00612   /*------------------.
00613   | Protected stuff.  |
00614   `------------------*/
00615 
00616     // get_data_size
00617     inline
00618     Bitset::size_type
00619     Bitset::get_data_size (size_type max)
00620     {
00621       precondition (max > 0);
00622 
00623       const size_type data_bits = sizeof (data_type) * 8;
00624       return max / data_bits + (max % data_bits ? 1 : 0);
00625     }
00626 
00627     // get_index
00628     inline
00629     Bitset::size_type
00630     Bitset::get_index (const key_type& x)
00631     {
00632       return x / (sizeof (data_type) * 8);
00633     }
00634 
00635     // get_bitnum
00636     inline
00637     Bitset::size_type
00638     Bitset::get_bitnum (const key_type& x)
00639     {
00640       return x % (sizeof (data_type) * 8);
00641     }
00642 
00643     // get_bit
00644     inline
00645     bool
00646     Bitset::get_bit (size_type index, size_type bit) const
00647     {
00648       return (data_[index] & (1 << bit)) != 0;
00649     }
00650 
00651     inline
00652     bool
00653     Bitset::get_bit (const bit_iterator& it) const
00654     {
00655       return get_bit (it.get_index (), it.get_bitnum ());
00656     }
00657 
00658     // compute_size
00659     inline
00660     Bitset::size_type
00661     Bitset::compute_size () const
00662     {
00663       BitActionCount<int, 0, 1> bc;
00664       for (bit_iterator it = bit_begin (); it != bit_end (); ++it)
00665         do_on_bit (bc, it);
00666       return size_ = bc.value;
00667     }
00668 
00669   /*---------------.
00670   | Bit iterator.  |
00671   `---------------*/
00672 
00673     // constructors.
00674     inline
00675     Bitset::
00676     bit_iterator::bit_iterator (size_type index, size_type bitnum) :
00677       index_     (index),
00678       bitnum_    (bitnum),
00679       value_     (index_ * sizeof (data_type) * 8 + bitnum_)
00680     {
00681     }
00682 
00683     // operators.
00684     inline
00685     const Bitset::bit_iterator&
00686     Bitset::bit_iterator::operator-- ()
00687     {
00688       --value_;
00689       if (bitnum_)
00690         --bitnum_;
00691       else
00692       {
00693         bitnum_ = sizeof (data_type) * 8 - 1;
00694         --index_;
00695       }
00696       return (*this);
00697     }
00698 
00699     inline
00700     const Bitset::bit_iterator&
00701     Bitset::bit_iterator::operator++ ()
00702     {
00703       ++value_;
00704       if (++bitnum_ >= sizeof (data_type) * 8)
00705       {
00706         bitnum_ = 0;
00707         ++index_;
00708       }
00709       return *this;
00710     }
00711 
00712     inline
00713     Bitset::value_type
00714     Bitset::bit_iterator::operator* () const
00715     {
00716       return value_;
00717     }
00718 
00719     inline
00720     bool
00721     Bitset::bit_iterator::operator== (const bit_iterator& rhs) const
00722     {
00723       return rhs.value_ == value_;
00724     }
00725 
00726     inline
00727     bool
00728     Bitset::bit_iterator::operator!= (const bit_iterator& rhs) const
00729     {
00730       return ! (*this == rhs);
00731     }
00732 
00733     // get_index
00734     inline
00735     Bitset::size_type
00736     Bitset::bit_iterator::get_index () const
00737     {
00738       return index_;
00739     }
00740 
00741     // get_bitnum
00742     inline
00743     Bitset::size_type
00744     Bitset::bit_iterator::get_bitnum () const
00745     {
00746       return bitnum_;
00747     }
00748 
00749     // bit_begin
00750     inline
00751     Bitset::bit_iterator
00752     Bitset::bit_begin () const
00753     {
00754       return bit_iterator ();
00755     }
00756 
00757     // bit_end
00758     inline
00759     const Bitset::bit_iterator&
00760     Bitset::bit_end () const
00761     {
00762       return end_;
00763     }
00764 
00765   /*--------------.
00766   | Bit actions.  |
00767   `--------------*/
00768 
00769     // Count
00770     template <typename CountType, CountType Start, CountType Step>
00771     Bitset::
00772     BitActionCount<CountType, Start, Step>::BitActionCount () : value (Start)
00773     {
00774     }
00775 
00776     template <typename CountType, CountType Start, CountType Step>
00777     bool
00778     Bitset::
00779     BitActionCount<CountType, Start, Step>::operator() (const Bitset&,
00780                                                         size_type,
00781                                                         size_type,
00782                                                         bool val)
00783     {
00784       if (val)
00785         value += Step;
00786       return val;
00787     }
00788 
00789   /*------------.
00790   | do_on_bit.  |
00791   `------------*/
00792 
00793     // non-const
00794     template <class BitAction>
00795     bool
00796     Bitset::do_on_bit (BitAction& action, const key_type& x)
00797     {
00798       precondition (x < max_size_);
00799 
00800       const size_type index = get_index (x);
00801       const size_type bit = get_bitnum (x);
00802       const bool value = get_bit (index, bit);
00803       return action (*this, index, bit, value);
00804     }
00805 
00806     template <class BitAction>
00807     bool
00808     Bitset::do_on_bit (BitAction& action, const bit_iterator& it)
00809     {
00810       return action (*this, it.get_index (), it.get_bitnum (), get_bit (it));
00811     }
00812 
00813     // const
00814     template <class ConstBitAction>
00815     bool
00816     Bitset::do_on_bit (ConstBitAction& action, const key_type& x) const
00817     {
00818       precondition (x < max_size_);
00819 
00820       const size_type index = get_index (x);
00821       const size_type bit = get_bitnum (x);
00822       const bool value = get_bit (index, bit);
00823       return action (*this, index, bit, value);
00824     }
00825 
00826     template <class ConstBitAction>
00827     bool
00828     Bitset::do_on_bit (ConstBitAction& action, const bit_iterator& it) const
00829     {
00830       return action (*this, it.get_index (), it.get_bitnum (), get_bit (it));
00831     }
00832 
00833   /*---------------.
00834   | const_iterator |
00835   `---------------*/
00836 
00837     // Default constructors.
00838     inline
00839     Bitset::const_iterator::const_iterator () : bs_ (0), cbit_ ()
00840     {
00841       WARNING ("The constructor Bitset::const_iterator::const_iterator () "
00842                "is dangerous and therefore should not be used.");
00843     }
00844 
00845     inline
00846     Bitset::const_iterator::const_iterator (const Bitset* bs) : bs_ (bs),
00847                                                                 cbit_ ()
00848     {
00849       skip_zeros_forward ();
00850     }
00851 
00852     inline
00853     Bitset::const_iterator::const_iterator (const Bitset* bs,
00854                                             const bit_iterator& cbit)
00855       : bs_ (bs),
00856         cbit_ (cbit)
00857     {
00858       skip_zeros_forward ();
00859     }
00860 
00861     // Copy constructors.
00862     inline
00863     Bitset::const_iterator::const_iterator (const const_iterator& it)
00864       : bs_ (it.bs_), cbit_ (it.cbit_)
00865     {
00866     }
00867 
00868     inline
00869     Bitset::const_iterator::const_iterator (const iterator& it)
00870       : bs_ (it.bs_), cbit_ (it.cbit_)
00871     {
00872     }
00873 
00874     // Operators.
00875     inline
00876     const Bitset::const_iterator&
00877     Bitset::const_iterator::operator++ ()
00878     {
00879       ++cbit_;
00880       skip_zeros_forward ();
00881       return *this;
00882     }
00883 
00884     inline
00885     Bitset::const_iterator
00886     Bitset::const_iterator::operator++ (int)
00887     {
00888       const_iterator ret (*this);
00889 
00890       operator++ ();
00891       return ret;
00892     }
00893 
00894     inline
00895     const Bitset::const_iterator&
00896     Bitset::const_iterator::operator-- ()
00897     {
00898       --cbit_;
00899       skip_zeros_backward ();
00900       return *this;
00901     }
00902 
00903     inline
00904     Bitset::const_iterator
00905     Bitset::const_iterator::operator-- (int)
00906     {
00907       const_iterator ret (*this);
00908 
00909       operator-- ();
00910       return ret;
00911     }
00912 
00913     inline
00914     bool
00915     Bitset::const_iterator::operator== (const const_iterator& rhs) const
00916     {
00917       return * (*this) == *rhs;
00918     }
00919 
00920     inline
00921     bool
00922     Bitset::const_iterator::operator== (const iterator& rhs) const
00923     {
00924       return * (*this) == *rhs;
00925     }
00926 
00927     inline
00928     bool
00929     Bitset::const_iterator::operator!= (const const_iterator& rhs) const
00930     {
00931       return ! (*this == rhs);
00932     }
00933 
00934     inline
00935     bool
00936     Bitset::const_iterator::operator!= (const iterator& rhs) const
00937     {
00938       return ! (*this == rhs);
00939     }
00940 
00941     inline
00942     Bitset::value_type
00943     Bitset::const_iterator::operator* () const
00944     {
00945       return *cbit_;
00946     }
00947 
00948     inline
00949     void
00950     Bitset::const_iterator::skip_zeros_forward ()
00951     {
00952       precondition (bs_ != 0);
00953 
00954       while ( (cbit_ != bs_->bit_end ()) && !bs_->get_bit (cbit_))
00955         ++cbit_;
00956     }
00957 
00958     inline
00959     void
00960     Bitset::const_iterator::skip_zeros_backward ()
00961     {
00962       precondition (bs_ != 0);
00963 
00964       while ( (cbit_ != bs_->bit_begin ()) && !bs_->get_bit (cbit_))
00965         --cbit_;
00966     }
00967 
00968   /*---------.
00969   | iterator |
00970   `---------*/
00971 
00972     // Default constructors.
00973     inline
00974     Bitset::iterator::iterator () : bs_ (0), cbit_ ()
00975     {
00976       WARNING ("The constructor Bitset::iterator::iterator () is dangerous "
00977                "and therefore should not be used.");
00978     }
00979 
00980     inline
00981     Bitset::iterator::iterator (const Bitset* bs)
00982       : bs_ (bs),
00983         cbit_ ()
00984     {
00985       skip_zeros_forward ();
00986     }
00987 
00988     inline
00989     Bitset::iterator::iterator (const Bitset* bs, const bit_iterator& cbit)
00990       : bs_ (bs),
00991         cbit_ (cbit)
00992     {
00993       skip_zeros_forward ();
00994     }
00995 
00996     // Copy constructor.
00997     inline
00998     Bitset::iterator::iterator (const iterator& it) : bs_ (it.bs_), cbit_ (it.cbit_)
00999     {
01000     }
01001 
01002     // Operators
01003     inline
01004     const Bitset::iterator&
01005     Bitset::iterator::operator++ ()
01006     {
01007       ++cbit_;
01008       skip_zeros_forward ();
01009       return *this;
01010     }
01011 
01012     inline
01013     Bitset::iterator
01014     Bitset::iterator::operator++ (int)
01015     {
01016       iterator res (*this);
01017 
01018       operator++ ();
01019       return res;
01020     }
01021 
01022     inline
01023     const Bitset::iterator&
01024     Bitset::iterator::operator-- ()
01025     {
01026       --cbit_;
01027       skip_zeros_backward ();
01028       return *this;
01029     }
01030 
01031     inline
01032     Bitset::iterator
01033     Bitset::iterator::operator-- (int)
01034     {
01035       iterator res (*this);
01036 
01037       operator-- ();
01038       return res;
01039     }
01040 
01041     inline
01042     bool
01043     Bitset::iterator::operator== (const iterator& rhs) const
01044     {
01045       return * (*this) == *rhs;
01046     }
01047 
01048     inline
01049     bool
01050     Bitset::iterator::operator== (const const_iterator& rhs) const
01051     {
01052       return * (*this) == *rhs;
01053     }
01054 
01055     inline
01056     bool
01057     Bitset::iterator::operator!= (const iterator& rhs) const
01058     {
01059       return ! (*this == rhs);
01060     }
01061 
01062     inline
01063     bool
01064     Bitset::iterator::operator!= (const const_iterator& rhs) const
01065     {
01066       return ! (*this == rhs);
01067     }
01068 
01069     inline
01070     Bitset::value_type
01071     Bitset::iterator::operator* () const
01072     {
01073       return *cbit_;
01074     }
01075 
01076     inline
01077     void
01078     Bitset::iterator::skip_zeros_forward ()
01079     {
01080       precondition (bs_ != 0);
01081 
01082       while ( (cbit_ != bs_->bit_end ()) && !bs_->get_bit (cbit_))
01083         ++cbit_;
01084     }
01085 
01086     inline
01087     void
01088     Bitset::iterator::skip_zeros_backward ()
01089     {
01090       precondition (bs_ != 0);
01091 
01092       while ( (cbit_ != bs_->bit_begin ()) && !bs_->get_bit (cbit_))
01093         --cbit_;
01094     }
01095 
01096     inline
01097     std::ostream&
01098     operator<< (std::ostream& ostr, const Bitset& set)
01099     {
01100       return set.print (ostr);
01101     }
01102 
01103   } // namespace misc
01104 } // namespace vcsn
01105 
01106 namespace std
01107 {
01108   template <>
01109   inline
01110   void swap (vcsn::misc::Bitset& lhs, vcsn::misc::Bitset& rhs)
01111   {
01112     lhs.swap (rhs);
01113   }
01114 
01115   inline
01116   insert_iterator<vcsn::misc::Bitset>::
01117   insert_iterator (vcsn::misc::Bitset& x,
01118                    vcsn::misc::Bitset::iterator)
01119   {
01120     container = &x;
01121   }
01122 
01123   inline
01124   insert_iterator<vcsn::misc::Bitset>&
01125   insert_iterator<vcsn::misc::Bitset>::operator= (vcsn::misc::Bitset::
01126                                                   const_reference value)
01127   {
01128     container->insert (value);
01129     return *this;
01130   }
01131 
01132   inline
01133   insert_iterator<vcsn::misc::Bitset>&
01134   insert_iterator<vcsn::misc::Bitset>::operator* ()
01135   {
01136     return *this;
01137   }
01138 
01139   inline
01140   insert_iterator<vcsn::misc::Bitset>&
01141   insert_iterator<vcsn::misc::Bitset>::operator++ ()
01142   {
01143     return *this;
01144   }
01145 
01146   inline
01147   insert_iterator<vcsn::misc::Bitset>&
01148   insert_iterator<vcsn::misc::Bitset>::operator++ (int)
01149   {
01150     return *this;
01151   }
01152 }
01153 
01154 #endif // ! VCSN_MISC_BITSET_HXX

Generated on Wed Jun 13 17:00:21 2007 for Vaucanson by  doxygen 1.5.1