Mercurial > botc / file comparison

comparison: src/list.h

src/list.h

changeset 124
a7b769a0e537
parent 119
bdf8d46c145f
child 125
85814c0918c5
equal deleted inserted replaced
123:ad33901eb4f6 124:a7b769a0e537
24 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 28
29 #ifndef BOTC_CONTAINERS_H 29 #ifndef BOTC_LIST_H
30 #define BOTC_CONTAINERS_H 30 #define BOTC_LIST_H
31 31
32 #include <cassert> 32 #include <cassert>
33 #include <algorithm> 33 #include <algorithm>
34 #include <deque> 34 #include <deque>
35 #include <initializer_list> 35 #include <initializer_list>
36 36
37 template<typename T> 37 template<typename T>
38 class List 38 class List
39 { 39 {
40 public: 40 public:
41 using WrappedList = typename std::deque<T>; 41 using Iterator = typename std::deque<T>::iterator;
42 using Iterator = typename WrappedList::iterator; 42 using ConstIterator = typename std::deque<T>::const_iterator;
43 using ConstIterator = typename WrappedList::const_iterator; 43 using ReverseIterator = typename std::deque<T>::reverse_iterator;
44 using ReverseIterator = typename WrappedList::reverse_iterator; 44 using ConstReverseIterator = typename std::deque<T>::const_reverse_iterator;
45 using ConstReverseIterator = typename WrappedList::const_reverse_iterator; 45
46 using ValueType = T; 46 List();
47 using Self = List<T>; 47 List (const std::deque<T>& a);
48 48 List (std::initializer_list<T>&& a);
49 // ===================================================================== 49
50 // 50 inline T& append (const T& value);
51 List() {} 51 inline Iterator begin();
52 52 inline ConstIterator begin() const;
53 // ===================================================================== 53 inline void clear();
54 // 54 inline bool contains (const T& a) const;
55 List (std::initializer_list<ValueType> vals) 55 inline ConstReverseIterator crbegin() const;
56 { 56 inline ConstReverseIterator crend() const;
57 m_data = vals; 57 inline const std::deque<T>& deque() const;
58 } 58 inline Iterator end();
59 59 inline ConstIterator end() const;
60 // ===================================================================== 60 int find (const T& needle) const;
61 // 61 inline const T& first() const;
62 List (const WrappedList& a) : 62 inline void insert (int pos, const T& value);
63 m_data (a) {} 63 inline bool isEmpty() const;
64 64 inline const T& last() const;
65 // ===================================================================== 65 void merge (const List<T>& other);
66 // 66 bool pop (T& val);
67 Iterator begin() 67 inline T& prepend (const T& value);
68 { 68 inline ReverseIterator rbegin();
69 return m_data.begin(); 69 inline void removeAt (int pos);
70 } 70 void removeDuplicates();
71 71 void removeOne (const T& it);
72 // ===================================================================== 72 inline ReverseIterator rend();
73 // 73 inline void resize (int size);
74 ConstIterator begin() const 74 List<T> reverse() const;
75 { 75 inline int size() const;
76 return m_data.cbegin(); 76 inline void sort();
77 } 77 List<T> splice (int a, int b) const;
78 78
79 // ===================================================================== 79 inline List<T>& operator<< (const T& value);
80 // 80 inline List<T>& operator<< (const List<T>& vals);
81 Iterator end() 81 inline T& operator[] (int n);
82 { 82 inline const T& operator[] (int n) const;
83 return m_data.end(); 83 inline List<T> operator+ (const List<T>& other) const;
84 } 84
85 85 private:
86 // ===================================================================== 86 std::deque<T> _deque;
87 //
88 ConstIterator end() const
89 {
90 return m_data.cend();
91 }
92
93 // =====================================================================
94 //
95 ReverseIterator rbegin()
96 {
97 return m_data.rbegin();
98 }
99
100 // =====================================================================
101 //
102 ConstReverseIterator crbegin() const
103 {
104 return m_data.crbegin();
105 }
106
107 // =====================================================================
108 //
109 ReverseIterator rend()
110 {
111 return m_data.rend();
112 }
113
114 // =====================================================================
115 //
116 ConstReverseIterator crend() const
117 {
118 return m_data.crend();
119 }
120
121 // =====================================================================
122 //
123 inline void removeAt (int pos)
124 {
125 assert (pos < size());
126 m_data.erase (m_data.begin() + pos);
127 }
128
129 // =====================================================================
130 //
131 ValueType& prepend (const ValueType& value)
132 {
133 m_data.push_front (value);
134 return m_data[0];
135 }
136
137 // =====================================================================
138 //
139 ValueType& append (const ValueType& value)
140 {
141 m_data.push_back (value);
142 return m_data[m_data.size() - 1];
143 }
144
145 // =====================================================================
146 //
147 void merge (const Self& other)
148 {
149 resize (size() + other.size());
150 std::copy (other.begin(), other.end(), begin() + other.size());
151 }
152
153 // =====================================================================
154 //
155 bool pop (T& val)
156 {
157 if (isEmpty())
158 return false;
159
160 val = m_data[size() - 1];
161 m_data.erase (m_data.end() - 1);
162 return true;
163 }
164
165 // =====================================================================
166 //
167 Self& operator<< (const T& value)
168 {
169 append (value);
170 return *this;
171 }
172
173 // =====================================================================
174 //
175 void operator<< (const Self& vals)
176 {
177 merge (vals);
178 }
179
180 // =====================================================================
181 //
182 bool operator>> (T& value)
183 {
184 return pop (value);
185 }
186
187 // =====================================================================
188 //
189 Self reverse() const
190 {
191 Self rev;
192
193 for (const T & val : *this)
194 val >> rev;
195
196 return rev;
197 }
198
199 // =====================================================================
200 //
201 void clear()
202 {
203 m_data.clear();
204 }
205
206 // =====================================================================
207 //
208 void insert (int pos, const ValueType& value)
209 {
210 m_data.insert (m_data.begin() + pos, value);
211 }
212
213 // =====================================================================
214 //
215 void removeDuplicates()
216 {
217 // Remove duplicate entries. For this to be effective, the vector must be
218 // sorted first.
219 sort();
220 Iterator pos = std::unique (begin(), end());
221 resize (std::distance (begin(), pos));
222 }
223
224 // =====================================================================
225 //
226 int size() const
227 {
228 return m_data.size();
229 }
230
231 // =====================================================================
232 //
233 ValueType& operator[] (int n)
234 {
235 assert (n < size());
236 return m_data[n];
237 }
238
239 // =====================================================================
240 //
241 const ValueType& operator[] (int n) const
242 {
243 assert (n < size());
244 return m_data[n];
245 }
246
247 // =====================================================================
248 //
249 void resize (int size)
250 {
251 m_data.resize (size);
252 }
253
254 // =====================================================================
255 //
256 void sort()
257 {
258 std::sort (begin(), end());
259 }
260
261 // =====================================================================
262 //
263 int find (const ValueType& needle) const
264 {
265 int i = 0;
266
267 for (const ValueType& hay : *this)
268 {
269 if (hay == needle)
270 return i;
271
272 i++;
273 }
274
275 return -1;
276 }
277
278 // =====================================================================
279 //
280 void removeOne (const ValueType& it)
281 {
282 int idx;
283
284 if ((idx = find (it)) != -1)
285 removeAt (idx);
286 }
287
288 // =====================================================================
289 //
290 inline bool isEmpty() const
291 {
292 return size() == 0;
293 }
294
295 // =====================================================================
296 //
297 Self splice (int a, int b) const
298 {
299 assert (a >= 0 && b >= 0 && a < size() && b < size() && a <= b);
300 Self result;
301
302 for (int i = a; i <= b; ++i)
303 result << operator[] (i);
304
305 return result;
306 }
307
308 // =====================================================================
309 //
310 inline const WrappedList& deque() const
311 {
312 return m_data;
313 }
314
315 // =====================================================================
316 //
317 inline const ValueType& first() const
318 {
319 return *m_data.begin();
320 }
321
322 // =====================================================================
323 //
324 inline const ValueType& last() const
325 {
326 return *(m_data.end() - 1);
327 }
328
329 // =====================================================================
330 //
331 inline bool contains (const ValueType& a) const
332 {
333 return find (a) != -1;
334 }
335
336 // =====================================================================
337 //
338 Self operator+ (const Self& other) const
339 {
340 Self out (*this);
341 out.merge (other);
342 return out;
343 }
344
345 private:
346 WrappedList m_data;
347 }; 87 };
348 88
349 // ============================================================================= 89 template<typename T>
90 List<T>& operator>> (const T& value, List<T>& haystack);
91
350 // 92 //
93 // --- IMPLEMENTATIONS
94 //
95
96 template<typename T>
97 List<T>::List() {}
98
99 template<typename T>
100 List<T>::List (const std::deque<T>& other) :
101 _deque (other) {}
102
103 template<typename T>
104 List<T>::List (std::initializer_list<T>&& a) :
105 _deque (a) {}
106
107 template<typename T>
108 inline typename List<T>::Iterator List<T>::begin()
109 {
110 return _deque.begin();
111 }
112
113 template<typename T>
114 inline typename List<T>::ConstIterator List<T>::begin() const
115 {
116 return _deque.cbegin();
117 }
118
119 template<typename T>
120 inline typename List<T>::Iterator List<T>::end()
121 {
122 return _deque.end();
123 }
124
125 template<typename T>
126 inline typename List<T>::ConstIterator List<T>::end() const
127 {
128 return _deque.cend();
129 }
130
131 template<typename T>
132 inline typename List<T>::ReverseIterator List<T>::rbegin()
133 {
134 return _deque.rbegin();
135 }
136
137 template<typename T>
138 inline typename List<T>::ConstReverseIterator List<T>::crbegin() const
139 {
140 return _deque.crbegin();
141 }
142
143 template<typename T>
144 inline typename List<T>::ReverseIterator List<T>::rend()
145 {
146 return _deque.rend();
147 }
148
149 template<typename T>
150 inline typename List<T>::ConstReverseIterator List<T>::crend() const
151 {
152 return _deque.crend();
153 }
154
155 template<typename T>
156 void List<T>::removeAt (int pos)
157 {
158 assert (pos < size());
159 _deque.erase (_deque.begin() + pos);
160 }
161
162 template<typename T>
163 inline T& List<T>::prepend (const T& value)
164 {
165 _deque.push_front (value);
166 return _deque[0];
167 }
168
169 template<typename T>
170 inline T& List<T>::append (const T& value)
171 {
172 _deque.push_back (value);
173 return _deque[_deque.size() - 1];
174 }
175
176 template<typename T>
177 void List<T>::merge (const List<T>& other)
178 {
179 resize (size() + other.size());
180 std::copy (other.begin(), other.end(), begin() + other.size());
181 }
182
183 template<typename T>
184 bool List<T>::pop (T& val)
185 {
186 if (isEmpty())
187 return false;
188
189 val = _deque[size() - 1];
190 _deque.erase (_deque.end() - 1);
191 return true;
192 }
193
194 template<typename T>
195 inline List<T>& List<T>::operator<< (const T& value)
196 {
197 append (value);
198 return *this;
199 }
200
201 template<typename T>
202 inline List<T>& List<T>::operator<< (const List<T>& vals)
203 {
204 merge (vals);
205 return *this;
206 }
207
208 template<typename T>
209 List<T> List<T>::reverse() const
210 {
211 List<T> rev;
212 std::copy (rbegin(), rend(), rev.begin());
213 return rev;
214 }
215
216 template<typename T>
217 inline void List<T>::clear()
218 {
219 _deque.clear();
220 }
221
222 template<typename T>
223 inline void List<T>::insert (int pos, const T& value)
224 {
225 _deque.insert (_deque.begin() + pos, value);
226 }
227
228 template<typename T>
229 void List<T>::removeDuplicates()
230 {
231 sort();
232 resize (std::distance (begin(), std::unique (begin(), end())));
233 }
234
235 template<typename T>
236 int List<T>::size() const
237 {
238 return _deque.size();
239 }
240
241 template<typename T>
242 inline T& List<T>::operator[] (int n)
243 {
244 assert (n < size());
245 return _deque[n];
246 }
247
248 template<typename T>
249 inline const T& List<T>::operator[] (int n) const
250 {
251 assert (n < size());
252 return _deque[n];
253 }
254
255 template<typename T>
256 inline void List<T>::resize (int size)
257 {
258 _deque.resize (size);
259 }
260
261 template<typename T>
262 inline void List<T>::sort()
263 {
264 std::sort (begin(), end());
265 }
266
267 template<typename T>
268 int List<T>::find (const T& needle) const
269 {
270 auto it = std::find (_deque.cbegin(), _deque.cend(), needle);
271
272 if (it == _deque.end())
273 return -1;
274
275 return it - _deque.cbegin();
276 }
277
278 template<typename T>
279 void List<T>::removeOne (const T& a)
280 {
281 auto it = std::find (_deque.begin(), _deque.end(), a);
282
283 if (it != _deque.end())
284 _deque.erase (it);
285 }
286
287 template<typename T>
288 inline bool List<T>::isEmpty() const
289 {
290 return size() == 0;
291 }
292
293 template<typename T>
294 List<T> List<T>::splice (int a, int b) const
295 {
296 assert (a >= 0 && b >= 0 && a < size() && b < size() && a <= b);
297 List<T> result;
298
299 for (int i = a; i <= b; ++i)
300 result << operator[] (i);
301
302 return result;
303 }
304
305 template<typename T>
306 inline const std::deque<T>& List<T>::deque() const
307 {
308 return _deque;
309 }
310
311 template<typename T>
312 inline const T& List<T>::first() const
313 {
314 return *_deque.cbegin();
315 }
316
317 template<typename T>
318 inline const T& List<T>::last() const
319 {
320 return *(_deque.cend() - 1);
321 }
322
323 template<typename T>
324 inline bool List<T>::contains (const T& a) const
325 {
326 return std::find (_deque.cbegin(), _deque.cend(), a) != _deque.end();
327 }
328
329 template<typename T>
330 inline List<T> List<T>::operator+ (const List<T>& other) const
331 {
332 List<T> out (*this);
333 out.merge (other);
334 return out;
335 }
336
351 template<typename T> 337 template<typename T>
352 List<T>& operator>> (const T& value, List<T>& haystack) 338 List<T>& operator>> (const T& value, List<T>& haystack)
353 { 339 {
354 haystack.prepend (value); 340 haystack.prepend (value);
355 return haystack; 341 return haystack;
356 } 342 }
357 343
358 #endif // BOTC_CONTAINERS_H 344 #endif // BOTC_LIST_H

Mercurial Repository: botc

mercurial