From fcf83dbf9effab3bd98bad2b83b2468b7eb05cfd Mon Sep 17 00:00:00 2001 From: Tim Foley Date: Fri, 9 Jun 2017 11:34:21 -0700 Subject: Initial import of code. --- source/core/link.h | 336 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 336 insertions(+) create mode 100644 source/core/link.h (limited to 'source/core/link.h') diff --git a/source/core/link.h b/source/core/link.h new file mode 100644 index 000000000..6abd5a9d5 --- /dev/null +++ b/source/core/link.h @@ -0,0 +1,336 @@ +#ifndef CORE_LIB_LINK_H +#define CORE_LIB_LINK_H + +#include "Common.h" +#include "Exception.h" + +namespace CoreLib +{ + namespace Basic + { + template + class LinkedList; + + template + class LinkedNode + { + template + friend class LinkedList; + private: + LinkedNode *pPrev, *pNext; + LinkedList * FLink; + public: + T Value; + LinkedNode (LinkedList * lnk):FLink(lnk) + { + pPrev = pNext = 0; + }; + LinkedNode * GetPrevious() + { + return pPrev; + }; + LinkedNode * GetNext() + { + return pNext; + }; + LinkedNode * InsertAfter(const T & nData) + { + LinkedNode * n = new LinkedNode(FLink); + n->Value = nData; + n->pPrev = this; + n->pNext = this->pNext; + LinkedNode *npp = n->pNext; + if (npp) + { + npp->pPrev = n; + } + pNext = n; + if (!n->pNext) + FLink->FTail = n; + FLink->FCount ++; + return n; + }; + LinkedNode * InsertBefore(const T & nData) + { + LinkedNode * n = new LinkedNode(FLink); + n->Value = nData; + n->pPrev = pPrev; + n->pNext = this; + pPrev = n; + LinkedNode *npp = n->pPrev; + if (npp) + npp->pNext = n; + if (!n->pPrev) + FLink->FHead = n; + FLink->FCount ++; + return n; + }; + void Delete() + { + if (pPrev) + pPrev->pNext = pNext; + if (pNext) + pNext->pPrev = pPrev; + FLink->FCount --; + if (FLink->FHead == this) + { + FLink->FHead = pNext; + } + if (FLink->FTail == this) + { + FLink->FTail = pPrev; + } + delete this; + } + }; + template + class LinkedList + { + template + friend class LinkedNode; + private: + LinkedNode * FHead, *FTail; + int FCount; + public: + class Iterator + { + public: + LinkedNode * Current, *Next; + void SetCurrent(LinkedNode * cur) + { + Current = cur; + if (Current) + Next = Current->GetNext(); + else + Next = 0; + } + Iterator() + { + Current = Next = 0; + } + Iterator(LinkedNode * cur) + { + SetCurrent(cur); + } + T & operator *() const + { + return Current->Value; + } + Iterator& operator ++() + { + SetCurrent(Next); + return *this; + } + Iterator operator ++(int) + { + Iterator rs = *this; + SetCurrent(Next); + return rs; + } + bool operator != (const Iterator & iter) const + { + return Current != iter.Current; + } + bool operator == (const Iterator & iter) const + { + return Current == iter.Current; + } + }; + Iterator begin() const + { + return Iterator(FHead); + } + Iterator end() const + { + return Iterator(0); + } + public: + LinkedList() : FHead(0), FTail(0), FCount(0) + { + } + ~LinkedList() + { + Clear(); + } + LinkedList(const LinkedList & link) : FHead(0), FTail(0), FCount(0) + { + this->operator=(link); + } + LinkedList(LinkedList && link) : FHead(0), FTail(0), FCount(0) + { + this->operator=(_Move(link)); + } + LinkedList & operator = (LinkedList && link) + { + if (FHead != 0) + Clear(); + FHead = link.FHead; + FTail = link.FTail; + FCount = link.FCount; + link.FHead = 0; + link.FTail = 0; + link.FCount = 0; + for (auto node = FHead; node; node = node->GetNext()) + node->FLink = this; + return *this; + } + LinkedList & operator = (const LinkedList & link) + { + if (FHead != 0) + Clear(); + auto p = link.FHead; + while (p) + { + AddLast(p->Value); + p = p->GetNext(); + } + return *this; + } + template + void ForEach(const IteratorFunc & f) + { + auto p = FHead; + while (p) + { + f(p->Value); + p = p->GetNext(); + } + } + LinkedNode * GetNode(int x) + { + LinkedNode *pCur = FHead; + for (int i=0;ipNext; + else + throw "Index out of range"; + } + return pCur; + }; + LinkedNode * Find(const T& fData) + { + for (LinkedNode * pCur = FHead; pCur; pCur = pCur->pNext) + { + if (pCur->Value == fData) + return pCur; + } + return 0; + }; + LinkedNode * FirstNode() const + { + return FHead; + }; + T & First() const + { + if (!FHead) + throw IndexOutofRangeException("LinkedList: index out of range."); + return FHead->Value; + } + T & Last() const + { + if (!FTail) + throw IndexOutofRangeException("LinkedList: index out of range."); + return FTail->Value; + } + LinkedNode * LastNode() const + { + return FTail; + }; + LinkedNode * AddLast(const T & nData) + { + LinkedNode * n = new LinkedNode(this); + n->Value = nData; + n->pPrev = FTail; + if (FTail) + FTail->pNext = n; + n->pNext = 0; + FTail = n; + if (!FHead) + FHead = n; + FCount ++; + return n; + }; + // Insert a blank node + LinkedNode * AddLast() + { + LinkedNode * n = new LinkedNode(this); + n->pPrev = FTail; + if (FTail) + FTail->pNext = n; + n->pNext = 0; + FTail = n; + if (!FHead) + FHead = n; + FCount ++; + return n; + }; + LinkedNode * AddFirst(const T& nData) + { + LinkedNode *n = new LinkedNode(this); + n->Value = nData; + n->pPrev = 0; + n->pNext = FHead; + if (FHead) + FHead->pPrev = n; + FHead = n; + if (!FTail) + FTail = n; + FCount ++; + return n; + }; + void Delete(LinkedNode*n, int Count = 1) + { + LinkedNode *n1,*n2 = 0, *tn; + n1 = n->pPrev; + tn = n; + int numDeleted = 0; + for (int i=0; ipNext; + delete tn; + tn = n2; + numDeleted++; + if (tn == 0) + break; + } + if (n1) + n1->pNext = n2; + else + FHead = n2; + if (n2) + n2->pPrev = n1; + else + FTail = n1; + FCount -= numDeleted; + } + void Clear() + { + for (LinkedNode *n = FHead; n; ) + { + LinkedNode * tmp = n->pNext; + delete n; + n = tmp; + } + FHead = 0; + FTail = 0; + FCount = 0; + } + List ToList() const + { + List rs; + rs.Reserve(FCount); + for (auto & item : *this) + { + rs.Add(item); + } + return rs; + } + int Count() + { + return FCount; + } + }; + } +} +#endif -- cgit v1.2.3