Tulip  5.2.1
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 } // namespace tlp
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.