Tulip  4.1.0
Better Visualization Through Research
 All Classes 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 1 and Inria Bordeaux - Sud Ouest
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  qWarning() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)";
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  qWarning() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)";
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  qWarning() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)";
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  qWarning() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)";
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  qWarning() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)";
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  if (i>maxIndex || i<minIndex)
350  return StoredType<TYPE>::get(defaultValue);
351  else
352  return StoredType<TYPE>::get((*vData)[i - minIndex]);
353 
354  case HASH: {
355  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i);
356 
357  if (it!=hData->end())
358  return StoredType<TYPE>::get((*it).second);
359  else
360  return StoredType<TYPE>::get(defaultValue);
361  }
362 
363  default:
364  assert(false);
365  qWarning() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)";
366  return StoredType<TYPE>::get(defaultValue);
367  break;
368  }
369 }
370 //===================================================================
371 template <typename TYPE>
372 typename tlp::StoredType<TYPE>::ReturnedValue tlp::MutableContainer<TYPE>::getDefault() const {
373  return StoredType<TYPE>::get(defaultValue);
374 }
375 //===================================================================
376 template <typename TYPE>
377 bool tlp::MutableContainer<TYPE>::hasNonDefaultValue(const unsigned int i) const {
378  if (maxIndex == UINT_MAX) return false;
379 
380  switch (state) {
381  case VECT:
382  return (i<=maxIndex && i>=minIndex &&
383  (((*vData)[i - minIndex]) != defaultValue));
384 
385  case HASH:
386  return ((hData->find(i))!=hData->end());
387 
388  default:
389  assert(false);
390  qWarning() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)";
391  return false;
392  }
393 }
394 //===================================================================
395 template <typename TYPE>
396 typename tlp::StoredType<TYPE>::ReturnedValue tlp::MutableContainer<TYPE>::get(const unsigned int i, bool& notDefault) const {
397  if (maxIndex == UINT_MAX) {
398  notDefault = false;
399  return StoredType<TYPE>::get(defaultValue);
400  }
401 
402  switch (state) {
403  case VECT:
404  if (i>maxIndex || i<minIndex) {
405  notDefault = false;
406  return StoredType<TYPE>::get(defaultValue);
407  }
408  else {
409  typename StoredType<TYPE>::Value val = (*vData)[i - minIndex];
410  notDefault = val != defaultValue;
411  return StoredType<TYPE>::get(val);
412  }
413 
414  case HASH: {
415  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::iterator it = hData->find(i);
416 
417  if (it!=hData->end()) {
418  notDefault = true;
419  return StoredType<TYPE>::get((*it).second);
420  }
421  else {
422  notDefault = false;
423  return StoredType<TYPE>::get(defaultValue);
424  }
425  }
426 
427  default:
428  assert(false);
429  notDefault = false;
430  qWarning() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)";
431  return StoredType<TYPE>::get(defaultValue);
432  }
433 }
434 //===================================================================
435 template <typename TYPE>
436 void tlp::MutableContainer<TYPE>::vecttohash() {
437  hData=new TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>(elementInserted);
438 
439  unsigned int newMaxIndex = 0;
440  unsigned int newMinIndex = UINT_MAX;
441  elementInserted = 0;
442 
443  for (unsigned int i=minIndex; i<=maxIndex; ++i) {
444  if ((*vData)[i - minIndex] != defaultValue) {
445  (*hData)[i] = (*vData)[i - minIndex];
446  newMaxIndex = std::max(newMaxIndex, i);
447  newMinIndex = std::min(newMinIndex, i);
448  ++elementInserted;
449  }
450  }
451 
452  maxIndex = newMaxIndex;
453  minIndex = newMinIndex;
454  delete vData;
455  vData = NULL;
456  state = HASH;
457 }
458 //===================================================================
459 template <typename TYPE>
460 void tlp::MutableContainer<TYPE>::hashtovect() {
461  vData = new std::deque<typename StoredType<TYPE>::Value>();
462  minIndex = UINT_MAX;
463  maxIndex = UINT_MAX;
464  elementInserted = 0;
465  state=VECT;
466  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it;
467 
468  for (it=hData->begin(); it!=hData->end(); ++it) {
469  if (it->second != defaultValue)
470  vectset(it->first, it->second);
471  }
472 
473  delete hData;
474  hData = NULL;
475 }
476 //===================================================================
477 template <typename TYPE>
478 void tlp::MutableContainer<TYPE>::compress(unsigned int min, unsigned int max, unsigned int nbElements) {
479  if (max == UINT_MAX || (max - min) < 10) return;
480 
481  double limitValue = ratio*(double(max - min + 1.0));
482 
483  switch (state) {
484  case VECT:
485 
486  if ( double(nbElements) < limitValue) {
487  vecttohash();
488  }
489 
490  break;
491 
492  case HASH:
493 
494  if ( double(nbElements) > limitValue*1.5) {
495  hashtovect();
496  }
497 
498  break;
499 
500  default:
501  assert(false);
502  qWarning() << __PRETTY_FUNCTION__ << "unexpected state value (serious bug)";
503  break;
504  }
505 }
506 
507 template <typename TYPE>
508 typename tlp::StoredType<TYPE>::ReturnedConstValue tlp::MutableContainer<TYPE>::operator[](const unsigned int i) const {
509  return get(i);
510 }