00001 #ifndef DV_UTIL_BITMAP_H
00002 #define DV_UTIL_BITMAP_H
00003
00004
00005 #include <stdlib.h>
00006 #include <iostream>
00007 #include <stdexcept>
00008
00009 namespace Dv {
00010 namespace Util {
00011
00012
00013
00014
00015
00016 class Bitmap {
00017 public:
00018 typedef size_t Chunk;
00019
00020
00021
00022
00023
00024 Bitmap(size_t n_bits, bool initial_value): size_(n_bits), data_(new size_t[n_chunks()]) {
00025 for (size_t i=0; (i<n_chunks()); ++i)
00026 data_[i] = (initial_value ? ~0 : 0 );
00027 }
00028
00029
00030 ~Bitmap() {
00031 delete [] data_;
00032 }
00033
00034
00035
00036
00037
00038
00039 bool get(size_t i) const {
00040 Chunk mask = 1;
00041 mask <<= (i% sizeof(Chunk));
00042 return data_[i/sizeof(Chunk)] & mask;
00043 }
00044
00045
00046
00047
00048
00049 void set(size_t i) throw (std::range_error) {
00050 if (i>=size())
00051 throw std::range_error("Dv::Util::Bitmap::operator[]: index too big");
00052 Chunk mask = 1;
00053 mask <<= (i% sizeof(Chunk));
00054 data_[i/sizeof(Chunk)] |= mask;
00055 }
00056
00057
00058
00059
00060
00061 void clear(size_t i) throw (std::range_error) {
00062 if (i>=size())
00063 throw std::range_error("Dv::Util::Bitmap::operator[]: index too big");
00064 Chunk mask = 1;
00065 mask <<= (i% sizeof(Chunk));
00066 data_[i/sizeof(Chunk)] &= ~mask;
00067 }
00068
00069
00070
00071
00072
00073
00074 bool operator[](size_t i) const throw(std::range_error) {
00075 if (i>=size())
00076 throw std::range_error("Dv::Util::Bitmap::operator[]: index too big");
00077 return get(i);
00078 }
00079
00080
00081 size_t size() const { return size_; }
00082
00083 size_t n_chunks() const { return size()/sizeof(Chunk) +1; }
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093 std::ostream& print(std::ostream& os) const {
00094 for (size_t i=0; i<size(); ++i)
00095 os << ( get(i) ? "1" : "0" );
00096 return os;
00097 }
00098 private:
00099 size_t size_;
00100 Chunk *data_;
00101 };
00102
00103 inline std::ostream& operator<<(std::ostream& os, const Bitmap& map) {
00104 return map.print(os);
00105 }
00106 }
00107 }
00108 #endif
00109