Mercurial > zfc9000 / file comparison

comparison: sources/list.h

sources/list.h

changeset 5
146825d63b9a
parent 1
4dd5bde4e777
child 11
cffa2777d917
equal deleted inserted replaced
4:ec5387e121fa 5:146825d63b9a
35 #include <initializer_list> 35 #include <initializer_list>
36 #include <functional> 36 #include <functional>
37 #include <cassert> 37 #include <cassert>
38 #include "range.h" 38 #include "range.h"
39 39
40 // 40 // -------------------------------------------------------------------------------------------------
41 // ------------------------------------------------------------------------------------------------- 41 //
42 //
43
44 template<typename T, typename C> 42 template<typename T, typename C>
45 class Container 43 class Container
46 { 44 {
47 public: 45 public:
48 using Iterator = typename C::iterator; 46 using Iterator = typename C::iterator;
139 // 137 //
140 138
141 template<typename T, typename C> 139 template<typename T, typename C>
142 Container<T, C>::Container() {} 140 Container<T, C>::Container() {}
143 141
144 // 142 // -------------------------------------------------------------------------------------------------
145 // ------------------------------------------------------------------------------------------------- 143 //
146 //
147
148 template<typename T, typename C> 144 template<typename T, typename C>
149 Container<T, C>::Container (const C& other) : 145 Container<T, C>::Container (const C& other) :
150 m_container (other) {} 146 m_container (other) {}
151 147
152 // 148 // -------------------------------------------------------------------------------------------------
153 // ------------------------------------------------------------------------------------------------- 149 //
154 //
155
156 template<typename T, typename C> 150 template<typename T, typename C>
157 Container<T, C>::Container (std::initializer_list<T> && a) : 151 Container<T, C>::Container (std::initializer_list<T> && a) :
158 m_container (a) {} 152 m_container (a) {}
159 153
160 // 154 // -------------------------------------------------------------------------------------------------
161 // ------------------------------------------------------------------------------------------------- 155 //
162 //
163
164 template<typename T, typename C> 156 template<typename T, typename C>
165 Container<T, C>::Container (int numvalues) : 157 Container<T, C>::Container (int numvalues) :
166 m_container (numvalues) {} 158 m_container (numvalues) {}
167 159
168 // 160 // -------------------------------------------------------------------------------------------------
169 // ------------------------------------------------------------------------------------------------- 161 //
170 //
171
172 template<typename T, typename C> 162 template<typename T, typename C>
173 auto Container<T, C>::begin() -> Iterator 163 auto Container<T, C>::begin() -> Iterator
174 { 164 {
175 return m_container.begin(); 165 return m_container.begin();
176 } 166 }
177 167
178 // 168 // -------------------------------------------------------------------------------------------------
179 // ------------------------------------------------------------------------------------------------- 169 //
180 //
181
182 template<typename T, typename C> 170 template<typename T, typename C>
183 auto Container<T, C>::begin() const -> ConstIterator 171 auto Container<T, C>::begin() const -> ConstIterator
184 { 172 {
185 return m_container.cbegin(); 173 return m_container.cbegin();
186 } 174 }
187 175
188 // 176 // -------------------------------------------------------------------------------------------------
189 // ------------------------------------------------------------------------------------------------- 177 //
190 //
191
192 template<typename T, typename C> 178 template<typename T, typename C>
193 auto Container<T, C>::end() -> Iterator 179 auto Container<T, C>::end() -> Iterator
194 { 180 {
195 return m_container.end(); 181 return m_container.end();
196 } 182 }
197 183
198 // 184 // -------------------------------------------------------------------------------------------------
199 // ------------------------------------------------------------------------------------------------- 185 //
200 //
201
202 template<typename T, typename C> 186 template<typename T, typename C>
203 auto Container<T, C>::end() const -> ConstIterator 187 auto Container<T, C>::end() const -> ConstIterator
204 { 188 {
205 return m_container.cend(); 189 return m_container.cend();
206 } 190 }
207 191
208 // 192 // -------------------------------------------------------------------------------------------------
209 // ------------------------------------------------------------------------------------------------- 193 //
210 //
211
212 template<typename T, typename C> 194 template<typename T, typename C>
213 auto Container<T, C>::rbegin() -> ReverseIterator 195 auto Container<T, C>::rbegin() -> ReverseIterator
214 { 196 {
215 return m_container.rbegin(); 197 return m_container.rbegin();
216 } 198 }
217 199
218 // 200 // -------------------------------------------------------------------------------------------------
219 // ------------------------------------------------------------------------------------------------- 201 //
220 //
221
222 template<typename T, typename C> 202 template<typename T, typename C>
223 auto Container<T, C>::crbegin() const -> ConstReverseIterator 203 auto Container<T, C>::crbegin() const -> ConstReverseIterator
224 { 204 {
225 return m_container.crbegin(); 205 return m_container.crbegin();
226 } 206 }
227 207
228 // 208 // -------------------------------------------------------------------------------------------------
229 // ------------------------------------------------------------------------------------------------- 209 //
230 //
231
232 template<typename T, typename C> 210 template<typename T, typename C>
233 auto Container<T, C>::rend() -> ReverseIterator 211 auto Container<T, C>::rend() -> ReverseIterator
234 { 212 {
235 return m_container.rend(); 213 return m_container.rend();
236 } 214 }
237 215
238 // 216 // -------------------------------------------------------------------------------------------------
239 // ------------------------------------------------------------------------------------------------- 217 //
240 //
241
242 template<typename T, typename C> 218 template<typename T, typename C>
243 auto Container<T, C>::crend() const -> ConstReverseIterator 219 auto Container<T, C>::crend() const -> ConstReverseIterator
244 { 220 {
245 return m_container.crend(); 221 return m_container.crend();
246 } 222 }
247 223
248 // 224 // -------------------------------------------------------------------------------------------------
249 // ------------------------------------------------------------------------------------------------- 225 //
250 //
251
252 template<typename T, typename C> 226 template<typename T, typename C>
253 auto Container<T, C>::remove_at (int pos) -> void 227 auto Container<T, C>::remove_at (int pos) -> void
254 { 228 {
255 assert (pos < size()); 229 assert (pos < size());
256 m_container.erase (m_container.begin() + pos); 230 m_container.erase (m_container.begin() + pos);
257 } 231 }
258 232
259 // 233 // -------------------------------------------------------------------------------------------------
260 // ------------------------------------------------------------------------------------------------- 234 //
261 //
262
263 template<typename T, typename C> 235 template<typename T, typename C>
264 auto Container<T, C>::prepend (const T& value) -> T& 236 auto Container<T, C>::prepend (const T& value) -> T&
265 { 237 {
266 m_container.push_front (value); 238 m_container.push_front (value);
267 return m_container[0]; 239 return m_container[0];
268 } 240 }
269 241
270 // 242 // -------------------------------------------------------------------------------------------------
271 // ------------------------------------------------------------------------------------------------- 243 //
272 //
273
274 template<typename T, typename C> 244 template<typename T, typename C>
275 auto Container<T, C>::append (const T& value) -> T& 245 auto Container<T, C>::append (const T& value) -> T&
276 { 246 {
277 m_container.push_back (value); 247 m_container.push_back (value);
278 return m_container[m_container.size() - 1]; 248 return m_container[m_container.size() - 1];
279 } 249 }
280 250
281 // 251 // -------------------------------------------------------------------------------------------------
282 // ------------------------------------------------------------------------------------------------- 252 //
283 //
284
285 template<typename T, typename C> 253 template<typename T, typename C>
286 auto Container<T, C>::merge (const Self& other) -> void 254 auto Container<T, C>::merge (const Self& other) -> void
287 { 255 {
288 int oldsize = size(); 256 int oldsize = size();
289 resize (size() + other.size()); 257 resize (size() + other.size());
290 std::copy (other.begin(), other.end(), begin() + oldsize); 258 std::copy (other.begin(), other.end(), begin() + oldsize);
291 } 259 }
292 260
293 // 261 // -------------------------------------------------------------------------------------------------
294 // ------------------------------------------------------------------------------------------------- 262 //
295 //
296
297 template<typename T, typename C> 263 template<typename T, typename C>
298 auto Container<T, C>::pop (T& val) -> bool 264 auto Container<T, C>::pop (T& val) -> bool
299 { 265 {
300 if (is_empty()) 266 if (is_empty())
301 return false; 267 return false;
303 val = m_container[size() - 1]; 269 val = m_container[size() - 1];
304 m_container.erase (m_container.end() - 1); 270 m_container.erase (m_container.end() - 1);
305 return true; 271 return true;
306 } 272 }
307 273
308 // 274 // -------------------------------------------------------------------------------------------------
309 // ------------------------------------------------------------------------------------------------- 275 //
310 //
311
312 template<typename T, typename C> 276 template<typename T, typename C>
313 auto Container<T, C>::operator<< (const T& value) -> Self& 277 auto Container<T, C>::operator<< (const T& value) -> Self&
314 { 278 {
315 append (value); 279 append (value);
316 return *this; 280 return *this;
317 } 281 }
318 282
319 // 283 // -------------------------------------------------------------------------------------------------
320 // ------------------------------------------------------------------------------------------------- 284 //
321 //
322
323 template<typename T, typename C> 285 template<typename T, typename C>
324 auto Container<T, C>::operator<< (const Self& vals) -> Self& 286 auto Container<T, C>::operator<< (const Self& vals) -> Self&
325 { 287 {
326 merge (vals); 288 merge (vals);
327 return *this; 289 return *this;
328 } 290 }
329 291
330 // 292 // -------------------------------------------------------------------------------------------------
331 // ------------------------------------------------------------------------------------------------- 293 //
332 //
333
334 template<typename T, typename C> 294 template<typename T, typename C>
335 auto Container<T, C>::reverse() const -> Self 295 auto Container<T, C>::reverse() const -> Self
336 { 296 {
337 Self rev; 297 Self rev;
338 std::copy (rbegin(), rend(), rev.begin()); 298 std::copy (rbegin(), rend(), rev.begin());
339 return rev; 299 return rev;
340 } 300 }
341 301
342 // 302 // -------------------------------------------------------------------------------------------------
343 // ------------------------------------------------------------------------------------------------- 303 //
344 //
345
346 template<typename T, typename C> 304 template<typename T, typename C>
347 auto Container<T, C>::clear() -> void 305 auto Container<T, C>::clear() -> void
348 { 306 {
349 m_container.clear(); 307 m_container.clear();
350 } 308 }
351 309
352 // 310 // -------------------------------------------------------------------------------------------------
353 // ------------------------------------------------------------------------------------------------- 311 //
354 //
355
356 template<typename T, typename C> 312 template<typename T, typename C>
357 auto Container<T, C>::insert (int pos, const T& value) -> void 313 auto Container<T, C>::insert (int pos, const T& value) -> void
358 { 314 {
359 m_container.insert (m_container.begin() + pos, value); 315 m_container.insert (m_container.begin() + pos, value);
360 } 316 }
361 317
362 // 318 // -------------------------------------------------------------------------------------------------
363 // ------------------------------------------------------------------------------------------------- 319 //
364 //
365
366 template<typename T, typename C> 320 template<typename T, typename C>
367 auto Container<T, C>::remove_duplicates() -> void 321 auto Container<T, C>::remove_duplicates() -> void
368 { 322 {
369 sort(); 323 sort();
370 resize (std::distance (begin(), std::unique (begin(), end()))); 324 resize (std::distance (begin(), std::unique (begin(), end())));
371 } 325 }
372 326
373 // 327 // -------------------------------------------------------------------------------------------------
374 // ------------------------------------------------------------------------------------------------- 328 //
375 //
376
377 template<typename T, typename C> 329 template<typename T, typename C>
378 auto Container<T, C>::size() const -> int 330 auto Container<T, C>::size() const -> int
379 { 331 {
380 return m_container.size(); 332 return m_container.size();
381 } 333 }
382 334
383 // 335 // -------------------------------------------------------------------------------------------------
384 // ------------------------------------------------------------------------------------------------- 336 //
385 //
386
387 template<typename T, typename C> 337 template<typename T, typename C>
388 auto Container<T, C>::operator[] (int n) -> T& 338 auto Container<T, C>::operator[] (int n) -> T&
389 { 339 {
390 assert (n < size()); 340 assert (n < size());
391 return m_container[n]; 341 return m_container[n];
392 } 342 }
393 343
394 // 344 // -------------------------------------------------------------------------------------------------
395 // ------------------------------------------------------------------------------------------------- 345 //
396 //
397
398 template<typename T, typename C> 346 template<typename T, typename C>
399 auto Container<T, C>::operator[] (int n) const -> const T& 347 auto Container<T, C>::operator[] (int n) const -> const T&
400 { 348 {
401 assert (n < size()); 349 assert (n < size());
402 return m_container[n]; 350 return m_container[n];
403 } 351 }
404 352
405 // 353 // -------------------------------------------------------------------------------------------------
406 // ------------------------------------------------------------------------------------------------- 354 //
407 //
408
409 template<typename T, typename C> 355 template<typename T, typename C>
410 auto Container<T, C>::operator[] (const Range<int>& n) const -> Self 356 auto Container<T, C>::operator[] (const Range<int>& n) const -> Self
411 { 357 {
412 return splice (n); 358 return splice (n);
413 } 359 }
414 360
415 // 361 // -------------------------------------------------------------------------------------------------
416 // ------------------------------------------------------------------------------------------------- 362 //
417 //
418
419 template<typename T, typename C> 363 template<typename T, typename C>
420 auto Container<T, C>::resize (int size) -> void 364 auto Container<T, C>::resize (int size) -> void
421 { 365 {
422 m_container.resize (size); 366 m_container.resize (size);
423 } 367 }
424 368
425 // 369 // -------------------------------------------------------------------------------------------------
426 // ------------------------------------------------------------------------------------------------- 370 //
427 //
428
429 template<typename T, typename C> 371 template<typename T, typename C>
430 auto Container<T, C>::sort() -> void 372 auto Container<T, C>::sort() -> void
431 { 373 {
432 std::sort (begin(), end()); 374 std::sort (begin(), end());
433 } 375 }
434 376
435 // 377 // -------------------------------------------------------------------------------------------------
436 // ------------------------------------------------------------------------------------------------- 378 //
437 //
438
439 template<typename T, typename C> 379 template<typename T, typename C>
440 auto Container<T, C>::find (const T& needle) -> Iterator 380 auto Container<T, C>::find (const T& needle) -> Iterator
441 { 381 {
442 auto it = std::find (m_container.begin(), m_container.end(), needle); 382 auto it = std::find (m_container.begin(), m_container.end(), needle);
443 383
445 return end(); 385 return end();
446 386
447 return it; 387 return it;
448 } 388 }
449 389
450 // 390 // -------------------------------------------------------------------------------------------------
451 // ------------------------------------------------------------------------------------------------- 391 //
452 //
453
454 template<typename T, typename C> 392 template<typename T, typename C>
455 auto Container<T, C>::find (const T& needle) const -> ConstIterator 393 auto Container<T, C>::find (const T& needle) const -> ConstIterator
456 { 394 {
457 auto it = std::find (m_container.cbegin(), m_container.cend(), needle); 395 auto it = std::find (m_container.cbegin(), m_container.cend(), needle);
458 396
460 return end(); 398 return end();
461 399
462 return it; 400 return it;
463 } 401 }
464 402
465 // 403 // -------------------------------------------------------------------------------------------------
466 // ------------------------------------------------------------------------------------------------- 404 //
467 //
468
469 template<typename T, typename C> 405 template<typename T, typename C>
470 auto Container<T, C>::find (Function<bool (T const&)> func) -> Iterator 406 auto Container<T, C>::find (Function<bool (T const&)> func) -> Iterator
471 { 407 {
472 for (Iterator it = begin(); it != end(); ++it) 408 for (Iterator it = begin(); it != end(); ++it)
473 { 409 {
476 } 412 }
477 413
478 return end(); 414 return end();
479 } 415 }
480 416
481 // 417 // -------------------------------------------------------------------------------------------------
482 // ------------------------------------------------------------------------------------------------- 418 //
483 //
484
485 template<typename T, typename C> 419 template<typename T, typename C>
486 auto Container<T, C>::find (Function<bool (T const&)> func) const -> ConstIterator 420 auto Container<T, C>::find (Function<bool (T const&)> func) const -> ConstIterator
487 { 421 {
488 for (ConstIterator it = begin(); it != end(); ++it) 422 for (ConstIterator it = begin(); it != end(); ++it)
489 { 423 {
492 } 426 }
493 427
494 return end(); 428 return end();
495 } 429 }
496 430
497 // 431 // -------------------------------------------------------------------------------------------------
498 // ------------------------------------------------------------------------------------------------- 432 //
499 //
500
501 template<typename T, typename C> 433 template<typename T, typename C>
502 auto Container<T, C>::remove_one (const T& a) -> void 434 auto Container<T, C>::remove_one (const T& a) -> void
503 { 435 {
504 auto it = std::find (m_container.begin(), m_container.end(), a); 436 auto it = std::find (m_container.begin(), m_container.end(), a);
505 437
506 if (it != m_container.end()) 438 if (it != m_container.end())
507 m_container.erase (it); 439 m_container.erase (it);
508 } 440 }
509 441
510 // 442 // -------------------------------------------------------------------------------------------------
511 // ------------------------------------------------------------------------------------------------- 443 //
512 //
513
514 template<typename T, typename C> 444 template<typename T, typename C>
515 auto Container<T, C>::is_empty() const -> bool 445 auto Container<T, C>::is_empty() const -> bool
516 { 446 {
517 return size() == 0; 447 return size() == 0;
518 } 448 }
519 449
520 // 450 // -------------------------------------------------------------------------------------------------
521 // ------------------------------------------------------------------------------------------------- 451 //
522 //
523
524 template<typename T, typename C> 452 template<typename T, typename C>
525 auto Container<T, C>::splice (int a, int b) const -> Self 453 auto Container<T, C>::splice (int a, int b) const -> Self
526 { 454 {
527 if (a < 0 or b >= size() or b < a) 455 if (a < 0 or b >= size() or b < a)
528 return Self(); 456 return Self();
533 result << operator[] (i); 461 result << operator[] (i);
534 462
535 return result; 463 return result;
536 } 464 }
537 465
538 // 466 // -------------------------------------------------------------------------------------------------
539 // ------------------------------------------------------------------------------------------------- 467 //
540 //
541
542 template<typename T, typename C> 468 template<typename T, typename C>
543 auto Container<T, C>::splice (const Range<int>& a) const -> Self 469 auto Container<T, C>::splice (const Range<int>& a) const -> Self
544 { 470 {
545 return splice (a.min(), a.max()); 471 return splice (a.min(), a.max());
546 } 472 }
547 473
548 // 474 // -------------------------------------------------------------------------------------------------
549 // ------------------------------------------------------------------------------------------------- 475 //
550 //
551
552 template<typename T, typename C> 476 template<typename T, typename C>
553 auto Container<T, C>::container() const -> const C& 477 auto Container<T, C>::container() const -> const C&
554 { 478 {
555 return m_container; 479 return m_container;
556 } 480 }
557 481
558 // 482 // -------------------------------------------------------------------------------------------------
559 // ------------------------------------------------------------------------------------------------- 483 //
560 //
561
562 template<typename T, typename C> 484 template<typename T, typename C>
563 auto Container<T, C>::first() const -> const T& 485 auto Container<T, C>::first() const -> const T&
564 { 486 {
565 return *m_container.cbegin(); 487 return *m_container.cbegin();
566 } 488 }
567 489
568 // 490 // -------------------------------------------------------------------------------------------------
569 // ------------------------------------------------------------------------------------------------- 491 //
570 //
571
572 template<typename T, typename C> 492 template<typename T, typename C>
573 auto Container<T, C>::last() const -> const T& 493 auto Container<T, C>::last() const -> const T&
574 { 494 {
575 return *(m_container.cend() - 1); 495 return *(m_container.cend() - 1);
576 } 496 }
577 497
578 // 498 // -------------------------------------------------------------------------------------------------
579 // ------------------------------------------------------------------------------------------------- 499 //
580 //
581
582 template<typename T, typename C> 500 template<typename T, typename C>
583 auto Container<T, C>::contains (const T& a) const -> bool 501 auto Container<T, C>::contains (const T& a) const -> bool
584 { 502 {
585 return std::find (m_container.cbegin(), m_container.cend(), a) != m_container.end(); 503 return std::find (m_container.cbegin(), m_container.cend(), a) != m_container.end();
586 } 504 }
587 505
588 // 506 // -------------------------------------------------------------------------------------------------
589 // ------------------------------------------------------------------------------------------------- 507 //
590 //
591
592 template<typename T, typename C> 508 template<typename T, typename C>
593 auto Container<T, C>::operator+ (const Self& other) const -> Self 509 auto Container<T, C>::operator+ (const Self& other) const -> Self
594 { 510 {
595 Self out (*this); 511 Self out (*this);
596 out.merge (other); 512 out.merge (other);
597 return out; 513 return out;
598 } 514 }
599 515
600 // 516 // -------------------------------------------------------------------------------------------------
601 // ------------------------------------------------------------------------------------------------- 517 //
602 //
603
604 template<typename T, typename C> 518 template<typename T, typename C>
605 auto operator>> (const T& value, Container<T, C>& haystack) -> Container<T, C>& 519 auto operator>> (const T& value, Container<T, C>& haystack) -> Container<T, C>&
606 { 520 {
607 haystack.prepend (value); 521 haystack.prepend (value);
608 return haystack; 522 return haystack;

Mercurial Repository: zfc9000

mercurial