dvander@347: /* ======== SourceMM ======== dvander@347: * Copyright (C) 2004-2007 Metamod:Source Development Team dvander@347: * No warranties of any kind dvander@347: * dvander@347: * License: zlib/libpng dvander@347: * dvander@347: * Author(s): David "BAILOPAN" Anderson dvander@347: * ============================ dvander@347: */ dvander@347: dvander@347: #ifndef _INCLUDE_SMM_LIST_H dvander@347: #define _INCLUDE_SMM_LIST_H dvander@347: dvander@347: #include dvander@347: #include dvander@347: dvander@347: namespace SourceHook dvander@347: { dvander@347: dvander@347: //This class is from CSDM for AMX Mod X dvander@347: /* dvander@347: A circular, doubly-linked list with one sentinel node dvander@347: dvander@347: Empty: dvander@347: m_Head = sentinel dvander@347: m_Head->next = m_Head; dvander@347: m_Head->prev = m_Head; dvander@347: One element: dvander@347: m_Head = sentinel dvander@347: m_Head->next = node1 dvander@347: m_Head->prev = node1 dvander@347: node1->next = m_Head dvander@347: node1->prev = m_Head dvander@347: Two elements: dvander@347: m_Head = sentinel dvander@347: m_Head->next = node1 dvander@347: m_Head->prev = node2 dvander@347: node1->next = node2 dvander@347: node1->prev = m_Head dvander@347: node2->next = m_Head dvander@347: node2->prev = node1 dvander@347: */ dvander@347: template dvander@347: class List dvander@347: { dvander@347: public: dvander@347: class iterator; dvander@347: friend class iterator; dvander@347: class ListNode dvander@347: { dvander@347: public: dvander@347: ListNode(const T & o) : obj(o) { }; dvander@347: ListNode() { }; dvander@347: T obj; dvander@347: ListNode *next; dvander@347: ListNode *prev; dvander@347: }; dvander@347: private: dvander@347: // Initializes the sentinel node. dvander@347: // BAIL used malloc instead of new in order to bypass the need for a constructor. dvander@347: ListNode *_Initialize() dvander@347: { dvander@347: ListNode *n = (ListNode *)malloc(sizeof(ListNode)); dvander@347: n->next = n; dvander@347: n->prev = n; dvander@347: return n; dvander@347: } dvander@347: public: dvander@347: List() : m_Head(_Initialize()), m_Size(0) dvander@347: { dvander@347: } dvander@347: List(const List &src) : m_Head(_Initialize()), m_Size(0) dvander@347: { dvander@347: iterator iter; dvander@347: for (iter=src.begin(); iter!=src.end(); iter++) dvander@347: push_back( (*iter) ); dvander@347: } dvander@347: ~List() dvander@347: { dvander@347: clear(); dvander@347: dvander@347: // Don't forget to free the sentinel dvander@347: if (m_Head) dvander@347: { dvander@347: free(m_Head); dvander@347: m_Head = NULL; dvander@347: } dvander@347: } dvander@347: void push_back(const T &obj) dvander@347: { dvander@347: ListNode *node = new ListNode(obj); dvander@347: dvander@347: node->prev = m_Head->prev; dvander@347: node->next = m_Head; dvander@347: m_Head->prev->next = node; dvander@347: m_Head->prev = node; dvander@347: dvander@347: m_Size++; dvander@347: } dvander@347: size_t size() const dvander@347: { dvander@347: return m_Size; dvander@347: } dvander@347: dvander@347: void clear() dvander@347: { dvander@347: ListNode *node = m_Head->next; dvander@347: ListNode *temp; dvander@347: m_Head->next = m_Head; dvander@347: m_Head->prev = m_Head; dvander@347: dvander@347: // Iterate through the nodes until we find g_Head (the sentinel) again dvander@347: while (node != m_Head) dvander@347: { dvander@347: temp = node->next; dvander@347: delete node; dvander@347: node = temp; dvander@347: } dvander@347: m_Size = 0; dvander@347: } dvander@347: bool empty() const dvander@347: { dvander@347: return (m_Size == 0); dvander@347: } dvander@347: T & back() dvander@347: { dvander@347: return m_Head->prev->obj; dvander@347: } dvander@347: private: dvander@347: ListNode *m_Head; dvander@347: size_t m_Size; dvander@347: public: dvander@347: class iterator dvander@347: { dvander@347: friend class List; dvander@347: public: dvander@347: iterator() dvander@347: { dvander@347: m_This = NULL; dvander@347: } dvander@347: iterator(const List &src) dvander@347: { dvander@347: m_This = src.m_Head; dvander@347: } dvander@347: iterator(ListNode *n) : m_This(n) dvander@347: { dvander@347: } dvander@347: iterator(const iterator &where) dvander@347: { dvander@347: m_This = where.m_This; dvander@347: } dvander@347: //pre decrement dvander@347: iterator & operator--() dvander@347: { dvander@347: if (m_This) dvander@347: m_This = m_This->prev; dvander@347: return *this; dvander@347: } dvander@347: //post decrement dvander@347: iterator operator--(int) dvander@347: { dvander@347: iterator old(*this); dvander@347: if (m_This) dvander@347: m_This = m_This->prev; dvander@347: return old; dvander@347: } dvander@347: dvander@347: //pre increment dvander@347: iterator & operator++() dvander@347: { dvander@347: if (m_This) dvander@347: m_This = m_This->next; dvander@347: return *this; dvander@347: } dvander@347: //post increment dvander@347: iterator operator++(int) dvander@347: { dvander@347: iterator old(*this); dvander@347: if (m_This) dvander@347: m_This = m_This->next; dvander@347: return old; dvander@347: } dvander@347: dvander@347: const T & operator * () const dvander@347: { dvander@347: return m_This->obj; dvander@347: } dvander@347: T & operator * () dvander@347: { dvander@347: return m_This->obj; dvander@347: } dvander@347: dvander@347: T * operator -> () dvander@347: { dvander@347: return &(m_This->obj); dvander@347: } dvander@347: const T * operator -> () const dvander@347: { dvander@347: return &(m_This->obj); dvander@347: } dvander@347: dvander@347: bool operator != (const iterator &where) const dvander@347: { dvander@347: return (m_This != where.m_This); dvander@347: } dvander@347: bool operator ==(const iterator &where) const dvander@347: { dvander@347: return (m_This == where.m_This); dvander@347: } dvander@347: private: dvander@347: ListNode *m_This; dvander@347: }; dvander@347: public: dvander@347: iterator begin() const dvander@347: { dvander@347: return iterator(m_Head->next); dvander@347: } dvander@347: iterator end() const dvander@347: { dvander@347: return iterator(m_Head); dvander@347: } dvander@347: iterator erase(iterator &where) dvander@347: { dvander@347: ListNode *pNode = where.m_This; dvander@347: iterator iter(where); dvander@347: iter++; dvander@347: dvander@347: dvander@347: // Works for all cases: empty list, erasing first element, erasing tail, erasing in the middle... dvander@347: pNode->prev->next = pNode->next; dvander@347: pNode->next->prev = pNode->prev; dvander@347: dvander@347: delete pNode; dvander@347: m_Size--; dvander@347: dvander@347: return iter; dvander@347: } dvander@347: dvander@347: iterator insert(iterator where, const T &obj) dvander@347: { dvander@347: // Insert obj right before where dvander@347: dvander@347: ListNode *node = new ListNode(obj); dvander@347: ListNode *pWhereNode = where.m_This; dvander@347: dvander@347: pWhereNode->prev->next = node; dvander@347: node->prev = pWhereNode->prev; dvander@347: pWhereNode->prev = node; dvander@347: node->next = pWhereNode; dvander@347: dvander@347: m_Size++; dvander@347: dvander@347: return iterator(node); dvander@347: } dvander@347: dvander@347: public: dvander@347: void remove(const T & obj) dvander@347: { dvander@347: iterator b; dvander@347: for (b=begin(); b!=end(); b++) dvander@347: { dvander@347: if ( (*b) == obj ) dvander@347: { dvander@347: erase( b ); dvander@347: break; dvander@347: } dvander@347: } dvander@347: } dvander@347: template dvander@347: iterator find(const U & equ) const dvander@347: { dvander@347: iterator iter; dvander@347: for (iter=begin(); iter!=end(); iter++) dvander@347: { dvander@347: if ( (*iter) == equ ) dvander@347: return iter; dvander@347: } dvander@347: return end(); dvander@347: } dvander@347: List & operator =(const List &src) dvander@347: { dvander@347: clear(); dvander@347: iterator iter; dvander@347: for (iter=src.begin(); iter!=src.end(); iter++) dvander@347: push_back( (*iter) ); dvander@347: return *this; dvander@347: } dvander@347: }; dvander@347: }; //NAMESPACE dvander@347: dvander@347: #endif //_INCLUDE_CSDM_LIST_H