1 | // Iterator-related utilities. |
2 | // Copyright (C) 2002-2023 Free Software Foundation, Inc. |
3 | // |
4 | // This file is part of GCC. |
5 | // |
6 | // GCC is free software; you can redistribute it and/or modify it under |
7 | // the terms of the GNU General Public License as published by the Free |
8 | // Software Foundation; either version 3, or (at your option) any later |
9 | // version. |
10 | // |
11 | // GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
12 | // WARRANTY; without even the implied warranty of MERCHANTABILITY or |
13 | // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
14 | // for more details. |
15 | // |
16 | // You should have received a copy of the GNU General Public License |
17 | // along with GCC; see the file COPYING3. If not see |
18 | // <http://www.gnu.org/licenses/>. |
19 | |
20 | #ifndef GCC_ITERATOR_UTILS_H |
21 | #define GCC_ITERATOR_UTILS_H 1 |
22 | |
23 | // A half-open [begin, end) range of iterators. |
24 | template<typename T> |
25 | struct iterator_range |
26 | { |
27 | public: |
28 | using const_iterator = T; |
29 | |
30 | iterator_range () = default; |
31 | iterator_range (const T &begin, const T &end) |
32 | : m_begin (begin), m_end (end) {} |
33 | |
34 | T begin () const { return m_begin; } |
35 | T end () const { return m_end; } |
36 | |
37 | explicit operator bool () const { return m_begin != m_end; } |
38 | |
39 | private: |
40 | T m_begin; |
41 | T m_end; |
42 | }; |
43 | |
44 | // Provide an iterator like BaseIT, except that it yields values of type T, |
45 | // which is derived from the type that BaseIT normally yields. |
46 | // |
47 | // The class doesn't inherit from BaseIT for two reasons: |
48 | // - using inheritance would stop the class working with plain pointers |
49 | // - not using inheritance increases type-safety for writable iterators |
50 | // |
51 | // Constructing this class from a BaseIT involves an assertion that all |
52 | // contents really do have type T. The constructor is therefore explicit. |
53 | template<typename T, typename BaseIT> |
54 | class derived_iterator |
55 | { |
56 | public: |
57 | using value_type = T; |
58 | |
59 | derived_iterator () = default; |
60 | |
61 | template<typename... Ts> |
62 | explicit derived_iterator (Ts... args) |
63 | : m_base (std::forward<Ts> (args)...) {} |
64 | |
65 | derived_iterator &operator++ () { ++m_base; return *this; } |
66 | derived_iterator operator++ (int); |
67 | |
68 | T operator* () const { return static_cast<T> (*m_base); } |
69 | T *operator-> () const { return static_cast<T *> (m_base.operator-> ()); } |
70 | |
71 | bool operator== (const derived_iterator &other) const; |
72 | bool operator!= (const derived_iterator &other) const; |
73 | |
74 | protected: |
75 | BaseIT m_base; |
76 | }; |
77 | |
78 | template<typename T, typename BaseIT> |
79 | inline derived_iterator<T, BaseIT> |
80 | derived_iterator<T, BaseIT>::operator++ (int) |
81 | { |
82 | derived_iterator ret = *this; |
83 | ++m_base; |
84 | return ret; |
85 | } |
86 | |
87 | template<typename T, typename BaseIT> |
88 | inline bool |
89 | derived_iterator<T, BaseIT>::operator== (const derived_iterator &other) const |
90 | { |
91 | return m_base == other.m_base; |
92 | } |
93 | |
94 | template<typename T, typename BaseIT> |
95 | inline bool |
96 | derived_iterator<T, BaseIT>::operator!= (const derived_iterator &other) const |
97 | { |
98 | return m_base != other.m_base; |
99 | } |
100 | |
101 | // Provide a constant view of a BaseCT in which every value is known to |
102 | // have type T, which is derived from the type that BaseCT normally presents. |
103 | // |
104 | // Constructing this class from a BaseCT involves an assertion that all |
105 | // contents really do have type T. The constructor is therefore explicit. |
106 | template<typename T, typename BaseCT> |
107 | class const_derived_container : public BaseCT |
108 | { |
109 | using base_const_iterator = typename BaseCT::const_iterator; |
110 | |
111 | public: |
112 | using value_type = T; |
113 | using const_iterator = derived_iterator<T, base_const_iterator>; |
114 | |
115 | const_derived_container () = default; |
116 | |
117 | template<typename... Ts> |
118 | explicit const_derived_container (Ts... args) |
119 | : BaseCT (std::forward<Ts> (args)...) {} |
120 | |
121 | const_iterator begin () const { return const_iterator (BaseCT::begin ()); } |
122 | const_iterator end () const { return const_iterator (BaseCT::end ()); } |
123 | |
124 | T front () const { return static_cast<T> (BaseCT::front ()); } |
125 | T back () const { return static_cast<T> (BaseCT::back ()); } |
126 | T operator[] (unsigned int i) const; |
127 | }; |
128 | |
129 | template<typename T, typename BaseCT> |
130 | inline T |
131 | const_derived_container<T, BaseCT>::operator[] (unsigned int i) const |
132 | { |
133 | return static_cast<T> (BaseCT::operator[] (i)); |
134 | } |
135 | |
136 | // A base class for iterators whose contents consist of a StoredT and that |
137 | // when dereferenced yield those StoredT contents as a T. Derived classes |
138 | // should implement at least operator++ or operator--. |
139 | template<typename T, typename StoredT = T> |
140 | class wrapper_iterator |
141 | { |
142 | public: |
143 | using value_type = T; |
144 | |
145 | wrapper_iterator () = default; |
146 | |
147 | template<typename... Ts> |
148 | wrapper_iterator (Ts... args) : m_contents (std::forward<Ts> (args)...) {} |
149 | |
150 | T operator* () const { return static_cast<T> (m_contents); } |
151 | bool operator== (const wrapper_iterator &) const; |
152 | bool operator!= (const wrapper_iterator &) const; |
153 | |
154 | protected: |
155 | StoredT m_contents; |
156 | }; |
157 | |
158 | template<typename T, typename StoredT> |
159 | inline bool |
160 | wrapper_iterator<T, StoredT>::operator== (const wrapper_iterator &other) const |
161 | { |
162 | return m_contents == other.m_contents; |
163 | } |
164 | |
165 | template<typename T, typename StoredT> |
166 | inline bool |
167 | wrapper_iterator<T, StoredT>::operator!= (const wrapper_iterator &other) const |
168 | { |
169 | return m_contents != other.m_contents; |
170 | } |
171 | |
172 | // A forward iterator for a linked list whose nodes are referenced using |
173 | // type T. Given a node "T N", the next element is given by (N->*Next) (). |
174 | template<typename T, T *(T::*Next) () const> |
175 | class list_iterator : public wrapper_iterator<T *> |
176 | { |
177 | private: |
178 | using parent = wrapper_iterator<T *>; |
179 | |
180 | public: |
181 | using parent::parent; |
182 | list_iterator &operator++ (); |
183 | list_iterator operator++ (int); |
184 | }; |
185 | |
186 | template<typename T, T *(T::*Next) () const> |
187 | inline list_iterator<T, Next> & |
188 | list_iterator<T, Next>::operator++ () |
189 | { |
190 | this->m_contents = (this->m_contents->*Next) (); |
191 | return *this; |
192 | } |
193 | |
194 | template<typename T, T *(T::*Next) () const> |
195 | inline list_iterator<T, Next> |
196 | list_iterator<T, Next>::operator++ (int) |
197 | { |
198 | list_iterator ret = *this; |
199 | this->m_contents = (this->m_contents->*Next) (); |
200 | return ret; |
201 | } |
202 | |
203 | #endif |
204 | |