Tulip  5.0.0
Large graphs analysis and drawing
uniqueiterator.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
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 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef UNIQUEITERATOR_H
22 #define UNIQUEITERATOR_H
23 #include <set>
24 #include <tulip/memorypool.h>
25 
26 
27 //===============================================================================
28 namespace tlp {
29 /**
30  * \brief that class implement a default functor that always return true
31  *
32  * @see UniqueIterator
33  */
34 template <typename TYPE>
35 class CheckAllFunctor {
36  bool operator()(const TYPE &) {
37  return true;
38  }
39 };
40 
41 /**
42  * @class UniqueIterator
43  * @ingroup Iterators
44  *
45  * @brief UniqueIterator enables to remove duplicated elements in an iterator
46  *
47  * @param it the iterator in which we want to filter out duplicated elements
48  * @param checkFuncor a functor that enable to indicate wheter or not the element could be duplicated (default test all elements)
49  *
50  * The functor function shoul have the following form
51  * @code
52  * class ACheckFunctor {
53  * bool operator(TYPE a) {
54  * return true if a could be duplicated else false;
55  * }
56  * };
57  * @endcode
58  * checkFunctor are used for optimization purpose to prevent to log(n) test for all elements when not necessary.
59  */
60 template <typename TYPE, typename TOCHECKFUNCTOR = CheckAllFunctor<TYPE> >
61 class UniqueIterator : public Iterator<TYPE> {
62 public:
63  UniqueIterator(Iterator<TYPE> *it, TOCHECKFUNCTOR checkFunctor = TOCHECKFUNCTOR()):_it(it), _checkFunctor(checkFunctor) {
64  update();
65  }
66  //================================================
67  ~UniqueIterator() {
68  delete _it;
69  }
70  //================================================
71  TYPE next() {
72  TYPE tmp = curVal;
73  update();
74  return tmp;
75  }
76  //================================================
77  inline bool hasNext() {
78  return _hasNext;
79  }
80  //================================================
81  void update() {
82  _hasNext = false;
83 
84  while(_it->hasNext()) {
85  curVal = _it->next();
86 
87  if (_checkFunctor(curVal) ) {
88  if (_flag.find(curVal) == _flag.end()) {
89  _hasNext = true;
90  _flag.insert(curVal);
91  return;
92  }
93  }
94  else {
95  _hasNext = true;
96  return;
97  }
98  }
99  }
100 
101 private:
102  std::set<TYPE> _flag;
103  bool _hasNext;
104  Iterator<TYPE> *_it;
105  TYPE curVal;
106  TOCHECKFUNCTOR _checkFunctor;
107 };
108 /**
109  * @class MPUniqueIterator
110  * @ingroup Iterators
111  * @brief MPUniqueIterator implements memory pool for UniqueIterator
112  * @warning never inherit from that class
113  * @see UniqueIterator
114  */
115 template <typename TYPE, typename TOCHECKFUNCTOR = CheckAllFunctor<TYPE> >
116 class MPUniqueIterator : public UniqueIterator<TYPE, TOCHECKFUNCTOR> ,
117  public MemoryPool<MPUniqueIterator<TYPE, TOCHECKFUNCTOR> > {
118 public:
119  MPUniqueIterator(Iterator<TYPE> *it, TOCHECKFUNCTOR checkFunctor = TOCHECKFUNCTOR()):
120  UniqueIterator<TYPE, TOCHECKFUNCTOR>(it, checkFunctor) {
121  }
122 };
123 
124 }
125 #endif // UNIQUEITERATOR_H
126 ///@endcond
Interface for Tulip iterators. Allows basic iteration operations only.
Definition: Iterator.h:39