chomp/struct/multitab.h

Go to the documentation of this file.
00001 /// @addtogroup struct
00002 /// @{
00003 
00004 /////////////////////////////////////////////////////////////////////////////
00005 ///
00006 /// @file multitab.h
00007 ///
00008 /// This file contains the definition of the container "multitable"
00009 /// which is essentially an automatically extendable array whose memory
00010 /// is allocated in small chunks which hold the elements.
00011 ///
00012 /// @author Pawel Pilarczyk
00013 ///
00014 /////////////////////////////////////////////////////////////////////////////
00015 
00016 // Copyright (C) 1997-2007 by Pawel Pilarczyk.
00017 //
00018 // This file is part of the Homology Library.  This library is free software;
00019 // you can redistribute it and/or modify it under the terms of the GNU
00020 // General Public License as published by the Free Software Foundation;
00021 // either version 2 of the License, or (at your option) any later version.
00022 //
00023 // This library is distributed in the hope that it will be useful,
00024 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00025 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00026 // GNU General Public License for more details.
00027 //
00028 // You should have received a copy of the GNU General Public License along
00029 // with this software; see the file "license.txt".  If not, write to the
00030 // Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
00031 // MA 02111-1307, USA.
00032 
00033 // Started in January 2002. Last revision: February 21, 2007.
00034 
00035 
00036 #ifndef _MULTITAB_H_
00037 #define _MULTITAB_H_
00038 
00039 #include "chomp/system/config.h"
00040 //#include "chomp/system/textfile.h"
00041 //#include "chomp/struct/integer.h"
00042 
00043 //#include <cstdlib>
00044 //#include <ctime>
00045 //#include <iostream>
00046 
00047 namespace chomp {
00048 namespace homology {
00049 
00050 
00051 // --------------------------------------------------
00052 // ------------------- swap data --------------------
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 } /* my_swap */
00063 
00064 
00065 // --------------------------------------------------
00066 // ------------------ multi table -------------------
00067 // --------------------------------------------------
00068 
00069 /// The default size of a piece used in the multi-table.
00070 #define DEFAULTPIECESIZE 32
00071 
00072 /// A container for elements placed in a table (like a vector)
00073 /// that is actually built of many smaller tables. This may be important
00074 /// for good memory allocation.
00075 /// The table extends automatically upon use of elements that are outside
00076 /// the range of its indices.
00077 template <class element>
00078 class multitable
00079 {
00080 public:
00081         /// The default constructor for a table with the given size
00082         /// of each piece (should be a power of 2 or is rounded up).
00083         multitable (int piecesize = 0);
00084 
00085         /// The copy constructor.
00086         multitable (const multitable<element> &m);
00087 
00088         /// The assignment operator.
00089         multitable<element> &operator = (const multitable<element> &m);
00090 
00091         /// The destructor.
00092         ~multitable ();
00093 
00094         /// Returns a reference of an element for reading/writing.
00095         /// If the index is out of range, the table is automatically
00096         /// extended.
00097         element &operator [] (int n);
00098 
00099         /// Returns a reference of an element for reading only.
00100         /// Throws an error message if the index is out of range.
00101         const element &operator () (int n) const;
00102 
00103         /// Returns a reference of an element for reading only.
00104         /// Throws an error message if the index is out of range.
00105         const element &operator [] (int n) const;
00106 
00107         /// Allocates the table for holding 'n' elements.
00108         /// The table is still able to grow further if necessary.
00109         void allocate (int n);
00110 
00111         /// Fills the table from 0 to the given index
00112         /// with the given element.
00113         void fill (const element &e, int n);
00114 
00115         /// Swaps data with another multitable object.
00116         void swap (multitable<element> &other);
00117 
00118 private:
00119         /// The number of pieces ready to allocate.
00120         int npieces;
00121 
00122         /// The number of bits to shift the index of an element
00123         /// in the table.
00124         int shiftbits;
00125 
00126         /// The mask to get the offset of an element in a table piece.
00127         int offsetmask;
00128 
00129         /// The actual tables.
00130         element **tab;
00131 
00132         /// Increases the number of pieces to the desired one.
00133         void increase (int n);
00134 
00135 }; /* class multitable */
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 } /* multitable<element>::multitable */
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 } /* multitable<element>::multitable */
00175 
00176 template <class element>
00177 multitable<element> &multitable<element>::operator =
00178         (const multitable<element> &m)
00179 {
00180         // have all the tables been deallocated?
00181         int deallocated = 0;
00182 
00183         // if the size of pieces does not match, they must be deallocated
00184         if (shiftbits != m. shiftbits)
00185         {
00186                 // deallocate all the pieces
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         // if the number of pieces is not the same, change the table
00200         // and for the moment gather in the new table all the pieces
00201         // that are already allocated
00202         if (npieces != m. npieces)
00203         {
00204                 // allocate a new table of pieces
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                 // if there may be some not deallocated elements,
00211                 // gather them at the beginning of the table
00212                 // and set the rest of the pointers to 0s
00213                 if (!deallocated)
00214                 {
00215                         // 'i' points to the current entry in the new table,
00216                         // 'j' points to the current entry in the old table
00217                         int i = 0, j = 0;
00218                         while (i < m. npieces)
00219                         {
00220                                 // find an allocated piece in the old table
00221                                 while ((j < npieces) && !tab [j])
00222                                         j ++;
00223                                 // if found, take it to the new table
00224                                 if (j < npieces)
00225                                         newtab [i ++] = tab [j ++];
00226                                 // otherwise zero the rest of the new table
00227                                 else
00228                                         while (i < m. npieces)
00229                                                 newtab [i ++] = 0;
00230                         }
00231                         // if there are some pieces remaining, delete them
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         // if the table is empty, then finish now
00252         if (!npieces)
00253                 return *this;
00254 
00255         // copy the data from 'm' to the current table;
00256         // try to use pieces which are already allocated
00257         int first_nonempty = 0, first_empty = 0, pos = 0;
00258         int piecesize = 1 << shiftbits;
00259 
00260         // find the first nonempty piece and the first empty one
00261         while ((first_nonempty < npieces) && !tab [first_nonempty])
00262                 first_nonempty ++;
00263         while ((first_empty < npieces) && tab [first_empty])
00264                 first_empty ++;
00265 
00266         // copy all the pieces
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                         // copy the source piece to this piece
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                 // move to the next position
00309                 pos ++;
00310 
00311                 // update pointers to the first available [non]empty piece
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 } /* multitable<element>::operator = */
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 } /* multitable<element>::~multitable */
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         // calculate the number of piece of interest
00340         int piece = n >> shiftbits;
00341 
00342         // increase the number of pieces if necessary
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         // allocate the piece if necessary
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 } /* multitable<element>::operator [] */
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         // calculate the number of piece of interest
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 } /* multitable<element>::operator () */
00376 
00377 template <class element>
00378 inline const element &multitable<element>::operator [] (int n) const
00379 {
00380         return (*this) (n);
00381 } /* multitable<element>::operator [] const */
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         // allocate more pieces if needed
00392         if (necessarypieces > npieces)
00393                 increase (necessarypieces);
00394 
00395         // deallocate unnecessary pieces
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 } /* multitable<element>::allocate */
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 } /* multitable<element>::fill */
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 } /* multitable<element>::swap */
00440 
00441 template <class element>
00442 void multitable<element>::increase (int n)
00443 {
00444         // DEBUG
00445 //      if (n != 1)
00446 //              sbug << "Inc " << n << ".\n";
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 } /* multitable<element>::increase */
00462 
00463 
00464 } // namespace homology
00465 } // namespace chomp
00466 
00467 #endif // _MULTITAB_H_
00468 
00469 /// @}
00470 

Generated on Wed Nov 21 11:08:41 2007 for The Uniform Expansion Software by  doxygen 1.5.3