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