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