diff options
Diffstat (limited to 'K2LABI/Common/linkedList.h')
-rw-r--r-- | K2LABI/Common/linkedList.h | 490 |
1 files changed, 490 insertions, 0 deletions
diff --git a/K2LABI/Common/linkedList.h b/K2LABI/Common/linkedList.h new file mode 100644 index 0000000..a49eda1 --- /dev/null +++ b/K2LABI/Common/linkedList.h @@ -0,0 +1,490 @@ +#pragma once +#include <windows.h> +#include "list.h" + +#define MAX_ITERATOR 10 + +template <class T> + +class CLinkedList : public IList<T> +{ +private: + class CNode + { + public: + CNode(T* item, CNode* pPrevious) + { + val = item; + m_pNext = 0; + m_pPrevious = pPrevious; + if(pPrevious) + { + pPrevious->m_pNext = this; + } + } + CNode(T* item, CNode* pPrevious, CNode* pNext) + { + val = item; + m_pNext = pNext; + m_pPrevious = pPrevious; + if(pNext) + { + pNext->m_pPrevious = this; + } + if(pPrevious) + { + pPrevious->m_pNext = this; + } + } + ~CNode() + { + } + CNode* m_pNext; + CNode* m_pPrevious; + T* val; + }; +public: + class CIterator : public IList<T>::IIterator + { + + public: + CIterator(CNode* pHead, CLinkedList* pList) + { + m_pHead = pHead; + m_pCurNode = pHead; + m_pList = pList; + } + virtual ~CIterator() + { + } + + bool hasNext() + { + return m_pCurNode != 0; + } + T* next() + { + T* pRet = 0; + m_pList->lock(); + if(m_pCurNode) + { + pRet = m_pCurNode->val; + m_pCurNode = m_pCurNode->m_pNext; + } + m_pList->unlock(); + return pRet; + } + void release() + { + delete this; + } + void reset() + { + m_pCurNode = m_pHead; + } + private: + void setCurrentNode(CNode* pHead) + { + m_pCurNode = pHead; + } + CNode* m_pCurNode; + CNode* m_pHead; + CLinkedList* m_pList; + friend class CLinkedList; + + }; + +public: + //------------------------------------------------------------------------- + CLinkedList() + { + m_nSize = 0; + m_pHead = 0; + m_pLastNode = 0; + ::InitializeCriticalSection(&m_CS); + m_bCreated = true; + } + //------------------------------------------------------------------------- + virtual ~CLinkedList() + { + if(m_bCreated) + { + ::DeleteCriticalSection(&m_CS); + m_bCreated = false; + } + } + //------------------------------------------------------------------------- + CIterator* getIterator() + { + return new CIterator(m_pHead, this); + } + //------------------------------------------------------------------------- + void releaseIterator(CIterator* pIterator) + { + delete pIterator; + } + //------------------------------------------------------------------------- + int size() + { + return m_nSize; + } + //------------------------------------------------------------------------- + T* find(T* pCmp, int* pnIdx = 0, bool bForward = true) + { + T* pRet = 0; + lock(); + if(pCmp != 0) + { + + CNode* e = (bForward) ? m_pHead : m_pLastNode; + if(!isEmpty()) + { + int nIdx = 0; + while(e) + { + if(e->val->Compare(pCmp) == 0) + { + pRet = e->val; + break; + } + e = (bForward) ? e->m_pNext : e->m_pPrevious; + nIdx++; + } + if(pnIdx != 0) + { + *pnIdx = nIdx; + } + } + } + unlock(); + return pRet; + } + //------------------------------------------------------------------------- + int add(T* pItem) + { + lock(); + int nRet = 0; + if(m_pHead == 0) + { + m_pHead = new CNode(pItem, 0); + m_pLastNode = m_pHead; + } + else + { + m_pLastNode->m_pNext = new CNode(pItem, m_pLastNode); + m_pLastNode = m_pLastNode->m_pNext; + } + m_nSize++; + unlock(); + return nRet; + } + //------------------------------------------------------------------------- + /* + * returns 0 if the item was successfully removed from the list and -1 if the item + * was not found in the list. + */ + int remove(T* pItem, bool bDelete = true) + { + lock(); + int nRet = -1; + if(!isEmpty()) + { + CNode* e = m_pHead; + while(e) + { + if(e->val == pItem) + { + if(e->m_pPrevious) + { + e->m_pPrevious->m_pNext = e->m_pNext; + } + else + { + //the head will be removed. + m_pHead = e->m_pNext; + } + if(e->m_pNext) + { + e->m_pNext->m_pPrevious = e->m_pPrevious; + } + else + { + //the last item will be removed. + m_pLastNode = e->m_pPrevious; + } + if(bDelete) + { + delete e->val; + } + delete e; + m_nSize--; + nRet = 0; + break; + } + e = e->m_pNext; + } + } + unlock(); + return nRet; + } + int removeByValue(T& item, bool bDelete = true) + { + lock(); + int nRet = -1; + if(!isEmpty()) + { + CNode* e = m_pHead; + while(e) + { + if(*(e->val) == item) + { + if(e->m_pPrevious) + { + e->m_pPrevious->m_pNext = e->m_pNext; + } + else + { + //the head will be removed. + m_pHead = e->m_pNext; + } + if(e->m_pNext) + { + e->m_pNext->m_pPrevious = e->m_pPrevious; + } + else + { + //the last item will be removed. + m_pLastNode = e->m_pPrevious; + } + if(bDelete) + { + delete e->val; + } + delete e; + m_nSize--; + nRet = 0; + break; + } + e = e->m_pNext; + } + } + unlock(); + return nRet; + } + //------------------------------------------------------------------------- + /* + * adds an element to the list if the element dont exist otherwise dont + * dont add the element. + * returns 0 if the element was added successfully and return a pointer to the element found otherwise. + */ + T* addNotExist(T* pItem) + { + T* pRet = 0; + T* p = find(pItem); + if(p == 0) + { + add(pItem); + } + else + { + pRet = p; + } + return pRet; + } + //------------------------------------------------------------------------- + int addAt(T* pItem, int nIndex) + { + int nRet = 0; + lock(); + CNode* pNext = getNodeAt(nIndex); + + if(pNext) + { + CNode* newNode = new CNode(pItem, pNext->m_pPrevious, pNext); + if(!newNode->m_pPrevious) + { + m_pHead = newNode; + } + m_nSize++; + } + else + { + if(isEmpty() && nIndex == 0) + { + add(pItem); + } + else if(nIndex == m_nSize) + { + addAfter(pItem, m_pLastNode); + } + } + unlock(); + return nRet; + } + int removeAt(int nIndex, bool bDelete = true) + { + int nRet = 0; + lock(); + CNode* e = getNodeAt(nIndex); + if(e) + { + if(e->m_pPrevious) + { + e->m_pPrevious->m_pNext = e->m_pNext; + } + else + { + //the head will be removed. + m_pHead = e->m_pNext; + } + if(e->m_pNext) + { + e->m_pNext->m_pPrevious = e->m_pPrevious; + } + else + { + //the last item will be removed. + m_pLastNode = e->m_pPrevious; + } + if(bDelete) + { + delete e->val; + } + delete e; + m_nSize--; + } + + unlock(); + return nRet; + } + //------------------------------------------------------------------------- + T* getAt(int nIndex) + { + T* ret = 0; + CNode* e = getNodeAt(nIndex); + if(e) + { + ret = (e->val); + } + return ret; + } + //------------------------------------------------------------------------- + T* getHead() + { + return (m_pHead != 0) ? m_pHead->val : 0; + } + //------------------------------------------------------------------------- + T* getLast() + { + CNode* pLastNode = getLastNode(); + return (pLastNode != 0) ? pLastNode->val : 0; + } + //------------------------------------------------------------------------- + void clear(bool bDelete = true, bool bArr = false) + { + lock(); + if(m_nSize > 0) + { + CNode* e = m_pHead; + CNode* next = e->m_pNext; + while(e) + { + if(bDelete) + { + if(bArr) + { + delete [] e->val; + } + else + { + delete e->val; + } + } + delete e; + e = next; + if(e)next = e->m_pNext; + } + m_pHead = 0; + m_nSize = 0; + m_pLastNode = 0; + } + unlock(); + } + //------------------------------------------------------------------------- + bool isEmpty() + { + bool bRet = (m_nSize == 0); + return bRet; + } + //------------------------------------------------------------------------- + int lock() + { + ::EnterCriticalSection(&m_CS); + return 0; + } + int unlock() + { + ::LeaveCriticalSection(&m_CS); + return 0; + } +private: + int addAfter(T* pItem, CNode* after) + { + int nRet = 0; + lock(); + CNode* newNode = new CNode(pItem, after, after->m_pNext); + if(newNode) + { + if(!newNode->m_pNext) + { + m_pLastNode = newNode; + } + m_nSize++; + } + unlock(); + return nRet; + } + //------------------------------------------------------------------------- + int addBefor(T* item, CNode* befor) + { + int nRet = 0; + return nRet; + } + + + //------------------------------------------------------------------------- + void show() + { + CNode *e; + for(e = m_pHead ; e != 0 ; e = e->m_pNext) + { + printf("previous %x node %x next %x\n", e->m_pPrevious, e, e->m_pNext); + } + printf("List size = %d\n", m_nSize); + } + //------------------------------------------------------------------------- + CNode* getLastNode() + { + return m_pLastNode; + } + //------------------------------------------------------------------------- + CNode* getNodeAt(int nIndex) + { + CNode* ret = 0; + lock(); + if(0 <= nIndex && nIndex < m_nSize) + { + CNode* e = m_pHead; + for(int i = 0 ; i < nIndex ; e = e->m_pNext,i++); + ret = e; + } + unlock(); + return ret; + } + + int m_nSize; + CNode *m_pHead; + CNode *m_pLastNode; + CRITICAL_SECTION m_CS; + bool m_bCreated; +}; |