1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/common/linkedlist.h	Thu Oct 23 01:46:07 2014 +0300
     1.3 @@ -0,0 +1,229 @@
     1.4 +#ifndef _LINKEDLIST_H_
     1.5 +#define _LINKEDLIST_H_
     1.6 +
     1.7 +template <class T>
     1.8 +struct ListNode {
     1.9 +	T data;
    1.10 +	ListNode<T> *next, *prev;
    1.11 +};
    1.12 +
    1.13 +
    1.14 +template <class T>
    1.15 +class LinkedList {
    1.16 +private:
    1.17 +	ListNode<T> *head, *tail;
    1.18 +	int size;
    1.19 +
    1.20 +public:
    1.21 +
    1.22 +	LinkedList();
    1.23 +	~LinkedList();
    1.24 +
    1.25 +	inline ListNode<T> *Begin();
    1.26 +	inline ListNode<T> *End();
    1.27 +
    1.28 +	void PushBack(ListNode<T> *node);
    1.29 +	void PushBack(T data);
    1.30 +
    1.31 +	void Insert(ListNode<T> *pos, ListNode<T> *node);
    1.32 +	void Insert(ListNode<T> *pos, T data);
    1.33 +
    1.34 +	void Remove(ListNode<T> *node);
    1.35 +	ListNode<T> *Erase(ListNode<T> *node);
    1.36 +
    1.37 +	ListNode<T> *Find(T key);
    1.38 +
    1.39 +	int CountNodes();
    1.40 +	inline int Size() const;
    1.41 +
    1.42 +	void operator =(LinkedList &rhs);
    1.43 +};
    1.44 +
    1.45 +
    1.46 +/////////// implementation //////////
    1.47 +template <class T>
    1.48 +LinkedList<T>::LinkedList() {
    1.49 +	head = tail = 0;
    1.50 +	size = 0;
    1.51 +}
    1.52 +
    1.53 +
    1.54 +template <class T>
    1.55 +LinkedList<T>::~LinkedList() {
    1.56 +
    1.57 +	while(head) {
    1.58 +		Erase(head);
    1.59 +	}
    1.60 +}
    1.61 +
    1.62 +template <class T>
    1.63 +ListNode<T> *LinkedList<T>::Begin() {
    1.64 +	return head;
    1.65 +}
    1.66 +
    1.67 +template <class T>
    1.68 +ListNode<T> *LinkedList<T>::End() {
    1.69 +	return tail;
    1.70 +}
    1.71 +
    1.72 +template <class T>
    1.73 +void LinkedList<T>::PushBack(ListNode<T> *node) {
    1.74 +
    1.75 +	if(!head) {		// empty list
    1.76 +		head = tail = node;
    1.77 +		node->next = node->prev = 0;
    1.78 +	} else {
    1.79 +		tail->next = node;
    1.80 +		node->prev = tail;
    1.81 +		tail = node;
    1.82 +		node->next = 0;
    1.83 +	}
    1.84 +
    1.85 +	size++;
    1.86 +}
    1.87 +
    1.88 +template <class T>
    1.89 +void LinkedList<T>::PushBack(T data) {
    1.90 +
    1.91 +	ListNode<T> *node = new ListNode<T>;
    1.92 +	node->data = data;
    1.93 +
    1.94 +	if(!head) {		// empty list
    1.95 +		head = tail = node;
    1.96 +		node->next = node->prev = 0;
    1.97 +	} else {
    1.98 +		tail->next = node;
    1.99 +		node->prev = tail;
   1.100 +		tail = node;
   1.101 +		node->next = 0;
   1.102 +	}
   1.103 +
   1.104 +	size++;
   1.105 +}
   1.106 +
   1.107 +template <class T>
   1.108 +void LinkedList<T>::Insert(ListNode<T> *pos, ListNode<T> *node) {
   1.109 +
   1.110 +	if(!head) {
   1.111 +		head = tail = node;
   1.112 +		node->next = node->prev = 0;
   1.113 +	} else {
   1.114 +		node->prev = pos->prev;
   1.115 +		pos->prev = node;
   1.116 +		node->next = pos;
   1.117 +		if(head == pos) head = node; else node->prev->next = node;
   1.118 +	}
   1.119 +
   1.120 +	size++;
   1.121 +}
   1.122 +
   1.123 +template <class T>
   1.124 +void LinkedList<T>::Insert(ListNode<T> *pos, T data) {
   1.125 +
   1.126 +	ListNode<T> *node = new ListNode<T>;
   1.127 +	node->data = data;
   1.128 +
   1.129 +	if(!head) {
   1.130 +		head = tail = node;
   1.131 +		node->next = node->prev = 0;
   1.132 +	} else {
   1.133 +		node->prev = pos->prev;
   1.134 +		pos->prev = node;
   1.135 +		node->next = pos;
   1.136 +		if(head == pos) head = node; else node->prev->next = node;
   1.137 +	}
   1.138 +
   1.139 +	size++;
   1.140 +}
   1.141 +
   1.142 +template <class T>
   1.143 +void LinkedList<T>::Remove(ListNode<T> *node) {
   1.144 +
   1.145 +	if(!node) return;	// e.g. Remove(head) on an empty list
   1.146 +
   1.147 +	if(node->prev) {
   1.148 +		node->prev->next = node->next;
   1.149 +	} else {
   1.150 +		head = node->next;
   1.151 +	}
   1.152 +
   1.153 +	if(node->next) {
   1.154 +		node->next->prev = node->prev;
   1.155 +	} else {
   1.156 +		tail = node->prev;
   1.157 +	}
   1.158 +
   1.159 +	size--;
   1.160 +}
   1.161 +
   1.162 +template <class T>
   1.163 +ListNode<T> *LinkedList<T>::Erase(ListNode<T> *node) {
   1.164 +
   1.165 +	if(!node) return 0;	// e.g. Erase(head) on an empty list
   1.166 +
   1.167 +	if(node->prev) {
   1.168 +		node->prev->next = node->next;
   1.169 +	} else {
   1.170 +		head = node->next;
   1.171 +	}
   1.172 +
   1.173 +	if(node->next) {
   1.174 +		node->next->prev = node->prev;
   1.175 +	} else {
   1.176 +		tail = node->prev;
   1.177 +	}
   1.178 +
   1.179 +	ListNode<T> *destr = node;
   1.180 +	node = node->next;
   1.181 +	
   1.182 +	delete destr;
   1.183 +
   1.184 +	size--;
   1.185 +
   1.186 +	return node;
   1.187 +}
   1.188 +
   1.189 +template <class T>
   1.190 +ListNode<T> *LinkedList<T>::Find(T key) {
   1.191 +	
   1.192 +	ListNode<T> *iter = head;
   1.193 +	while(iter) {
   1.194 +		if(iter->data == key) return iter;
   1.195 +		iter = iter->next;
   1.196 +	}
   1.197 +
   1.198 +	return 0;	// null pointer if not found
   1.199 +}
   1.200 +
   1.201 +template <class T>
   1.202 +int LinkedList<T>::CountNodes() {
   1.203 +
   1.204 +	size = 0;
   1.205 +
   1.206 +	ListNode<T> *iter = head;
   1.207 +	while(iter) {
   1.208 +		size++;
   1.209 +		iter = iter->next;
   1.210 +	}
   1.211 +
   1.212 +	return size;
   1.213 +}
   1.214 +
   1.215 +template <class T>
   1.216 +int LinkedList<T>::Size() const {
   1.217 +	return size;
   1.218 +}
   1.219 +
   1.220 +
   1.221 +template <class T>
   1.222 +void LinkedList<T>::operator =(LinkedList<T> &rhs) {
   1.223 +	
   1.224 +	ListNode<T> *src = rhs.Begin();
   1.225 +	while(src) {
   1.226 +		PushBack(src->data);
   1.227 +		src = src->next;
   1.228 +	}
   1.229 +}
   1.230 +
   1.231 +
   1.232 +#endif	// _LINKEDLIST_H_
   1.233 \ No newline at end of file