Tulip  5.2.0
Large graphs analysis and drawing
MutableContainer.h
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 #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 <tulip/tulipconf.h>
30 #include <tulip/tuliphash.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 private:
113  MutableContainer(const MutableContainer<TYPE> &) {}
114  void operator=(const MutableContainer<TYPE> &) {}
115  typename StoredType<TYPE>::ReturnedConstValue operator[](const unsigned int i) const;
116  void vecttohash();
117  void hashtovect();
118  void compress(unsigned int min, unsigned int max, unsigned int nbElements);
119  inline void vectset(const unsigned int i, typename StoredType<TYPE>::Value value);
120  IteratorValue *findAllValues(typename StoredType<TYPE>::ReturnedConstValue value,
121  bool equal = true) const;
122 
123 private:
124  std::deque<typename StoredType<TYPE>::Value> *vData;
125  TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value> *hData;
126  unsigned int minIndex, maxIndex;
127  typename StoredType<TYPE>::Value defaultValue;
128  enum State { VECT = 0, HASH = 1 };
129  State state;
130  unsigned int elementInserted;
131  double ratio;
132  bool compressing;
133 };
134 
135 //===================================================================
136 // we implement 2 templates with IteratorValue as parent class
137 // for the two kinds of storage used in a MutableContainer
138 // one for vector storage
139 template <typename TYPE>
140 class IteratorVect : public tlp::IteratorValue {
141 public:
142  IteratorVect(const TYPE &value, bool equal, std::deque<typename StoredType<TYPE>::Value> *vData,
143  unsigned int minIndex)
144  : _value(value), _equal(equal), _pos(minIndex), vData(vData), it(vData->begin()) {
145  while (it != (*vData).end() && StoredType<TYPE>::equal((*it), _value) != _equal) {
146  ++it;
147  ++_pos;
148  }
149  }
150  bool hasNext() override {
151  return (_pos < UINT_MAX && it != (*vData).end());
152  }
153  unsigned int next() override {
154  unsigned int tmp = _pos;
155 
156  do {
157  ++it;
158  ++_pos;
159  } while (it != (*vData).end() && StoredType<TYPE>::equal((*it), _value) != _equal);
160 
161  return tmp;
162  }
163  unsigned int nextValue(DataMem &val) override {
164  static_cast<TypedValueContainer<TYPE> &>(val).value = StoredType<TYPE>::get(*it);
165  unsigned int pos = _pos;
166 
167  do {
168  ++it;
169  ++_pos;
170  } while (it != (*vData).end() && StoredType<TYPE>::equal((*it), _value) != _equal);
171 
172  return pos;
173  }
174 
175 private:
176  const TYPE _value;
177  bool _equal;
178  unsigned int _pos;
179  std::deque<typename StoredType<TYPE>::Value> *vData;
180  typename std::deque<typename StoredType<TYPE>::Value>::const_iterator it;
181 };
182 
183 ///@cond DOXYGEN_HIDDEN
184 // one for hash storage
185 template <typename TYPE>
186 class IteratorHash : public IteratorValue {
187 public:
188  IteratorHash(const TYPE &value, bool equal,
189  TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value> *hData)
190  : _value(value), _equal(equal), hData(hData) {
191  it = (*hData).begin();
192 
193  while (it != (*hData).end() && StoredType<TYPE>::equal((*it).second, _value) != _equal)
194  ++it;
195  }
196  bool hasNext() override {
197  return (it != (*hData).end());
198  }
199  unsigned int next() override {
200  unsigned int tmp = (*it).first;
201 
202  do {
203  ++it;
204  } while (it != (*hData).end() && StoredType<TYPE>::equal((*it).second, _value) != _equal);
205 
206  return tmp;
207  }
208  unsigned int nextValue(DataMem &val) override {
209  static_cast<TypedValueContainer<TYPE> &>(val).value = StoredType<TYPE>::get((*it).second);
210  unsigned int pos = (*it).first;
211 
212  do {
213  ++it;
214  } while (it != (*hData).end() && StoredType<TYPE>::equal((*it).second, _value) != _equal);
215 
216  return pos;
217  }
218 
219 private:
220  const TYPE _value;
221  bool _equal;
222  TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value> *hData;
223  typename TLP_HASH_MAP<unsigned int, typename StoredType<TYPE>::Value>::const_iterator it;
224 };
225 ///@endcond
226 }
227 
228 ///@cond DOXYGEN_HIDDEN
229 #include "cxx/MutableContainer.cxx"
230 ///@endcond
231 
232 #endif