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