Main Page | Class Hierarchy | Compound List | File List | Compound Members | File Members

sparse.h

Go to the documentation of this file.
00001 
00002 #ifndef SPARSE_H
00003 #define SPARSE_H
00004 
00005 
00006 /*===============================<o>=====================================
00007 
00008 Copyright 1996, 1997, 2004 Ian Kaplan, Bear Products International,
00009 www.bearcave.com.
00010 
00011 All Rights Reserved
00012 
00013 You may use this software in software components for which you do
00014 not collect money (e.g., non-commercial software).  All commercial
00015 use is reserved.
00016 
00017 ===============================<o>=====================================*/
00018 
00019 #include <string.h> // for memset
00020 
00021 #define GetTopIndex(i) ((i)>>power)
00022 #define GetLeafIndex(i) ((i)&leafMask)
00023 
00037 template <class T>
00038 class sparse_array {
00039 private:
00040 
00041     unsigned int power;
00042     unsigned int dimension_size;
00043     unsigned int leafMask;
00044     unsigned int bytes_alloced;
00045     T **top;
00046 
00047 public:
00048     void init( const unsigned int size )
00049     {
00050         if (size > 0) {
00051             // round size up to the nearest power of two
00052             power = get_power_of_two( size );
00053             dimension_size = two_to_n( power );
00054             leafMask = dimension_size - 1;  // (2^n) - 1
00055 
00056             top = new T* [ dimension_size ];
00057             bytes_alloced = sizeof( T *) * dimension_size;
00058             memset( (char *)top, 0, bytes_alloced );  // make sure that top is NULL
00059         }
00060         else {
00061             power = 0;
00062             dimension_size = 0;
00063             leafMask = 0;
00064             bytes_alloced = 0;
00065             top = NULL;
00066         }
00067     }  // init
00068     // constructor
00069     sparse_array( const unsigned int size )
00070     {
00071         init( size );
00072     } // sparse_array constructor
00073 
00074     // copy constructor
00075     sparse_array( const sparse_array<T> &a )
00076     {
00077         init(0);
00078         (*this) = a;
00079     }  // sparse_array
00080 
00094     void dealloc(void)
00095     {
00096         unsigned int i;
00097 
00098         for (i = 0; i < dimension_size; i++) {
00099             if (top[i] != NULL) {
00100                 delete [] top[ i ];  // delete the array pointed to by top[ i ]
00101                 top[ i ] = NULL;
00102             }
00103         }
00104         if (top != NULL) {
00105             delete [] top;
00106             init(0);
00107         }
00108     } // dealloc
00109 
00110 
00111     unsigned int two_to_n( unsigned int n ) { return 1 << (n & 0x1f); }
00112 
00119     unsigned int get_power_of_two( const unsigned int val )
00120     {
00121         const uint powerMin = 1; // set a resonable minimum
00122         uint p;
00123 
00124         for( p = powerMin; val > (uint)(1 << p); p++ )
00125             /* nada */
00126             ;
00127         return p;
00128     } // get_power_of_two
00129 
00130 
00131     void add_leaf( const unsigned int top_ix )
00132     {
00133         assert( top[ top_ix ] == NULL );
00134 
00135         top[ top_ix ] = new T [ dimension_size ];
00136         memset( top[top_ix], 0, sizeof( T ) * dimension_size );
00137         bytes_alloced += sizeof( T ) * dimension_size;
00138     } // add_leaf
00139 
00140     void insert( const T &val, const unsigned int ix) 
00141     {
00142         unsigned int top_ix = GetTopIndex(ix);
00143         unsigned int leaf_ix = GetLeafIndex(ix);
00144     
00145         assert( top_ix < dimension_size );
00146         if (top[top_ix] == NULL) {
00147             add_leaf( top_ix );
00148         }
00149 
00150         top[top_ix][ leaf_ix ] = val;
00151     } // insert
00152 
00153 
00159     T &operator[]( const unsigned int i )
00160     {
00161         unsigned int top_ix = GetTopIndex(i);
00162         unsigned int leaf_ix = GetLeafIndex(i);
00163 
00164         assert( top_ix < dimension_size );
00165         assert( top[ top_ix ] != NULL );
00166         return top[ top_ix ][ leaf_ix ];
00167     }
00168 
00169 
00175     int probe( const unsigned int ix )
00176     {
00177         int rslt = TRUE;
00178         unsigned int top_ix = GetTopIndex(ix);
00179         
00180         assert( top_ix < dimension_size );
00181         if (top[top_ix] == NULL) {
00182             rslt = FALSE;
00183         }
00184         return rslt;
00185     }
00186 
00190     unsigned int get_total_size() { return dimension_size * dimension_size; }
00191 
00192     // ----- debug functions -----
00193     unsigned int get_bytes_alloced(void) { return bytes_alloced; };
00194     unsigned int get_percent_alloced(void);
00195 };  // class sparse_array
00196 
00197 
00198 
00199 
00200 // ----------------- debug functions
00201 
00202 template <class T>
00203 unsigned int sparse_array<T>::get_percent_alloced(void)
00204 {
00205     uint i;
00206     int top_used, trunc;
00207     float percent, tsize, used;
00208 
00209     trunc = 0;
00210     if (top != NULL) {
00211         top_used = 0;
00212         for (i = 0; i < dimension_size; i++) {
00213             if (top[ i ] != NULL)
00214                 top_used++;
00215         }
00216         tsize = (float)dimension_size;
00217         used = (float)top_used;
00218         percent = (used / tsize) * (float)100;
00219         trunc = (int)percent;
00220     }
00221 
00222     return trunc;
00223 }
00224 
00225 
00226 #undef GetTopIndex
00227 #undef GetLeafIndex
00228 
00229 #endif

Generated on Wed Mar 31 21:15:55 2004 for Data Structures for a VHDL Compiler by doxygen 1.3.3