sourcehook/sh_list.h
author Pavol Marko <pavolmarko@gmail.com>
Sun Oct 07 22:45:22 2007 +0000 (2007-10-07)
changeset 384 264cab8ff2cc
parent 380 f9e21a2ac558
child 435 35296642e147
permissions -rw-r--r--
correct version now... i guess i'm just tired :)
     1 /* ======== SourceMM ========
     2 * Copyright (C) 2004-2007 Metamod:Source Development Team
     3 * No warranties of any kind
     4 *
     5 * License: zlib/libpng
     6 *
     7 * Author(s): David "BAILOPAN" Anderson
     8 * ============================
     9 */
    10 
    11 #ifndef _INCLUDE_SMM_LIST_H
    12 #define _INCLUDE_SMM_LIST_H
    13 
    14 #include <new>
    15 #include <malloc.h>
    16 
    17 namespace SourceHook
    18 {
    19 
    20 	//This class is from CSDM for AMX Mod X
    21 	/*
    22 		A circular, doubly-linked list with one sentinel node
    23 
    24 		Empty:
    25 			m_Head = sentinel
    26 			m_Head->next = m_Head;
    27 			m_Head->prev = m_Head;
    28 		One element:
    29 			m_Head = sentinel
    30 			m_Head->next = node1
    31 			m_Head->prev = node1
    32 			node1->next = m_Head
    33 			node1->prev = m_Head
    34 		Two elements:
    35 			m_Head = sentinel
    36 			m_Head->next = node1
    37 			m_Head->prev = node2
    38 			node1->next = node2
    39 			node1->prev = m_Head
    40 			node2->next = m_Head
    41 			node2->prev = node1
    42 	*/
    43 	template <class T>
    44 	class List
    45 	{
    46 	public:
    47 		class iterator;
    48 		friend class iterator;
    49 		class ListNode
    50 		{
    51 		public:
    52 			ListNode(const T & o) : obj(o) { };
    53 			ListNode() { };
    54 			T obj;
    55 			ListNode *next;
    56 			ListNode *prev;
    57 		};
    58 	private:
    59 		// Initializes the sentinel node.
    60 		// BAIL used malloc instead of new in order to bypass the need for a constructor.
    61 		ListNode *_Initialize()
    62 		{
    63 			ListNode *n = (ListNode *)malloc(sizeof(ListNode));
    64 			n->next = n;
    65 			n->prev = n;
    66 			return n;
    67 		}
    68 	public:
    69 		List() : m_Head(_Initialize()), m_Size(0)
    70 		{
    71 		}
    72 		List(const List &src) : m_Head(_Initialize()), m_Size(0)
    73 		{
    74 			iterator iter;
    75 			for (iter=src.begin(); iter!=src.end(); iter++)
    76 				push_back( (*iter) );
    77 		}
    78 		~List()
    79 		{
    80 			clear();
    81 
    82 			// Don't forget to free the sentinel
    83 			if (m_Head)
    84 			{
    85 				free(m_Head);
    86 				m_Head = NULL;
    87 			}
    88 		}
    89 		void push_back(const T &obj)
    90 		{
    91 			ListNode *node = new ListNode(obj);
    92 
    93 			node->prev = m_Head->prev;
    94 			node->next = m_Head;
    95 			m_Head->prev->next = node;
    96 			m_Head->prev = node;
    97 
    98 			m_Size++;
    99 		}
   100 
   101 		void push_front(const T &obj)
   102 		{
   103 			insert(begin(), obj);
   104 		}
   105 
   106 		size_t size() const
   107 		{
   108 			return m_Size;
   109 		}
   110 
   111 		void clear()
   112 		{
   113 			ListNode *node = m_Head->next;
   114 			ListNode *temp;
   115 			m_Head->next = m_Head;
   116 			m_Head->prev = m_Head;
   117 
   118 			// Iterate through the nodes until we find g_Head (the sentinel) again
   119 			while (node != m_Head)
   120 			{
   121 				temp = node->next;
   122 				delete node;
   123 				node = temp;
   124 			}
   125 			m_Size = 0;
   126 		}
   127 		bool empty() const
   128 		{
   129 			return (m_Size == 0);
   130 		}
   131 		T & front()
   132 		{
   133 			return m_Head->next->obj;
   134 		}
   135 		T & back()
   136 		{
   137 			return m_Head->prev->obj;
   138 		}
   139 	private:
   140 		ListNode *m_Head;
   141 		size_t m_Size;
   142 	public:
   143 		class iterator
   144 		{
   145 		friend class List;
   146 		public:
   147 			iterator()
   148 			{
   149 				m_This = NULL;
   150 			}
   151 			iterator(const List &src)
   152 			{
   153 				m_This = src.m_Head;
   154 			}
   155 			iterator(ListNode *n) : m_This(n)
   156 			{
   157 			}
   158 			iterator(const iterator &where)
   159 			{
   160 				m_This = where.m_This;
   161 			}
   162 			//pre decrement
   163 			iterator & operator--()
   164 			{
   165 				if (m_This)
   166 					m_This = m_This->prev;
   167 				return *this;
   168 			}
   169 			//post decrement
   170 			iterator operator--(int)
   171 			{
   172 				iterator old(*this);
   173 				if (m_This)
   174 					m_This = m_This->prev;
   175 				return old;
   176 			}	
   177 			
   178 			//pre increment
   179 			iterator & operator++()
   180 			{
   181 				if (m_This)
   182 					m_This = m_This->next;
   183 				return *this;
   184 			}
   185 			//post increment
   186 			iterator operator++(int)
   187 			{
   188 				iterator old(*this);
   189 				if (m_This)
   190 					m_This = m_This->next;
   191 				return old;
   192 			}
   193 			
   194 			const T & operator * () const
   195 			{
   196 				return m_This->obj;
   197 			}
   198 			T & operator * ()
   199 			{
   200 				return m_This->obj;
   201 			}
   202 			
   203 			T * operator -> ()
   204 			{
   205 				return &(m_This->obj);
   206 			}
   207 			const T * operator -> () const
   208 			{
   209 				return &(m_This->obj);
   210 			}
   211 			
   212 			bool operator != (const iterator &where) const
   213 			{
   214 				return (m_This != where.m_This);
   215 			}
   216 			bool operator ==(const iterator &where) const
   217 			{
   218 				return (m_This == where.m_This);
   219 			}
   220 
   221 			operator bool()
   222 			{
   223 				return m_This != NULL;
   224 			}
   225 		private:
   226 			ListNode *m_This;
   227 		};
   228 	public:
   229 		iterator begin() const
   230 		{
   231 			return iterator(m_Head->next);
   232 		}
   233 		iterator end() const
   234 		{
   235 			return iterator(m_Head);
   236 		}
   237 		iterator erase(iterator &where)
   238 		{
   239 			ListNode *pNode = where.m_This;
   240 			iterator iter(where);
   241 			iter++;
   242 
   243 
   244 			// Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle...
   245 			pNode->prev->next = pNode->next;
   246 			pNode->next->prev = pNode->prev;
   247 
   248 			delete pNode;
   249 			m_Size--;
   250 
   251 			return iter;
   252 		}
   253 
   254 		iterator insert(iterator where, const T &obj)
   255 		{
   256 			// Insert obj right before where
   257 
   258 			ListNode *node = new ListNode(obj);
   259 			ListNode *pWhereNode = where.m_This;
   260 			
   261 			pWhereNode->prev->next = node;
   262 			node->prev = pWhereNode->prev;
   263 			pWhereNode->prev = node;
   264 			node->next = pWhereNode;
   265 
   266 			m_Size++;
   267 
   268 			return iterator(node);
   269 		}
   270 
   271 	public:
   272 		void remove(const T & obj)
   273 		{
   274 			iterator b;
   275 			for (b=begin(); b!=end(); b++)
   276 			{
   277 				if ( (*b) == obj )
   278 				{
   279 					erase( b );
   280 					break;
   281 				}
   282 			}
   283 		}
   284 		template <typename U>
   285 		iterator find(const U & equ) const
   286 		{
   287 			iterator iter;
   288 			for (iter=begin(); iter!=end(); iter++)
   289 			{
   290 				if ( (*iter) == equ )
   291 					return iter;
   292 			}
   293 			return end();
   294 		}
   295 		List & operator =(const List &src)
   296 		{
   297 			clear();
   298 			iterator iter;
   299 			for (iter=src.begin(); iter!=src.end(); iter++)
   300 				push_back( (*iter) );
   301 			return *this;
   302 		}
   303 	};
   304 };	//NAMESPACE
   305 
   306 #endif //_INCLUDE_CSDM_LIST_H