1.1 --- a/sourcehook/sh_list.h Fri Dec 23 11:58:11 2005 +0000
1.2 +++ b/sourcehook/sh_list.h Fri Dec 23 23:00:55 2005 +0000
1.3 @@ -16,253 +16,276 @@
1.4
1.5 namespace SourceHook
1.6 {
1.7 -//This class is from CSDM for AMX Mod X
1.8 -template <class T>
1.9 -class List
1.10 -{
1.11 -public:
1.12 - class iterator;
1.13 - friend class iterator;
1.14 - class ListNode
1.15 +
1.16 + //This class is from CSDM for AMX Mod X
1.17 + /*
1.18 + A circular, doubly-linked list with one sentinel node
1.19 +
1.20 + Empty:
1.21 + m_Head = sentinel
1.22 + m_Head->next = m_Head;
1.23 + m_Head->prev = m_Head;
1.24 + One element:
1.25 + m_Head = sentinel
1.26 + m_Head->next = node1
1.27 + m_Head->prev = node1
1.28 + node1->next = m_Head
1.29 + node1->prev = m_Head
1.30 + Two elements:
1.31 + m_Head = sentinel
1.32 + m_Head->next = node1
1.33 + m_Head->prev = node2
1.34 + node1->next = node2
1.35 + node1->prev = m_Head
1.36 + node2->next = m_Head
1.37 + node2->prev = node1
1.38 + */
1.39 + template <class T>
1.40 + class List
1.41 {
1.42 public:
1.43 - ListNode(const T & o) : obj(o) { };
1.44 - ListNode() { };
1.45 - T obj;
1.46 - ListNode *next;
1.47 - ListNode *prev;
1.48 - };
1.49 -private:
1.50 - ListNode *_Initialize()
1.51 - {
1.52 - ListNode *n = (ListNode *)malloc(sizeof(ListNode));
1.53 - n->next = NULL;
1.54 - n->prev = NULL;
1.55 - return n;
1.56 - }
1.57 -public:
1.58 - List() : m_Head(_Initialize()), m_Size(0)
1.59 - {
1.60 - }
1.61 - List(const List &src) : m_Head(_Initialize()), m_Size(0)
1.62 - {
1.63 - iterator iter;
1.64 - for (iter=src.begin(); iter!=src.end(); iter++)
1.65 - push_back( (*iter) );
1.66 - }
1.67 - ~List()
1.68 - {
1.69 - clear();
1.70 - if (m_Head)
1.71 + class iterator;
1.72 + friend class iterator;
1.73 + class ListNode
1.74 + {
1.75 + public:
1.76 + ListNode(const T & o) : obj(o) { };
1.77 + ListNode() { };
1.78 + T obj;
1.79 + ListNode *next;
1.80 + ListNode *prev;
1.81 + };
1.82 + private:
1.83 + // Initializes the sentinel node.
1.84 + // BAIL used malloc instead of new in order to bypass the need for a constructor.
1.85 + ListNode *_Initialize()
1.86 {
1.87 - free(m_Head);
1.88 - m_Head = NULL;
1.89 + ListNode *n = (ListNode *)malloc(sizeof(ListNode));
1.90 + n->next = n;
1.91 + n->prev = n;
1.92 + return n;
1.93 + }
1.94 + public:
1.95 + List() : m_Head(_Initialize()), m_Size(0)
1.96 + {
1.97 }
1.98 - }
1.99 - void push_back(const T &obj)
1.100 - {
1.101 - ListNode *node = new ListNode(obj);
1.102 + List(const List &src) : m_Head(_Initialize()), m_Size(0)
1.103 + {
1.104 + iterator iter;
1.105 + for (iter=src.begin(); iter!=src.end(); iter++)
1.106 + push_back( (*iter) );
1.107 + }
1.108 + ~List()
1.109 + {
1.110 + clear();
1.111
1.112 - if (!m_Head->prev)
1.113 + // Don't forget to free the sentinel
1.114 + if (m_Head)
1.115 + {
1.116 + free(m_Head);
1.117 + m_Head = NULL;
1.118 + }
1.119 + }
1.120 + void push_back(const T &obj)
1.121 {
1.122 - //link in the node as the first item
1.123 - node->next = m_Head;
1.124 - node->prev = m_Head;
1.125 - m_Head->prev = node;
1.126 - m_Head->next = node;
1.127 - } else {
1.128 + ListNode *node = new ListNode(obj);
1.129 +
1.130 node->prev = m_Head->prev;
1.131 node->next = m_Head;
1.132 m_Head->prev->next = node;
1.133 m_Head->prev = node;
1.134 +
1.135 + m_Size++;
1.136 }
1.137 - m_Size++;
1.138 - }
1.139 - size_t size()
1.140 - {
1.141 - return m_Size;
1.142 - }
1.143 - void clear()
1.144 - {
1.145 - ListNode *node = m_Head->next;
1.146 - ListNode *temp;
1.147 - m_Head->next = NULL;
1.148 - m_Head->prev = NULL;
1.149 - while (node && node != m_Head)
1.150 + size_t size()
1.151 + {
1.152 + return m_Size;
1.153 + }
1.154 +
1.155 + void clear()
1.156 {
1.157 - temp = node->next;
1.158 - delete node;
1.159 - node = temp;
1.160 + ListNode *node = m_Head->next;
1.161 + ListNode *temp;
1.162 + m_Head->next = m_Head;
1.163 + m_Head->prev = m_Head;
1.164 +
1.165 + // Iterate through the nodes until we find g_Head (the sentinel) again
1.166 + while (node != m_Head)
1.167 + {
1.168 + temp = node->next;
1.169 + delete node;
1.170 + node = temp;
1.171 + }
1.172 + m_Size = 0;
1.173 }
1.174 - m_Size = 0;
1.175 - }
1.176 - bool empty()
1.177 - {
1.178 - return (m_Head->next == NULL);
1.179 - }
1.180 - T & back()
1.181 - {
1.182 - return m_Head->prev->obj;
1.183 - }
1.184 -private:
1.185 - ListNode *m_Head;
1.186 - size_t m_Size;
1.187 -public:
1.188 - class iterator
1.189 - {
1.190 - friend class List;
1.191 + bool empty()
1.192 + {
1.193 + return (m_Size == 0);
1.194 + }
1.195 + T & back()
1.196 + {
1.197 + return m_Head->prev->obj;
1.198 + }
1.199 + private:
1.200 + ListNode *m_Head;
1.201 + size_t m_Size;
1.202 public:
1.203 - iterator()
1.204 - {
1.205 - m_This = NULL;
1.206 - }
1.207 - iterator(const List &src)
1.208 - {
1.209 - m_This = src.m_Head;
1.210 - }
1.211 - iterator(ListNode *n) : m_This(n)
1.212 - {
1.213 - }
1.214 - iterator(const iterator &where)
1.215 - {
1.216 - m_This = where.m_This;
1.217 - }
1.218 - //pre decrement
1.219 - iterator & operator--()
1.220 + class iterator
1.221 {
1.222 - if (m_This)
1.223 - m_This = m_This->prev;
1.224 - return *this;
1.225 - }
1.226 - //post decrement
1.227 - iterator operator--(int)
1.228 + friend class List;
1.229 + public:
1.230 + iterator()
1.231 + {
1.232 + m_This = NULL;
1.233 + }
1.234 + iterator(const List &src)
1.235 + {
1.236 + m_This = src.m_Head;
1.237 + }
1.238 + iterator(ListNode *n) : m_This(n)
1.239 + {
1.240 + }
1.241 + iterator(const iterator &where)
1.242 + {
1.243 + m_This = where.m_This;
1.244 + }
1.245 + //pre decrement
1.246 + iterator & operator--()
1.247 + {
1.248 + if (m_This)
1.249 + m_This = m_This->prev;
1.250 + return *this;
1.251 + }
1.252 + //post decrement
1.253 + iterator operator--(int)
1.254 + {
1.255 + iterator old(*this);
1.256 + if (m_This)
1.257 + m_This = m_This->prev;
1.258 + return old;
1.259 + }
1.260 +
1.261 + //pre increment
1.262 + iterator & operator++()
1.263 + {
1.264 + if (m_This)
1.265 + m_This = m_This->next;
1.266 + return *this;
1.267 + }
1.268 + //post increment
1.269 + iterator operator++(int)
1.270 + {
1.271 + iterator old(*this);
1.272 + if (m_This)
1.273 + m_This = m_This->next;
1.274 + return old;
1.275 + }
1.276 +
1.277 + const T & operator * () const
1.278 + {
1.279 + return m_This->obj;
1.280 + }
1.281 + T & operator * ()
1.282 + {
1.283 + return m_This->obj;
1.284 + }
1.285 +
1.286 + T * operator -> ()
1.287 + {
1.288 + return &(m_This->obj);
1.289 + }
1.290 + const T * operator -> () const
1.291 + {
1.292 + return &(m_This->obj);
1.293 + }
1.294 +
1.295 + bool operator != (const iterator &where) const
1.296 + {
1.297 + return (m_This != where.m_This);
1.298 + }
1.299 + bool operator ==(const iterator &where) const
1.300 + {
1.301 + return (m_This == where.m_This);
1.302 + }
1.303 + private:
1.304 + ListNode *m_This;
1.305 + };
1.306 + public:
1.307 + iterator begin() const
1.308 {
1.309 - iterator old(*this);
1.310 - if (m_This)
1.311 - m_This = m_This->prev;
1.312 - return old;
1.313 - }
1.314 -
1.315 - //pre increment
1.316 - iterator & operator++()
1.317 + return iterator(m_Head->next);
1.318 + }
1.319 + iterator end() const
1.320 + {
1.321 + return iterator(m_Head);
1.322 + }
1.323 + iterator erase(iterator &where)
1.324 + {
1.325 + ListNode *pNode = where.m_This;
1.326 + iterator iter(where);
1.327 + iter++;
1.328 +
1.329 +
1.330 + // Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle...
1.331 + pNode->prev->next = pNode->next;
1.332 + pNode->next->prev = pNode->prev;
1.333 +
1.334 + delete pNode;
1.335 + m_Size--;
1.336 +
1.337 + return iter;
1.338 + }
1.339 +
1.340 + iterator insert(iterator where, const T &obj)
1.341 {
1.342 - if (m_This)
1.343 - m_This = m_This->next;
1.344 + // Insert obj right before where
1.345 +
1.346 + ListNode *node = new ListNode(obj);
1.347 + ListNode *pWhereNode = where.m_This;
1.348 +
1.349 + pWhereNode->prev->next = node;
1.350 + node->prev = pWhereNode->prev;
1.351 + pWhereNode->prev = node;
1.352 + node->next = pWhereNode;
1.353 +
1.354 + m_Size++;
1.355 +
1.356 + return iterator(node);
1.357 + }
1.358 +
1.359 + public:
1.360 + void remove(const T & obj)
1.361 + {
1.362 + iterator b;
1.363 + for (b=begin(); b!=end(); b++)
1.364 + {
1.365 + if ( (*b) == obj )
1.366 + {
1.367 + erase( b );
1.368 + break;
1.369 + }
1.370 + }
1.371 + }
1.372 + template <typename U>
1.373 + iterator find(const U & equ)
1.374 + {
1.375 + iterator iter;
1.376 + for (iter=begin(); iter!=end(); iter++)
1.377 + {
1.378 + if ( (*iter) == equ )
1.379 + return iter;
1.380 + }
1.381 + return end();
1.382 + }
1.383 + List & operator =(const List &src)
1.384 + {
1.385 + clear();
1.386 + iterator iter;
1.387 + for (iter=src.begin(); iter!=src.end(); iter++)
1.388 + push_back( (*iter) );
1.389 return *this;
1.390 }
1.391 - //post increment
1.392 - iterator operator++(int)
1.393 - {
1.394 - iterator old(*this);
1.395 - if (m_This)
1.396 - m_This = m_This->next;
1.397 - return old;
1.398 - }
1.399 -
1.400 - const T & operator * () const
1.401 - {
1.402 - return m_This->obj;
1.403 - }
1.404 - T & operator * ()
1.405 - {
1.406 - return m_This->obj;
1.407 - }
1.408 -
1.409 - T * operator -> ()
1.410 - {
1.411 - return &(m_This->obj);
1.412 - }
1.413 - const T * operator -> () const
1.414 - {
1.415 - return &(m_This->obj);
1.416 - }
1.417 -
1.418 - bool operator != (const iterator &where) const
1.419 - {
1.420 - return (m_This != where.m_This);
1.421 - }
1.422 - bool operator ==(const iterator &where) const
1.423 - {
1.424 - return (m_This == where.m_This);
1.425 - }
1.426 - private:
1.427 - ListNode *m_This;
1.428 };
1.429 -public:
1.430 - iterator begin() const
1.431 - {
1.432 - if (m_Size)
1.433 - return iterator(m_Head->next);
1.434 - else
1.435 - return iterator(m_Head);
1.436 - }
1.437 - iterator end() const
1.438 - {
1.439 - return iterator(m_Head);
1.440 - }
1.441 - iterator erase(iterator &where)
1.442 - {
1.443 - ListNode *pNode = where.m_This;
1.444 - iterator iter(where);
1.445 - iter++;
1.446 -
1.447 - //If we are both the head and tail...
1.448 - if (m_Head->next == pNode && m_Head->prev == pNode)
1.449 - {
1.450 - m_Head->next = NULL;
1.451 - m_Head->prev = NULL;
1.452 - } else if (m_Head->next == pNode) {
1.453 - //we are only the first
1.454 - pNode->next->prev = m_Head;
1.455 - m_Head->next = pNode->next;
1.456 - } else if (m_Head->prev == pNode) {
1.457 - //we are the tail
1.458 - pNode->prev->next = m_Head;
1.459 - m_Head->prev = pNode->prev;
1.460 - } else {
1.461 - //middle unlink
1.462 - pNode->prev->next = pNode->next;
1.463 - pNode->next->prev = pNode->prev;
1.464 - }
1.465 -
1.466 - delete pNode;
1.467 - m_Size--;
1.468 -
1.469 - return iter;
1.470 - }
1.471 -public:
1.472 - void remove(const T & obj)
1.473 - {
1.474 - iterator b;
1.475 - for (b=begin(); b!=end(); b++)
1.476 - {
1.477 - if ( (*b) == obj )
1.478 - {
1.479 - erase( b );
1.480 - break;
1.481 - }
1.482 - }
1.483 - }
1.484 - template <typename U>
1.485 - iterator find(const U & equ)
1.486 - {
1.487 - iterator iter;
1.488 - for (iter=begin(); iter!=end(); iter++)
1.489 - {
1.490 - if ( (*iter) == equ )
1.491 - return iter;
1.492 - }
1.493 - return end();
1.494 - }
1.495 - List & operator =(const List &src)
1.496 - {
1.497 - clear();
1.498 - iterator iter;
1.499 - for (iter=src.begin(); iter!=src.end(); iter++)
1.500 - push_back( (*iter) );
1.501 - return *this;
1.502 - }
1.503 -};
1.504 }; //NAMESPACE
1.505
1.506 #endif //_INCLUDE_CSDM_LIST_H