1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5// ==++==
6//
7
8//
9
10//
11// ==--==
12
13/*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
14XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
15XX XX
16XX list<T> XX
17XX XX
18XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
19XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
20*/
21
22#pragma once
23
24#include "iterator.h"
25#include "functional.h"
26
27namespace jitstd
28{
29
30template <typename T, typename Allocator = jitstd::allocator<T>>
31class list
32{
33public:
34 typedef Allocator allocator_type;
35 typedef T* pointer;
36 typedef T& reference;
37 typedef const T* const_pointer;
38 typedef const T& const_reference;
39
40 typedef size_t size_type;
41 typedef ptrdiff_t difference_type;
42 typedef T value_type;
43
44 // Forward declaration
45private:
46 struct Node;
47
48public:
49 // nested classes
50 class iterator;
51 class const_iterator : public jitstd::iterator<bidirectional_iterator_tag, T>
52 {
53 private:
54 const_iterator(Node* ptr);
55 const_iterator();
56 public:
57 const_iterator(const const_iterator& it);
58 const_iterator(const typename list<T, Allocator>::iterator& it);
59
60 const_iterator& operator++();
61 const_iterator& operator++(int);
62 const_iterator& operator--();
63 const_iterator& operator--(int);
64 const_iterator operator+(difference_type n);
65 const_iterator operator-(difference_type n);
66 size_type operator-(const const_iterator& that);
67 bool operator==(const const_iterator& it) const;
68 bool operator!=(const const_iterator& it) const;
69 const T& operator*() const;
70 const T* operator&() const;
71 const T* operator->() const;
72 operator const T*() const;
73
74 private:
75 friend class list<T, Allocator>;
76 Node* m_pNode;
77 };
78
79 class iterator : public jitstd::iterator<bidirectional_iterator_tag, T>
80 {
81 iterator(Node* ptr);
82 public:
83 iterator();
84 iterator(const iterator& it);
85
86 iterator& operator++();
87 iterator& operator++(int);
88 iterator& operator--();
89 iterator& operator--(int);
90 iterator operator+(difference_type n);
91 iterator operator-(difference_type n);
92 size_type operator-(const iterator& that);
93 bool operator==(const iterator& it);
94 bool operator!=(const iterator& it);
95 T& operator*();
96 T* operator&();
97 T* operator->();
98 operator T*();
99
100 private:
101 friend class list<T, Allocator>;
102 friend class list<T, Allocator>::const_iterator;
103 Node* m_pNode;
104 };
105
106 class reverse_iterator;
107 class const_reverse_iterator : public jitstd::iterator<bidirectional_iterator_tag, T>
108 {
109 private:
110 const_reverse_iterator(Node* ptr);
111 public:
112 const_reverse_iterator();
113 const_reverse_iterator(const const_reverse_iterator& it);
114 const_reverse_iterator(const reverse_iterator& it);
115
116 const_reverse_iterator& operator++();
117 const_reverse_iterator& operator++(int);
118 const_reverse_iterator& operator--();
119 const_reverse_iterator& operator--(int);
120 const_reverse_iterator operator+(difference_type n);
121 const_reverse_iterator operator-(difference_type n);
122 size_type operator-(const const_reverse_iterator& that);
123 bool operator==(const const_reverse_iterator& it) const;
124 bool operator!=(const const_reverse_iterator& it) const;
125 const T& operator*() const;
126 const T* operator&() const;
127 const T* operator->() const;
128 operator const T*() const;
129
130 private:
131 friend class list<T, Allocator>;
132 Node* m_pNode;
133 };
134
135 class reverse_iterator : public jitstd::iterator<bidirectional_iterator_tag, T>
136 {
137 private:
138 reverse_iterator(Node* ptr);
139 public:
140 reverse_iterator();
141 reverse_iterator(const reverse_iterator& it);
142
143 reverse_iterator& operator++();
144 reverse_iterator& operator++(int);
145 reverse_iterator& operator--();
146 reverse_iterator& operator--(int);
147 reverse_iterator operator+(difference_type n);
148 reverse_iterator operator-(difference_type n);
149 size_type operator-(const reverse_iterator& that);
150 bool operator==(const reverse_iterator& it);
151 bool operator!=(const reverse_iterator& it);
152 T& operator*();
153 T* operator&();
154 T* operator->();
155 operator T*();
156 friend class list<T, Allocator>::const_reverse_iterator;
157
158 private:
159 friend class list<T, Allocator>;
160 Node* m_pNode;
161 };
162
163 explicit list(const Allocator&);
164 list(size_type n, const T& value, const Allocator&);
165
166 template <typename InputIterator>
167 list(InputIterator first, InputIterator last, const Allocator&);
168
169 list(const list<T, Allocator>&);
170
171 ~list();
172
173 template <class InputIterator>
174 void assign(InputIterator first, InputIterator last);
175
176 void assign(size_type size, const T& val);
177
178 reference back();
179 const_reference back() const;
180 iterator backPosition();
181 const_iterator backPosition() const;
182
183 iterator begin();
184 const_iterator begin() const;
185
186 void clear();
187 bool empty() const;
188
189 iterator end();
190 const_iterator end() const;
191
192 iterator erase(iterator position);
193 iterator erase(iterator first, iterator last);
194
195 reference front();
196 const_reference front() const;
197
198 allocator_type get_allocator() const;
199
200 iterator insert(iterator position, const T& x);
201 template <class... Args>
202 iterator emplace(iterator position, Args&&... args);
203 void insert(iterator position, size_type n, const T& x);
204 template <class InputIterator>
205 void insert(iterator position, InputIterator first, InputIterator last);
206
207 size_type max_size() const;
208
209 void merge(list<T, Allocator>& lst);
210 template <class Compare>
211 void merge (list<T, Allocator>& lst, Compare comp);
212
213 list<T, Allocator>& operator=(const list<T, Allocator>& lst);
214
215 void pop_back();
216 void pop_front();
217
218 void push_back(const T& val);
219 template <class... Args>
220 void emplace_back(Args&&... args);
221 void push_front (const T& val);
222 template <class... Args>
223 void emplace_front(Args&&... args);
224
225 reverse_iterator rbegin();
226 const_reverse_iterator rbegin() const;
227
228 void remove(const T& val);
229 template <class Predicate>
230 void remove_if(Predicate pred);
231
232 reverse_iterator rend();
233 const_reverse_iterator rend() const;
234
235 void resize(size_type sz, const T& c);
236 void reverse();
237
238 size_type size() const;
239 void sort();
240
241 template <class Compare>
242 void sort(Compare comp);
243
244 void splice(iterator position, list& lst);
245 void splice(iterator position, list& lst, iterator i);
246 void splice(iterator position, list& x, iterator first, iterator last);
247
248 void swap(list<T,Allocator>& lst);
249
250 void unique();
251
252 template <class BinaryPredicate>
253 void unique(const BinaryPredicate& binary_pred);
254
255private:
256 struct Node
257 {
258 T m_value;
259 Node* m_pNext;
260 Node* m_pPrev;
261
262 template <class... Args>
263 Node(Args&&... args)
264 : m_value(jitstd::forward<Args>(args)...)
265 {
266 }
267 };
268
269 void destroy_helper();
270
271 void construct_helper(size_type n, const T& value, int_not_an_iterator_tag);
272 template <typename InputIterator>
273 void construct_helper(InputIterator first, InputIterator last, forward_iterator_tag);
274
275 void assign_helper(size_type n, const T& value, int_not_an_iterator_tag);
276 template <typename InputIterator>
277 void assign_helper(InputIterator first, InputIterator last, forward_iterator_tag);
278
279 void insert_helper(iterator position, size_type n, const T& value, int_not_an_iterator_tag);
280 template <typename InputIterator>
281 void insert_helper(iterator position, InputIterator first, InputIterator last, forward_iterator_tag);
282
283 void insert_new_node_helper(Node* pInsert, Node* pNewNode);
284
285 Node* m_pHead;
286 Node* m_pTail;
287 size_type m_nSize;
288 typename Allocator::template rebind<T>::allocator m_allocator;
289 typename Allocator::template rebind<Node>::allocator m_nodeAllocator;
290};
291
292}
293
294namespace jitstd
295{
296template <typename T, typename Allocator>
297list<T, Allocator>::list(const Allocator& allocator)
298 : m_pHead(nullptr)
299 , m_pTail(nullptr)
300 , m_nSize(0)
301 , m_allocator(allocator)
302 , m_nodeAllocator(allocator)
303{
304}
305
306template <typename T, typename Allocator>
307list<T, Allocator>::list(size_type n, const T& value, const Allocator& allocator)
308 : m_pHead(NULL)
309 , m_pTail(NULL)
310 , m_nSize(0)
311 , m_allocator(allocator)
312 , m_nodeAllocator(allocator)
313{
314 construct_helper(n, value, int_not_an_iterator_tag());
315}
316
317template <typename T, typename Allocator>
318template <typename InputIterator>
319list<T, Allocator>::list(InputIterator first, InputIterator last, const Allocator& allocator)
320 : m_pHead(NULL)
321 , m_pTail(NULL)
322 , m_nSize(0)
323 , m_allocator(allocator)
324 , m_nodeAllocator(allocator)
325{
326 construct_helper(first, last, iterator_traits<InputIterator>::iterator_category());
327}
328
329template <typename T, typename Allocator>
330list<T, Allocator>::list(const list<T, Allocator>& other)
331 : m_pHead(NULL)
332 , m_pTail(NULL)
333 , m_nSize(0)
334 , m_allocator(other.m_allocator)
335 , m_nodeAllocator(other.m_nodeAllocator)
336{
337 construct_helper(other.begin(), other.end(), forward_iterator_tag());
338}
339
340template <typename T, typename Allocator>
341list<T, Allocator>::~list()
342{
343 destroy_helper();
344}
345
346template <typename T, typename Allocator>
347template <class InputIterator>
348void list<T, Allocator>::assign(InputIterator first, InputIterator last)
349{
350 assign_helper(first, last, iterator_traits<InputIterator>::iterator_category());
351}
352
353template <typename T, typename Allocator>
354void list<T, Allocator>::assign(size_type size, const T& val)
355{
356 assign_helper(size, val, int_not_an_iterator_tag());
357}
358
359template <typename T, typename Allocator>
360typename list<T, Allocator>::reference list<T, Allocator>::back()
361{
362 return m_pTail->m_value;
363}
364
365template <typename T, typename Allocator>
366typename list<T, Allocator>::const_reference list<T, Allocator>::back() const
367{
368 return m_pTail->m_value;
369}
370
371template <typename T, typename Allocator>
372typename list<T, Allocator>::iterator list<T, Allocator>::backPosition()
373{
374 return iterator(m_pTail);
375}
376
377template <typename T, typename Allocator>
378typename list<T, Allocator>::const_iterator list<T, Allocator>::backPosition() const
379{
380 return const_iterator(m_pTail);
381}
382
383template <typename T, typename Allocator>
384typename list<T, Allocator>::iterator list<T, Allocator>::begin()
385{
386 return iterator(m_pHead);
387}
388
389template <typename T, typename Allocator>
390typename list<T, Allocator>::const_iterator list<T, Allocator>::begin() const
391{
392 return const_iterator(m_pHead);
393}
394
395template <typename T, typename Allocator>
396void list<T, Allocator>::clear()
397{
398 destroy_helper();
399}
400
401template <typename T, typename Allocator>
402bool list<T, Allocator>::empty() const
403{
404 return (m_nSize == 0);
405}
406
407template <typename T, typename Allocator>
408typename list<T, Allocator>::iterator list<T, Allocator>::end()
409{
410 return iterator(nullptr);
411}
412
413template <typename T, typename Allocator>
414typename list<T, Allocator>::const_iterator list<T, Allocator>::end() const
415{
416 return const_iterator(NULL);
417}
418
419template <typename T, typename Allocator>
420typename list<T, Allocator>::iterator list<T, Allocator>::erase(iterator position)
421{
422 // Nothing to erase.
423 assert(position.m_pNode != nullptr);
424
425 --m_nSize;
426
427 Node* pNode = position.m_pNode;
428 Node* pPrev = pNode->m_pPrev;
429 Node* pNext = pNode->m_pNext;
430
431 if (pPrev != nullptr)
432 {
433 pPrev->m_pNext = pNext;
434 }
435 else
436 {
437 m_pHead = pNext;
438 }
439
440 if (pNext != nullptr)
441 {
442 pNext->m_pPrev = pPrev;
443 }
444 else
445 {
446 m_pTail = pPrev;
447 }
448
449 m_nodeAllocator.deallocate(pNode, 1);
450 return iterator(pNext);
451}
452
453template <typename T, typename Allocator>
454typename list<T, Allocator>::iterator list<T, Allocator>::erase(iterator first, iterator last)
455{
456 for (; first != last; first++)
457 {
458 erase(first);
459 }
460}
461
462template <typename T, typename Allocator>
463typename list<T, Allocator>::reference list<T, Allocator>::front()
464{
465 return m_pHead->m_value;
466}
467
468template <typename T, typename Allocator>
469typename list<T, Allocator>::const_reference list<T, Allocator>::front() const
470{
471 return m_pHead->m_value;
472}
473
474template <typename T, typename Allocator>
475typename list<T, Allocator>::allocator_type list<T, Allocator>::get_allocator() const
476{
477 return m_allocator;
478}
479
480template <typename T, typename Allocator>
481typename list<T, Allocator>::iterator
482 list<T, Allocator>::insert(iterator position, const T& val)
483{
484 Node* pNewNode = new (m_nodeAllocator.allocate(1), placement_t()) Node(val);
485 insert_new_node_helper(position.m_pNode, pNewNode);
486 return iterator(pNewNode);
487}
488
489template <typename T, typename Allocator>
490template <typename... Args>
491typename list<T, Allocator>::iterator
492 list<T, Allocator>::emplace(iterator position, Args&&... args)
493{
494 Node* pNewNode = new (m_nodeAllocator.allocate(1), placement_t()) Node(jitstd::forward<Args>(args)...);
495 insert_new_node_helper(position.m_pNode, pNewNode);
496 return iterator(pNewNode);
497}
498
499template <typename T, typename Allocator>
500void list<T, Allocator>::insert(iterator position, size_type n, const T& val)
501{
502 insert_helper(position, n, val, int_not_an_iterator_tag());
503}
504
505template <typename T, typename Allocator>
506template <class InputIterator>
507void list<T, Allocator>::insert(iterator position, InputIterator first, InputIterator last)
508{
509 insert_helper(position, first, last, iterator_traits<InputIterator>::iterator_category());
510}
511
512template <typename T, typename Allocator>
513typename list<T, Allocator>::size_type list<T, Allocator>::max_size() const
514{
515 return (((size_type)-1) >> 1) / sizeof(Node);
516}
517
518template <typename T, typename Allocator>
519void list<T, Allocator>::merge(list<T, Allocator>& lst)
520{
521 merge(lst, jitstd::greater<T>());
522}
523
524template <typename T, typename Allocator>
525template <class Compare>
526void list<T, Allocator>::merge(list<T, Allocator>& lst, Compare comp)
527{
528 int size = lst.m_nSize;
529
530 iterator i = begin();
531 iterator j = lst.begin();
532 while (i != end() && j != lst.end())
533 {
534 if (comp(*i, *j))
535 {
536 i = insert(i, *j);
537 ++j;
538 --size;
539 }
540 else
541 {
542 ++i;
543 }
544 }
545
546 if (j != lst.end())
547 {
548 if (m_pTail != NULL)
549 {
550 m_pTail->m_pNext = j.m_pNode;
551 }
552 else
553 {
554 m_pHead = j.m_pNode;
555 }
556 m_pTail = lst.m_pTail;
557 m_nSize += size;
558 }
559}
560
561template <typename T, typename Allocator>
562list<T, Allocator>& list<T, Allocator>::operator=(const list<T, Allocator>& lst)
563{
564 destroy_helper();
565 construct_helper(lst.begin(), lst.end(), forward_iterator_tag());
566 return *this;
567}
568
569template <typename T, typename Allocator>
570void list<T, Allocator>::pop_back()
571{
572 assert(m_nSize != 0);
573
574 --m_nSize;
575
576 Node* pDelete = m_pTail;
577 if (m_pHead != m_pTail)
578 {
579 m_pTail = m_pTail->m_pPrev;
580 m_pTail->m_pNext = nullptr;
581 }
582 else
583 {
584 m_pHead = nullptr;
585 m_pTail = nullptr;
586 }
587 pDelete->~Node();
588 m_nodeAllocator.deallocate(pDelete, 1);
589}
590
591template <typename T, typename Allocator>
592void list<T, Allocator>::pop_front()
593{
594 assert(m_nSize != 0);
595
596 --m_nSize;
597
598 Node* pDelete = m_pHead;
599 if (m_pHead != m_pTail)
600 {
601 m_pHead = m_pHead->m_pNext;
602 m_pHead->m_pPrev = NULL;
603 }
604 else
605 {
606 m_pHead = NULL;
607 m_pTail = NULL;
608 }
609 pDelete->~Node();
610 m_nodeAllocator.deallocate(pDelete, 1);
611}
612
613template <typename T, typename Allocator>
614void list<T, Allocator>::push_back(const T& val)
615{
616 insert(end(), val);
617}
618
619template <typename T, typename Allocator>
620template <typename... Args>
621void list<T, Allocator>::emplace_back(Args&&... args)
622{
623 emplace(end(), jitstd::forward<Args>(args)...);
624}
625
626template <typename T, typename Allocator>
627void list<T, Allocator>::push_front(const T& val)
628{
629 insert(begin(), val);
630}
631
632template <typename T, typename Allocator>
633template <typename... Args>
634void list<T, Allocator>::emplace_front(Args&&... args)
635{
636 emplace(begin(), jitstd::forward<Args>(args)...);
637}
638
639template <typename T, typename Allocator>
640typename list<T, Allocator>::reverse_iterator
641 list<T, Allocator>::rbegin()
642{
643 return reverse_iterator(m_pTail);
644}
645
646template <typename T, typename Allocator>
647typename list<T, Allocator>::const_reverse_iterator
648 list<T, Allocator>::rbegin() const
649{
650 return const_reverse_iterator(m_pTail);
651}
652
653template <typename T, typename Allocator>
654void list<T, Allocator>::remove(const T& val)
655{
656 for (iterator i = begin(); i != end();)
657 {
658 if (*i == val)
659 {
660 i = erase(i);
661 }
662 else
663 {
664 ++i;
665 }
666 }
667}
668
669template <typename T, typename Allocator>
670template <class Predicate>
671void list<T, Allocator>::remove_if(Predicate pred)
672{
673 for (iterator i = begin(); i != end();)
674 {
675 if (pred(*i))
676 {
677 i = erase(i);
678 }
679 else
680 {
681 ++i;
682 }
683 }
684}
685
686template <typename T, typename Allocator>
687typename list<T, Allocator>::reverse_iterator list<T, Allocator>::rend()
688{
689 return reverse_iterator(nullptr);
690}
691
692template <typename T, typename Allocator>
693typename list<T, Allocator>::const_reverse_iterator list<T, Allocator>::rend() const
694{
695 return reverse_iterator(NULL);
696}
697
698template <typename T, typename Allocator>
699void list<T, Allocator>::resize(size_type sz, const T& c)
700{
701 while (m_nSize < sz)
702 {
703 insert(end(), c);
704 }
705
706 while (m_nSize > sz)
707 {
708 erase(end());
709 }
710}
711
712template <typename T, typename Allocator>
713void list<T, Allocator>::reverse()
714{
715 for (Node* p = m_pHead; p != NULL; p = p->m_pNext)
716 {
717 jitstd::swap(p->m_pPrev, p->m_pNext);
718 }
719 jitstd::swap(m_pHead, m_pTail);
720}
721
722template <typename T, typename Allocator>
723typename list<T, Allocator>::size_type list<T, Allocator>::size() const
724{
725 return m_nSize;
726}
727
728template <typename T, typename Allocator>
729void list<T, Allocator>::sort()
730{
731 assert(false && !"template method not implemented.");
732}
733
734template <typename T, typename Allocator>
735template <class Compare>
736void list<T, Allocator>::sort(Compare comp)
737{
738 assert(false && !"template method not implemented.");
739}
740
741template <typename T, typename Allocator>
742void list<T, Allocator>::splice(iterator position, list& lst)
743{
744 if (lst.m_nSize == 0)
745 {
746 return;
747 }
748 if (m_nSize == 0)
749 {
750 std::swap(lst.m_pHead, m_pHead);
751 std::swap(lst.m_pTail, m_pTail);
752 std::swap(lst.m_nSize, m_nSize);
753 }
754}
755
756template <typename T, typename Allocator>
757void list<T, Allocator>::splice(iterator position, list& lst, iterator i)
758{
759}
760
761template <typename T, typename Allocator>
762void list<T, Allocator>::splice(iterator position, list& x, iterator first, iterator last)
763{
764}
765
766template <typename T, typename Allocator>
767void list<T, Allocator>::swap(list<T, Allocator>& lst)
768{
769 jitstd::swap(lst.m_pHead, m_pHead);
770 jitstd::swap(lst.m_pTail, m_pTail);
771 jitstd::swap(lst.m_nSize, m_nSize);
772 jitstd::swap(lst.m_allocator, m_allocator);
773 jitstd::swap(lst.m_nodeAllocator, m_nodeAllocator);
774}
775
776template <typename T, typename Allocator>
777void list<T, Allocator>::unique()
778{
779 assert(false && !"template method not implemented.");
780}
781
782template <typename T, typename Allocator>
783template <class BinaryPredicate>
784void list<T, Allocator>::unique(const BinaryPredicate& binary_pred)
785{
786 assert(false && !"template method not implemented.");
787}
788
789// private
790template <typename T, typename Allocator>
791void list<T, Allocator>::destroy_helper()
792{
793 while (m_pTail != nullptr)
794 {
795 Node* prev = m_pTail->m_pPrev;
796 m_pTail->~Node();
797 m_nodeAllocator.deallocate(m_pTail, 1);
798 m_pTail = prev;
799 }
800 m_pHead = nullptr;
801 m_nSize = 0;
802}
803
804
805template <typename T, typename Allocator>
806void list<T, Allocator>::construct_helper(size_type n, const T& value, int_not_an_iterator_tag)
807{
808 for (int i = 0; i < n; ++i)
809 {
810 insert(end(), value);
811 }
812 assert(m_nSize == n);
813}
814
815template <typename T, typename Allocator>
816template <typename InputIterator>
817void list<T, Allocator>::construct_helper(InputIterator first, InputIterator last, forward_iterator_tag)
818{
819 while (first != last)
820 {
821 insert(end(), *first);
822 ++first;
823 }
824}
825
826template <typename T, typename Allocator>
827void list<T, Allocator>::assign_helper(size_type n, const T& value, int_not_an_iterator_tag)
828{
829 destroy_helper();
830 for (int i = 0; i < n; ++i)
831 {
832 insert(end(), value);
833 }
834}
835
836template <typename T, typename Allocator>
837template <typename InputIterator>
838void list<T, Allocator>::assign_helper(InputIterator first, InputIterator last, forward_iterator_tag)
839{
840 destroy_helper();
841 while (first != last)
842 {
843 insert(end(), *first);
844 ++first;
845 }
846}
847
848template <typename T, typename Allocator>
849void list<T, Allocator>::insert_helper(iterator position, size_type n, const T& value, int_not_an_iterator_tag)
850{
851 for (int i = 0; i < n; ++i)
852 {
853 insert(position, value);
854 }
855}
856
857template <typename T, typename Allocator>
858template <typename InputIterator>
859void list<T, Allocator>::insert_helper(iterator position, InputIterator first, InputIterator last, forward_iterator_tag)
860{
861 while (first != last)
862 {
863 insert(position, *first);
864 ++first;
865 }
866}
867
868template <typename T, typename Allocator>
869void list<T, Allocator>::insert_new_node_helper(Node* pInsert, Node* pNewNode)
870{
871 ++m_nSize;
872
873 if (pInsert == nullptr)
874 {
875 pNewNode->m_pPrev = m_pTail;
876 pNewNode->m_pNext = nullptr;
877 if (m_pHead == nullptr)
878 {
879 m_pHead = pNewNode;
880 }
881 else
882 {
883 m_pTail->m_pNext = pNewNode;
884 }
885 m_pTail = pNewNode;
886 }
887 else
888 {
889 pNewNode->m_pPrev = pInsert->m_pPrev;
890 pNewNode->m_pNext = pInsert;
891 if (pInsert->m_pPrev == nullptr)
892 {
893 m_pHead = pNewNode;
894 }
895 else
896 {
897 pInsert->m_pPrev->m_pNext = pNewNode;
898 }
899 pInsert->m_pPrev = pNewNode;
900 }
901}
902
903} // end of namespace jitstd.
904
905
906
907
908
909// Implementation of list iterators
910
911namespace jitstd
912{
913
914// iterator
915template <typename T, typename Allocator>
916list<T, Allocator>::iterator::iterator()
917 : m_pNode(NULL)
918{
919}
920
921template <typename T, typename Allocator>
922list<T, Allocator>::iterator::iterator(Node* pNode)
923 : m_pNode(pNode)
924{
925}
926
927template <typename T, typename Allocator>
928list<T, Allocator>::iterator::iterator(const iterator& it)
929 : m_pNode(it.m_pNode)
930{
931}
932
933
934template <typename T, typename Allocator>
935typename list<T, Allocator>::iterator& list<T, Allocator>::iterator::operator++()
936{
937 m_pNode = m_pNode->m_pNext;
938 return *this;
939}
940
941template <typename T, typename Allocator>
942typename list<T, Allocator>::iterator& list<T, Allocator>::iterator::operator++(int)
943{
944 m_pNode = m_pNode->m_pNext;
945 return *this;
946}
947
948template <typename T, typename Allocator>
949typename list<T, Allocator>::iterator& list<T, Allocator>::iterator::operator--()
950{
951 m_pNode = m_pNode->m_pPrev;
952 return *this;
953}
954
955template <typename T, typename Allocator>
956typename list<T, Allocator>::iterator& list<T, Allocator>::iterator::operator--(int)
957{
958 m_pNode = m_pNode->m_pPrev;
959 return *this;
960}
961
962template <typename T, typename Allocator>
963bool list<T, Allocator>::iterator::operator==(const iterator& it)
964{
965 return (m_pNode == it.m_pNode);
966}
967
968template <typename T, typename Allocator>
969bool list<T, Allocator>::iterator::operator!=(const iterator& it)
970{
971 return !operator==(it);
972}
973
974template <typename T, typename Allocator>
975T& list<T, Allocator>::iterator::operator*()
976{
977 return m_pNode->m_value;
978}
979
980template <typename T, typename Allocator>
981T* list<T, Allocator>::iterator::operator&()
982{
983 return &(m_pNode->m_value);
984}
985
986template <typename T, typename Allocator>
987T* list<T, Allocator>::iterator::operator->()
988{
989 return &(m_pNode->m_value);
990}
991
992template <typename T, typename Allocator>
993list<T, Allocator>::iterator::operator T*()
994{
995 return &(m_pNode->m_value);
996}
997
998
999
1000
1001// const_iterator
1002template <typename T, typename Allocator>
1003list<T, Allocator>::const_iterator::const_iterator()
1004 : m_pNode(NULL)
1005{
1006}
1007
1008template <typename T, typename Allocator>
1009list<T, Allocator>::const_iterator::const_iterator(Node* pNode)
1010 : m_pNode(pNode)
1011{
1012}
1013
1014template <typename T, typename Allocator>
1015list<T, Allocator>::const_iterator::const_iterator(const const_iterator& it)
1016 : m_pNode(it.m_pNode)
1017{
1018}
1019
1020template <typename T, typename Allocator>
1021list<T, Allocator>::const_iterator::const_iterator(const typename list<T, Allocator>::iterator& it)
1022 : m_pNode(it.m_pNode)
1023{
1024}
1025
1026template <typename T, typename Allocator>
1027typename list<T, Allocator>::const_iterator& list<T, Allocator>::const_iterator::operator++()
1028{
1029 m_pNode = m_pNode->m_pNext;
1030 return *this;
1031}
1032
1033template <typename T, typename Allocator>
1034typename list<T, Allocator>::const_iterator& list<T, Allocator>::const_iterator::operator++(int)
1035{
1036 m_pNode = m_pNode->m_pNext;
1037 return *this;
1038}
1039
1040template <typename T, typename Allocator>
1041typename list<T, Allocator>::const_iterator& list<T, Allocator>::const_iterator::operator--()
1042{
1043 m_pNode = m_pNode->m_pPrev;
1044 return *this;
1045}
1046
1047template <typename T, typename Allocator>
1048typename list<T, Allocator>::const_iterator& list<T, Allocator>::const_iterator::operator--(int)
1049{
1050 m_pNode = m_pNode->m_pPrev;
1051 return *this;
1052}
1053
1054template <typename T, typename Allocator>
1055bool list<T, Allocator>::const_iterator::operator==(const const_iterator& it) const
1056{
1057 return (m_pNode == it.m_pNode);
1058}
1059
1060template <typename T, typename Allocator>
1061bool list<T, Allocator>::const_iterator::operator!=(const const_iterator& it) const
1062{
1063 return !operator==(it);
1064}
1065
1066template <typename T, typename Allocator>
1067const T& list<T, Allocator>::const_iterator::operator*() const
1068{
1069 return m_pNode->m_value;
1070}
1071
1072template <typename T, typename Allocator>
1073const T* list<T, Allocator>::const_iterator::operator&() const
1074{
1075 return &(m_pNode->m_value);
1076}
1077
1078template <typename T, typename Allocator>
1079const T* list<T, Allocator>::const_iterator::operator->() const
1080{
1081 return &(m_pNode->m_value);
1082}
1083
1084template <typename T, typename Allocator>
1085list<T, Allocator>::const_iterator::operator const T*() const
1086{
1087 return &(m_pNode->m_value);
1088}
1089
1090
1091// reverse_iterator
1092template <typename T, typename Allocator>
1093list<T, Allocator>::reverse_iterator::reverse_iterator()
1094 : m_pNode(NULL)
1095{
1096}
1097
1098template <typename T, typename Allocator>
1099list<T, Allocator>::reverse_iterator::reverse_iterator(Node* pNode)
1100 : m_pNode(pNode)
1101{
1102}
1103
1104template <typename T, typename Allocator>
1105list<T, Allocator>::reverse_iterator::reverse_iterator(const reverse_iterator& it)
1106 : m_pNode(it.m_pNode)
1107{
1108}
1109
1110
1111template <typename T, typename Allocator>
1112typename list<T, Allocator>::reverse_iterator& list<T, Allocator>::reverse_iterator::operator++()
1113{
1114 m_pNode = m_pNode->m_pPrev;
1115 return *this;
1116}
1117
1118template <typename T, typename Allocator>
1119typename list<T, Allocator>::reverse_iterator& list<T, Allocator>::reverse_iterator::operator++(int)
1120{
1121 m_pNode = m_pNode->m_pPrev;
1122 return *this;
1123}
1124
1125template <typename T, typename Allocator>
1126typename list<T, Allocator>::reverse_iterator& list<T, Allocator>::reverse_iterator::operator--()
1127{
1128 m_pNode = m_pNode->m_pNext;
1129 return *this;
1130}
1131
1132template <typename T, typename Allocator>
1133typename list<T, Allocator>::reverse_iterator& list<T, Allocator>::reverse_iterator::operator--(int)
1134{
1135 m_pNode = m_pNode->m_pNext;
1136 return *this;
1137}
1138
1139template <typename T, typename Allocator>
1140bool list<T, Allocator>::reverse_iterator::operator==(const reverse_iterator& it)
1141{
1142 return (m_pNode == it.m_pNode);
1143}
1144
1145template <typename T, typename Allocator>
1146bool list<T, Allocator>::reverse_iterator::operator!=(const reverse_iterator& it)
1147{
1148 return !operator==(it);
1149}
1150
1151template <typename T, typename Allocator>
1152T& list<T, Allocator>::reverse_iterator::operator*()
1153{
1154 return m_pNode->m_value;
1155}
1156
1157template <typename T, typename Allocator>
1158T* list<T, Allocator>::reverse_iterator::operator&()
1159{
1160 return &(m_pNode->m_value);
1161}
1162
1163template <typename T, typename Allocator>
1164T* list<T, Allocator>::reverse_iterator::operator->()
1165{
1166 return &(m_pNode->m_value);
1167}
1168
1169template <typename T, typename Allocator>
1170list<T, Allocator>::reverse_iterator::operator T*()
1171{
1172 return &(m_pNode->m_value);
1173}
1174
1175// const_reverse_iterator
1176template <typename T, typename Allocator>
1177list<T, Allocator>::const_reverse_iterator::const_reverse_iterator()
1178 : m_pNode(NULL)
1179{
1180}
1181
1182template <typename T, typename Allocator>
1183list<T, Allocator>::const_reverse_iterator::const_reverse_iterator(Node* pNode)
1184 : m_pNode(pNode)
1185{
1186}
1187
1188template <typename T, typename Allocator>
1189list<T, Allocator>::const_reverse_iterator::const_reverse_iterator(const const_reverse_iterator& it)
1190 : m_pNode(it.m_pNode)
1191{
1192}
1193
1194template <typename T, typename Allocator>
1195list<T, Allocator>::const_reverse_iterator::const_reverse_iterator(const reverse_iterator& it)
1196 : m_pNode(it.m_pNode)
1197{
1198}
1199
1200template <typename T, typename Allocator>
1201typename list<T, Allocator>::const_reverse_iterator& list<T, Allocator>::const_reverse_iterator::operator++()
1202{
1203 m_pNode = m_pNode->m_pPrev;
1204 return *this;
1205}
1206
1207template <typename T, typename Allocator>
1208typename list<T, Allocator>::const_reverse_iterator& list<T, Allocator>::const_reverse_iterator::operator++(int)
1209{
1210 m_pNode = m_pNode->m_pPrev;
1211 return *this;
1212}
1213
1214template <typename T, typename Allocator>
1215typename list<T, Allocator>::const_reverse_iterator& list<T, Allocator>::const_reverse_iterator::operator--()
1216{
1217 m_pNode = m_pNode->m_pNext;
1218 return *this;
1219}
1220
1221template <typename T, typename Allocator>
1222typename list<T, Allocator>::const_reverse_iterator& list<T, Allocator>::const_reverse_iterator::operator--(int)
1223{
1224 m_pNode = m_pNode->m_pNext;
1225 return *this;
1226}
1227
1228template <typename T, typename Allocator>
1229bool list<T, Allocator>::const_reverse_iterator::operator==(const const_reverse_iterator& it) const
1230{
1231 return (m_pNode == it.m_pNode);
1232}
1233
1234template <typename T, typename Allocator>
1235bool list<T, Allocator>::const_reverse_iterator::operator!=(const const_reverse_iterator& it) const
1236{
1237 return !operator==(it);
1238}
1239
1240template <typename T, typename Allocator>
1241const T& list<T, Allocator>::const_reverse_iterator::operator*() const
1242{
1243 return m_pNode->m_value;
1244}
1245
1246template <typename T, typename Allocator>
1247const T* list<T, Allocator>::const_reverse_iterator::operator&() const
1248{
1249 return &(m_pNode->m_value);
1250}
1251
1252template <typename T, typename Allocator>
1253const T* list<T, Allocator>::const_reverse_iterator::operator->() const
1254{
1255 return &(m_pNode->m_value);
1256}
1257
1258template <typename T, typename Allocator>
1259list<T, Allocator>::const_reverse_iterator::operator const T*() const
1260{
1261 return &(m_pNode->m_value);
1262}
1263
1264}
1265
1266