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