Tulip  5.2.0
Large graphs analysis and drawing
UniqueIterator.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 UNIQUEITERATOR_H
21 #define UNIQUEITERATOR_H
22 
23 #include <set>
24 
25 #include <tulip/Iterator.h>
26 #include <tulip/StlIterator.h>
27 #include <tulip/memorypool.h>
28 
29 //===============================================================================
30 namespace tlp {
31 /**
32 * @brief That class implement a default functor that always returns true
33 *
34 * @see UniqueIterator
35 */
36 template <typename T>
38  bool operator()(const T &) {
39  return true;
40  }
41 };
42 
43 /**
44 * @class UniqueIterator
45 * @ingroup Iterators
46 *
47 * @brief UniqueIterator enables to remove duplicated elements in an iterator
48 *
49 * @param it the iterator in which we want to filter out duplicated elements
50 * @param checkFunctor a functor or a lambda function that enables to indicate whether or not the
51 *element could be duplicated (default test all elements)
52 *
53 * The functor function shoul have the following form
54 * @code
55 * template <typename T>
56 * class ACheckFunctor {
57 * bool operator(const T &a) {
58 * return true if a could be duplicated else false;
59 * }
60 * };
61 * @endcode
62 * checkFunctor are used for optimization purpose to prevent to log(n) test for all elements when not
63 *necessary.
64 **/
65 template <typename T, typename CheckFunc = CheckAllFunctor<T>>
66 class UniqueIterator : public Iterator<T> {
67 public:
68  UniqueIterator(Iterator<T> *it, CheckFunc checkFunctor = CheckFunc())
69  : _it(it), _checkFunctor(checkFunctor) {
70  update();
71  }
72  //================================================
73  ~UniqueIterator() {
74  delete _it;
75  }
76  //================================================
77  T next() {
78  T tmp = curVal;
79  update();
80  return tmp;
81  }
82  //================================================
83  inline bool hasNext() {
84  return _hasNext;
85  }
86  //================================================
87  void update() {
88  _hasNext = false;
89 
90  while (_it->hasNext()) {
91  curVal = _it->next();
92 
93  if (_checkFunctor(curVal)) {
94  if (_flag.find(curVal) == _flag.end()) {
95  _hasNext = true;
96  _flag.insert(curVal);
97  return;
98  }
99  } else {
100  _hasNext = true;
101  return;
102  }
103  }
104  }
105 
106 private:
107  std::set<T> _flag;
108  bool _hasNext;
109  Iterator<T> *_it;
110  T curVal;
111  CheckFunc _checkFunctor;
112 };
113 
114 template <typename T, typename CheckFunc = CheckAllFunctor<T>>
115 class MPUniqueIterator : public UniqueIterator<T, CheckFunc>,
116  public MemoryPool<MPUniqueIterator<T, CheckFunc>> {
117 public:
118  MPUniqueIterator(Iterator<T> *it, CheckFunc checkFunctor = CheckFunc())
119  : UniqueIterator<T, CheckFunc>(it, checkFunctor) {}
120 };
121 
122 /**
123 * @brief Convenient function for creating a UniqueIterator.
124 * @ingroup Iterators
125 *
126 * @since Tulip 5.2
127 *
128 * Creates a UniqueIterator from another Iterator.
129 * The returned Iterator takes ownership of the one provided as parameter.
130 *
131 * @param it a Tulip Iterator
132 * @param checkFunctor a functor or a lambda function that enables to indicate whether or not the
133 *element could be duplicated (default test all elements)
134 *
135 * @return a UniqueIterator
136 *
137 **/
138 template <typename T, typename CheckFunc = CheckAllFunctor<T>>
139 inline UniqueIterator<T> *uniqueIterator(Iterator<T> *it, CheckFunc checkFunctor = CheckFunc()) {
140  return new MPUniqueIterator<T, CheckFunc>(it, checkFunctor);
141 }
142 
143 /**
144 * @brief Convenient function for creating a UniqueIterator from a STL container.
145 * @ingroup Iterators
146 *
147 * @since Tulip 5.2
148 *
149 * Creates a UniqueIterator from a STL container (std::list, std::vector, std::set, std::map, ...).
150 *
151 * @param stlContainer any STL container
152 * @param checkFunctor a functor or a lambda function that enables to indicate whether or not the
153 *element could be duplicated (default test all elements)
154 *
155 * @return a UniqueIterator
156 *
157 **/
158 template <typename Container, typename CheckFunc = CheckAllFunctor<typename Container::value_type>>
159 typename std::enable_if<has_const_iterator<Container>::value,
161  *>::type inline uniqueIterator(const Container &stlContainer,
162  CheckFunc checkFunctor = CheckFunc()) {
163  return new MPUniqueIterator<typename Container::value_type, CheckFunc>(stlIterator(stlContainer),
164  checkFunctor);
165 }
166 }
167 #endif // UNIQUEITERATOR_H
That class implement a default functor that always returns true.
Interface for Tulip iterators. Allows basic iteration operations only.
Definition: Graph.h:41
T next()
Moves the Iterator on the next element.
UniqueIterator< T > * uniqueIterator(Iterator< T > *it, CheckFunc checkFunctor=CheckFunc())
Convenient function for creating a UniqueIterator.
bool hasNext()
Tells if the sequence is at its end.
UniqueIterator enables to remove duplicated elements in an iterator.
std::enable_if< has_const_iterator< Container >::value, StlIterator< typename Container::value_type, typename Container::const_iterator > * >::type stlIterator(const Container &stlContainer)
Convenient function for creating a StlIterator from a stl container.
Definition: StlIterator.h:95