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