Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/cxx/MutableContainer.cxx
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 }
 All Classes Files Functions Variables Enumerations Enumerator Properties