Subversion Repositories Kolibri OS

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
4680 right-hear 1 
#ifndef _LIST_INCLUDED
2 
#define _LIST_INCLUDED
3 
#include
4 
namespace std
5 
{
6 
	struct __list_node_base
7 
	{
8 
		__list_node_base* prev;
9 
		__list_node_base* next;
10 
	};
11 
	template  struct __list_node : __list_node_base
12 
	{
13 
		T data;
14 
		__list_node(const T& d):data(d){}
15 
	};
16 
	template  class list
17 
	{
18 
		__list_node_base head;	// head.prev = end, head.next = start
19 
		unsigned _size;
20 
	public:
21 
		list():_size(0) {head.prev=head.next=&head;}
22 
		~list()	{clear();}
23 
		void clear()
24 
		{
25 
			__list_node* a =
26 
				static_cast<__list_node*>(head.next);
27 
			while (a!=&head)
28 
			{
29 
				__list_node* b =
30 
					static_cast<__list_node*>(a->next);
31 
				delete a;
32 
				a = b;
33 
			}
34 
			head.prev = head.next = &head;
35 
			_size = 0;
36 
		}
37 
		class iterator
38 
		{
39 
		public:
40 
			__list_node_base* cur;
41 
			friend class list;
42 
			iterator(){}
43 
			iterator(__list_node_base*c):cur(c){}
44 
			iterator(const iterator& it):cur(it.cur){}
45 
			iterator& operator++()
46 
			{cur=cur->next;return *this;}
47 
			iterator operator++(int)
48 
			{iterator tmp(*this);cur=cur->next;return tmp;}
49 
			iterator& operator--()
50 
			{cur=cur->prev;return *this;}
51 
			iterator operator--(int)
52 
			{iterator tmp(*this);cur=cur->prev;return tmp;}
53 
			bool operator!=(const iterator& it)
54 
			{return cur!=it.cur;}
55 
			bool operator==(const iterator& it)
56 
			{return cur==it.cur;}
57 
			T& operator*()
58 
			{return static_cast<__list_node*>(cur)->data;}
59 
			T* operator->() {return &**this;}
60 
		};
61 
		class const_iterator
62 
		{
63 
			const __list_node_base* cur;
64 
			friend class list;
65 
		public:
66 
			const_iterator(){}
67 
			const_iterator(const __list_node_base*c):cur(c){}
68 
			const_iterator(const const_iterator& it):cur(it.cur){}
69 
			const_iterator(const iterator& it):cur(it.cur){}
70 
			const_iterator& operator++()
71 
			{cur=cur->next;return *this;}
72 
			const_iterator operator++(int)
73 
			{const_iterator tmp(*this);cur=cur->next;return tmp;}
74 
			const_iterator& operator--()
75 
			{cur=cur->prev;return *this;}
76 
			const_iterator operator--(int)
77 
			{const_iterator tmp(*this);cur=cur->prev;return tmp;}
78 
			bool operator!=(const const_iterator& it)
79 
			{return cur!=it.cur;}
80 
			bool operator==(const const_iterator& it)
81 
			{return cur==it.cur;}
82 
			const T& operator*()
83 
			{return static_cast*>(cur)->data;}
84 
			const T* operator->() {return &**this;}
85 
		};
86 
		iterator erase(iterator it)
87 
		{
88 
			if (it==end()) return it;
89 
			it.cur->prev->next = it.cur->next;
90 
			it.cur->next->prev = it.cur->prev;
91 
			iterator res(it.cur->next);
92 
			delete static_cast<__list_node*>(it.cur);
93 
			--_size;
94 
			return res;
95 
		}
96 
		iterator erase(iterator first, iterator last)
97 
		{
98 
			while (first!=last)
99 
				first=erase(first);
100 
			return first;
101 
		}
102 
		void pop_front(void) {erase(begin());}
103 
		class reverse_iterator
104 
		{
105 
			__list_node_base* cur;
106 
			friend class list;
107 
		public:
108 
			reverse_iterator(){}
109 
			reverse_iterator(__list_node_base*c):cur(c){}
110 
			reverse_iterator(const reverse_iterator& it):
111 
			  cur(it.cur){}
112 
			reverse_iterator& operator++()
113 
			{cur=cur->prev;return *this;}
114 
			reverse_iterator operator++(int)
115 
			{reverse_iterator tmp(*this);
116 
			cur=cur->prev;return tmp;}
117 
			bool operator!=(const reverse_iterator& it)
118 
			{return cur!=it.cur;}
119 
			bool operator==(const reverse_iterator& it)
120 
			{return cur==it.cur;}
121 
			T& operator*()
122 
			{return static_cast<__list_node*>(cur)->data;}
123 
		};
124 
		class const_reverse_iterator
125 
		{
126 
			const __list_node_base* cur;
127 
			friend class list;
128 
		public:
129 
			const_reverse_iterator(){}
130 
			const_reverse_iterator(const __list_node_base*c):cur(c){}
131 
			const_reverse_iterator(const const_reverse_iterator& it):
132 
			  cur(it.cur){}
133 
			const_reverse_iterator& operator++()
134 
			{cur=cur->prev;return *this;}
135 
			const_reverse_iterator operator++(int)
136 
			{const_reverse_iterator tmp(*this);
137 
			cur=cur->prev;return tmp;}
138 
			bool operator!=(const const_reverse_iterator& it)
139 
			{return cur!=it.cur;}
140 
			bool operator==(const const_reverse_iterator& it)
141 
			{return cur==it.cur;}
142 
			const T& operator*()
143 
			{return static_cast<__list_node*>(cur)->data;}
144 
		};
145 
		void push_front(const T& x)
146 
		{
147 
			__list_node* a = new __list_node(x);
148 
			a->next = head.next;
149 
			a->prev = &head;
150 
			head.next = a;
151 
			a->next->prev = a;
152 
			++_size;
153 
		}
154 
		void push_back(const T& x)
155 
		{
156 
			__list_node* a = new __list_node(x);
157 
			a->next = &head;
158 
			a->prev = head.prev;
159 
			head.prev = a;
160 
			a->prev->next = a;
161 
			++_size;
162 
		}
163 
		iterator begin() {return iterator(head.next);}
164 
		const_iterator begin() const {return const_iterator(head.next);}
165 
		iterator end() {return iterator(&head);}
166 
		const_iterator end() const {return const_iterator(&head);}
167 
		reverse_iterator rbegin()
168 
		{return reverse_iterator(head.prev);}
169 
		reverse_iterator rend() {return reverse_iterator(&head);}
170 
		void remove(const T& x)
171 
		{
172 
			__list_node* a =
173 
				static_cast<__list_node*>(head.next);
174 
			while (a!=&head)
175 
			{
176 
				__list_node* b =
177 
					static_cast<__list_node*>(a->next);
178 
				if (a->data==x)
179 
				{
180 
					a->prev->next = a->next;
181 
					a->next->prev = a->prev;
182 
				        delete a;
183 
				        --_size;
184 
				}
185 
				a=b;
186 
			}
187 
		}
188 
		unsigned size() const {return _size;}
189 
		bool empty() const {return _size==0;}
190 
	};
191 
}
192 
#endif