bitset.hh

Go to the documentation of this file.
00001 // bitset.hh: 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_HH
00018 # define VCSN_MISC_BITSET_HH
00019 
00028 # include <iterator>
00029 # include <iostream>
00030 # include <functional>
00031 
00032 namespace vcsn
00033 {
00034   namespace misc
00035   {
00036 
00045     struct Bitset
00046     {
00047         typedef int                     key_type;
00048         typedef int                     value_type;
00049         typedef std::less<key_type>     key_compare;
00050         typedef key_compare             value_compare;
00051         // FIXME: Missing to be std::set compliant: allocator_type.
00052         // FIXME: reference and const_reference are not real references, because
00053         // it would prevents a code using a reverse_iterator to compile.
00054         typedef value_type              reference;
00055         typedef const value_type        const_reference;
00056         struct                          iterator;
00057         struct                          const_iterator;
00058         typedef unsigned int            size_type;
00059         typedef int                     difference_type;
00060         typedef value_type*             pointer;
00061         typedef const value_type*       const_pointer;
00062         typedef std::reverse_iterator<iterator>         reverse_iterator;
00063         typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
00064 
00065         // data_type is the type used for the bit field.
00066         typedef unsigned int            data_type;
00067 
00068         // FIXME: Constructors have almost nothing common to std::set.
00069 
00075         Bitset (size_type max);
00076 
00078         Bitset (size_type max, const data_type* data);
00079 
00081         Bitset (const Bitset& bs);
00082 
00084         template <class InputIterator>
00085         Bitset (InputIterator first, InputIterator last);
00086 
00088         ~Bitset ();
00089 
00091         Bitset& operator= (const Bitset& rhs);
00092 
00094 
00095         iterator        begin ();
00096         const_iterator  begin () const;
00097         iterator        end ();
00098         const_iterator  end () const;
00101 
00102 
00103         reverse_iterator                rbegin ();
00104         const_reverse_iterator  rbegin () const;
00105         reverse_iterator                rend ();
00106         const_reverse_iterator  rend () const;
00109         bool    empty () const;
00110         size_type       size () const;
00111         size_type       max_size () const;
00112 
00114 
00115         std::pair<iterator, bool>       insert (const value_type& x);
00116         iterator                        insert (iterator position, const value_type& x);
00117         template <class InputIterator>
00118         void                    insert (InputIterator first,
00119                                         InputIterator last);
00122 
00123 
00124         void    erase (iterator position);
00125         size_type       erase (const key_type& x);
00126         void    erase (iterator first, iterator last);
00129 
00130         void    swap (Bitset& other);
00131 
00133         void    clear ();
00134 
00135         key_compare             key_comp () const;
00136         value_compare   value_comp () const;
00137 
00139         iterator        find (const key_type& x) const;
00140 
00142         size_type       count (const key_type& x) const;
00143 
00144         iterator                                lower_bound (const key_type& x) const;
00145         iterator                                upper_bound (const key_type& x) const;
00146         std::pair<iterator, iterator>   equal_range (const key_type& x) const;
00147 
00148         bool    operator== (const Bitset& rhs) const;
00149         bool    operator< (const Bitset& rhs) const;
00150         bool    operator!= (const Bitset& rhs) const;
00151         bool    operator> (const Bitset& rhs) const;
00152         bool    operator>= (const Bitset& rhs) const;
00153         bool    operator<= (const Bitset& rhs) const;
00154 
00155         Bitset  operator& (const Bitset& rhs) const;
00156         Bitset  operator| (const Bitset& rhs) const;
00157 
00159         bool    operator[] (const key_type& x) const;
00160 
00162         Bitset  project (const Bitset& b) const;
00163 
00171         Bitset  unproject (const Bitset& b) const;
00172 
00174         unsigned        to_unsigned () const;
00175 
00177         template <typename Type>
00178         const Type      cast () const;
00179 
00181         std::ostream&   print (std::ostream& ostr) const;
00182 
00183       protected:
00185         static
00186         size_type       get_data_size (size_type max);
00187 
00189         static
00190         size_type       get_index (const key_type& x);
00191 
00193         static
00194         size_type       get_bitnum (const key_type& x);
00195 
00197         bool    get_bit (size_type index, size_type bit) const;
00198 
00200         size_type       compute_size () const;
00201 
00202     /*-------------------.
00203     | Iterator on bits.  |
00204     `-------------------*/
00205         struct bit_iterator
00206         {
00207             bit_iterator (size_type index = 0, size_type bitnum = 0);
00208             const bit_iterator& operator-- ();
00209             const bit_iterator& operator++ ();
00210             value_type          operator* () const;
00211             bool                operator== (const bit_iterator& rhs) const;
00212             bool                operator!= (const bit_iterator& rhs) const;
00213             size_type           get_index () const;
00214             size_type           get_bitnum () const;
00215           protected:
00216             size_type   index_;
00217             size_type   bitnum_;
00218             value_type  value_;
00219         };
00220 
00221         bit_iterator            bit_begin () const;
00222         const bit_iterator&     bit_end () const;
00223 
00225         bool get_bit (const bit_iterator& it) const;
00226 
00227     /*------------------.
00228     | Actions on bits.  |
00229     `------------------*/
00230 
00231         template <typename CountType, CountType Start, CountType Step>
00232         struct BitActionCount
00233         {
00234             BitActionCount ();
00235             CountType value;
00236             bool operator() (const Bitset& bitset,
00237                               size_type index,
00238                               size_type bit,
00239                               bool value);
00240         };
00241 
00242     /*--------------------------------.
00243     | do_on_bit (BitAction, element_t) |
00244     `--------------------------------*/
00245 
00247 
00248         template <class BitAction>
00249         bool    do_on_bit (BitAction& action, const key_type& x);
00250         template <class BitAction>
00251         bool    do_on_bit (BitAction& action, const bit_iterator& it);
00254 
00255 
00256         template <class ConstBitAction>
00257         bool    do_on_bit (ConstBitAction& action, const key_type& x) const;
00258         template <class ConstBitAction>
00259         bool    do_on_bit (ConstBitAction& action,
00260                            const bit_iterator& it) const;
00263     /*-------------------.
00264     | Attributes, misc.  |
00265     `-------------------*/
00266 
00267         enum { invalid_size = static_cast <unsigned int> (-1) };
00268 
00269         size_type               data_size_;
00270         data_type*              data_;
00271 
00272         size_type               max_size_;
00273         mutable size_type       size_;
00274         bit_iterator            end_;
00275 
00276       public:
00277 
00278     /*-----------------.
00279     | const_iterator.  |
00280     `-----------------*/
00281 
00282         struct const_iterator
00283         {
00284             typedef std::bidirectional_iterator_tag iterator_category;
00285             typedef Bitset::value_type              value_type;
00286             typedef Bitset::difference_type         difference_type;
00287             typedef Bitset::reference               reference;
00288             typedef Bitset::pointer                 pointer;
00289 
00290             const_iterator ();
00291             const_iterator (const Bitset* bs);
00292             const_iterator (const Bitset* bs, const bit_iterator& cbit);
00293             const_iterator (const const_iterator& it);
00294             const_iterator (const iterator& it);
00295 
00296             const const_iterator& operator++ ();
00297             const_iterator        operator++ (int);
00298             const const_iterator& operator-- ();
00299             const_iterator        operator-- (int);
00300             bool                  operator== (const const_iterator& rhs) const;
00301             bool                  operator== (const iterator& rhs) const;
00302             bool                  operator!= (const const_iterator& rhs) const;
00303             bool                  operator!= (const iterator& rhs) const;
00304             value_type            operator* () const;
00305 
00306           protected:
00307             void                  skip_zeros_forward ();
00308             void                  skip_zeros_backward ();
00309 
00310             const Bitset* bs_;
00311             bit_iterator  cbit_;
00312         };
00313 
00314     /*-----------.
00315     | iterator.  |
00316     `-----------*/
00317 
00318         struct iterator
00319         {
00320             typedef std::bidirectional_iterator_tag     iterator_category;
00321             typedef Bitset::value_type                  value_type;
00322             typedef Bitset::difference_type             difference_type;
00323             typedef Bitset::reference                   reference;
00324             typedef Bitset::pointer                     pointer;
00325 
00326             iterator ();
00327             iterator (const Bitset* bs);
00328             iterator (const Bitset* bs, const bit_iterator& cbit);
00329             iterator (const iterator& it);
00330 
00331             // Friend functions for const_iterator
00332             friend const_iterator::const_iterator (const iterator& it);
00333 
00334             const iterator&     operator++ ();
00335             iterator            operator++ (int);
00336             const iterator&     operator-- ();
00337             iterator            operator-- (int);
00338             bool                operator== (const iterator& rhs) const;
00339             bool                operator== (const const_iterator& rhs) const;
00340             bool                operator!= (const iterator& rhs) const;
00341             bool                operator!= (const const_iterator& rhs) const;
00342             value_type          operator* () const;
00343 
00344           protected:
00345             void                skip_zeros_forward ();
00346             void                skip_zeros_backward ();
00347 
00348             const Bitset* bs_;
00349             bit_iterator  cbit_;
00350         };
00351     };
00352 
00353 
00355     std::ostream&
00356     operator<< (std::ostream& ostr, const Bitset& set);
00357 
00358   } // end of namespace misc.
00359 } // end of namespace vcsn.
00360 
00361 namespace std
00362 {
00364   template <>
00365   void swap (vcsn::misc::Bitset& lhs, vcsn::misc::Bitset& rhs);
00366 
00368   template <>
00369   class insert_iterator<vcsn::misc::Bitset> :
00370       public iterator<output_iterator_tag, void, void, void, void>
00371   {
00372     public:
00373       typedef vcsn::misc::Bitset container_type;
00374 
00375       insert_iterator (vcsn::misc::Bitset& x, vcsn::misc::Bitset::iterator);
00376       insert_iterator<vcsn::misc::Bitset>&
00377       operator= (vcsn::misc::Bitset::const_reference value);
00378       insert_iterator<vcsn::misc::Bitset>& operator* ();
00379       insert_iterator<vcsn::misc::Bitset>& operator++ ();
00380       insert_iterator<vcsn::misc::Bitset>& operator++ (int);
00381     protected:
00382       vcsn::misc::Bitset* container;
00383   };
00384 }
00385 
00386 
00387 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00388 #  include <vaucanson/misc/bitset.hxx>
00389 # endif // VCSN_USE_INTERFACE_ONLY
00390 
00391 
00392 #endif // ! VCSN_MISC_BITSET_HH

Generated on Sun Jul 29 19:35:18 2007 for Vaucanson by  doxygen 1.5.2