Subversion Repositories spk

Rev

Rev 1 | Details | Compare with Previous | Last modification | View Log | RSS feed

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