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