#ifndef CONTAINERS_H #define CONTAINERS_H template<class TYPE, class ARG_TYPE> class TList { protected: struct Node { Node* pNext; Node* pPrev; TYPE data; }; struct __POSITION { }; public: typedef __POSITION* POSITION; TList() { m_nCount = 0; m_pNodeHead = m_pNodeTail = ((Node *)0); } ~TList() { RemoveAll(); } int GetCount() const { return m_nCount; } bool IsEmpty() const { return m_nCount == 0; } TYPE& GetHead() { return m_pNodeHead->data; } TYPE GetHead() const { return m_pNodeHead->data; } TYPE& GetTail() { return m_pNodeTail->data; } TYPE GetTail() const { return m_pNodeTail->data; } // get head or tail (and remove it) - don't call on empty list ! TYPE RemoveHead() { Node* pOldNode = m_pNodeHead; TYPE returnValue = pOldNode->data; m_pNodeHead = pOldNode->pNext; if (m_pNodeHead != ((Node *)0)) m_pNodeHead->pPrev = ((Node *)0); else m_pNodeTail = ((Node *)0); FreeNode(pOldNode); return returnValue; } TYPE RemoveTail() { Node* pOldNode = m_pNodeTail; TYPE returnValue = pOldNode->data; m_pNodeTail = pOldNode->pPrev; if (m_pNodeTail != ((Node *)0)) m_pNodeTail->pNext = ((Node *)0); else m_pNodeHead = ((Node *)0); FreeNode(pOldNode); return returnValue; } // add before head or after tail POSITION AddHead(ARG_TYPE newElement) { Node* pNewNode = NewNode(((Node *)0), m_pNodeHead); pNewNode->data = newElement; if (m_pNodeHead != ((void *)0)) m_pNodeHead->pPrev = pNewNode; else m_pNodeTail = pNewNode; m_pNodeHead = pNewNode; return (POSITION) pNewNode; } POSITION AddTail(ARG_TYPE newElement) { Node* pNewNode = NewNode(m_pNodeTail, ((Node *)0)); pNewNode->data = newElement; if (m_pNodeTail != ((Node *)0)) m_pNodeTail->pNext = pNewNode; else m_pNodeHead = pNewNode; m_pNodeTail = pNewNode; return (POSITION) pNewNode; } // remove all elements void RemoveAll() { // destroy elements Node* pNode = m_pNodeHead; while (pNode) { m_pNodeTail = pNode->pNext; delete pNode; pNode = m_pNodeTail; } m_nCount = 0; m_pNodeHead = m_pNodeTail = ((Node *)0); } // iteration POSITION GetHeadPosition() const { return (POSITION) m_pNodeHead; } POSITION GetTailPosition() const { return (POSITION) m_pNodeTail; } TYPE& GetNext(POSITION& rPosition) { // return *Position++ Node* pNode = (Node*) rPosition; rPosition = (POSITION) pNode->pNext; return pNode->data; } TYPE GetNext(POSITION& rPosition) const { // return *Position++ Node* pNode = (Node*) rPosition; rPosition = (POSITION) pNode->pNext; return pNode->data; } TYPE& GetPrev(POSITION& rPosition) { // return *Position-- Node* pNode = (Node*) rPosition; rPosition = (POSITION) pNode->pPrev; return pNode->data; } TYPE GetPrev(POSITION& rPosition) const { // return *Position-- Node* pNode = (Node*) rPosition; rPosition = (POSITION) pNode->pPrev; return pNode->data; } // getting/modifying an element at a given position TYPE& GetAt(POSITION position) { Node* pNode = (Node*) position; return pNode->data; } TYPE GetAt(POSITION position) const { Node* pNode = (Node*) position; return pNode->data; } void SetAt(POSITION pos, ARG_TYPE newElement) { Node* pNode = (Node*) pos; pNode->data = newElement; } void RemoveAt(POSITION position) { Node* pOldNode = (Node*) position; // remove pOldNode from list if (pOldNode == m_pNodeHead) m_pNodeHead = pOldNode->pNext; else pOldNode->pPrev->pNext = pOldNode->pNext; if (pOldNode == m_pNodeTail) m_pNodeTail = pOldNode->pPrev; else pOldNode->pNext->pPrev = pOldNode->pPrev; FreeNode(pOldNode); } // inserting before or after a given position POSITION InsertBefore(POSITION position, ARG_TYPE newElement) { if (position == ((void *)0)) return AddHead(newElement); // insert before nothing -> head of the list // Insert it before position Node* pOldNode = (Node*) position; Node* pNewNode = NewNode(pOldNode->pPrev, pOldNode); pNewNode->data = newElement; if (pOldNode->pPrev != ((Node *)0)) pOldNode->pPrev->pNext = pNewNode; else m_pNodeHead = pNewNode; pOldNode->pPrev = pNewNode; return (POSITION) pNewNode; } POSITION InsertAfter(POSITION position, ARG_TYPE newElement) { if (position == ((void *)0)) return AddTail(newElement); // insert after nothing -> tail of the list // Insert it before position Node* pOldNode = (Node*) position; Node* pNewNode = NewNode(pOldNode, pOldNode->pNext); pNewNode->data = newElement; if (pOldNode->pNext != ((Node *)0)) pOldNode->pNext->pPrev = pNewNode; else m_pNodeTail = pNewNode; pOldNode->pNext = pNewNode; return (POSITION) pNewNode; } // helper functions (note: O(n) speed) // defaults to starting at the HEAD, return NULL if not found POSITION Find(ARG_TYPE searchValue, POSITION startAfter = (POSITION)0) const { Node* pNode = (Node*) startAfter; if (pNode == ((Node *)0)) pNode = m_pNodeHead; // start at head else pNode = pNode->pNext; // start after the one specified for (; pNode != ((Node *)0); pNode = pNode->pNext) if (pNode->data==searchValue) return (POSITION)pNode; return ((POSITION)0); } // get the 'nIndex'th element (may return NULL) POSITION FindIndex(int nIndex) const { if (nIndex >= m_nCount || nIndex < 0) return (POSITION)0; // went too far Node* pNode = m_pNodeHead; while (nIndex--) pNode = pNode->pNext; return (POSITION) pNode; } protected: Node* m_pNodeHead; Node* m_pNodeTail; int m_nCount; Node* NewNode(Node* pPrev, Node* pNext) { Node* pNode = new Node; pNode->pPrev = pPrev; pNode->pNext = pNext; m_nCount++; return pNode; } void FreeNode(Node*pNode) { delete pNode; m_nCount--; // if no more elements, cleanup completely if (m_nCount == 0) RemoveAll(); } }; template<class TYPE, class ARG_TYPE> class TArray { public: TArray() {}; int GetSize() const { return m_ArrayData.GetCount(); } // Clean up void RemoveAll() { return m_ArrayData.RemoveAll(); } // Accessing elements TYPE GetAt(int nIndex) const { return m_ArrayData.GetAt(m_ArrayData.FindIndex(nIndex)); } TYPE& ElementAt(int nIndex) { return m_ArrayData.GetAt(m_ArrayData.FindIndex(nIndex)); } void SetAt(int nIndex, ARG_TYPE newElement) { m_ArrayData.SetAt(m_ArrayData.FindIndex(nIndex),newElement); } // Potentially growing the array int Add(ARG_TYPE newElement) { m_ArrayData.AddTail(newElement); return m_ArrayData.GetCount(); } // overloaded operator helpers TYPE operator[](int nIndex) const { return m_ArrayData.GetAt(m_ArrayData.FindIndex(nIndex)); } TYPE& operator[](int nIndex) { return m_ArrayData.GetAt(m_ArrayData.FindIndex(nIndex)); } // Operations that move elements around void InsertAt(int nIndex, ARG_TYPE newElement, int nCount = 1) { TList<TYPE, ARG_TYPE>::POSITION pos = m_ArrayData.FindIndex(nIndex); for (int i=0; i<nCount; i++) m_ArrayData.InsertBefore(pos,newElement); } void RemoveAt(int nIndex, int nCount = 1) { for (int i=0; i<nCount; i++) m_ArrayData.RemoveAt(m_ArrayData.FindIndex(nIndex)); } protected: TList<TYPE, ARG_TYPE> m_ArrayData; }; #include "SString.h" typedef TArray<int,int> ArrayInts; typedef TArray<SString,SString> ArrayStrings; #endif |