Tulip  6.0.0
Large graphs analysis and drawing
MutableContainer.cxx
1 /*
2  *
3  * This file is part of Tulip (https://tulip.labri.fr)
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()
22  : vData(new std::deque<typename StoredType<TYPE>::Value>()), hData(nullptr), minIndex(UINT_MAX),
23  maxIndex(UINT_MAX), defaultValue(StoredType<TYPE>::defaultValue()), state(VECT),
24  elementInserted(0),
25  ratio(double(sizeof(typename tlp::StoredType<TYPE>::Value)) /
26  (3.0 * double(sizeof(void *)) + double(sizeof(typename tlp::StoredType<TYPE>::Value)))),
27  compressing(false) {}
28 //===================================================================
29 template <typename TYPE>
30 tlp::MutableContainer<TYPE>::~MutableContainer() {
31  switch (state) {
32  case VECT:
33 
34  if (StoredType<TYPE>::isPointer) {
35  // delete stored values
36  typename std::deque<typename StoredType<TYPE>::Value>::const_iterator it = vData->begin();
37 
38  while (it != vData->end()) {
39  if ((*it) != defaultValue)
40  StoredType<TYPE>::destroy(*it);
41 
42  ++it;
43  }
44  }
45 
46  delete vData;
47  vData = nullptr;
48  break;
49 
50  case HASH:
51 
52  if (StoredType<TYPE>::isPointer) {
53  // delete stored values
54  typename tlp_hash_map<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it =
55  hData->begin();
56 
57  while (it != hData->end()) {
58  StoredType<TYPE>::destroy(it->second);
59  ++it;
60  }
61  }
62 
63  delete hData;
64  hData = nullptr;
65  break;
66 
67  default:
68  assert(false);
69  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
70  break;
71  }
72 
73  StoredType<TYPE>::destroy(defaultValue);
74 }
75 //===================================================================
76 template <typename TYPE>
77 void tlp::MutableContainer<TYPE>::setDefault(typename StoredType<TYPE>::ReturnedConstValue value) {
78  StoredType<TYPE>::destroy(defaultValue);
79  defaultValue = StoredType<TYPE>::clone(value);
80 }
81 //===================================================================
82 template <typename TYPE>
83 void tlp::MutableContainer<TYPE>::setAll(typename StoredType<TYPE>::ReturnedConstValue value) {
84  switch (state) {
85  case VECT:
86 
87  if (StoredType<TYPE>::isPointer) {
88  // delete stored values
89  typename std::deque<typename StoredType<TYPE>::Value>::const_iterator it = vData->begin();
90 
91  while (it != vData->end()) {
92  if ((*it) != defaultValue)
93  StoredType<TYPE>::destroy(*it);
94 
95  ++it;
96  }
97  }
98 
99  vData->clear();
100  break;
101 
102  case HASH:
103 
104  if (StoredType<TYPE>::isPointer) {
105  // delete stored values
106  typename tlp_hash_map<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it =
107  hData->begin();
108 
109  while (it != hData->end()) {
110  StoredType<TYPE>::destroy(it->second);
111  ++it;
112  }
113  }
114 
115  delete hData;
116  hData = nullptr;
117  vData = new std::deque<typename StoredType<TYPE>::Value>();
118  break;
119 
120  default:
121  assert(false);
122  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
123  break;
124  }
125 
126  StoredType<TYPE>::destroy(defaultValue);
127  defaultValue = StoredType<TYPE>::clone(value);
128  state = VECT;
129  maxIndex = UINT_MAX;
130  minIndex = UINT_MAX;
131  elementInserted = 0;
132 }
133 //===================================================================
134 // this method is private and used as is by GraphUpdatesRecorder class
135 // it is also used to implement findAll
136 template <typename TYPE>
137 tlp::IteratorValue *
138 tlp::MutableContainer<TYPE>::findAllValues(typename StoredType<TYPE>::ReturnedConstValue value,
139  bool equal) const {
140  if (equal && StoredType<TYPE>::equal(defaultValue, value))
141  // error
142  return nullptr;
143  else {
144  switch (state) {
145  case VECT:
146  return new IteratorVect<TYPE>(value, equal, vData, minIndex);
147  break;
148 
149  case HASH:
150  return new IteratorHash<TYPE>(value, equal, hData);
151  break;
152 
153  default:
154  assert(false);
155  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
156  return nullptr;
157  }
158  }
159 }
160 //===================================================================
161 // this method is visible for any class
162 template <typename TYPE>
164 tlp::MutableContainer<TYPE>::findAll(typename StoredType<TYPE>::ReturnedConstValue value,
165  bool equal) const {
166  return findAllValues(value, equal);
167 }
168 //===================================================================
169 template <typename TYPE>
170 void tlp::MutableContainer<TYPE>::vectset(const unsigned int i,
171  typename StoredType<TYPE>::Value value) {
172  if (minIndex == UINT_MAX) {
173  minIndex = i;
174  maxIndex = i;
175  (*vData).push_back(value);
176  ++elementInserted;
177  } else {
178  // the time performance of these two attempts of nicer coding
179  // in this commented code seems worse than the loops below (about 15%)
180  // if ( i > maxIndex ) {
181  //-- 1st attempt --
182  // vData->resize(i+1 - minIndex, defaultValue);
183  //-- 2nd attempt
184  // vData->insert(vData->end(), i - maxIndex, defaultValue);
185  // maxIndex = i;
186  // } else if (i < minIndex) {
187  // vData->insert(vData->begin(), minIndex - i, defaultValue);
188  // minIndex = i;
189  // }
190  while (i > maxIndex) {
191  (*vData).push_back(defaultValue);
192  ++maxIndex;
193  }
194 
195  while (i < minIndex) {
196  (*vData).push_front(defaultValue);
197  --minIndex;
198  }
199 
200  typename StoredType<TYPE>::Value val = (*vData)[i - minIndex];
201  (*vData)[i - minIndex] = value;
202 
203  if (val != defaultValue)
204  StoredType<TYPE>::destroy(val);
205  else
206  ++elementInserted;
207  }
208 }
209 //===================================================================
210 template <typename TYPE>
211 void tlp::MutableContainer<TYPE>::set(const unsigned int i,
212  typename StoredType<TYPE>::ReturnedConstValue value,
213  bool forceDefaultValueRemoval) {
214  // Test if after insertion we need to resize
215  if (!compressing && !StoredType<TYPE>::equal(defaultValue, value)) {
216  compressing = true;
217  compress(std::min(i, minIndex), std::max(i, maxIndex), elementInserted);
218  compressing = false;
219  }
220 
221  if (StoredType<TYPE>::equal(defaultValue, value)) {
222 
223  switch (state) {
224  case VECT:
225 
226  if (i <= maxIndex && i >= minIndex) {
227  typename StoredType<TYPE>::Value val = (*vData)[i - minIndex];
228 
229  if (val != defaultValue) {
230  (*vData)[i - minIndex] = defaultValue;
231  StoredType<TYPE>::destroy(val);
232  --elementInserted;
233  } else if (forceDefaultValueRemoval)
234  --elementInserted;
235  }
236 
237  return;
238 
239  case HASH: {
240  typename tlp_hash_map<unsigned int, typename StoredType<TYPE>::Value>::iterator it =
241  hData->find(i);
242 
243  if (it != hData->end()) {
244  StoredType<TYPE>::destroy(it->second);
245  hData->erase(it);
246  --elementInserted;
247  }
248 
249  break;
250  }
251 
252  default:
253  assert(false);
254  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
255  break;
256  }
257  } else {
258  typename StoredType<TYPE>::Value newVal = StoredType<TYPE>::clone(value);
259 
260  switch (state) {
261  case VECT:
262 
263  vectset(i, newVal);
264 
265  return;
266 
267  case HASH: {
268  typename tlp_hash_map<unsigned int, typename StoredType<TYPE>::Value>::iterator it =
269  hData->find(i);
270 
271  if (it != hData->end()) {
272  StoredType<TYPE>::destroy(it->second);
273  it->second = newVal;
274  } else {
275  ++elementInserted;
276  (*hData)[i] = newVal;
277  }
278  break;
279  }
280 
281  default:
282  assert(false);
283  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
284  break;
285  }
286 
287  maxIndex = std::max(maxIndex, i);
288  minIndex = std::min(minIndex, i);
289  }
290 }
291 //===================================================================
292 template <typename TYPE>
293 void tlp::MutableContainer<TYPE>::add(const unsigned int i, TYPE val) {
294  if (tlp::StoredType<TYPE>::isPointer == false) {
295  if (maxIndex == UINT_MAX) {
296  assert(state == VECT);
297  minIndex = i;
298  maxIndex = i;
299  (*vData).push_back(defaultValue + val);
300  ++elementInserted;
301  return;
302  }
303 
304  switch (state) {
305  case VECT: {
306  if (i > maxIndex || i < minIndex) {
307  set(i, defaultValue + val);
308  return;
309  }
310 
311  TYPE &oldVal = (*vData)[i - minIndex];
312 
313  if (oldVal == defaultValue) {
314  set(i, defaultValue + val);
315  return;
316  }
317 
318  oldVal += val;
319 
320  return;
321  }
322 
323  case HASH: {
324  typename tlp_hash_map<unsigned int, typename StoredType<TYPE>::Value>::iterator it =
325  hData->find(i);
326 
327  if (it != hData->end()) {
328  // check default value
329  if ((it->second + val) == defaultValue) {
330  StoredType<TYPE>::destroy(it->second);
331  hData->erase(it);
332  --elementInserted;
333  } else
334  it->second += val;
335  } else {
336  set(i, defaultValue + val);
337  }
338 
339  return;
340  }
341 
342  default:
343  assert(false);
344  std::cerr << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
345  }
346  }
347 
348  assert(false);
349  std::cerr << __PRETTY_FUNCTION__ << "not implemented" << std::endl;
350 }
351 //===================================================================
352 template <typename TYPE>
353 typename tlp::StoredType<TYPE>::ReturnedConstValue
354 tlp::MutableContainer<TYPE>::get(const unsigned int i) const {
355  // cerr << __PRETTY_FUNCTION__ << endl;
356  if (!elementInserted)
357  return StoredType<TYPE>::get(defaultValue);
358 
359  switch (state) {
360  case VECT:
361 
362  if (i > maxIndex || i < minIndex)
363  return StoredType<TYPE>::get(defaultValue);
364  else
365  return StoredType<TYPE>::get((*vData)[i - minIndex]);
366 
367  case HASH: {
368  typename tlp_hash_map<unsigned int, typename StoredType<TYPE>::Value>::iterator it =
369  hData->find(i);
370 
371  if (it != hData->end())
372  return StoredType<TYPE>::get(it->second);
373  else
374  return StoredType<TYPE>::get(defaultValue);
375  }
376 
377  default:
378  assert(false);
379  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
380  return StoredType<TYPE>::get(defaultValue);
381  break;
382  }
383 }
384 //===================================================================
385 template <typename TYPE>
386 void tlp::MutableContainer<TYPE>::invertBooleanValue(const unsigned int i) {
387  if (std::is_same<typename StoredType<TYPE>::Value, bool>::value) {
388  switch (state) {
389  case VECT: {
390  if (i > maxIndex || i < minIndex)
391  vectset(i, !defaultValue);
392  else {
393  typename StoredType<TYPE>::Value val = (*vData)[i - minIndex];
394 
395  if (val != defaultValue)
396  --elementInserted;
397  else
398  ++elementInserted;
399  (*vData)[i - minIndex] = !val;
400  }
401  return;
402  }
403 
404  case HASH: {
405  typename tlp_hash_map<unsigned int, typename StoredType<TYPE>::Value>::iterator it =
406  hData->find(i);
407 
408  if (it != hData->end()) {
409  hData->erase(it);
410  --elementInserted;
411  } else {
412  (*hData)[i] = !defaultValue;
413  ++elementInserted;
414  }
415  return;
416  }
417 
418  default:
419  assert(false);
420  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
421  break;
422  }
423  }
424 
425  assert(false);
426  std::cerr << __PRETTY_FUNCTION__ << "not implemented" << std::endl;
427 }
428 //===================================================================
429 template <typename TYPE>
430 typename tlp::StoredType<TYPE>::ReturnedValue tlp::MutableContainer<TYPE>::getDefault() const {
431  return StoredType<TYPE>::get(defaultValue);
432 }
433 //===================================================================
434 template <typename TYPE>
435 bool tlp::MutableContainer<TYPE>::hasNonDefaultValue(const unsigned int i) const {
436  if (!elementInserted)
437  return false;
438 
439  switch (state) {
440  case VECT:
441  return (i <= maxIndex && i >= minIndex && (((*vData)[i - minIndex]) != defaultValue));
442 
443  case HASH:
444  return ((hData->find(i)) != hData->end());
445 
446  default:
447  assert(false);
448  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
449  return false;
450  }
451 }
452 //===================================================================
453 template <typename TYPE>
454 typename tlp::StoredType<TYPE>::ReturnedValue
455 tlp::MutableContainer<TYPE>::get(const unsigned int i, bool &notDefault) const {
456  if (!elementInserted) {
457  notDefault = false;
458  return StoredType<TYPE>::get(defaultValue);
459  }
460 
461  switch (state) {
462  case VECT:
463 
464  if (i > maxIndex || i < minIndex) {
465  notDefault = false;
466  return StoredType<TYPE>::get(defaultValue);
467  } else {
468  typename StoredType<TYPE>::Value val = (*vData)[i - minIndex];
469  notDefault = val != defaultValue;
470  return StoredType<TYPE>::get(val);
471  }
472 
473  case HASH: {
474  typename tlp_hash_map<unsigned int, typename StoredType<TYPE>::Value>::iterator it =
475  hData->find(i);
476 
477  if (it != hData->end()) {
478  notDefault = true;
479  return StoredType<TYPE>::get(it->second);
480  } else {
481  notDefault = false;
482  return StoredType<TYPE>::get(defaultValue);
483  }
484  }
485 
486  default:
487  assert(false);
488  notDefault = false;
489  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
490  return StoredType<TYPE>::get(defaultValue);
491  }
492 }
493 //===================================================================
494 template <typename TYPE>
495 unsigned int tlp::MutableContainer<TYPE>::numberOfNonDefaultValues() const {
496  return elementInserted;
497 }
498 //===================================================================
499 template <typename TYPE>
500 void tlp::MutableContainer<TYPE>::vecttohash() {
501  hData = new tlp_hash_map<unsigned int, typename StoredType<TYPE>::Value>(elementInserted);
502 
503  unsigned int newMaxIndex = 0;
504  unsigned int newMinIndex = UINT_MAX;
505  elementInserted = 0;
506 
507  for (unsigned int i = minIndex; i <= maxIndex; ++i) {
508  if ((*vData)[i - minIndex] != defaultValue) {
509  (*hData)[i] = (*vData)[i - minIndex];
510  newMaxIndex = std::max(newMaxIndex, i);
511  newMinIndex = std::min(newMinIndex, i);
512  ++elementInserted;
513  }
514  }
515 
516  maxIndex = newMaxIndex;
517  minIndex = newMinIndex;
518  delete vData;
519  vData = nullptr;
520  state = HASH;
521 }
522 //===================================================================
523 template <typename TYPE>
524 void tlp::MutableContainer<TYPE>::hashtovect() {
525  vData = new std::deque<typename StoredType<TYPE>::Value>();
526  minIndex = UINT_MAX;
527  maxIndex = UINT_MAX;
528  elementInserted = 0;
529  state = VECT;
530  typename tlp_hash_map<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it;
531 
532  for (it = hData->begin(); it != hData->end(); ++it) {
533  if (it->second != defaultValue)
534  vectset(it->first, it->second);
535  }
536 
537  delete hData;
538  hData = nullptr;
539 }
540 //===================================================================
541 template <typename TYPE>
542 void tlp::MutableContainer<TYPE>::compress(unsigned int min, unsigned int max,
543  unsigned int nbElements) {
544  if (max == UINT_MAX || (max - min) < 10)
545  return;
546 
547  double limitValue = ratio * (double(max - min + 1.0));
548 
549  switch (state) {
550  case VECT:
551 
552  if (double(nbElements) < limitValue) {
553  vecttohash();
554  }
555 
556  break;
557 
558  case HASH:
559 
560  if (double(nbElements) > limitValue * 1.5) {
561  hashtovect();
562  }
563 
564  break;
565 
566  default:
567  assert(false);
568  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
569  break;
570  }
571 }
572 
573 template <typename TYPE>
574 typename tlp::StoredType<TYPE>::ReturnedConstValue
575 tlp::MutableContainer<TYPE>::operator[](const unsigned int i) const {
576  return get(i);
577 }