Tulip  5.7.4
Large graphs analysis and drawing
MutableContainer.h
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 #ifndef _TLPMUTABLECONTAINER_
21 #define _TLPMUTABLECONTAINER_
22 
23 #include <deque>
24 #include <iostream>
25 #include <string>
26 #include <cassert>
27 #include <climits>
28 #include <cstring>
29 #include <unordered_map>
30 #include <tulip/tulipconf.h>
31 #include <tulip/StoredType.h>
32 #include <tulip/DataSet.h>
33 #include <tulip/Iterator.h>
34 
35 namespace tlp {
36 
37 ///@cond DOXYGEN_HIDDEN
38 //===================================================================
39 // we first define an interface
40 // to make easier the iteration on values
41 // stored in a MutableContainer for the GraphUpdatesRecorder
42 class IteratorValue : public Iterator<unsigned int> {
43 public:
44  IteratorValue() {}
45  ~IteratorValue() override {}
46  virtual unsigned int nextValue(DataMem &) = 0;
47 };
48 ///@endcond
49 //===================================================================
50 template <typename TYPE>
51 class MutableContainer {
52  friend class MutableContainerTest;
53  friend class GraphUpdatesRecorder;
54 
55 public:
56  MutableContainer();
57  ~MutableContainer();
58 
59  /**
60  * Set the default value
61  */
62  void setDefault(typename StoredType<TYPE>::ReturnedConstValue value);
63  /**
64  * set the same value to all elements and modify the default value
65  */
66  void setAll(typename StoredType<TYPE>::ReturnedConstValue value);
67  /**
68  * set the value associated to i
69  */
70  void set(const unsigned int i, typename StoredType<TYPE>::ReturnedConstValue value,
71  bool forceDefaultValueRemoval = false);
72  /**
73  * add val to the value associated to i
74  */
75  void add(const unsigned int i, TYPE val);
76  /**
77  * get the value associated to i
78  */
79  typename StoredType<TYPE>::ReturnedConstValue get(const unsigned int i) const;
80  /**
81  * get the value associated to i and indicates if it is not the default one
82  */
83  typename StoredType<TYPE>::ReturnedValue get(const unsigned int i, bool &isNotDefault) const;
84  /**
85  * get the default value
86  */
87  typename StoredType<TYPE>::ReturnedValue getDefault() const;
88  /**
89  * return if the value associated to i is not the default one
90  */
91  bool hasNonDefaultValue(const unsigned int i) const;
92  /**
93  * return a pointer on an iterator for all the elements whose associated value
94  * is equal to a given value or different from the default value.
95  * A null pointer is returned in case of an iteration on all the elements
96  * whose value is equal to the default value.
97  */
98  Iterator<unsigned int> *findAll(typename StoredType<TYPE>::ReturnedConstValue value,
99  bool equal = true) const;
100  /**
101  * return the number of non default values
102  */
103  unsigned int numberOfNonDefaultValues() const;
104 
105  /**
106  * return whether a non default value exists
107  */
108  bool hasNonDefaultValues() const {
109  return numberOfNonDefaultValues() != 0;
110  }
111 
112  /**
113  * invert the Boolean value set to i (do nothing for non Boolean value)
114  */
115  void invertBooleanValue(const unsigned int i);
116 
117 private:
118  MutableContainer(const MutableContainer<TYPE> &) {}
119  void operator=(const MutableContainer<TYPE> &) {}
120  typename StoredType<TYPE>::ReturnedConstValue operator[](const unsigned int i) const;
121  void vecttohash();
122  void hashtovect();
123  void compress(unsigned int min, unsigned int max, unsigned int nbElements);
124  inline void vectset(const unsigned int i, typename StoredType<TYPE>::Value value);
125  IteratorValue *findAllValues(typename StoredType<TYPE>::ReturnedConstValue value,
126  bool equal = true) const;
127 
128 private:
129  std::deque<typename StoredType<TYPE>::Value> *vData;
130  std::unordered_map<unsigned int, typename StoredType<TYPE>::Value> *hData;
131  unsigned int minIndex, maxIndex;
132  typename StoredType<TYPE>::Value defaultValue;
133  enum State { VECT = 0, HASH = 1 };
134  State state;
135  unsigned int elementInserted;
136  double ratio;
137  bool compressing;
138 };
139 
140 //===================================================================
141 // we implement 2 templates with IteratorValue as parent class
142 // for the two kinds of storage used in a MutableContainer
143 // one for vector storage
144 template <typename TYPE>
145 class IteratorVect : public tlp::IteratorValue {
146 public:
147  IteratorVect(const TYPE &value, bool equal, std::deque<typename StoredType<TYPE>::Value> *vData,
148  unsigned int minIndex)
149  : _value(value), _equal(equal), _pos(minIndex), vData(vData), it(vData->begin()) {
150  while (it != (*vData).end() && StoredType<TYPE>::equal((*it), _value) != _equal) {
151  ++it;
152  ++_pos;
153  }
154  }
155  bool hasNext() override {
156  return (_pos < UINT_MAX && it != (*vData).end());
157  }
158  unsigned int next() override {
159  unsigned int tmp = _pos;
160 
161  do {
162  ++it;
163  ++_pos;
164  } while (it != (*vData).end() && StoredType<TYPE>::equal((*it), _value) != _equal);
165 
166  return tmp;
167  }
168  unsigned int nextValue(DataMem &val) override {
169  static_cast<TypedValueContainer<TYPE> &>(val).value = StoredType<TYPE>::get(*it);
170  unsigned int pos = _pos;
171 
172  do {
173  ++it;
174  ++_pos;
175  } while (it != (*vData).end() && StoredType<TYPE>::equal((*it), _value) != _equal);
176 
177  return pos;
178  }
179 
180 private:
181  const TYPE _value;
182  bool _equal;
183  unsigned int _pos;
184  std::deque<typename StoredType<TYPE>::Value> *vData;
185  typename std::deque<typename StoredType<TYPE>::Value>::const_iterator it;
186 };
187 
188 ///@cond DOXYGEN_HIDDEN
189 // one for hash storage
190 template <typename TYPE>
191 class IteratorHash : public IteratorValue {
192 public:
193  IteratorHash(const TYPE &value, bool equal,
194  std::unordered_map<unsigned int, typename StoredType<TYPE>::Value> *hData)
195  : _value(value), _equal(equal), hData(hData) {
196  it = (*hData).begin();
197 
198  while (it != (*hData).end() && StoredType<TYPE>::equal((*it).second, _value) != _equal)
199  ++it;
200  }
201  bool hasNext() override {
202  return (it != (*hData).end());
203  }
204  unsigned int next() override {
205  unsigned int tmp = (*it).first;
206 
207  do {
208  ++it;
209  } while (it != (*hData).end() && StoredType<TYPE>::equal((*it).second, _value) != _equal);
210 
211  return tmp;
212  }
213  unsigned int nextValue(DataMem &val) override {
214  static_cast<TypedValueContainer<TYPE> &>(val).value = StoredType<TYPE>::get((*it).second);
215  unsigned int pos = (*it).first;
216 
217  do {
218  ++it;
219  } while (it != (*hData).end() && StoredType<TYPE>::equal((*it).second, _value) != _equal);
220 
221  return pos;
222  }
223 
224 private:
225  const TYPE _value;
226  bool _equal;
227  std::unordered_map<unsigned int, typename StoredType<TYPE>::Value> *hData;
228  typename std::unordered_map<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it;
229 };
230 ///@endcond
231 } // namespace tlp
232 
233 ///@cond DOXYGEN_HIDDEN
234 #include "cxx/MutableContainer.cxx"
235 ///@endcond
236 
237 #endif