00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035 #ifndef _BITSETS_H_
00036 #define _BITSETS_H_
00037
00038 #include "chomp/system/config.h"
00039
00040 #include <iostream>
00041 #include <cstdlib>
00042
00043 namespace chomp {
00044 namespace homology {
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058 class BitSets
00059 {
00060 public:
00061
00062
00063
00064 BitSets (int _nsets, int _nelem);
00065
00066
00067 BitSets (const BitSets &s);
00068
00069
00070 BitSets &operator = (const BitSets &s);
00071
00072
00073 ~BitSets ();
00074
00075
00076 void add (int n, int e);
00077
00078
00079 void remove (int n, int e);
00080
00081
00082 bool check (int n, int e) const;
00083
00084
00085 void addset (int n, int m);
00086
00087
00088
00089 int get (int n, int start = 0) const;
00090
00091 private:
00092
00093 int nsets;
00094
00095
00096 int nelem;
00097
00098
00099 int nbytes;
00100
00101
00102 unsigned char *bits;
00103
00104 };
00105
00106
00107
00108 inline BitSets::BitSets (int _nsets, int _nelem):
00109 nsets (_nsets), nelem (_nelem), nbytes ((_nelem + 7) >> 3), bits (0)
00110 {
00111 int size = nsets * nbytes;
00112 bits = new unsigned char [size];
00113 for (int i = 0; i < size; ++ i)
00114 bits [i] = 0;
00115 return;
00116 }
00117
00118 inline BitSets::BitSets (const BitSets &s):
00119 nsets (s. nsets), nelem (s. nelem), nbytes (s. nbytes), bits (0)
00120 {
00121 int size = nsets * nbytes;
00122 bits = new unsigned char [size];
00123 for (int i = 0; i < size; ++ i)
00124 bits [i] = s. bits [i];
00125 return;
00126 }
00127
00128 inline BitSets &BitSets::operator = (const BitSets &s)
00129 {
00130 delete [] bits;
00131 nsets = s. nsets;
00132 nelem = s. nelem;
00133 nbytes = s. nbytes;
00134 int size = nsets * nbytes;
00135 bits = new unsigned char [size];
00136 for (int i = 0; i < size; ++ i)
00137 bits [i] = s. bits [i];
00138 return *this;
00139 }
00140
00141 inline BitSets::~BitSets ()
00142 {
00143 delete [] bits;
00144 return;
00145 }
00146
00147 inline void BitSets::add (int n, int e)
00148 {
00149
00150 unsigned char *buf = bits + n * nbytes;
00151 buf [e >> 3] |= (unsigned char) (0x01 << (e & 0x07));
00152 return;
00153 }
00154
00155 inline void BitSets::remove (int n, int e)
00156 {
00157 unsigned char *buf = bits + n * nbytes;
00158 buf [e >> 3] &= (unsigned char) ~(0x01 << (e & 0x07));
00159 return;
00160 }
00161
00162 inline bool BitSets::check (int n, int e) const
00163 {
00164 unsigned char *buf = bits + n * nbytes;
00165 return !!(buf [e >> 3] & (0x01 << (e & 0x07)));
00166 }
00167
00168 inline void BitSets::addset (int n, int m)
00169 {
00170 unsigned char *nbuf = bits + n * nbytes;
00171 unsigned char *mbuf = bits + m * nbytes;
00172 for (int i = 0; i < nbytes; ++ i)
00173 *(nbuf ++) |= *(mbuf ++);
00174 return;
00175 }
00176
00177 inline int BitSets::get (int n, int start) const
00178 {
00179 if (start >= nelem)
00180 return -1;
00181 unsigned char *buf = bits + n * nbytes;
00182 int offset = start >> 3;
00183 int bit = start & 0x07;
00184 if (buf [offset] & (0xFF << bit))
00185 {
00186 for (; bit < 8; ++ bit)
00187 {
00188 if (buf [offset] & (0x01 << bit))
00189 return (offset << 3) + bit;
00190 }
00191 throw "Wrong bit number in BitSets.";
00192 }
00193 for (++ offset; offset < nbytes; ++ offset)
00194 {
00195 if (!buf [offset])
00196 continue;
00197 for (int bit = 0; bit < 8; ++ bit)
00198 {
00199 if (buf [offset] & (0x01 << bit))
00200 return (offset << 3) + bit;
00201 }
00202 throw "False bit in BitSets.";
00203 }
00204 return -1;
00205 }
00206
00207
00208 }
00209 }
00210
00211 #endif // _BITSETS_H_
00212
00213
00214