Tulip  5.2.1
Large graphs analysis and drawing
MutableContainer.cxx
1 /*
2  *
3  * This file is part of Tulip (http://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(i);
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  else
274  ++elementInserted;
275 
276  (*hData)[i] = newVal;
277  break;
278  }
279 
280  default:
281  assert(false);
282  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
283  break;
284  }
285 
286  maxIndex = std::max(maxIndex, i);
287  minIndex = std::min(minIndex, i);
288  }
289 }
290 //===================================================================
291 template <typename TYPE>
292 void tlp::MutableContainer<TYPE>::add(const unsigned int i, TYPE val) {
293  if (tlp::StoredType<TYPE>::isPointer == false) {
294  if (maxIndex == UINT_MAX) {
295  assert(state == VECT);
296  minIndex = i;
297  maxIndex = i;
298  (*vData).push_back(defaultValue + val);
299  ++elementInserted;
300  return;
301  }
302 
303  switch (state) {
304  case VECT: {
305  if (i > maxIndex || i < minIndex) {
306  set(i, defaultValue + val);
307  return;
308  }
309 
310  TYPE &oldVal = (*vData)[i - minIndex];
311 
312  if (oldVal == defaultValue) {
313  set(i, defaultValue + val);
314  return;
315  }
316 
317  oldVal += val;
318 
319  return;
320  }
321 
322  case HASH: {
323  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it =
324  hData->find(i);
325 
326  if (it != hData->end()) {
327  // check default value
328  if ((it->second + val) == defaultValue) {
329  StoredType<TYPE>::destroy((*it).second);
330  hData->erase(i);
331  --elementInserted;
332  } else
333  it->second += val;
334  } else {
335  set(i, defaultValue + val);
336  }
337 
338  return;
339  }
340 
341  default:
342  assert(false);
343  std::cerr << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
344  }
345  }
346 
347  assert(false);
348  std::cerr << __PRETTY_FUNCTION__ << "not implemented" << std::endl;
349 }
350 //===================================================================
351 template <typename TYPE>
352 typename tlp::StoredType<TYPE>::ReturnedConstValue
353 tlp::MutableContainer<TYPE>::get(const unsigned int i) const {
354  // cerr << __PRETTY_FUNCTION__ << endl;
355  if (maxIndex == UINT_MAX)
356  return StoredType<TYPE>::get(defaultValue);
357 
358  switch (state) {
359  case VECT:
360 
361  if (i > maxIndex || i < minIndex)
362  return StoredType<TYPE>::get(defaultValue);
363  else
364  return StoredType<TYPE>::get((*vData)[i - minIndex]);
365 
366  case HASH: {
367  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it =
368  hData->find(i);
369 
370  if (it != hData->end())
371  return StoredType<TYPE>::get((*it).second);
372  else
373  return StoredType<TYPE>::get(defaultValue);
374  }
375 
376  default:
377  assert(false);
378  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
379  return StoredType<TYPE>::get(defaultValue);
380  break;
381  }
382 }
383 //===================================================================
384 template <typename TYPE>
385 typename tlp::StoredType<TYPE>::ReturnedValue tlp::MutableContainer<TYPE>::getDefault() const {
386  return StoredType<TYPE>::get(defaultValue);
387 }
388 //===================================================================
389 template <typename TYPE>
390 bool tlp::MutableContainer<TYPE>::hasNonDefaultValue(const unsigned int i) const {
391  if (maxIndex == UINT_MAX)
392  return false;
393 
394  switch (state) {
395  case VECT:
396  return (i <= maxIndex && i >= minIndex && (((*vData)[i - minIndex]) != defaultValue));
397 
398  case HASH:
399  return ((hData->find(i)) != hData->end());
400 
401  default:
402  assert(false);
403  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
404  return false;
405  }
406 }
407 //===================================================================
408 template <typename TYPE>
409 typename tlp::StoredType<TYPE>::ReturnedValue
410 tlp::MutableContainer<TYPE>::get(const unsigned int i, bool &notDefault) const {
411  if (maxIndex == UINT_MAX) {
412  notDefault = false;
413  return StoredType<TYPE>::get(defaultValue);
414  }
415 
416  switch (state) {
417  case VECT:
418 
419  if (i > maxIndex || i < minIndex) {
420  notDefault = false;
421  return StoredType<TYPE>::get(defaultValue);
422  } else {
423  typename StoredType<TYPE>::Value val = (*vData)[i - minIndex];
424  notDefault = val != defaultValue;
425  return StoredType<TYPE>::get(val);
426  }
427 
428  case HASH: {
429  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it =
430  hData->find(i);
431 
432  if (it != hData->end()) {
433  notDefault = true;
434  return StoredType<TYPE>::get((*it).second);
435  } else {
436  notDefault = false;
437  return StoredType<TYPE>::get(defaultValue);
438  }
439  }
440 
441  default:
442  assert(false);
443  notDefault = false;
444  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
445  return StoredType<TYPE>::get(defaultValue);
446  }
447 }
448 //===================================================================
449 template <typename TYPE>
450 unsigned int tlp::MutableContainer<TYPE>::numberOfNonDefaultValues() const {
451  return elementInserted;
452 }
453 //===================================================================
454 template <typename TYPE>
455 void tlp::MutableContainer<TYPE>::vecttohash() {
456  hData = new TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>(elementInserted);
457 
458  unsigned int newMaxIndex = 0;
459  unsigned int newMinIndex = UINT_MAX;
460  elementInserted = 0;
461 
462  for (unsigned int i = minIndex; i <= maxIndex; ++i) {
463  if ((*vData)[i - minIndex] != defaultValue) {
464  (*hData)[i] = (*vData)[i - minIndex];
465  newMaxIndex = std::max(newMaxIndex, i);
466  newMinIndex = std::min(newMinIndex, i);
467  ++elementInserted;
468  }
469  }
470 
471  maxIndex = newMaxIndex;
472  minIndex = newMinIndex;
473  delete vData;
474  vData = nullptr;
475  state = HASH;
476 }
477 //===================================================================
478 template <typename TYPE>
479 void tlp::MutableContainer<TYPE>::hashtovect() {
480  vData = new std::deque<typename StoredType<TYPE>::Value>();
481  minIndex = UINT_MAX;
482  maxIndex = UINT_MAX;
483  elementInserted = 0;
484  state = VECT;
485  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it;
486 
487  for (it = hData->begin(); it != hData->end(); ++it) {
488  if (it->second != defaultValue)
489  vectset(it->first, it->second);
490  }
491 
492  delete hData;
493  hData = nullptr;
494 }
495 //===================================================================
496 template <typename TYPE>
497 void tlp::MutableContainer<TYPE>::compress(unsigned int min, unsigned int max,
498  unsigned int nbElements) {
499  if (max == UINT_MAX || (max - min) < 10)
500  return;
501 
502  double limitValue = ratio * (double(max - min + 1.0));
503 
504  switch (state) {
505  case VECT:
506 
507  if (double(nbElements) < limitValue) {
508  vecttohash();
509  }
510 
511  break;
512 
513  case HASH:
514 
515  if (double(nbElements) > limitValue * 1.5) {
516  hashtovect();
517  }
518 
519  break;
520 
521  default:
522  assert(false);
523  tlp::error() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)" << std::endl;
524  break;
525  }
526 }
527 
528 template <typename TYPE>
529 typename tlp::StoredType<TYPE>::ReturnedConstValue tlp::MutableContainer<TYPE>::
530 operator[](const unsigned int i) const {
531  return get(i);
532 }