|
Vaucanson 1.4
|
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
1.7.4