Subversion Repositories spk

Rev

Rev 1 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 1 Rev 114
Line 4... Line 4...
4 
 *
 4 
 *
5 
 ****************************************/
 5 
 ****************************************/
6 
 
 6 
 
7 
#ifndef EXT_LIST_INCLUDED
 7 
#ifndef EXT_LIST_INCLUDED
8 
#define EXT_LIST_INCLUDED
 8 
#define EXT_LIST_INCLUDED
- 
 
 9 
 
- 
 
 10 
#include <stddef.h>
9 
 
 11 
 
10 
namespace ext
 12 
namespace ext
11 
{
 13 
{
12 
 
 14 
 
13 
template <class T> class list
 15 
template <class T> class list
Line 15... Line 17...
15 
	public:
 17 
	public:
16 
		typedef T value_type;
 18 
		typedef T value_type;
17 
		typedef size_t size_type;
 19 
		typedef size_t size_type;
18 
		typedef T& reference;
 20 
		typedef T& reference;
19 
		typedef const T& const_reference;
 21 
		typedef const T& const_reference;
20
22 
 
21 
	private:
 23 
	private:
22 
		class node
 24 
		class node
23 
		{
 25 
		{
24 
			public:
 26 
			public:
25 
				node *prev, *next;
 27 
				node *prev, *next;
26 
				value_type val;
 28 
				value_type val;
27 
		};
 29 
		};
28
30 
 
29 
	public:
 31 
	public:
30 
		class const_iterator
 32 
		class const_iterator
31 
		{
 33 
		{
32 
			private:
 34 
			private:
33 
				node *_mynode;
 35 
				node *_mynode;
34
36 
 
35 
			public:
 37 
			public:
36 
				node* mynode() const { return _mynode; }
38 
				node* mynode() const { return _mynode; }
37
39 
 
38 
				const_iterator() { _mynode=0; }
 40 
				const_iterator() { _mynode=0; }
39 
				const_iterator(node* n) { _mynode=n; }
 41 
				const_iterator(node* n) { _mynode=n; }
40
42 
 
41 
				const_reference operator *() const { return _mynode->val; }
 43 
				const_reference operator *() const { return _mynode->val; }
42 
				const_reference operator ->() const { return _mynode->val; }
 44 
				const_reference operator ->() const { return _mynode->val; }
43
45 
 
44 
				bool operator ==(const const_iterator &right) const { return _mynode==right.mynode(); }
 46 
				bool operator ==(const const_iterator &right) const { return _mynode==right.mynode(); }
45 
				bool operator !=(const const_iterator &right) const { return _mynode!=right.mynode(); }
 47 
				bool operator !=(const const_iterator &right) const { return _mynode!=right.mynode(); }
46
48 
 
47 
				const_iterator operator++(int) { _mynode=_mynode->next; return const_iterator(_mynode->prev); }
 49 
				const_iterator operator++(int) { _mynode=_mynode->next; return const_iterator(_mynode->prev); }
48 
				const_iterator& operator++() { _mynode=_mynode->next; return *this; }
 50 
				const_iterator& operator++() { _mynode=_mynode->next; return *this; }
49
51 
 
50 
				const_iterator operator--(int) { _mynode=_mynode->prev; return const_iterator(_mynode->next); }
 52 
				const_iterator operator--(int) { _mynode=_mynode->prev; return const_iterator(_mynode->next); }
51 
				const_iterator& operator--() { _mynode=_mynode->prev; return *this; }
 53 
				const_iterator& operator--() { _mynode=_mynode->prev; return *this; }
52
54 
 
53 
				const_iterator operator+(int offset)
55 
				const_iterator operator+(int offset)
54 
				{
56 
				{
55 
					const_iterator it(mynode());
 57 
					const_iterator it(mynode());
56 
					for(int i=0; i < offset; ++i, ++it)
 58 
					for(int i=0; i < offset; ++i, ++it)
57 
						;
 59 
						;
58 
					return it;
 60 
					return it;
59 
				}
 61 
				}
60
62 
 
61 
				const_iterator operator-(int offset)
63 
				const_iterator operator-(int offset)
62 
				{
64 
				{
63 
					const_iterator it(mynode());
 65 
					const_iterator it(mynode());
64 
					for(int i=offset; i > 0; --i, --it)
 66 
					for(int i=offset; i > 0; --i, --it)
65 
						;
 67 
						;
66 
					return it;
 68 
					return it;
67 
				}
 69 
				}
68 
		};
 70 
		};
69
71 
 
70 
		class iterator : public const_iterator
72 
		class iterator : public const_iterator
71 
		{
 73 
		{
72 
			public:
74 
			public:
- 
 
 75 
				typedef const_iterator base;
- 
 
 76 
 
73 
				iterator() { }
 77 
				iterator() { }
74 
				iterator(node* n) : const_iterator(n) { }
 78 
				iterator(node* n) : const_iterator(n) { }
75
79 
 
76 
				reference operator *() { return mynode()->val; }
 80 
				reference operator *() { return base::mynode()->val; }
77 
				reference operator ->() { return mynode()->val; }
 81 
				reference operator ->() { return base::mynode()->val; }
78
82 
 
79 
				bool operator ==(const iterator &right) const { return mynode()==right.mynode(); }
 83 
				bool operator ==(const iterator &right) const { return base::mynode()==right.base::mynode(); }
80 
				bool operator !=(const iterator &right) const { return mynode()!=right.mynode(); }
 84 
				bool operator !=(const iterator &right) const { return base::mynode()!=right.base::mynode(); }
81
85 
 
82 
				iterator operator++(int) { iterator tmp=*this; ++*this; return tmp; }
 86 
				iterator operator++(int) { iterator tmp=*this; ++*this; return tmp; }
83 
				iterator& operator++() { ++(*(const_iterator*)this); return *this; }
 87 
				iterator& operator++() { ++(*(const_iterator*)this); return *this; }
84
88 
 
85 
				iterator operator--(int) { iterator tmp=*this; --*this; return tmp; }
 89 
				iterator operator--(int) { iterator tmp=*this; --*this; return tmp; }
86 
				iterator& operator--() { --(*(const_iterator*)this); return *this; }
 90 
				iterator& operator--() { --(*(const_iterator*)this); return *this; }
87
91 
 
88 
				iterator operator+(int offset)
92 
				iterator operator+(int offset)
89 
				{
93 
				{
90 
					iterator it(mynode());
 94 
					iterator it(base::mynode());
91 
					for(int i=0; i < offset; ++i, ++it);
 95 
					for(int i=0; i < offset; ++i, ++it);
92 
					return it;
 96 
					return it;
93 
				}
 97 
				}
94
98 
 
95 
				iterator operator-(int offset)
99 
				iterator operator-(int offset)
96 
				{
100 
				{
97 
					iterator it(mynode());
 101 
					iterator it(base::mynode());
98 
					for(int i=offset; i > 0; --i, --it)
 102 
					for(int i=offset; i > 0; --i, --it)
99 
						;
 103 
						;
100 
					return it;
 104 
					return it;
101 
				}
 105 
				}
102
106 
 
103 
		};
 107 
		};
104
108 
 
105 
		class const_reverse_iterator
 109 
		class const_reverse_iterator
106 
		{
 110 
		{
107 
			private:
 111 
			private:
108 
				node *_mynode;
 112 
				node *_mynode;
109
113 
 
110 
			public:
 114 
			public:
111 
				node* mynode() const { return _mynode; }
115 
				node* mynode() const { return _mynode; }
112
116 
 
113 
				const_reverse_iterator() { _mynode=0; }
 117 
				const_reverse_iterator() { _mynode=0; }
114 
				const_reverse_iterator(node* n) { _mynode=n; }
 118 
				const_reverse_iterator(node* n) { _mynode=n; }
115
119 
 
116 
				const_reference operator *() const { return _mynode->val; }
 120 
				const_reference operator *() const { return _mynode->val; }
117 
				const_reference operator ->() const { return _mynode->val; }
 121 
				const_reference operator ->() const { return _mynode->val; }
118
122 
 
119 
				bool operator ==(const const_reverse_iterator &right) const { return _mynode==right.mynode(); }
 123 
				bool operator ==(const const_reverse_iterator &right) const { return _mynode==right.mynode(); }
120 
				bool operator !=(const const_reverse_iterator &right) const { return _mynode!=right.mynode(); }
 124 
				bool operator !=(const const_reverse_iterator &right) const { return _mynode!=right.mynode(); }
121
125 
 
122 
				const_reverse_iterator operator++(int) { _mynode=_mynode->prev; return const_reverse_iterator(_mynode->next); }
 126 
				const_reverse_iterator operator++(int) { _mynode=_mynode->prev; return const_reverse_iterator(_mynode->next); }
123 
				const_reverse_iterator& operator++() { _mynode=_mynode->prev; return *this; }
 127 
				const_reverse_iterator& operator++() { _mynode=_mynode->prev; return *this; }
124
128 
 
125 
				const_reverse_iterator operator--(int) { _mynode=_mynode->next; return const_reverse_iterator(_mynode->prev); }
 129 
				const_reverse_iterator operator--(int) { _mynode=_mynode->next; return const_reverse_iterator(_mynode->prev); }
126 
				const_reverse_iterator& operator--() { _mynode=_mynode->next; return *this; }
 130 
				const_reverse_iterator& operator--() { _mynode=_mynode->next; return *this; }
127
131 
 
128 
				const_reverse_iterator operator+(int offset)
132 
				const_reverse_iterator operator+(int offset)
129 
				{
133 
				{
130 
					const_reverse_iterator it(mynode());
 134 
					const_reverse_iterator it(mynode());
131 
					for(int i=0; i < offset; ++i, ++it)
 135 
					for(int i=0; i < offset; ++i, ++it)
132 
						;;
 136 
						;;
133 
					return it;
 137 
					return it;
134 
				}
 138 
				}
135
139 
 
136 
				const_reverse_iterator operator-(int offset)
140 
				const_reverse_iterator operator-(int offset)
137 
				{
141 
				{
138 
					const_reverse_iterator it(mynode());
 142 
					const_reverse_iterator it(mynode());
139 
					for(int i=offset; i > 0; --i, --it)
 143 
					for(int i=offset; i > 0; --i, --it)
140 
						;;
 144 
						;;
141 
					return it;
 145 
					return it;
142 
				}
 146 
				}
143 
		};
 147 
		};
144
148 
 
145 
		class reverse_iterator : public const_reverse_iterator
149 
		class reverse_iterator : public const_reverse_iterator
146 
		{
 150 
		{
147 
			public:
151 
			public:
- 
 
 152 
				typedef const_reverse_iterator base;
- 
 
 153 
 
148 
				reverse_iterator() { }
 154 
				reverse_iterator() { }
149 
				reverse_iterator(node* n) : const_reverse_iterator(n) { }
 155 
				reverse_iterator(node* n) : const_reverse_iterator(n) { }
150
156 
 
151 
				reference operator *() { return mynode()->val; }
 157 
				reference operator *() { return base::mynode()->val; }
152 
				reference operator ->() { return mynode()->val; }
 158 
				reference operator ->() { return base::mynode()->val; }
153
159 
 
154 
				bool operator ==(const reverse_iterator &right) const { return mynode()==right.mynode(); }
 160 
				bool operator ==(const reverse_iterator &right) const { return base::mynode()==right.base::mynode(); }
155 
				bool operator !=(const reverse_iterator &right) const { return mynode()!=right.mynode(); }
 161 
				bool operator !=(const reverse_iterator &right) const { return base::mynode()!=right.base::mynode(); }
156
162 
 
157 
				reverse_iterator operator++(int) { reverse_iterator tmp=*this; ++*this; return tmp; }
 163 
				reverse_iterator operator++(int) { reverse_iterator tmp=*this; ++*this; return tmp; }
158 
				reverse_iterator& operator++() { ++(*(const_reverse_iterator*)this); return *this; }
 164 
				reverse_iterator& operator++() { ++(*(const_reverse_iterator*)this); return *this; }
159
165 
 
160 
				reverse_iterator operator--(int) { reverse_iterator tmp=*this; --*this; return tmp; }
 166 
				reverse_iterator operator--(int) { reverse_iterator tmp=*this; --*this; return tmp; }
161 
				reverse_iterator& operator--() { --(*(const_reverse_iterator*)this); return *this; }
 167 
				reverse_iterator& operator--() { --(*(const_reverse_iterator*)this); return *this; }
162
168 
 
163 
				reverse_iterator operator+(int offset)
169 
				reverse_iterator operator+(int offset)
164 
				{
170 
				{
165 
					reverse_iterator it(mynode());
 171 
					reverse_iterator it(base::mynode());
166 
					for(int i=0; i < offset; ++i, ++it)
 172 
					for(int i=0; i < offset; ++i, ++it)
167 
						;;
 173 
						;;
168 
					return it;
 174 
					return it;
169 
				}
 175 
				}
170
176 
 
171 
				iterator operator-(int offset)
177 
				iterator operator-(int offset)
172 
				{
178 
				{
173 
					reverse_iterator it(mynode());
 179 
					reverse_iterator it(base::mynode());
174 
					for(int i=offset; i > 0; --i, --it)
 180 
					for(int i=offset; i > 0; --i, --it)
175 
						;;
 181 
						;;
176 
					return it;
 182 
					return it;
177 
				}
 183 
				}
178 
		};
 184 
		};
179
185 
 
180 
	private:
 186 
	private:
181 
		node *myhead;
 187 
		node *myhead;
182 
		size_type count;
 188 
		size_type count;
183
189 
 
184 
		static node* nextnode(node *n) { return n->next; }
 190 
		static node* nextnode(node *n) { return n->next; }
185 
		static node* prevnode(node *n) { return n->prev; }
 191 
		static node* prevnode(node *n) { return n->prev; }
186 
		static reference nodeval(node *n) { return n->val; }
 192 
		static reference nodeval(node *n) { return n->val; }
187
193 
 
188 
		void _insert(iterator& where, value_type val)
 194 
		void _insert(iterator where, const_reference val)
189 
		{
 195 
		{
190 
			node *newnode=new node(), *nodeptr=where.mynode();
 196 
			node *newnode=new node(), *nodeptr=where.mynode();
191 
			newnode->prev=nodeptr->prev;
 197 
			newnode->prev=nodeptr->prev;
192 
			newnode->next=nodeptr;
 198 
			newnode->next=nodeptr;
193 
			newnode->prev->next=newnode;
 199 
			newnode->prev->next=newnode;
194 
			nodeptr->prev=newnode;
 200 
			nodeptr->prev=newnode;
195
201 
 
196 
			newnode->val=val;
 202 
			newnode->val=val;
197 
			count++;
 203 
			count++;
198 
		}
 204 
		}
199
205 
 
200 
	public:
 206 
	public:
201 
		list()
207 
		list()
202 
		{
208 
		{
203 
			myhead=new node();
 209 
			myhead=new node();
204 
			myhead->next=myhead;
 210 
			myhead->next=myhead;
205 
			myhead->prev=myhead;
 211 
			myhead->prev=myhead;
206 
			count=0;
 212 
			count=0;
207 
		}
 213 
		}
208
214 
 
209 
		list(const list& other)
 215 
		list(const list& other)
210 
		{
216 
		{
211 
			myhead=new node();
 217 
			myhead=new node();
212 
			myhead->next=myhead;
 218 
			myhead->next=myhead;
213 
			myhead->prev=myhead;
 219 
			myhead->prev=myhead;
214 
			count=0;
 220 
			count=0;
215
221 
 
216 
			insert(end(), other.begin(), other.end());
 222 
			insert(end(), other.begin(), other.end());
217 
		}
 223 
		}
218
224 
 
219 
		~list()
 225 
		virtual ~list()
220 
		{
 226 
		{
221 
			clear();
 227 
			clear();
222 
			delete myhead;
 228 
			delete myhead;
223 
		}
 229 
		}
224
230 
 
225 
		void clear()
 231 
		void clear()
226 
		{
 232 
		{
227 
			node *n, *d;
 233 
			node *n, *d;
228 
			n=d=nextnode(myhead);
 234 
			n=d=nextnode(myhead);
229 
			for( ; n!=myhead; d=n){
 235 
			for( ; n!=myhead; d=n){
Line 232... Line 238...
232 
			}
 238 
			}
233 
			myhead->next=myhead;
 239 
			myhead->next=myhead;
234 
			myhead->prev=myhead;
 240 
			myhead->prev=myhead;
235 
			count=0;
 241 
			count=0;
236 
		}
 242 
		}
237
243 
 
238 
		size_type size() const { return count; }
 244 
		size_type size() const { return count; }
239
245 
 
240 
		iterator begin() { return iterator(nextnode(myhead)); }
 246 
		iterator begin() { return iterator(nextnode(myhead)); }
241 
		iterator end() { return iterator(myhead); }
 247 
		iterator end() { return iterator(myhead); }
242
248 
 
243 
		const_iterator begin() const { return iterator(nextnode(myhead)); }
 249 
		const_iterator begin() const { return iterator(nextnode(myhead)); }
244 
		const_iterator end() const { return iterator(myhead); }
 250 
		const_iterator end() const { return iterator(myhead); }
245
251 
 
246 
		reverse_iterator rbegin() { return reverse_iterator(prevnode(myhead)); }
 252 
		reverse_iterator rbegin() { return reverse_iterator(prevnode(myhead)); }
247 
		reverse_iterator rend() { return reverse_iterator(myhead); }
 253 
		reverse_iterator rend() { return reverse_iterator(myhead); }
248
254 
 
249 
		const_reverse_iterator rbegin() const { return reverse_iterator(prevnode(myhead)); }
 255 
		const_reverse_iterator rbegin() const { return reverse_iterator(prevnode(myhead)); }
250 
		const_reverse_iterator rend() const { return reverse_iterator(myhead); }
 256 
		const_reverse_iterator rend() const { return reverse_iterator(myhead); }
251
257 
 
252 
		iterator insert(iterator where, const_reference val)
 258 
		iterator insert(iterator where, const_reference val)
253 
		{
 259 
		{
254 
			_insert(where, val);
 260 
			_insert(where, val);
255 
			return --where;
 261 
			return --where;
256 
		}
 262 
		}
257
263 
 
258 
		void insert(iterator where, const_iterator first, const_iterator last)
 264 
		void insert(iterator where, const_iterator first, const_iterator last)
259 
		{
 265 
		{
260 
			for(; first!=last; ++first){
 266 
			for(; first!=last; ++first){
261 
				_insert(where, *first);
 267 
				_insert(where, *first);
262 
			}
 268 
			}
263 
		}
 269 
		}
264
270 
 
265 
		iterator erase(iterator& where)
 271 
		iterator erase(iterator where)
266 
		{
 272 
		{
267 
			node *delnode=(where++).mynode();
 273 
			node *delnode=(where++).mynode();
268 
			if(delnode!=myhead){
 274 
			if(delnode!=myhead){
269 
				delnode->prev->next=delnode->next;
 275 
				delnode->prev->next=delnode->next;
270 
				delnode->next->prev=delnode->prev;
 276 
				delnode->next->prev=delnode->prev;
271 
				delete delnode;
 277 
				delete delnode;
272 
				count--;
 278 
				count--;
273 
			}
 279 
			}
274 
			return where;
 280 
			return where;
275 
		}
 281 
		}
276
282 
 
277 
		iterator erase(iterator& first, iterator& last)
 283 
		iterator erase(iterator first, iterator last)
278 
		{
 284 
		{
279 
			if(first==begin() && last==end())
 285 
			if(first==begin() && last==end())
280 
				clear();
 286 
				clear();
281 
			else{
 287 
			else{
282 
				while(first!=last)
 288 
				while(first!=last)
283 
					first=erase(first);
 289 
					first=erase(first);
284 
			}
 290 
			}
285 
			return last;
 291 
			return last;
286 
		}
 292 
		}
287
293 
 
288 
		iterator push_front(const_reference val)
 294 
		iterator push_front(const_reference val)
289 
		{
 295 
		{
290 
			_insert(begin(), val);
 296 
			_insert(begin(), val);
291 
			return begin();
 297 
			return begin();
292 
		}
 298 
		}
293
299 
 
294 
		iterator push_back(const_reference val)
 300 
		iterator push_back(const_reference val)
295 
		{
 301 
		{
296 
			_insert(end(), val);
 302 
			_insert(end(), val);
297 
			return --end();
 303 
			return --end();
298 
		}
 304 
		}
299
305 
 
300 
		bool empty() const { return size()==0; }
 306 
		bool empty() const { return size()==0; }
301
307 
 
302 
		void pop_front() { erase(begin()); }
 308 
		void pop_front() { erase(begin()); }
303 
		void pop_back() { erase(--end()); }
 309 
		void pop_back() { erase(--end()); }
304
310 
 
305 
		const_reference front() const { return nodeval(myhead); }
 311 
		const_reference front() const { return nodeval(myhead); }
306 
		reference front() { return nodeval(myhead->next); }
 312 
		reference front() { return nodeval(myhead->next); }
307
313 
 
308 
		const_reference back() const { return nodeval(myhead->prev); }
 314 
		const_reference back() const { return nodeval(myhead->prev); }
309 
		reference back() { return nodeval(myhead->prev); }
 315 
		reference back() { return nodeval(myhead->prev); }
310
316 
 
311 
		iterator find(const_reference val)
 317 
		iterator find(const_reference val)
312 
		{
 318 
		{
313 
			for(iterator &it=begin(); it!=end(); ++it){
 319 
			for(iterator it=begin(); it!=end(); ++it){
314 
				if(*it==val)
 320 
				if(*it==val)
315 
					break;
 321 
					return it;
316 
			}
 322 
			}
317 
			return it;
 323 
			return end();
318 
		}
 324 
		}
319
325 
 
320 
		void remove(const_reference val)
 326 
		void remove(const_reference val)
321 
		{
 327 
		{
322 
			iterator old;
 328 
			iterator old;
323 
			for(iterator &it=begin(); it!=end(); ++it){
 329 
			for(iterator &it=begin(); it!=end(); ++it){
324 
				if(*it==val){
 330 
				if(*it==val){