Iterators.h
Go to the documentation of this file.
1 /*!
2  *
3  *
4  * \brief Small Iterator collection.
5  *
6  *
7  *
8  *
9  * \author Oswin Krause
10  * \date 2012
11  *
12  *
13  * \par Copyright 1995-2015 Shark Development Team
14  *
15  * <BR><HR>
16  * This file is part of Shark.
17  * <http://image.diku.dk/shark/>
18  *
19  * Shark is free software: you can redistribute it and/or modify
20  * it under the terms of the GNU Lesser General Public License as published
21  * by the Free Software Foundation, either version 3 of the License, or
22  * (at your option) any later version.
23  *
24  * Shark is distributed in the hope that it will be useful,
25  * but WITHOUT ANY WARRANTY; without even the implied warranty of
26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27  * GNU Lesser General Public License for more details.
28  *
29  * You should have received a copy of the GNU Lesser General Public License
30  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
31  *
32  */
33 #ifndef SHARK_CORE_ITERATORS_H
34 #define SHARK_CORE_ITERATORS_H
35 
36 #include <boost/version.hpp>
37 #include "Impl/boost_iterator_facade_fixed.hpp"//thanks, boost.
38 
40 #include <boost/range/iterator.hpp>
41 namespace shark{
42 
43 ///\brief creates an Indexed Iterator, an Iterator which also carries index information using index()
44 ///
45 ///The underlying Iterator must be a random access iterator
46 template<class Iterator>
47 class IndexedIterator: public SHARK_ITERATOR_FACADE<
48  IndexedIterator<Iterator>,
49  typename boost::iterator_value<Iterator>::type,
50  std::random_access_iterator_tag,
51  typename boost::iterator_reference<Iterator>::type
52 >
53 {
54 public:
56  :m_index(0){}
57 
58  ///\brief Copy-Constructs this iterator from some other IndexedIterator convertible to this.
59  template<class I>
61  : m_iterator(iterator.m_iterator),m_index(iterator.index){}
62 
63  ///\brief Constructs the iterator from another iterator plus a starting index.
64  template<class IteratorT>
65  IndexedIterator(IteratorT const& iterator, std::size_t startIndex)
66  : m_iterator(Iterator(iterator)),m_index(startIndex){}
67 
68  std::size_t index()const{
69  return m_index;
70  }
71 private:
72  typedef SHARK_ITERATOR_FACADE<
74  typename boost::iterator_value<Iterator>::type,
75  boost::random_access_traversal_tag,
76  typename boost::iterator_reference<Iterator>::type
77  > base_type;
78 
80 
81  typename base_type::reference dereference() const {
82  return *m_iterator;
83  }
84 
85  void increment() {
86  ++m_index;
87  ++m_iterator;
88  }
89  void decrement() {
90  --m_index;
91  --m_iterator;
92  }
93 
94  void advance(std::ptrdiff_t n){
95  m_index += n;
96  m_iterator += n;
97  }
98 
99  template<class I>
100  std::ptrdiff_t distance_to(IndexedIterator<I> const& other) const{
101  return other.m_iterator - m_iterator;
102  }
103 
104  template<class I>
105  bool equal(IndexedIterator<I> const& other) const{
106  return m_iterator == other.m_iterator;
107  }
108 
109  Iterator m_iterator;
110  std::size_t m_index;
111 };
112 
113 /// \brief Creates an iterator which reinterpretes an object as a range
114 ///
115 /// The second template argument represents the elements by the proxy reference type. it must offer
116 /// a constructor Reference(sequence,i) which constructs a reference to the i-th proxy-element
117 template<class Sequence, class ValueType, class Reference>
118 class ProxyIterator: public SHARK_ITERATOR_FACADE<
119  ProxyIterator<Sequence,ValueType,Reference>,
120  ValueType,
121  //boost::random_access_traversal_tag,
122  std::random_access_iterator_tag,//keep VC quiet.
123  Reference
124 >{
125 public:
126  ProxyIterator() : m_position(0) {}
127 
128  ProxyIterator(Sequence& seq, std::size_t position)
129  : m_sequence(&seq),m_position(position) {}
130 
131  template<class S, class V, class R>
133  : m_sequence(other.m_sequence),m_position(other.m_position) {}
134 
135 private:
137  template <class,class,class> friend class ProxyIterator;
138 
139  void increment() {
140  ++m_position;
141  }
142  void decrement() {
143  --m_position;
144  }
145 
146  void advance(std::ptrdiff_t n){
147  m_position += n;
148  }
149 
150  template<class Iter>
151  std::ptrdiff_t distance_to(const Iter& other) const{
152  return (std::ptrdiff_t)other.m_position - (std::ptrdiff_t)m_position;
153  }
154 
155  template<class Iter>
156  bool equal(Iter const& other) const{
157  return (m_position == other.m_position);
158  }
159  Reference dereference() const {
160  return Reference(*m_sequence,m_position);
161  }
162 
163  Sequence* m_sequence;
164  std::size_t m_position;
165 };
166 
167 
168 namespace detail{
169 
170  ///\brief Helper class of the MultiSequenceIterator, which querys everything needed to deduce the right iterator_facade
171  template<class Self, class SequenceContainer>
172  struct SequenceOfSequenceIteratorTraits{
173  typedef typename boost::remove_const<SequenceContainer>::type OuterSequence;
174  typedef typename boost::range_iterator<SequenceContainer>::type outer_iterator;
175  //the inner Sequence type is the value_type of the outer sequence. But if the outer sequence is const
176  //we have to make sure, that we also get const value_type.
177  //~ typedef typename CopyConst<typename boost::iterator_value<outer_iterator>::type,SequenceContainer>::type InnerSequence;
178  typedef typename boost::remove_reference<
179  typename boost::iterator_reference<outer_iterator>::type
180  >::type InnerSequence;
181  typedef typename boost::range_iterator<InnerSequence>::type inner_iterator;
182  typedef typename boost::iterator_reference<inner_iterator>::type reference;
183  typedef typename boost::iterator_value<inner_iterator>::type value_type;
184 
185  //typedef boost::iterator_facade_fixed< Self, value_type, boost::random_access_traversal_tag, reference > base;
186  typedef SHARK_ITERATOR_FACADE< Self, value_type, std::random_access_iterator_tag, reference > base;
187  };
188 }
189 
190 ///\brief Iterator which iterates of the elements of a nested sequence
191 ///
192 ///Think about a sequence which is split in several parts. These parts
193 ///are than stored into a new sequence. An example for this is std::deque
194 ///or the Data class. This iterator let's you tierate over the elements of the sequence
195 ///without having to care about that the sequence itself is splitted.
196 ///The Sequences both have to be random access containers.
197 template<class SequenceContainer>
198 class MultiSequenceIterator: public detail::SequenceOfSequenceIteratorTraits<
199  MultiSequenceIterator<SequenceContainer>,
200  SequenceContainer
201 >::base{
202 private:
203  typedef detail::SequenceOfSequenceIteratorTraits<
205  > Traits;
206  typedef typename Traits::outer_iterator outer_iterator;
207 public:
208  typedef typename Traits::inner_iterator inner_iterator;
210  :m_positionInSequence(0){}
211 
212  template<class OuterIter, class InnerIter>
214  OuterIter outerBegin,
215  OuterIter outerEnd,
216  OuterIter outerPosition,
217  InnerIter innerPosition,
218  std::size_t positionInSequence
219  ):m_outerBegin(outer_iterator(outerBegin)),
220  m_outerPosition(outer_iterator(outerPosition)),
221  m_outerEnd(outer_iterator(outerEnd)),
222  m_innerPosition(innerPosition),
223  m_positionInSequence(positionInSequence){
224  //we can't dereference if we are past the end...
225  if(m_outerPosition != m_outerEnd){
226  m_innerBegin = boost::begin(*m_outerPosition);
227  m_innerEnd = boost::end(*m_outerPosition);
228  }
229 
230  }
231 
232 
233  template<class S>
235  : m_outerBegin(other.m_outerBegin),m_outerPosition(other.m_outerPosition),m_outerEnd(other.m_outerEnd),
236  m_innerBegin(other.m_innerBegin),m_innerPosition(other.m_innerPosition),m_innerEnd(other.m_innerEnd),
237  m_positionInSequence(other.m_positionInSequence) {}
238 
239  std::size_t index()const{
240  return m_positionInSequence;
241  }
242 
243  inner_iterator getInnerIterator()const{
244  return m_innerPosition;
245  }
246 
247 private:
249  template <class> friend class MultiSequenceIterator;
250 
251  void increment() {
252  ++m_positionInSequence;
253  ++m_innerPosition;
254  if(m_innerPosition == m_innerEnd){
255  ++m_outerPosition;
256  while (m_outerPosition != m_outerEnd){//support for empty subsequences
257  m_innerBegin = boost::begin(*m_outerPosition);
258  m_innerEnd = boost::end(*m_outerPosition);
259  if(m_innerBegin != m_innerEnd){
260  m_innerPosition = m_innerBegin;
261  return;
262  }
263  ++m_outerPosition;
264  }
265  }
266  }
267  void decrement() {
268  SIZE_CHECK(m_positionInSequence);//don't call this method when the iterator is on the first element
269  --m_positionInSequence;
270  if(m_innerPosition != m_innerBegin){
271  --m_innerPosition;
272  return;
273  }
274 
275  --m_outerPosition;
276  m_innerBegin = boost::begin(*m_outerPosition);
277  m_innerEnd = boost::end(*m_outerPosition);
278  while(m_innerBegin == m_innerEnd){//support for empty subsequences
279  if( m_outerPosition == m_outerBegin)
280  return;//we are at the end
281  --m_outerPosition;
282  m_innerBegin = boost::begin(*m_outerPosition);
283  m_innerEnd = boost::end(*m_outerPosition);
284  }
285  m_innerPosition = m_innerEnd-1;
286  }
287  //this is not exactly O(1) as the standard wants. in fact it's O(n) in the number of inner sequences
288  //so approximately O(1) if the size of a sequence is big...
289  void advance(std::ptrdiff_t n){
290  m_positionInSequence += n;
291  std::ptrdiff_t diff = m_innerPosition - m_innerBegin;
292  n += diff;//jump from the start of the current inner sequence
293  if(n== 0)
294  m_innerPosition = m_innerBegin;
295  if(n < 0){
296  n *= -1;
297  --m_outerPosition;
298  --n;
299  //jump over the outer position until we are in the correct range again
300  while ((unsigned int) n >= shark::size(*m_outerPosition) ){
301  n -= shark::size(*m_outerPosition);
302  --m_outerPosition;
303  }
304  //get the iterators to the current position if we are not before the beginning of the sequence
305  m_innerBegin = boost::begin(*m_outerPosition);
306  m_innerEnd = boost::end(*m_outerPosition);
307  m_innerPosition = m_innerEnd-(n+1);
308  }
309  else{
310 
311  //jump over the outer position until we are in the correct range again
312  while (m_outerPosition != m_outerEnd && (unsigned int)n >= shark::size(*m_outerPosition) ){
313  n -= shark::size(*m_outerPosition);
314  ++m_outerPosition;
315  }
316  SHARK_CHECK(m_outerPosition != m_outerEnd || (n == 0), "iterator went past the end");
317  //get the iterators to the current position if we are not past the end
318  if(m_outerPosition != m_outerEnd){
319  m_innerBegin = boost::begin(*m_outerPosition);
320  m_innerPosition = m_innerBegin+n;
321  m_innerEnd = boost::end(*m_outerPosition);
322  }
323  }
324  }
325 
326  template<class Iter>
327  std::ptrdiff_t distance_to(const Iter& other) const{
328  return (std::ptrdiff_t)other.m_positionInSequence - (std::ptrdiff_t)m_positionInSequence;
329  }
330 
331  template<class Iter>
332  bool equal(Iter const& other) const{
333  return (m_positionInSequence == other.m_positionInSequence);
334  }
335  typename Traits::reference dereference() const {
336  return *m_innerPosition;
337  }
338 
339  outer_iterator m_outerBegin;//in fact, it is a before-the-begin iterator
340  outer_iterator m_outerPosition;
341  outer_iterator m_outerEnd;
342 
343  inner_iterator m_innerBegin;//in fact, it is a before-the-begin iterator
344  inner_iterator m_innerPosition;
345  inner_iterator m_innerEnd;
346 
347  std::size_t m_positionInSequence;
348 };
349 
350 }
351 #endif