Mercurial > zfc9000 / file comparison

comparison: sources/list.h

sources/list.h

changeset 1
4dd5bde4e777
child 5
146825d63b9a
equal deleted inserted replaced
0:792876306489 1:4dd5bde4e777
1 /*
2 Copyright 2014 Teemu Piippo
3 All rights reserved.
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
7 are met:
8
9 1. Redistributions of source code must retain the above copyright
10 notice, this list of conditions and the following disclaimer.
11 2. Redistributions in binary form must reproduce the above copyright
12 notice, this list of conditions and the following disclaimer in the
13 documentation and/or other materials provided with the distribution.
14 3. Neither the name of the copyright holder nor the names of its
15 contributors may be used to endorse or promote products derived from
16 this software without specific prior written permission.
17
18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
20 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
21 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER
22 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
25 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
26 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
27 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31 #pragma once
32 #include "basics.h"
33 #include <algorithm>
34 #include <deque>
35 #include <initializer_list>
36 #include <functional>
37 #include <cassert>
38 #include "range.h"
39
40 //
41 // -------------------------------------------------------------------------------------------------
42 //
43
44 template<typename T, typename C>
45 class Container
46 {
47 public:
48 using Iterator = typename C::iterator;
49 using ConstIterator = typename C::const_iterator;
50 using ReverseIterator = typename C::reverse_iterator;
51 using ConstReverseIterator = typename C::const_reverse_iterator;
52 using Self = Container<T, C>;
53
54 Container();
55 Container (int numvalues);
56 Container (const C& a);
57 Container (std::initializer_list<T>&& a);
58
59 auto append (const T& value) -> T&;
60 auto begin() -> Iterator;
61 auto begin() const -> ConstIterator;
62 auto clear() -> void;
63 auto contains (const T& a) const -> bool;
64 auto crbegin() const -> ConstReverseIterator;
65 auto crend() const -> ConstReverseIterator;
66 auto container() const -> const C&;
67 auto end() -> Iterator;
68 auto end() const -> ConstIterator;
69 auto find (const T& needle) -> Iterator;
70 auto find (const T& needle) const -> ConstIterator;
71 auto find (Function<bool (T const&)> func) -> Iterator;
72 auto find (Function<bool (T const&)> func) const -> ConstIterator;
73 auto first() const -> const T&;
74 auto insert (int pos, const T& value) -> void;
75 auto is_empty() const -> bool;
76 auto last() const -> const T&;
77 auto merge (const Self& other) -> void;
78 auto pop (T& val) -> bool;
79 auto prepend (const T& value) -> T&;
80 auto rbegin() -> ReverseIterator;
81 auto remove_at (int pos) -> void;
82 auto remove_duplicates() -> void;
83 auto remove_one (const T& it) -> void;
84 auto rend() -> ReverseIterator;
85 auto resize (int size) -> void;
86 auto reverse() const -> Self;
87 auto size() const -> int;
88 auto sort() -> void;
89 auto splice (int a, int b) const -> Self;
90 auto splice (const Range<int>& a) const -> Self;
91
92 auto operator<< (const T& value) -> Self&;
93 auto operator<< (const Self& vals) -> Self&;
94 auto operator[] (int n) -> T&;
95 auto operator[] (int n) const -> const T&;
96 auto operator[] (Range<int> const& n) const -> Self;
97 auto operator+ (const Self& other) const -> Self;
98
99 protected:
100 C m_container;
101 };
102
103 template<typename T, typename C>
104 Container<T, C>& operator>> (const T& value, Container<T, C>& haystack);
105
106 template<typename T>
107 using List = Container<T, std::deque<T>>;
108
109 template<typename T>
110 class Vector : public Container<T, std::vector<T>>
111 {
112 public:
113 using Super = Container<T, std::vector<T>>;
114
115 template<typename... Args>
116 Vector (Args ...args) :
117 Super (args...) {}
118
119 auto data() -> T*
120 {
121 return Super::m_container.data();
122 }
123
124 auto data() const -> const T*
125 {
126 return Super::m_container.data();
127 }
128
129 operator const T*() const
130 {
131 return data();
132 }
133 };
134
135 //
136 // -------------------------------------------------------------------------------------------------
137 //
138 // IMPLEMENTATIONS
139 //
140
141 template<typename T, typename C>
142 Container<T, C>::Container() {}
143
144 //
145 // -------------------------------------------------------------------------------------------------
146 //
147
148 template<typename T, typename C>
149 Container<T, C>::Container (const C& other) :
150 m_container (other) {}
151
152 //
153 // -------------------------------------------------------------------------------------------------
154 //
155
156 template<typename T, typename C>
157 Container<T, C>::Container (std::initializer_list<T> && a) :
158 m_container (a) {}
159
160 //
161 // -------------------------------------------------------------------------------------------------
162 //
163
164 template<typename T, typename C>
165 Container<T, C>::Container (int numvalues) :
166 m_container (numvalues) {}
167
168 //
169 // -------------------------------------------------------------------------------------------------
170 //
171
172 template<typename T, typename C>
173 auto Container<T, C>::begin() -> Iterator
174 {
175 return m_container.begin();
176 }
177
178 //
179 // -------------------------------------------------------------------------------------------------
180 //
181
182 template<typename T, typename C>
183 auto Container<T, C>::begin() const -> ConstIterator
184 {
185 return m_container.cbegin();
186 }
187
188 //
189 // -------------------------------------------------------------------------------------------------
190 //
191
192 template<typename T, typename C>
193 auto Container<T, C>::end() -> Iterator
194 {
195 return m_container.end();
196 }
197
198 //
199 // -------------------------------------------------------------------------------------------------
200 //
201
202 template<typename T, typename C>
203 auto Container<T, C>::end() const -> ConstIterator
204 {
205 return m_container.cend();
206 }
207
208 //
209 // -------------------------------------------------------------------------------------------------
210 //
211
212 template<typename T, typename C>
213 auto Container<T, C>::rbegin() -> ReverseIterator
214 {
215 return m_container.rbegin();
216 }
217
218 //
219 // -------------------------------------------------------------------------------------------------
220 //
221
222 template<typename T, typename C>
223 auto Container<T, C>::crbegin() const -> ConstReverseIterator
224 {
225 return m_container.crbegin();
226 }
227
228 //
229 // -------------------------------------------------------------------------------------------------
230 //
231
232 template<typename T, typename C>
233 auto Container<T, C>::rend() -> ReverseIterator
234 {
235 return m_container.rend();
236 }
237
238 //
239 // -------------------------------------------------------------------------------------------------
240 //
241
242 template<typename T, typename C>
243 auto Container<T, C>::crend() const -> ConstReverseIterator
244 {
245 return m_container.crend();
246 }
247
248 //
249 // -------------------------------------------------------------------------------------------------
250 //
251
252 template<typename T, typename C>
253 auto Container<T, C>::remove_at (int pos) -> void
254 {
255 assert (pos < size());
256 m_container.erase (m_container.begin() + pos);
257 }
258
259 //
260 // -------------------------------------------------------------------------------------------------
261 //
262
263 template<typename T, typename C>
264 auto Container<T, C>::prepend (const T& value) -> T&
265 {
266 m_container.push_front (value);
267 return m_container[0];
268 }
269
270 //
271 // -------------------------------------------------------------------------------------------------
272 //
273
274 template<typename T, typename C>
275 auto Container<T, C>::append (const T& value) -> T&
276 {
277 m_container.push_back (value);
278 return m_container[m_container.size() - 1];
279 }
280
281 //
282 // -------------------------------------------------------------------------------------------------
283 //
284
285 template<typename T, typename C>
286 auto Container<T, C>::merge (const Self& other) -> void
287 {
288 int oldsize = size();
289 resize (size() + other.size());
290 std::copy (other.begin(), other.end(), begin() + oldsize);
291 }
292
293 //
294 // -------------------------------------------------------------------------------------------------
295 //
296
297 template<typename T, typename C>
298 auto Container<T, C>::pop (T& val) -> bool
299 {
300 if (is_empty())
301 return false;
302
303 val = m_container[size() - 1];
304 m_container.erase (m_container.end() - 1);
305 return true;
306 }
307
308 //
309 // -------------------------------------------------------------------------------------------------
310 //
311
312 template<typename T, typename C>
313 auto Container<T, C>::operator<< (const T& value) -> Self&
314 {
315 append (value);
316 return *this;
317 }
318
319 //
320 // -------------------------------------------------------------------------------------------------
321 //
322
323 template<typename T, typename C>
324 auto Container<T, C>::operator<< (const Self& vals) -> Self&
325 {
326 merge (vals);
327 return *this;
328 }
329
330 //
331 // -------------------------------------------------------------------------------------------------
332 //
333
334 template<typename T, typename C>
335 auto Container<T, C>::reverse() const -> Self
336 {
337 Self rev;
338 std::copy (rbegin(), rend(), rev.begin());
339 return rev;
340 }
341
342 //
343 // -------------------------------------------------------------------------------------------------
344 //
345
346 template<typename T, typename C>
347 auto Container<T, C>::clear() -> void
348 {
349 m_container.clear();
350 }
351
352 //
353 // -------------------------------------------------------------------------------------------------
354 //
355
356 template<typename T, typename C>
357 auto Container<T, C>::insert (int pos, const T& value) -> void
358 {
359 m_container.insert (m_container.begin() + pos, value);
360 }
361
362 //
363 // -------------------------------------------------------------------------------------------------
364 //
365
366 template<typename T, typename C>
367 auto Container<T, C>::remove_duplicates() -> void
368 {
369 sort();
370 resize (std::distance (begin(), std::unique (begin(), end())));
371 }
372
373 //
374 // -------------------------------------------------------------------------------------------------
375 //
376
377 template<typename T, typename C>
378 auto Container<T, C>::size() const -> int
379 {
380 return m_container.size();
381 }
382
383 //
384 // -------------------------------------------------------------------------------------------------
385 //
386
387 template<typename T, typename C>
388 auto Container<T, C>::operator[] (int n) -> T&
389 {
390 assert (n < size());
391 return m_container[n];
392 }
393
394 //
395 // -------------------------------------------------------------------------------------------------
396 //
397
398 template<typename T, typename C>
399 auto Container<T, C>::operator[] (int n) const -> const T&
400 {
401 assert (n < size());
402 return m_container[n];
403 }
404
405 //
406 // -------------------------------------------------------------------------------------------------
407 //
408
409 template<typename T, typename C>
410 auto Container<T, C>::operator[] (const Range<int>& n) const -> Self
411 {
412 return splice (n);
413 }
414
415 //
416 // -------------------------------------------------------------------------------------------------
417 //
418
419 template<typename T, typename C>
420 auto Container<T, C>::resize (int size) -> void
421 {
422 m_container.resize (size);
423 }
424
425 //
426 // -------------------------------------------------------------------------------------------------
427 //
428
429 template<typename T, typename C>
430 auto Container<T, C>::sort() -> void
431 {
432 std::sort (begin(), end());
433 }
434
435 //
436 // -------------------------------------------------------------------------------------------------
437 //
438
439 template<typename T, typename C>
440 auto Container<T, C>::find (const T& needle) -> Iterator
441 {
442 auto it = std::find (m_container.begin(), m_container.end(), needle);
443
444 if (it == m_container.end())
445 return end();
446
447 return it;
448 }
449
450 //
451 // -------------------------------------------------------------------------------------------------
452 //
453
454 template<typename T, typename C>
455 auto Container<T, C>::find (const T& needle) const -> ConstIterator
456 {
457 auto it = std::find (m_container.cbegin(), m_container.cend(), needle);
458
459 if (it == m_container.cend())
460 return end();
461
462 return it;
463 }
464
465 //
466 // -------------------------------------------------------------------------------------------------
467 //
468
469 template<typename T, typename C>
470 auto Container<T, C>::find (Function<bool (T const&)> func) -> Iterator
471 {
472 for (Iterator it = begin(); it != end(); ++it)
473 {
474 if (func (*it))
475 return it;
476 }
477
478 return end();
479 }
480
481 //
482 // -------------------------------------------------------------------------------------------------
483 //
484
485 template<typename T, typename C>
486 auto Container<T, C>::find (Function<bool (T const&)> func) const -> ConstIterator
487 {
488 for (ConstIterator it = begin(); it != end(); ++it)
489 {
490 if (func (*it))
491 return it;
492 }
493
494 return end();
495 }
496
497 //
498 // -------------------------------------------------------------------------------------------------
499 //
500
501 template<typename T, typename C>
502 auto Container<T, C>::remove_one (const T& a) -> void
503 {
504 auto it = std::find (m_container.begin(), m_container.end(), a);
505
506 if (it != m_container.end())
507 m_container.erase (it);
508 }
509
510 //
511 // -------------------------------------------------------------------------------------------------
512 //
513
514 template<typename T, typename C>
515 auto Container<T, C>::is_empty() const -> bool
516 {
517 return size() == 0;
518 }
519
520 //
521 // -------------------------------------------------------------------------------------------------
522 //
523
524 template<typename T, typename C>
525 auto Container<T, C>::splice (int a, int b) const -> Self
526 {
527 if (a < 0 or b >= size() or b < a)
528 return Self();
529
530 Self result;
531
532 for (int i = a; i <= b; ++i)
533 result << operator[] (i);
534
535 return result;
536 }
537
538 //
539 // -------------------------------------------------------------------------------------------------
540 //
541
542 template<typename T, typename C>
543 auto Container<T, C>::splice (const Range<int>& a) const -> Self
544 {
545 return splice (a.min(), a.max());
546 }
547
548 //
549 // -------------------------------------------------------------------------------------------------
550 //
551
552 template<typename T, typename C>
553 auto Container<T, C>::container() const -> const C&
554 {
555 return m_container;
556 }
557
558 //
559 // -------------------------------------------------------------------------------------------------
560 //
561
562 template<typename T, typename C>
563 auto Container<T, C>::first() const -> const T&
564 {
565 return *m_container.cbegin();
566 }
567
568 //
569 // -------------------------------------------------------------------------------------------------
570 //
571
572 template<typename T, typename C>
573 auto Container<T, C>::last() const -> const T&
574 {
575 return *(m_container.cend() - 1);
576 }
577
578 //
579 // -------------------------------------------------------------------------------------------------
580 //
581
582 template<typename T, typename C>
583 auto Container<T, C>::contains (const T& a) const -> bool
584 {
585 return std::find (m_container.cbegin(), m_container.cend(), a) != m_container.end();
586 }
587
588 //
589 // -------------------------------------------------------------------------------------------------
590 //
591
592 template<typename T, typename C>
593 auto Container<T, C>::operator+ (const Self& other) const -> Self
594 {
595 Self out (*this);
596 out.merge (other);
597 return out;
598 }
599
600 //
601 // -------------------------------------------------------------------------------------------------
602 //
603
604 template<typename T, typename C>
605 auto operator>> (const T& value, Container<T, C>& haystack) -> Container<T, C>&
606 {
607 haystack.prepend (value);
608 return haystack;
609 }

Mercurial Repository: zfc9000

mercurial