summaryrefslogtreecommitdiffstats
path: root/K2LABI/Common/linkedList.h
diff options
context:
space:
mode:
Diffstat (limited to 'K2LABI/Common/linkedList.h')
-rw-r--r--K2LABI/Common/linkedList.h490
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;
+};