Tulip  5.2.0
Large graphs analysis and drawing
Iterator.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 TULIP_ITERATOR_H
21 #define TULIP_ITERATOR_H
22 
23 #include <cassert>
24 #include <list>
25 #include <set>
26 #include <tuple>
27 #include <vector>
28 
29 #include <tulip/tulipconf.h>
30 
31 namespace tlp {
32 
33 ///@cond DOXYGEN_HIDDEN
34 extern TLP_SCOPE void incrNumIterators();
35 extern TLP_SCOPE void decrNumIterators();
36 extern TLP_SCOPE int getNumIterators();
37 ///@endcond
38 
39 /**
40 * @brief Interface for Tulip iterators.
41 * Allows basic iteration operations only.
42 *
43 * Below are some examples about how to use Tulip iterators in C++ code.
44 *
45 * @code
46 *
47 * // graph is a pointer to a tlp::Graph instance
48 *
49 * // shortest syntax using C++11 for range based loops
50 * for (auto n : graph->getNodes()) {
51 * // do someting with n
52 * }
53 *
54 * // legacy syntax using Tulip forEach macro
55 * #include <tulip/ForEach.h>
56 * tlp::node n;
57 * forEach(n, graph->getNodes()) {
58 * // do something with n
59 * }
60 *
61 * // no syntactic sugar syntax (needs to explicitely delete the iterator
62 * // after its use)
63 * tlp::Iterator<tl::node> *nodesIt = graph->getNodes();
64 * while (nodesIt->hasNext()) {
65 * tlp::node n = nodes->next();
66 * // do something with n
67 * }
68 * delete nodesIt;
69 * @endcode
70 **/
71 template <typename T>
72 struct Iterator {
73  ///
74  Iterator() {
75 #ifndef NDEBUG
76  incrNumIterators();
77 #endif
78  }
79  ///
80  virtual ~Iterator() {
81 #ifndef NDEBUG
82  decrNumIterators();
83 #endif
84  }
85  /**
86  * @brief Moves the Iterator on the next element.
87  *
88  * @return The current element pointed by the Iterator.
89  **/
90  virtual T next() = 0;
91 
92  /**
93  * @brief Tells if the sequence is at its end.
94  *
95  * @return bool Whether there are more elements to iterate.
96  **/
97  virtual bool hasNext() = 0;
98 
99 private:
100  // glue code in order to use Tulip iterators with C++11 for range based loops
101  struct iterator_t {
102 
103  enum IteratorStatus { Begin = 0, Finished = 1, End = 3 };
104 
105  IteratorStatus _iteratorStatus;
106  Iterator<T> *_it;
107 
108  iterator_t(Iterator<T> *it, IteratorStatus iteratorStatus = End)
109  : _iteratorStatus(iteratorStatus), _it(it) {
110  if ((_iteratorStatus == Begin) && (_it->hasNext() == false)) {
111  _iteratorStatus = Finished;
112  }
113  }
114 
115  ~iterator_t() {
116  if (_iteratorStatus != End) {
117  delete _it;
118  }
119  }
120 
121  inline bool operator!=(const iterator_t &it) const {
122  return ((_iteratorStatus & it._iteratorStatus) == 0) || (_it != it._it);
123  }
124 
125  inline const iterator_t &operator++() {
126  if (!_it->hasNext())
127  _iteratorStatus = Finished;
128  return *this;
129  }
130 
131  inline T operator*() const {
132  assert(_iteratorStatus != Finished);
133  return _it->next();
134  }
135  };
136 
137 public:
138  inline iterator_t begin() {
139  return iterator_t(this, iterator_t::Begin);
140  }
141 
142  inline iterator_t end() {
143  return iterator_t(this);
144  }
145 };
146 
147 #ifndef DOXYGEN_NOTFOR_DEVEL
148 // as Iterator is only accessible through pointer
149 // we must have a specific definition of begin and end
150 template <typename T>
151 inline auto begin(Iterator<T> *it) -> decltype(it->begin()) {
152  return it->begin();
153 }
154 
155 template <typename T>
156 inline auto end(Iterator<T> *it) -> decltype(it->end()) {
157  return it->end();
158 }
159 #endif
160 
161 /**
162 * @brief Counts the number of iterated elements
163 * @ingroup Iterators
164 *
165 * @since Tulip 5.2
166 *
167 * Counts the number of elements iterated by the provided iterator.
168 * That function takes ownership of the iterator and will delete it.
169 *
170 * @param it a Tulip iterator
171 *
172 * @return The number of iterated elements
173 **/
174 template <typename T>
175 inline unsigned int iteratorCount(Iterator<T> *it) {
176  unsigned int count = 0;
177  while (it->hasNext()) {
178  ++count;
179  it->next();
180  }
181  delete it;
182  return count;
183 }
184 
185 /**
186 * @brief Checks a mimimum amount of iterated elements
187 * @ingroup Iterators
188 *
189 * @since Tulip 5.2
190 *
191 * Checks if the iterator returns at least n values.
192 * That function takes ownership of the iterator and will delete it.
193 *
194 * @param it a Tulip iterator
195 *
196 * @return true if the iterator returns at least n values
197 **/
198 template <typename T>
199 inline bool iteratorCountCheck(Iterator<T> *it, unsigned int minNbElements) {
200  unsigned int count = 0;
201  while (it->hasNext()) {
202  ++count;
203  if (count == minNbElements) {
204  delete it;
205  return true;
206  }
207  it->next();
208  }
209  delete it;
210  return false;
211 }
212 
213 /**
214 * @brief Checks if an iterator is empty
215 * @ingroup Iterators
216 *
217 * @since Tulip 5.2
218 *
219 * Checks if the iterator does not return any value.
220 * That function takes ownership of the iterator and will delete it.
221 *
222 * @param it a Tulip iterator
223 *
224 * @return true if the iterator is empty
225 **/
226 template <typename T>
227 inline bool iteratorEmpty(Iterator<T> *it) {
228  return !iteratorCountCheck(it, 1);
229 }
230 
231 /**
232 * @brief Applies a function to each iterated element
233 * @ingroup Iterators
234 *
235 * @since Tulip 5.2
236 *
237 * Applies a function to each element iterated by the provided iterator.
238 * That function takes ownership of the iterator and will delete it.
239 *
240 * @param it a Tulip iterator
241 * @param mapFunction functor or lambda function taking one parameter of the same type of the
242 *iterated elements
243 *
244 *
245 **/
246 template <typename T, class MapFunction>
247 inline void iteratorMap(Iterator<T> *it, MapFunction &&mapFunction) {
248  if (sizeof(T) > sizeof(double)) {
249  for (const auto &v : it) {
250  mapFunction(v);
251  }
252  } else {
253  for (auto v : it) {
254  mapFunction(v);
255  }
256  }
257 }
258 
259 /**
260 * @brief Reduces iterated elements to a single value
261 * @ingroup Iterators
262 *
263 * @since Tulip 5.2
264 *
265 * Produces a single value from the iterated elements (e.g. sum).
266 * That function takes ownership of the iterator and will delete it.
267 *
268 * @param it a Tulip iterator
269 * @param initVal initial value of the reduced result
270 * @param reduceFunction functor or lambda function taking two parameters : first one being the
271 *current reduced value,
272 * second one being the current iterated element and returning intermediate reduced value
273 *
274 * @return the reduced value from the iterated elements
275 *
276 **/
277 template <typename T, typename reduceType, class ReduceFunction>
278 inline reduceType iteratorReduce(Iterator<T> *it, const reduceType &initVal,
279  ReduceFunction reduceFunction) {
280  reduceType val = initVal;
281  if (sizeof(T) > sizeof(double)) {
282  for (const auto &v : it) {
283  val = reduceFunction(val, v);
284  }
285  } else {
286  for (auto v : it) {
287  val = reduceFunction(val, v);
288  }
289  }
290  return val;
291 }
292 
293 /**
294 * @brief Converts an iterator to a std::list
295 * @ingroup Iterators
296 *
297 * @since Tulip 5.2
298 *
299 * Returns a std::list filled with the iterated elements.
300 * That function takes ownership of the iterator and will delete it.
301 *
302 * @param it a Tulip iterator
303 *
304 * @return a std::list filled with iterated elements
305 **/
306 template <typename T>
307 inline std::list<T> iteratorList(Iterator<T> *it) {
308  std::list<T> ret;
309  while (it->hasNext()) {
310  ret.push_back(std::move(it->next()));
311  }
312  delete it;
313  return ret;
314 }
315 
316 /**
317 * @brief Converts an iterator to a std::vector
318 * @ingroup Iterators
319 *
320 * @since Tulip 5.2
321 *
322 * Returns a std::vector filled with the iterated elements.
323 * That function takes ownership of the iterator and will delete it.
324 *
325 * @param it a Tulip iterator
326 *
327 * @return a std::vector filled with iterated elements
328 **/
329 template <typename T>
330 inline std::vector<T> iteratorVector(Iterator<T> *it) {
331  std::vector<T> ret;
332  while (it->hasNext()) {
333  ret.push_back(std::move(it->next()));
334  }
335  delete it;
336  return ret;
337 }
338 
339 /**
340 * @brief Converts an iterator to a std::set
341 * @ingroup Iterators
342 *
343 * @since Tulip 5.2
344 *
345 * Returns a std::set filled with the iterated elements.
346 * That function takes ownership of the iterator and will delete it.
347 *
348 * @param it a Tulip iterator
349 *
350 * @return a std::set filled with iterated elements
351 **/
352 template <typename T>
353 inline std::set<T> iteratorSet(Iterator<T> *it) {
354  std::set<T> ret;
355  while (it->hasNext()) {
356  ret.insert(std::move(it->next()));
357  }
358  delete it;
359  return ret;
360 }
361 
362 #ifndef DOXYGEN_NOTFOR_DEVEL
363 template <typename TYPE>
364 class UINTIterator : public Iterator<TYPE> {
365 public:
366  UINTIterator(Iterator<unsigned int> *it) : it(it) {}
367  ~UINTIterator() override {
368  delete it;
369  }
370  bool hasNext() override {
371  return it->hasNext();
372  }
373  TYPE next() override {
374  return TYPE(it->next());
375  }
376 
377 private:
379 };
380 
381 #endif // DOXYGEN_NOTFOR_DEVEL
382 }
383 
384 #ifdef _MSC_VER
385 
386 #include <tulip/Edge.h>
387 #include <tulip/Node.h>
388 
389 template struct TLP_SCOPE tlp::Iterator<tlp::edge>;
390 template struct TLP_SCOPE tlp::Iterator<tlp::node>;
391 #endif
392 #endif
bool iteratorEmpty(Iterator< T > *it)
Checks if an iterator is empty.
Definition: Iterator.h:227
unsigned int iteratorCount(Iterator< T > *it)
Counts the number of iterated elements.
Definition: Iterator.h:175
virtual T next()=0
Moves the Iterator on the next element.
Interface for Tulip iterators. Allows basic iteration operations only.
Definition: Graph.h:41
void iteratorMap(Iterator< T > *it, MapFunction &&mapFunction)
Applies a function to each iterated element.
Definition: Iterator.h:247
std::list< T > iteratorList(Iterator< T > *it)
Converts an iterator to a std::list.
Definition: Iterator.h:307
std::set< T > iteratorSet(Iterator< T > *it)
Converts an iterator to a std::set.
Definition: Iterator.h:353
bool iteratorCountCheck(Iterator< T > *it, unsigned int minNbElements)
Checks a mimimum amount of iterated elements.
Definition: Iterator.h:199
std::vector< T > iteratorVector(Iterator< T > *it)
Converts an iterator to a std::vector.
Definition: Iterator.h:330
reduceType iteratorReduce(Iterator< T > *it, const reduceType &initVal, ReduceFunction reduceFunction)
Reduces iterated elements to a single value.
Definition: Iterator.h:278
virtual bool hasNext()=0
Tells if the sequence is at its end.