Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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//===================================================================
20template <typename TYPE>
21tlp::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//===================================================================
29template <typename TYPE>
30tlp::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 std::unordered_map<unsigned int, typename StoredType<TYPE>::Value>::const_iterator
55 it = 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//===================================================================
76template <typename TYPE>
77void tlp::MutableContainer<TYPE>::setDefault(typename StoredType<TYPE>::ReturnedConstValue value) {
78 StoredType<TYPE>::destroy(defaultValue);
79 defaultValue = StoredType<TYPE>::clone(value);
80}
81//===================================================================
82template <typename TYPE>
83void 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 std::unordered_map<unsigned int, typename StoredType<TYPE>::Value>::const_iterator
107 it = 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
136template <typename TYPE>
137tlp::IteratorValue *
138tlp::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
162template <typename TYPE>
164tlp::MutableContainer<TYPE>::findAll(typename StoredType<TYPE>::ReturnedConstValue value,
165 bool equal) const {
166 return findAllValues(value, equal);
167}
168//===================================================================
169template <typename TYPE>
170void 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//===================================================================
210template <typename TYPE>
211void 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 std::unordered_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 std::unordered_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//===================================================================
292template <typename TYPE>
293void 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 std::unordered_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//===================================================================
352template <typename TYPE>
353typename tlp::StoredType<TYPE>::ReturnedConstValue
354tlp::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 std::unordered_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//===================================================================
385template <typename TYPE>
386void 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 std::unordered_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//===================================================================
429template <typename TYPE>
430typename tlp::StoredType<TYPE>::ReturnedValue tlp::MutableContainer<TYPE>::getDefault() const {
431 return StoredType<TYPE>::get(defaultValue);
432}
433//===================================================================
434template <typename TYPE>
435bool 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//===================================================================
453template <typename TYPE>
454typename tlp::StoredType<TYPE>::ReturnedValue
455tlp::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 std::unordered_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//===================================================================
494template <typename TYPE>
495unsigned int tlp::MutableContainer<TYPE>::numberOfNonDefaultValues() const {
496 return elementInserted;
497}
498//===================================================================
499template <typename TYPE>
500void tlp::MutableContainer<TYPE>::vecttohash() {
501 hData = new std::unordered_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//===================================================================
523template <typename TYPE>
524void 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 std::unordered_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//===================================================================
541template <typename TYPE>
542void 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
573template <typename TYPE>
574typename tlp::StoredType<TYPE>::ReturnedConstValue
575tlp::MutableContainer<TYPE>::operator[](const unsigned int i) const {
576 return get(i);
577}
Interface for Tulip iterators. Allows basic iteration operations only.
Definition: Iterator.h:74