Tulip  4.7.0
Better Visualization Through Research
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Groups Pages
MutableContainer.cxx
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 //===================================================================
20 template <typename TYPE>
21 tlp::MutableContainer<TYPE>::MutableContainer(): vData(new std::deque<typename StoredType<TYPE>::Value>()),
22  hData(NULL), minIndex(UINT_MAX), maxIndex(UINT_MAX), defaultValue(StoredType<TYPE>::defaultValue()), state(VECT), elementInserted(0),
23  ratio(double(sizeof(typename tlp::StoredType<TYPE>::Value)) / (3.0*double(sizeof(void *))+double(sizeof(typename tlp::StoredType<TYPE>::Value)))),
24  compressing(false) {
25 }
26 //===================================================================
27 template <typename TYPE>
28 tlp::MutableContainer<TYPE>::~MutableContainer() {
29  switch (state) {
30  case VECT:
31 
32  if (StoredType<TYPE>::isPointer) {
33  // delete stored values
34  typename std::deque<typename StoredType<TYPE>::Value>::const_iterator it =
35  vData->begin();
36 
37  while (it!= vData->end()) {
38  if ((*it) != defaultValue)
39  StoredType<TYPE>::destroy(*it);
40 
41  ++it;
42  }
43  }
44 
45  delete vData;
46  vData = NULL;
47  break;
48 
49  case HASH:
50 
51  if (StoredType<TYPE>::isPointer) {
52  // delete stored values
53  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it = hData->begin();
54 
55  while (it!= hData->end()) {
56  StoredType<TYPE>::destroy((*it).second);
57  ++it;
58  }
59  }
60 
61  delete hData;
62  hData = NULL;
63  break;
64 
65  default:
66  assert(false);
67  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
68  break;
69  }
70 
71  StoredType<TYPE>::destroy(defaultValue);
72 }
73 //===================================================================
74 template <typename TYPE>
75 void tlp::MutableContainer<TYPE>::setAll(const TYPE &value) {
76  switch (state) {
77  case VECT:
78 
79  if (StoredType<TYPE>::isPointer) {
80  // delete stored values
81  typename std::deque<typename StoredType<TYPE>::Value>::const_iterator it =
82  vData->begin();
83 
84  while (it!= vData->end()) {
85  if ((*it) != defaultValue)
86  StoredType<TYPE>::destroy(*it);
87 
88  ++it;
89  }
90  }
91 
92  vData->clear();
93  break;
94 
95  case HASH:
96 
97  if (StoredType<TYPE>::isPointer) {
98  // delete stored values
99  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it = hData->begin();
100 
101  while (it!= hData->end()) {
102  StoredType<TYPE>::destroy((*it).second);
103  ++it;
104  }
105  }
106 
107  delete hData;
108  hData = NULL;
109  vData = new std::deque<typename StoredType<TYPE>::Value>();
110  break;
111 
112  default:
113  assert(false);
114  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
115  break;
116  }
117 
118  StoredType<TYPE>::destroy(defaultValue);
119  defaultValue = StoredType<TYPE>::clone(value);
120  state = VECT;
121  maxIndex = UINT_MAX;
122  minIndex = UINT_MAX;
123  elementInserted = 0;
124 }
125 //===================================================================
126 // this method is private and used as is by GraphUpdatesRecorder class
127 // it is also used to implement findAll
128 template <typename TYPE>
129 tlp::IteratorValue* tlp::MutableContainer<TYPE>::findAllValues(const TYPE &value,
130  bool equal) const {
131  if (equal &&
132  StoredType<TYPE>::equal(defaultValue, value))
133  // error
134  return NULL;
135  else {
136  switch (state) {
137  case VECT:
138  return new IteratorVect<TYPE>(value, equal, vData, minIndex);
139  break;
140 
141  case HASH:
142  return new IteratorHash<TYPE>(value, equal, hData);
143  break;
144 
145  default:
146  assert(false);
147  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
148  return NULL;
149  }
150  }
151 }
152 //===================================================================
153 // this method is visible for any class
154 template <typename TYPE>
155 tlp::Iterator<unsigned int>* tlp::MutableContainer<TYPE>::findAll(const TYPE &value,
156  bool equal) const {
157  return findAllValues(value, equal);
158 }
159 //===================================================================
160 template <typename TYPE>
161 void tlp::MutableContainer<TYPE>::vectset(const unsigned int i,
162  typename StoredType<TYPE>::Value value) {
163  if (minIndex == UINT_MAX) {
164  minIndex = i;
165  maxIndex = i;
166  (*vData).push_back(value);
167  ++elementInserted;
168  }
169  else {
170  // the time performance of these two attempts of nicer coding
171  // in this commented code seems worse than the loops below (about 15%)
172  // if ( i > maxIndex ) {
173  //-- 1st attempt --
174  // vData->resize(i+1 - minIndex, defaultValue);
175  //-- 2nd attempt
176  // vData->insert(vData->end(), i - maxIndex, defaultValue);
177  // maxIndex = i;
178  // } else if (i < minIndex) {
179  // vData->insert(vData->begin(), minIndex - i, defaultValue);
180  // minIndex = i;
181  // }
182  while ( i > maxIndex ) {
183  (*vData).push_back(defaultValue);
184  ++maxIndex;
185  }
186 
187  while ( i < minIndex ) {
188  (*vData).push_front(defaultValue);
189  --minIndex;
190  }
191 
192  typename StoredType<TYPE>::Value val = (*vData)[i - minIndex];
193  (*vData)[i - minIndex] = value;
194 
195  if (val != defaultValue)
196  StoredType<TYPE>::destroy(val);
197  else
198  ++elementInserted;
199  }
200 }
201 //===================================================================
202 template <typename TYPE>
203 void tlp::MutableContainer<TYPE>::set(const unsigned int i, const TYPE &value) {
204  //Test if after insertion we need to resize
205  if (!compressing &&
206  !StoredType<TYPE>::equal(defaultValue, value)) {
207  compressing = true;
208  compress (std::min(i,minIndex), std::max(i,maxIndex), elementInserted);
209  compressing = false;
210  }
211 
212  if (StoredType<TYPE>::equal(defaultValue, value)) {
213 
214  switch (state) {
215  case VECT :
216 
217  if (i<=maxIndex && i>=minIndex) {
218  typename StoredType<TYPE>::Value val = (*vData)[i - minIndex];
219 
220  if (val != defaultValue) {
221  (*vData)[i - minIndex]= defaultValue;
222  StoredType<TYPE>::destroy(val);
223  --elementInserted;
224  }
225  }
226 
227  return;
228 
229  case HASH : {
230  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i);
231 
232  if (it!=hData->end()) {
233  StoredType<TYPE>::destroy((*it).second);
234  hData->erase(i);
235  --elementInserted;
236  }
237 
238  break;
239  }
240 
241  default:
242  assert(false);
243  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
244  break;
245  }
246  }
247  else {
248  typename StoredType<TYPE>::Value newVal =
249  StoredType<TYPE>::clone(value);
250 
251  switch (state) {
252  case VECT :
253 
254  vectset(i, newVal);
255 
256  return;
257 
258  case HASH : {
259  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i);
260 
261  if (it!=hData->end())
262  StoredType<TYPE>::destroy((*it).second);
263  else
264  ++elementInserted;
265 
266  (*hData)[i]= newVal;
267  break;
268  }
269 
270  default:
271  assert(false);
272  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
273  break;
274  }
275 
276  maxIndex = std::max(maxIndex, i);
277  minIndex = std::min(minIndex, i);
278  }
279 }
280 //===================================================================
281 template <typename TYPE>
282 void tlp::MutableContainer<TYPE>::add(const unsigned int i, TYPE val) {
283  if (tlp::StoredType<TYPE>::isPointer == false) {
284  if (maxIndex == UINT_MAX) {
285  assert(state == VECT);
286  minIndex = i;
287  maxIndex = i;
288  (*vData).push_back(defaultValue + val);
289  ++elementInserted;
290  return;
291  }
292 
293  switch (state) {
294  case VECT: {
295  if (i > maxIndex || i < minIndex) {
296  set(i, defaultValue + val);
297  return;
298  }
299 
300  TYPE& oldVal = (*vData)[i - minIndex];
301 
302  if (oldVal == defaultValue) {
303  set(i, defaultValue + val);
304  return;
305  }
306 
307  oldVal += val;
308 
309  return;
310  }
311 
312  case HASH: {
313  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i);
314 
315  if (it!=hData->end()) {
316  // check default value
317  if ((it->second + val) == defaultValue) {
318  StoredType<TYPE>::destroy((*it).second);
319  hData->erase(i);
320  --elementInserted;
321  }
322  else
323  it->second += val;
324  }
325  else {
326  set(i, defaultValue + val);
327  }
328 
329  return;
330  }
331 
332  default:
333  assert(false);
334  std::cerr << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
335  }
336  }
337 
338  assert(false);
339  std::cerr << __PRETTY_FUNCTION__ << "not implemented" << std::endl;
340 }
341 //===================================================================
342 template <typename TYPE>
343 typename tlp::StoredType<TYPE>::ReturnedConstValue tlp::MutableContainer<TYPE>::get(const unsigned int i) const {
344  // cerr << __PRETTY_FUNCTION__ << endl;
345  if (maxIndex == UINT_MAX) return StoredType<TYPE>::get(defaultValue);
346 
347  switch (state) {
348  case VECT:
349 
350  if (i>maxIndex || i<minIndex)
351  return StoredType<TYPE>::get(defaultValue);
352  else
353  return StoredType<TYPE>::get((*vData)[i - minIndex]);
354 
355  case HASH: {
356  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i);
357 
358  if (it!=hData->end())
359  return StoredType<TYPE>::get((*it).second);
360  else
361  return StoredType<TYPE>::get(defaultValue);
362  }
363 
364  default:
365  assert(false);
366  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
367  return StoredType<TYPE>::get(defaultValue);
368  break;
369  }
370 }
371 //===================================================================
372 template <typename TYPE>
373 typename tlp::StoredType<TYPE>::ReturnedValue tlp::MutableContainer<TYPE>::getDefault() const {
374  return StoredType<TYPE>::get(defaultValue);
375 }
376 //===================================================================
377 template <typename TYPE>
378 bool tlp::MutableContainer<TYPE>::hasNonDefaultValue(const unsigned int i) const {
379  if (maxIndex == UINT_MAX) return false;
380 
381  switch (state) {
382  case VECT:
383  return (i<=maxIndex && i>=minIndex &&
384  (((*vData)[i - minIndex]) != defaultValue));
385 
386  case HASH:
387  return ((hData->find(i))!=hData->end());
388 
389  default:
390  assert(false);
391  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
392  return false;
393  }
394 }
395 //===================================================================
396 template <typename TYPE>
397 typename tlp::StoredType<TYPE>::ReturnedValue tlp::MutableContainer<TYPE>::get(const unsigned int i, bool& notDefault) const {
398  if (maxIndex == UINT_MAX) {
399  notDefault = false;
400  return StoredType<TYPE>::get(defaultValue);
401  }
402 
403  switch (state) {
404  case VECT:
405 
406  if (i>maxIndex || i<minIndex) {
407  notDefault = false;
408  return StoredType<TYPE>::get(defaultValue);
409  }
410  else {
411  typename StoredType<TYPE>::Value val = (*vData)[i - minIndex];
412  notDefault = val != defaultValue;
413  return StoredType<TYPE>::get(val);
414  }
415 
416  case HASH: {
417  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i);
418 
419  if (it!=hData->end()) {
420  notDefault = true;
421  return StoredType<TYPE>::get((*it).second);
422  }
423  else {
424  notDefault = false;
425  return StoredType<TYPE>::get(defaultValue);
426  }
427  }
428 
429  default:
430  assert(false);
431  notDefault = false;
432  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
433  return StoredType<TYPE>::get(defaultValue);
434  }
435 }
436 //===================================================================
437 template <typename TYPE>
438 unsigned int tlp::MutableContainer<TYPE>::numberOfNonDefaultValues() const {
439  return elementInserted;
440 }
441 //===================================================================
442 template <typename TYPE>
443 void tlp::MutableContainer<TYPE>::vecttohash() {
444  hData=new TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>(elementInserted);
445 
446  unsigned int newMaxIndex = 0;
447  unsigned int newMinIndex = UINT_MAX;
448  elementInserted = 0;
449 
450  for (unsigned int i=minIndex; i<=maxIndex; ++i) {
451  if ((*vData)[i - minIndex] != defaultValue) {
452  (*hData)[i] = (*vData)[i - minIndex];
453  newMaxIndex = std::max(newMaxIndex, i);
454  newMinIndex = std::min(newMinIndex, i);
455  ++elementInserted;
456  }
457  }
458 
459  maxIndex = newMaxIndex;
460  minIndex = newMinIndex;
461  delete vData;
462  vData = NULL;
463  state = HASH;
464 }
465 //===================================================================
466 template <typename TYPE>
467 void tlp::MutableContainer<TYPE>::hashtovect() {
468  vData = new std::deque<typename StoredType<TYPE>::Value>();
469  minIndex = UINT_MAX;
470  maxIndex = UINT_MAX;
471  elementInserted = 0;
472  state=VECT;
473  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it;
474 
475  for (it=hData->begin(); it!=hData->end(); ++it) {
476  if (it->second != defaultValue)
477  vectset(it->first, it->second);
478  }
479 
480  delete hData;
481  hData = NULL;
482 }
483 //===================================================================
484 template <typename TYPE>
485 void tlp::MutableContainer<TYPE>::compress(unsigned int min, unsigned int max, unsigned int nbElements) {
486  if (max == UINT_MAX || (max - min) < 10) return;
487 
488  double limitValue = ratio*(double(max - min + 1.0));
489 
490  switch (state) {
491  case VECT:
492 
493  if ( double(nbElements) < limitValue) {
494  vecttohash();
495  }
496 
497  break;
498 
499  case HASH:
500 
501  if ( double(nbElements) > limitValue*1.5) {
502  hashtovect();
503  }
504 
505  break;
506 
507  default:
508  assert(false);
509  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
510  break;
511  }
512 }
513 
514 template <typename TYPE>
515 typename tlp::StoredType<TYPE>::ReturnedConstValue tlp::MutableContainer<TYPE>::operator[](const unsigned int i) const {
516  return get(i);
517 }