![]() |
Tulip
4.6.0
Better Visualization Through Research
|
00001 /* 00002 * 00003 * This file is part of Tulip (www.tulip-software.org) 00004 * 00005 * Authors: David Auber and the Tulip development Team 00006 * from LaBRI, University of Bordeaux 00007 * 00008 * Tulip is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU Lesser General Public License 00010 * as published by the Free Software Foundation, either version 3 00011 * of the License, or (at your option) any later version. 00012 * 00013 * Tulip is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00016 * See the GNU General Public License for more details. 00017 * 00018 */ 00019 //=================================================================== 00020 template <typename TYPE> 00021 tlp::MutableContainer<TYPE>::MutableContainer(): vData(new std::deque<typename StoredType<TYPE>::Value>()), 00022 hData(NULL), minIndex(UINT_MAX), maxIndex(UINT_MAX), defaultValue(StoredType<TYPE>::defaultValue()), state(VECT), elementInserted(0), 00023 ratio(double(sizeof(typename tlp::StoredType<TYPE>::Value)) / (3.0*double(sizeof(void *))+double(sizeof(typename tlp::StoredType<TYPE>::Value)))), 00024 compressing(false) { 00025 } 00026 //=================================================================== 00027 template <typename TYPE> 00028 tlp::MutableContainer<TYPE>::~MutableContainer() { 00029 switch (state) { 00030 case VECT: 00031 00032 if (StoredType<TYPE>::isPointer) { 00033 // delete stored values 00034 typename std::deque<typename StoredType<TYPE>::Value>::const_iterator it = 00035 vData->begin(); 00036 00037 while (it!= vData->end()) { 00038 if ((*it) != defaultValue) 00039 StoredType<TYPE>::destroy(*it); 00040 00041 ++it; 00042 } 00043 } 00044 00045 delete vData; 00046 vData = NULL; 00047 break; 00048 00049 case HASH: 00050 00051 if (StoredType<TYPE>::isPointer) { 00052 // delete stored values 00053 typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it = hData->begin(); 00054 00055 while (it!= hData->end()) { 00056 StoredType<TYPE>::destroy((*it).second); 00057 ++it; 00058 } 00059 } 00060 00061 delete hData; 00062 hData = NULL; 00063 break; 00064 00065 default: 00066 assert(false); 00067 tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl; 00068 break; 00069 } 00070 00071 StoredType<TYPE>::destroy(defaultValue); 00072 } 00073 //=================================================================== 00074 template <typename TYPE> 00075 void tlp::MutableContainer<TYPE>::setAll(const TYPE &value) { 00076 switch (state) { 00077 case VECT: 00078 00079 if (StoredType<TYPE>::isPointer) { 00080 // delete stored values 00081 typename std::deque<typename StoredType<TYPE>::Value>::const_iterator it = 00082 vData->begin(); 00083 00084 while (it!= vData->end()) { 00085 if ((*it) != defaultValue) 00086 StoredType<TYPE>::destroy(*it); 00087 00088 ++it; 00089 } 00090 } 00091 00092 vData->clear(); 00093 break; 00094 00095 case HASH: 00096 00097 if (StoredType<TYPE>::isPointer) { 00098 // delete stored values 00099 typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it = hData->begin(); 00100 00101 while (it!= hData->end()) { 00102 StoredType<TYPE>::destroy((*it).second); 00103 ++it; 00104 } 00105 } 00106 00107 delete hData; 00108 hData = NULL; 00109 vData = new std::deque<typename StoredType<TYPE>::Value>(); 00110 break; 00111 00112 default: 00113 assert(false); 00114 tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl; 00115 break; 00116 } 00117 00118 StoredType<TYPE>::destroy(defaultValue); 00119 defaultValue = StoredType<TYPE>::clone(value); 00120 state = VECT; 00121 maxIndex = UINT_MAX; 00122 minIndex = UINT_MAX; 00123 elementInserted = 0; 00124 } 00125 //=================================================================== 00126 // this method is private and used as is by GraphUpdatesRecorder class 00127 // it is also used to implement findAll 00128 template <typename TYPE> 00129 tlp::IteratorValue* tlp::MutableContainer<TYPE>::findAllValues(const TYPE &value, 00130 bool equal) const { 00131 if (equal && 00132 StoredType<TYPE>::equal(defaultValue, value)) 00133 // error 00134 return NULL; 00135 else { 00136 switch (state) { 00137 case VECT: 00138 return new IteratorVect<TYPE>(value, equal, vData, minIndex); 00139 break; 00140 00141 case HASH: 00142 return new IteratorHash<TYPE>(value, equal, hData); 00143 break; 00144 00145 default: 00146 assert(false); 00147 tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl; 00148 return NULL; 00149 } 00150 } 00151 } 00152 //=================================================================== 00153 // this method is visible for any class 00154 template <typename TYPE> 00155 tlp::Iterator<unsigned int>* tlp::MutableContainer<TYPE>::findAll(const TYPE &value, 00156 bool equal) const { 00157 return findAllValues(value, equal); 00158 } 00159 //=================================================================== 00160 template <typename TYPE> 00161 void tlp::MutableContainer<TYPE>::vectset(const unsigned int i, 00162 typename StoredType<TYPE>::Value value) { 00163 if (minIndex == UINT_MAX) { 00164 minIndex = i; 00165 maxIndex = i; 00166 (*vData).push_back(value); 00167 ++elementInserted; 00168 } 00169 else { 00170 // the time performance of these two attempts of nicer coding 00171 // in this commented code seems worse than the loops below (about 15%) 00172 // if ( i > maxIndex ) { 00173 //-- 1st attempt -- 00174 // vData->resize(i+1 - minIndex, defaultValue); 00175 //-- 2nd attempt 00176 // vData->insert(vData->end(), i - maxIndex, defaultValue); 00177 // maxIndex = i; 00178 // } else if (i < minIndex) { 00179 // vData->insert(vData->begin(), minIndex - i, defaultValue); 00180 // minIndex = i; 00181 // } 00182 while ( i > maxIndex ) { 00183 (*vData).push_back(defaultValue); 00184 ++maxIndex; 00185 } 00186 00187 while ( i < minIndex ) { 00188 (*vData).push_front(defaultValue); 00189 --minIndex; 00190 } 00191 00192 typename StoredType<TYPE>::Value val = (*vData)[i - minIndex]; 00193 (*vData)[i - minIndex] = value; 00194 00195 if (val != defaultValue) 00196 StoredType<TYPE>::destroy(val); 00197 else 00198 ++elementInserted; 00199 } 00200 } 00201 //=================================================================== 00202 template <typename TYPE> 00203 void tlp::MutableContainer<TYPE>::set(const unsigned int i, const TYPE &value) { 00204 //Test if after insertion we need to resize 00205 if (!compressing && 00206 !StoredType<TYPE>::equal(defaultValue, value)) { 00207 compressing = true; 00208 compress (std::min(i,minIndex), std::max(i,maxIndex), elementInserted); 00209 compressing = false; 00210 } 00211 00212 if (StoredType<TYPE>::equal(defaultValue, value)) { 00213 00214 switch (state) { 00215 case VECT : 00216 00217 if (i<=maxIndex && i>=minIndex) { 00218 typename StoredType<TYPE>::Value val = (*vData)[i - minIndex]; 00219 00220 if (val != defaultValue) { 00221 (*vData)[i - minIndex]= defaultValue; 00222 StoredType<TYPE>::destroy(val); 00223 --elementInserted; 00224 } 00225 } 00226 00227 return; 00228 00229 case HASH : { 00230 typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i); 00231 00232 if (it!=hData->end()) { 00233 StoredType<TYPE>::destroy((*it).second); 00234 hData->erase(i); 00235 --elementInserted; 00236 } 00237 00238 break; 00239 } 00240 00241 default: 00242 assert(false); 00243 tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl; 00244 break; 00245 } 00246 } 00247 else { 00248 typename StoredType<TYPE>::Value newVal = 00249 StoredType<TYPE>::clone(value); 00250 00251 switch (state) { 00252 case VECT : 00253 00254 vectset(i, newVal); 00255 00256 return; 00257 00258 case HASH : { 00259 typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i); 00260 00261 if (it!=hData->end()) 00262 StoredType<TYPE>::destroy((*it).second); 00263 else 00264 ++elementInserted; 00265 00266 (*hData)[i]= newVal; 00267 break; 00268 } 00269 00270 default: 00271 assert(false); 00272 tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl; 00273 break; 00274 } 00275 00276 maxIndex = std::max(maxIndex, i); 00277 minIndex = std::min(minIndex, i); 00278 } 00279 } 00280 //=================================================================== 00281 template <typename TYPE> 00282 void tlp::MutableContainer<TYPE>::add(const unsigned int i, TYPE val) { 00283 if (tlp::StoredType<TYPE>::isPointer == false) { 00284 if (maxIndex == UINT_MAX) { 00285 assert(state == VECT); 00286 minIndex = i; 00287 maxIndex = i; 00288 (*vData).push_back(defaultValue + val); 00289 ++elementInserted; 00290 return; 00291 } 00292 00293 switch (state) { 00294 case VECT: { 00295 if (i > maxIndex || i < minIndex) { 00296 set(i, defaultValue + val); 00297 return; 00298 } 00299 00300 TYPE& oldVal = (*vData)[i - minIndex]; 00301 00302 if (oldVal == defaultValue) { 00303 set(i, defaultValue + val); 00304 return; 00305 } 00306 00307 oldVal += val; 00308 00309 return; 00310 } 00311 00312 case HASH: { 00313 typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i); 00314 00315 if (it!=hData->end()) { 00316 // check default value 00317 if ((it->second + val) == defaultValue) { 00318 StoredType<TYPE>::destroy((*it).second); 00319 hData->erase(i); 00320 --elementInserted; 00321 } 00322 else 00323 it->second += val; 00324 } 00325 else { 00326 set(i, defaultValue + val); 00327 } 00328 00329 return; 00330 } 00331 00332 default: 00333 assert(false); 00334 std::cerr << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl; 00335 } 00336 } 00337 00338 assert(false); 00339 std::cerr << __PRETTY_FUNCTION__ << "not implemented" << std::endl; 00340 } 00341 //=================================================================== 00342 template <typename TYPE> 00343 typename tlp::StoredType<TYPE>::ReturnedConstValue tlp::MutableContainer<TYPE>::get(const unsigned int i) const { 00344 // cerr << __PRETTY_FUNCTION__ << endl; 00345 if (maxIndex == UINT_MAX) return StoredType<TYPE>::get(defaultValue); 00346 00347 switch (state) { 00348 case VECT: 00349 00350 if (i>maxIndex || i<minIndex) 00351 return StoredType<TYPE>::get(defaultValue); 00352 else 00353 return StoredType<TYPE>::get((*vData)[i - minIndex]); 00354 00355 case HASH: { 00356 typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i); 00357 00358 if (it!=hData->end()) 00359 return StoredType<TYPE>::get((*it).second); 00360 else 00361 return StoredType<TYPE>::get(defaultValue); 00362 } 00363 00364 default: 00365 assert(false); 00366 tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl; 00367 return StoredType<TYPE>::get(defaultValue); 00368 break; 00369 } 00370 } 00371 //=================================================================== 00372 template <typename TYPE> 00373 typename tlp::StoredType<TYPE>::ReturnedValue tlp::MutableContainer<TYPE>::getDefault() const { 00374 return StoredType<TYPE>::get(defaultValue); 00375 } 00376 //=================================================================== 00377 template <typename TYPE> 00378 bool tlp::MutableContainer<TYPE>::hasNonDefaultValue(const unsigned int i) const { 00379 if (maxIndex == UINT_MAX) return false; 00380 00381 switch (state) { 00382 case VECT: 00383 return (i<=maxIndex && i>=minIndex && 00384 (((*vData)[i - minIndex]) != defaultValue)); 00385 00386 case HASH: 00387 return ((hData->find(i))!=hData->end()); 00388 00389 default: 00390 assert(false); 00391 tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl; 00392 return false; 00393 } 00394 } 00395 //=================================================================== 00396 template <typename TYPE> 00397 typename tlp::StoredType<TYPE>::ReturnedValue tlp::MutableContainer<TYPE>::get(const unsigned int i, bool& notDefault) const { 00398 if (maxIndex == UINT_MAX) { 00399 notDefault = false; 00400 return StoredType<TYPE>::get(defaultValue); 00401 } 00402 00403 switch (state) { 00404 case VECT: 00405 00406 if (i>maxIndex || i<minIndex) { 00407 notDefault = false; 00408 return StoredType<TYPE>::get(defaultValue); 00409 } 00410 else { 00411 typename StoredType<TYPE>::Value val = (*vData)[i - minIndex]; 00412 notDefault = val != defaultValue; 00413 return StoredType<TYPE>::get(val); 00414 } 00415 00416 case HASH: { 00417 typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i); 00418 00419 if (it!=hData->end()) { 00420 notDefault = true; 00421 return StoredType<TYPE>::get((*it).second); 00422 } 00423 else { 00424 notDefault = false; 00425 return StoredType<TYPE>::get(defaultValue); 00426 } 00427 } 00428 00429 default: 00430 assert(false); 00431 notDefault = false; 00432 tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl; 00433 return StoredType<TYPE>::get(defaultValue); 00434 } 00435 } 00436 //=================================================================== 00437 template <typename TYPE> 00438 unsigned int tlp::MutableContainer<TYPE>::numberOfNonDefaultValues() const { 00439 return elementInserted; 00440 } 00441 //=================================================================== 00442 template <typename TYPE> 00443 void tlp::MutableContainer<TYPE>::vecttohash() { 00444 hData=new TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>(elementInserted); 00445 00446 unsigned int newMaxIndex = 0; 00447 unsigned int newMinIndex = UINT_MAX; 00448 elementInserted = 0; 00449 00450 for (unsigned int i=minIndex; i<=maxIndex; ++i) { 00451 if ((*vData)[i - minIndex] != defaultValue) { 00452 (*hData)[i] = (*vData)[i - minIndex]; 00453 newMaxIndex = std::max(newMaxIndex, i); 00454 newMinIndex = std::min(newMinIndex, i); 00455 ++elementInserted; 00456 } 00457 } 00458 00459 maxIndex = newMaxIndex; 00460 minIndex = newMinIndex; 00461 delete vData; 00462 vData = NULL; 00463 state = HASH; 00464 } 00465 //=================================================================== 00466 template <typename TYPE> 00467 void tlp::MutableContainer<TYPE>::hashtovect() { 00468 vData = new std::deque<typename StoredType<TYPE>::Value>(); 00469 minIndex = UINT_MAX; 00470 maxIndex = UINT_MAX; 00471 elementInserted = 0; 00472 state=VECT; 00473 typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it; 00474 00475 for (it=hData->begin(); it!=hData->end(); ++it) { 00476 if (it->second != defaultValue) 00477 vectset(it->first, it->second); 00478 } 00479 00480 delete hData; 00481 hData = NULL; 00482 } 00483 //=================================================================== 00484 template <typename TYPE> 00485 void tlp::MutableContainer<TYPE>::compress(unsigned int min, unsigned int max, unsigned int nbElements) { 00486 if (max == UINT_MAX || (max - min) < 10) return; 00487 00488 double limitValue = ratio*(double(max - min + 1.0)); 00489 00490 switch (state) { 00491 case VECT: 00492 00493 if ( double(nbElements) < limitValue) { 00494 vecttohash(); 00495 } 00496 00497 break; 00498 00499 case HASH: 00500 00501 if ( double(nbElements) > limitValue*1.5) { 00502 hashtovect(); 00503 } 00504 00505 break; 00506 00507 default: 00508 assert(false); 00509 tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl; 00510 break; 00511 } 00512 } 00513 00514 template <typename TYPE> 00515 typename tlp::StoredType<TYPE>::ReturnedConstValue tlp::MutableContainer<TYPE>::operator[](const unsigned int i) const { 00516 return get(i); 00517 }