|
1
|
1 #pragma once
|
|
|
2 #include "ref_counter.h"
|
|
|
3
|
|
|
4 namespace pfc {
|
|
|
5 //! Base class for list nodes. Implemented by list implementers.
|
|
|
6 template<typename t_item> class _list_node : public refcounted_object_root {
|
|
|
7 public:
|
|
|
8 typedef _list_node<t_item> t_self;
|
|
|
9
|
|
|
10 template<typename ... arg_t> _list_node(arg_t && ... arg) : m_content( std::forward<arg_t>(arg) ...) {}
|
|
|
11
|
|
|
12 t_item m_content;
|
|
|
13
|
|
|
14 virtual t_self * prev() throw() {return NULL;}
|
|
|
15 virtual t_self * next() throw() {return NULL;}
|
|
|
16
|
|
|
17 t_self * walk(bool forward) throw() {return forward ? next() : prev();}
|
|
|
18 };
|
|
|
19
|
|
|
20 template<typename t_item> class const_iterator {
|
|
|
21 public:
|
|
|
22 typedef _list_node<t_item> t_node;
|
|
|
23 typedef refcounted_object_ptr_t<t_node> t_nodeptr;
|
|
|
24 typedef const_iterator<t_item> t_self;
|
|
|
25
|
|
|
26 bool is_empty() const throw() {return m_content.is_empty();}
|
|
|
27 bool is_valid() const throw() {return m_content.is_valid();}
|
|
|
28 void invalidate() throw() {m_content = NULL;}
|
|
|
29
|
|
|
30 void walk(bool forward) throw() {m_content = m_content->walk(forward);}
|
|
|
31 void prev() throw() {m_content = m_content->prev();}
|
|
|
32 void next() throw() {m_content = m_content->next();}
|
|
|
33
|
|
|
34 //! For internal use / list implementations only! Do not call!
|
|
|
35 t_node* _node() const throw() {return m_content.get_ptr();}
|
|
|
36
|
|
|
37 const_iterator() {}
|
|
|
38 const_iterator(t_node* source) : m_content(source) {}
|
|
|
39 const_iterator(t_nodeptr const & source) : m_content(source) {}
|
|
|
40 const_iterator(t_self const & other) : m_content(other.m_content) {}
|
|
|
41 const_iterator(t_self && other) : m_content(std::move(other.m_content)) {}
|
|
|
42
|
|
|
43 t_self const & operator=(t_self const & other) {m_content = other.m_content; return *this;}
|
|
|
44 t_self const & operator=(t_self && other) {m_content = std::move(other.m_content); return *this;}
|
|
|
45
|
|
|
46 const t_item& operator*() const throw() {return m_content->m_content;}
|
|
|
47 const t_item* operator->() const throw() {return &m_content->m_content;}
|
|
|
48
|
|
|
49 const t_self & operator++() throw() {this->next(); return *this;}
|
|
|
50 const t_self & operator--() throw() {this->prev(); return *this;}
|
|
|
51 t_self operator++(int) throw() {t_self old = *this; this->next(); return old;}
|
|
|
52 t_self operator--(int) throw() {t_self old = *this; this->prev(); return old;}
|
|
|
53
|
|
|
54 bool operator==(const t_self & other) const throw() {return this->m_content == other.m_content;}
|
|
|
55 bool operator!=(const t_self & other) const throw() {return this->m_content != other.m_content;}
|
|
|
56
|
|
|
57 // Returns pointer to referenced item - null if iterator isn't valid
|
|
|
58 const t_item* get() const noexcept { return this->m_content.is_valid() ? &this->m_content->m_content : nullptr; }
|
|
|
59 protected:
|
|
|
60 t_nodeptr m_content;
|
|
|
61 };
|
|
|
62 template<typename t_item> class iterator : public const_iterator<t_item> {
|
|
|
63 public:
|
|
|
64 typedef const_iterator<t_item> t_selfConst;
|
|
|
65 typedef iterator<t_item> t_self;
|
|
|
66 typedef _list_node<t_item> t_node;
|
|
|
67 typedef refcounted_object_ptr_t<t_node> t_nodeptr;
|
|
|
68
|
|
|
69 iterator() {}
|
|
|
70 iterator(t_node* source) : t_selfConst(source) {}
|
|
|
71 iterator(t_nodeptr const & source) : t_selfConst(source) {}
|
|
|
72 iterator(t_self const & other) : t_selfConst(other) {}
|
|
|
73 iterator(t_self && other) : t_selfConst(std::move(other)) {}
|
|
|
74
|
|
|
75 t_self const & operator=(t_self const & other) {this->m_content = other.m_content; return *this;}
|
|
|
76 t_self const & operator=(t_self && other) {this->m_content = std::move(other.m_content); return *this;}
|
|
|
77
|
|
|
78 t_item& operator*() const throw() {return this->m_content->m_content;}
|
|
|
79 t_item* operator->() const throw() {return &this->m_content->m_content;}
|
|
|
80
|
|
|
81 const t_self & operator++() throw() {this->next(); return *this;}
|
|
|
82 const t_self & operator--() throw() {this->prev(); return *this;}
|
|
|
83 t_self operator++(int) throw() {t_self old = *this; this->next(); return old;}
|
|
|
84 t_self operator--(int) throw() {t_self old = *this; this->prev(); return old;}
|
|
|
85
|
|
|
86 bool operator==(const t_self & other) const throw() {return this->m_content == other.m_content;}
|
|
|
87 bool operator!=(const t_self & other) const throw() {return this->m_content != other.m_content;}
|
|
|
88
|
|
|
89 // Returns pointer to referenced item - null if iterator isn't valid
|
|
|
90 t_item* get() const noexcept { return this->m_content.is_valid() ? &this->m_content->m_content : nullptr; }
|
|
|
91 };
|
|
|
92
|
|
|
93 template<typename item_t> class forward_iterator {
|
|
|
94 iterator<item_t> m_iter;
|
|
|
95 public:
|
|
|
96 typedef forward_iterator<item_t> self_t;
|
|
|
97 void operator++() { ++m_iter; }
|
|
|
98
|
|
|
99 item_t& operator*() const throw() { return *m_iter; }
|
|
|
100 item_t* operator->() const throw() { return &*m_iter; }
|
|
|
101
|
|
|
102 bool operator==(const self_t& other) const { return m_iter == other.m_iter; }
|
|
|
103 bool operator!=(const self_t& other) const { return m_iter != other.m_iter; }
|
|
|
104
|
|
|
105 forward_iterator() {}
|
|
|
106 forward_iterator(iterator<item_t>&& i) : m_iter(std::move(i)) {}
|
|
|
107 };
|
|
|
108
|
|
|
109
|
|
|
110 template<typename item_t> class forward_const_iterator {
|
|
|
111 const_iterator<item_t> m_iter;
|
|
|
112 public:
|
|
|
113 typedef forward_const_iterator<item_t> self_t;
|
|
|
114 void operator++() { ++m_iter; }
|
|
|
115
|
|
|
116 const item_t& operator*() const throw() { return *m_iter; }
|
|
|
117 const item_t* operator->() const throw() { return &*m_iter; }
|
|
|
118
|
|
|
119 bool operator==(const self_t& other) const { return m_iter == other.m_iter; }
|
|
|
120 bool operator!=(const self_t& other) const { return m_iter != other.m_iter; }
|
|
|
121
|
|
|
122 forward_const_iterator() {}
|
|
|
123 forward_const_iterator(const_iterator<item_t>&& i) : m_iter(std::move(i)) {}
|
|
|
124 };
|
|
|
125
|
|
|
126 template<typename t_comparator = comparator_default>
|
|
|
127 class comparator_list {
|
|
|
128 public:
|
|
|
129 template<typename t_list1, typename t_list2>
|
|
|
130 static int compare(const t_list1 & p_list1, const t_list2 & p_list2) {
|
|
|
131 typename t_list1::const_iterator iter1 = p_list1.first();
|
|
|
132 typename t_list2::const_iterator iter2 = p_list2.first();
|
|
|
133 for(;;) {
|
|
|
134 if (iter1.is_empty() && iter2.is_empty()) return 0;
|
|
|
135 else if (iter1.is_empty()) return -1;
|
|
|
136 else if (iter2.is_empty()) return 1;
|
|
|
137 else {
|
|
|
138 int state = t_comparator::compare(*iter1,*iter2);
|
|
|
139 if (state != 0) return state;
|
|
|
140 }
|
|
|
141 ++iter1; ++iter2;
|
|
|
142 }
|
|
|
143 }
|
|
|
144 };
|
|
|
145
|
|
|
146 template<typename t_list1, typename t_list2>
|
|
|
147 static bool listEquals(const t_list1 & p_list1, const t_list2 & p_list2) {
|
|
|
148 typename t_list1::const_iterator iter1 = p_list1.first();
|
|
|
149 typename t_list2::const_iterator iter2 = p_list2.first();
|
|
|
150 for(;;) {
|
|
|
151 if (iter1.is_empty() && iter2.is_empty()) return true;
|
|
|
152 else if (iter1.is_empty() || iter2.is_empty()) return false;
|
|
|
153 else if (*iter1 != *iter2) return false;
|
|
|
154 ++iter1; ++iter2;
|
|
|
155 }
|
|
|
156 }
|
|
|
157
|
|
|
158 template<typename comparator_t = comparator_default>
|
|
|
159 class comparator_stdlist {
|
|
|
160 public:
|
|
|
161 template<typename t_list1, typename t_list2>
|
|
|
162 static int compare(const t_list1 & p_list1, const t_list2 & p_list2) {
|
|
|
163 auto iter1 = p_list1.begin();
|
|
|
164 auto iter2 = p_list2.begin();
|
|
|
165 for(;;) {
|
|
|
166 const bool end1 = iter1 == p_list1.end();
|
|
|
167 const bool end2 = iter2 == p_list2.end();
|
|
|
168 if ( end1 && end2 ) return 0;
|
|
|
169 else if ( end1 ) return -1;
|
|
|
170 else if ( end2 ) return 1;
|
|
|
171 else {
|
|
|
172 int state = comparator_t::compare(*iter1,*iter2);
|
|
|
173 if (state != 0) return state;
|
|
|
174 }
|
|
|
175 ++iter1; ++iter2;
|
|
|
176 }
|
|
|
177 }
|
|
|
178 };
|
|
|
179 }
|
|
|
180
|
|
|
181 namespace std {
|
|
|
182
|
|
|
183 template<typename item_t>
|
|
|
184 struct iterator_traits< pfc::forward_iterator< item_t > > {
|
|
|
185 typedef ptrdiff_t difference_type;
|
|
|
186 typedef item_t value_type;
|
|
|
187 typedef value_type* pointer;
|
|
|
188 typedef value_type& reference;
|
|
|
189 typedef std::forward_iterator_tag iterator_category;
|
|
|
190 };
|
|
|
191 template<typename item_t>
|
|
|
192 struct iterator_traits< pfc::forward_const_iterator< item_t > > {
|
|
|
193 typedef ptrdiff_t difference_type;
|
|
|
194 typedef item_t value_type;
|
|
|
195 typedef const value_type* pointer;
|
|
|
196 typedef const value_type& reference;
|
|
|
197 typedef std::forward_iterator_tag iterator_category;
|
|
|
198 };
|
|
|
199 } |
