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