SDSL  3.0.0
Succinct Data Structure Library
iterators.hpp
Go to the documentation of this file.
1 // Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2 // Please see the AUTHORS file for details. Use of this source code is governed
3 // by a BSD license that can be found in the LICENSE file.
8 #ifndef INCLUDED_SDSL_ITERATORS
9 #define INCLUDED_SDSL_ITERATORS
10 
11 #include <iterator>
12 
13 #include <sdsl/int_vector.hpp>
14 
15 namespace sdsl
16 {
17 
19 
21 template <class t_rac>
23  : public std::iterator<std::random_access_iterator_tag, typename t_rac::value_type, typename t_rac::difference_type>
24 {
25  public:
26  typedef const typename t_rac::value_type const_reference;
27  typedef typename t_rac::size_type size_type;
29  typedef typename t_rac::difference_type difference_type;
30 
31  private:
32  const t_rac * m_rac; // pointer to the random access container
33  typename t_rac::size_type m_idx;
34 
35  template <class t_RAC>
39 
40  public:
42  random_access_const_iterator(const t_rac * rac, size_type idx = 0)
43  : m_rac(rac)
44  , m_idx(idx)
45  {}
46 
48  const_reference operator*() const { return (*m_rac)[m_idx]; }
49 
52  {
53  ++m_idx;
54  return *this;
55  }
56 
59  {
61  ++(*this);
62  return it;
63  }
64 
67  {
68  --m_idx;
69  return *this;
70  }
71 
74  {
76  --(*this);
77  return it;
78  }
79 
81  {
82  if (i < 0) return *this -= (-i);
83  m_idx += i;
84  return *this;
85  }
86 
88  {
89  if (i < 0) return *this += (-i);
90  m_idx -= i;
91  return *this;
92  }
93 
95  {
96  iterator it = *this;
97  return it += i;
98  }
99 
101  {
102  iterator it = *this;
103  return it -= i;
104  }
105 
106  const_reference operator[](difference_type i) const { return *(*this + i); }
107 
108  bool operator==(const iterator & it) const { return it.m_rac == m_rac && it.m_idx == m_idx; }
109 
110  bool operator!=(const iterator & it) const { return !(*this == it); }
111 
112  bool operator<(const iterator & it) const { return m_idx < it.m_idx; }
113 
114  bool operator>(const iterator & it) const { return m_idx > it.m_idx; }
115 
116  bool operator>=(const iterator & it) const { return !(*this < it); }
117 
118  bool operator<=(const iterator & it) const { return !(*this > it); }
119 };
120 
121 template <class t_rac>
125 {
128 }
129 
130 template <class t_rac>
133 {
134  return it + n;
135 }
136 
137 template <typename t_F>
139 {
142  typedef typename std::result_of<t_F(size_type)>::type value_type;
144 
145  t_F f;
147 
150  : f(ff)
151  , m_size(size)
152  {}
153 
154  value_type operator[](size_type i) const { return f(i); }
155 
156  size_type size() const { return m_size; }
157 
158  iterator_type begin() const { return iterator_type(this, 0); }
159 
160  iterator_type end() const { return iterator_type(this, size()); }
161 };
162 
163 } // end namespace sdsl
164 #endif
A generic vector class for integers of width .
Definition: int_vector.hpp:253
Generic iterator for a random access container.
Definition: iterators.hpp:24
random_access_const_iterator< t_rac > iterator
Definition: iterators.hpp:28
iterator operator++(int)
Postfix increment of the Iterator.
Definition: iterators.hpp:58
bool operator>=(const iterator &it) const
Definition: iterators.hpp:116
bool operator<=(const iterator &it) const
Definition: iterators.hpp:118
bool operator!=(const iterator &it) const
Definition: iterators.hpp:110
bool operator<(const iterator &it) const
Definition: iterators.hpp:112
iterator & operator+=(difference_type i)
Definition: iterators.hpp:80
t_rac::difference_type difference_type
Definition: iterators.hpp:29
iterator & operator++()
Prefix increment of the Iterator.
Definition: iterators.hpp:51
iterator & operator--()
Prefix decrement of the Iterator.
Definition: iterators.hpp:66
friend random_access_const_iterator< t_RAC >::difference_type operator-(const random_access_const_iterator< t_RAC > &x, const random_access_const_iterator< t_RAC > &y)
iterator & operator-=(difference_type i)
Definition: iterators.hpp:87
bool operator>(const iterator &it) const
Definition: iterators.hpp:114
iterator operator--(int)
Postfix decrement of the Iterator.
Definition: iterators.hpp:73
iterator operator+(difference_type i) const
Definition: iterators.hpp:94
const_reference operator[](difference_type i) const
Definition: iterators.hpp:106
const_reference operator*() const
Dereference operator for the Iterator.
Definition: iterators.hpp:48
random_access_const_iterator(const t_rac *rac, size_type idx=0)
Constructor.
Definition: iterators.hpp:42
const t_rac::value_type const_reference
Definition: iterators.hpp:26
iterator operator-(difference_type i) const
Definition: iterators.hpp:100
bool operator==(const iterator &it) const
Definition: iterators.hpp:108
int_vector.hpp contains the sdsl::int_vector class.
int_vector ::size_type size_type
Namespace for the succinct data structure library.
int_vector_const_iterator< t_int_vector >::difference_type operator-(const int_vector_const_iterator< t_int_vector > &x, const int_vector_const_iterator< t_int_vector > &y)
int_vector_iterator< t_int_vector > operator+(typename int_vector_iterator< t_int_vector >::difference_type n, const int_vector_iterator< t_int_vector > &it)
iterator_type begin() const
Definition: iterators.hpp:158
std::result_of< t_F(size_type)>::type value_type
Definition: iterators.hpp:142
int_vector ::difference_type difference_type
Definition: iterators.hpp:141
random_access_const_iterator< random_access_container > iterator_type
Definition: iterators.hpp:143
int_vector ::size_type size_type
Definition: iterators.hpp:140
iterator_type end() const
Definition: iterators.hpp:160
value_type operator[](size_type i) const
Definition: iterators.hpp:154
random_access_container(t_F ff, size_type size)
Definition: iterators.hpp:149