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
00036 #ifndef _MULTITAB_H_
00037 #define _MULTITAB_H_
00038
00039 #include "chomp/system/config.h"
00040
00041
00042
00043
00044
00045
00046
00047 namespace chomp {
00048 namespace homology {
00049
00050
00051
00052
00053
00054
00055 template <typename T>
00056 inline void my_swap (T &x, T &y)
00057 {
00058 T tmp = x;
00059 x = y;
00060 y = tmp;
00061 return;
00062 }
00063
00064
00065
00066
00067
00068
00069
00070 #define DEFAULTPIECESIZE 32
00071
00072
00073
00074
00075
00076
00077 template <class element>
00078 class multitable
00079 {
00080 public:
00081
00082
00083 multitable (int piecesize = 0);
00084
00085
00086 multitable (const multitable<element> &m);
00087
00088
00089 multitable<element> &operator = (const multitable<element> &m);
00090
00091
00092 ~multitable ();
00093
00094
00095
00096
00097 element &operator [] (int n);
00098
00099
00100
00101 const element &operator () (int n) const;
00102
00103
00104
00105 const element &operator [] (int n) const;
00106
00107
00108
00109 void allocate (int n);
00110
00111
00112
00113 void fill (const element &e, int n);
00114
00115
00116 void swap (multitable<element> &other);
00117
00118 private:
00119
00120 int npieces;
00121
00122
00123
00124 int shiftbits;
00125
00126
00127 int offsetmask;
00128
00129
00130 element **tab;
00131
00132
00133 void increase (int n);
00134
00135 };
00136
00137
00138
00139 template <class element>
00140 inline multitable<element>::multitable (int piecesize)
00141 {
00142 tab = 0;
00143 npieces = 0;
00144 if (piecesize <= 0)
00145 piecesize = DEFAULTPIECESIZE;
00146 shiftbits = 1;
00147 while ((1 << shiftbits) < piecesize)
00148 ++ shiftbits;
00149 offsetmask = (1 << shiftbits) - 1;
00150 return;
00151 }
00152
00153 template <class element>
00154 multitable<element>::multitable (const multitable<element> &m):
00155 npieces (m. npieces), shiftbits (m. shiftbits),
00156 offsetmask (m. offsetmask)
00157 {
00158 int piecesize = 1 << shiftbits;
00159 tab = new element * [npieces];
00160 if (!tab)
00161 throw "Cannot alloc mem in copying constructor of a table.";
00162 for (int i = 0; i < npieces; ++ i)
00163 if (m. tab [i])
00164 {
00165 tab [i] = new element [piecesize];
00166 if (!tab [i])
00167 throw "No memory in copying constr.";
00168 for (int j = 0; j < piecesize; ++ j)
00169 tab [i] [j] = m. tab [i] [j];
00170 }
00171 else
00172 tab [i] = 0;
00173 return;
00174 }
00175
00176 template <class element>
00177 multitable<element> &multitable<element>::operator =
00178 (const multitable<element> &m)
00179 {
00180
00181 int deallocated = 0;
00182
00183
00184 if (shiftbits != m. shiftbits)
00185 {
00186
00187 for (int i = 0; i < npieces; ++ i)
00188 if (tab [i])
00189 {
00190 delete [] tab [i];
00191 tab [i] = 0;
00192 }
00193
00194 deallocated = 1;
00195 shiftbits = m. shiftbits;
00196 offsetmask = m. offsetmask;
00197 }
00198
00199
00200
00201
00202 if (npieces != m. npieces)
00203 {
00204
00205 element **newtab = (m. npieces) ?
00206 (new element * [m. npieces]) : 0;
00207 if (!newtab && m. npieces)
00208 throw "No memory for a table in operator =.";
00209
00210
00211
00212
00213 if (!deallocated)
00214 {
00215
00216
00217 int i = 0, j = 0;
00218 while (i < m. npieces)
00219 {
00220
00221 while ((j < npieces) && !tab [j])
00222 j ++;
00223
00224 if (j < npieces)
00225 newtab [i ++] = tab [j ++];
00226
00227 else
00228 while (i < m. npieces)
00229 newtab [i ++] = 0;
00230 }
00231
00232 while (j < npieces)
00233 {
00234 if (tab [j])
00235 delete [] tab [j];
00236 j ++;
00237 }
00238 }
00239 else
00240 {
00241 for (int i = 0; i < m. npieces; i ++)
00242 newtab [i] = 0;
00243 }
00244
00245 if (tab)
00246 delete [] tab;
00247 tab = newtab;
00248 npieces = m. npieces;
00249 }
00250
00251
00252 if (!npieces)
00253 return *this;
00254
00255
00256
00257 int first_nonempty = 0, first_empty = 0, pos = 0;
00258 int piecesize = 1 << shiftbits;
00259
00260
00261 while ((first_nonempty < npieces) && !tab [first_nonempty])
00262 first_nonempty ++;
00263 while ((first_empty < npieces) && tab [first_empty])
00264 first_empty ++;
00265
00266
00267 while (pos < npieces)
00268 {
00269 if (m. tab [pos])
00270 {
00271 if (!tab [pos])
00272 {
00273 if (first_nonempty < npieces)
00274 {
00275 tab [pos] = tab [first_nonempty];
00276 tab [first_nonempty ++] = 0;
00277 }
00278 else
00279 {
00280 tab [pos] = new element [piecesize];
00281 if (!tab [pos])
00282 throw "Error in operator =.";
00283 }
00284 first_empty ++;
00285 }
00286 else
00287 first_nonempty ++;
00288
00289
00290 for (int i = 0; i < (1 << shiftbits); i ++)
00291 tab [pos] [i] = m. tab [pos] [i];
00292 }
00293 else if (tab [pos])
00294 {
00295 if (first_empty < npieces)
00296 {
00297 tab [first_empty] = tab [pos];
00298 first_empty ++;
00299 }
00300 else
00301 delete [] tab [pos];
00302 first_nonempty ++;
00303 tab [pos] = 0;
00304 }
00305 else
00306 first_empty ++;
00307
00308
00309 pos ++;
00310
00311
00312 while ((first_nonempty < npieces) && !tab [first_nonempty])
00313 first_nonempty ++;
00314 while ((first_empty < npieces) && tab [first_empty])
00315 first_empty ++;
00316 }
00317
00318 return *this;
00319 }
00320
00321 template <class element>
00322 inline multitable<element>::~multitable ()
00323 {
00324 if (!tab)
00325 return;
00326 for (int i = 0; i < npieces; i ++)
00327 if (tab [i])
00328 delete [] tab [i];
00329 delete [] tab;
00330 return;
00331 }
00332
00333 template <class element>
00334 inline element &multitable<element>::operator [] (int n)
00335 {
00336 if (n < 0)
00337 throw "Negative index of an element in a table used.";
00338
00339
00340 int piece = n >> shiftbits;
00341
00342
00343 if (piece >= npieces)
00344 {
00345 int newnpieces = 2 * npieces + 1;
00346 if (newnpieces <= piece)
00347 newnpieces = piece + 1;
00348 increase (newnpieces);
00349 }
00350
00351
00352 if (!tab [piece])
00353 {
00354 tab [piece] = new element [1 << shiftbits];
00355 if (!tab [piece])
00356 throw "Cannot allocate a piece of a table";
00357 }
00358
00359 return tab [piece] [n & offsetmask];
00360 }
00361
00362 template <class element>
00363 inline const element &multitable<element>::operator () (int n) const
00364 {
00365 if (n < 0)
00366 throw "Negative index of an element in a table used.";
00367
00368
00369 int piece = n >> shiftbits;
00370
00371 if ((piece >= npieces) || (!tab [piece]))
00372 throw "Non-existent table entry requested.";
00373
00374 return tab [piece] [n & offsetmask];
00375 }
00376
00377 template <class element>
00378 inline const element &multitable<element>::operator [] (int n) const
00379 {
00380 return (*this) (n);
00381 }
00382
00383 template <class element>
00384 void multitable<element>::allocate (int n)
00385 {
00386 if (n <= 0)
00387 return;
00388 int piecesize = 1 << shiftbits;
00389 int necessarypieces = (n + piecesize - 1) / piecesize;
00390
00391
00392 if (necessarypieces > npieces)
00393 increase (necessarypieces);
00394
00395
00396 for (int i = necessarypieces; i < npieces; i ++)
00397 if (tab [i])
00398 {
00399 delete [] tab [i];
00400 tab [i] = 0;
00401 }
00402 return;
00403 }
00404
00405 template <class element>
00406 void multitable<element>::fill (const element &e, int n)
00407 {
00408 if (n <= 0)
00409 return;
00410 int piecesize = 1 << shiftbits;
00411 int maxpiece = (n + piecesize - 1) / piecesize;
00412 if (maxpiece > npieces)
00413 increase (maxpiece);
00414 for (int piece = 0; piece < maxpiece; piece ++)
00415 {
00416 if (!tab [piece])
00417 {
00418 tab [piece] = new element [piecesize];
00419 if (!tab [piece])
00420 throw "Too little mem for a piece.";
00421
00422 }
00423 if ((piece == maxpiece - 1) && (n & offsetmask))
00424 piecesize = n & offsetmask;
00425 for (int i = 0; i < piecesize; i ++)
00426 tab [piece] [i] = e;
00427 }
00428 return;
00429 }
00430
00431 template <class element>
00432 inline void multitable<element>::swap (multitable<element> &other)
00433 {
00434 my_swap (npieces, other. npieces);
00435 my_swap (shiftbits, other. shiftbits);
00436 my_swap (offsetmask, other. offsetmask);
00437 my_swap (tab, other. tab);
00438 return;
00439 }
00440
00441 template <class element>
00442 void multitable<element>::increase (int n)
00443 {
00444
00445
00446
00447 if (n <= npieces)
00448 throw "Trying to increase a multitable incorrectly.";
00449 element **newtab = new element * [n];
00450 if (!newtab)
00451 throw "Cannot increase a table.";
00452 int i;
00453 for (i = 0; i < npieces; i ++)
00454 newtab [i] = tab [i];
00455 for (i = npieces; i < n; i ++)
00456 newtab [i] = 0;
00457 delete [] tab;
00458 tab = newtab;
00459 npieces = n;
00460 return;
00461 }
00462
00463
00464 }
00465 }
00466
00467 #endif // _MULTITAB_H_
00468
00469
00470