cArraySort.h

Go to the documentation of this file.

//
//
 
#ifndef _INC_cArraySort_H
#define _INC_cArraySort_H
#ifndef NO_PRAGMA_ONCE
#pragma once
#endif
 
#include "cArray.h"
#include "StrT.h"
#include "cValT.h"
#include "cUnitTestDecl.h"
 
namespace Gray
{
        UNITTEST2_PREDEF(cArraySort);
 
        template<class TYPE, class TYPE_ARG, typename TYPE_KEY>
        class cArraySorted : public cArrayTyped < TYPE, TYPE_ARG >
        {
 
        public:
                typedef cArrayTyped<TYPE, TYPE_ARG> SUPER_t;
                typedef TYPE_KEY KEY_t;
                typedef typename SUPER_t::REF_t REF_t;
 
        protected:
                virtual COMPARE_t CompareKey(KEY_t key1, REF_t Data2) const
                {
                        return cMem::Compare(&key1, &Data2, sizeof(TYPE_KEY));
                }
 
                bool RemoveArgKey(REF_t pObj, KEY_t key)
                {
                        ITERATE_t index = FindIForKey(key);
                        if (index <= k_ITERATE_BAD)
                                return false;
                        TYPE_ARG pObjOld = this->GetAt(index);
                        if (!(pObjOld == pObj)) // not the current one !! weird!
                        {
                                ASSERT(0);
                                return false;
                        }
                        this->RemoveAt(index);
                        return true;
                }
 
        public:
                virtual ~cArraySorted()
                {
                        // Make this virtual to allow derived classes to override this and make destructors work.
                }
 
                ITERATE_t FindINear(REF_t pNew, COMPARE_t& iCompareRes) const;
                ITERATE_t FindINearKey(KEY_t key, COMPARE_t& iCompareRes) const;
                ITERATE_t FindIForKey(KEY_t key) const
                {
                        COMPARE_t iCompareRes;
                        ITERATE_t index = FindINearKey(key, iCompareRes);
                        if (iCompareRes != COMPARE_Equal)
                                return k_ITERATE_BAD;
                        return index;
                }
 
                ITERATE_t FindIFirstForKey(TYPE_KEY nKey) const
                {
                        ITERATE_t i = this->FindIForKey(nKey);
                        if (i < 0)
                                return k_ITERATE_BAD;
                        // Walk Back to get First.
                        for (;;)
                        {
                                if (--i < 0)
                                        break;
                                if (CompareKey(nKey, this->GetAt(i)) != COMPARE_Equal)
                                        break;
                        }
                        return(i + 1);
                }
                ITERATE_t FindILastForKey(TYPE_KEY nKey) const
                {
                        ITERATE_t i = this->FindIForKey(nKey);
                        if (i < 0)
                                return k_ITERATE_BAD;
                        // Walk Forward to get Last.
                        for (;;)
                        {
                                if (++i >= this->GetSize())
                                        break;
                                if (CompareKey(nKey, this->GetAt(i)) != COMPARE_Equal)
                                        break;
                        }
                        return(i - 1);  // last
                }
 
                ITERATE_t AddPresorted(ITERATE_t index, COMPARE_t iCompareRes, TYPE_ARG pNew)
                {
                        if (iCompareRes > 0) // key is greater than existing element at index. so put it after.
                        {
                                index++;
                        }
                        this->InsertAt(index, pNew);
                        return index;
                }
                bool RemoveKey(TYPE_KEY key)
                {
                        ITERATE_t index = FindIForKey(key);
                        if (index <= k_ITERATE_BAD)
                                return false;
                        this->RemoveAt(index);
                        return true;
                }
 
                ITERATE_t Add(TYPE_ARG pNew);
 
                void AddArray(const SUPER_t& a)
                {
                        for (ITERATE_t i = 0; i < a.GetSize(); i++)
                        {
                                Add(a[i]);
                        }
                }
        };
 
        template<class TYPE, class TYPE_ARG, typename TYPE_KEY>
        ITERATE_t cArraySorted<TYPE, TYPE_ARG, TYPE_KEY>::FindINear(REF_t pNew, COMPARE_t& riCompareRes) const
        {
 
                ITERATE_t iHigh = this->GetSize() - 1;
                if (iHigh < 0)
                {
                        riCompareRes = COMPARE_Less;
                        return 0;
                }
 
                ITERATE_t iLow = 0;
                ITERATE_t i = 0;
                COMPARE_t iCompareRes = COMPARE_Less;
                while (iLow <= iHigh)
                {
                        i = (iHigh + iLow) / 2;
                        iCompareRes = this->CompareData(pNew, this->ConstElementAt(i)); // virtual call.
                        if (iCompareRes == COMPARE_Equal)
                                break;
                        if (iCompareRes > 0)
                        {
                                iLow = i + 1;
                        }
                        else
                        {
                                iHigh = i - 1;
                        }
                }
                riCompareRes = iCompareRes;
                return i;
        }
 
        template<class TYPE, class TYPE_ARG, typename TYPE_KEY>
        ITERATE_t cArraySorted<TYPE, TYPE_ARG, TYPE_KEY>::Add(TYPE_ARG pNew)
        {
                COMPARE_t iCompareRes;
                ITERATE_t index = FindINear(pNew, iCompareRes);
                if (iCompareRes == COMPARE_Equal)
                {
                        // duplicates don't normally happen, but just replace the old one just in case.
                        // DestructElements is called automatically for previous.
                        this->SetAt(index, pNew);
                        return index;
                }
                return AddPresorted(index, iCompareRes, pNew);
        }
 
        template<class TYPE, class TYPE_ARG, typename TYPE_KEY>
        ITERATE_t cArraySorted<TYPE, TYPE_ARG, TYPE_KEY>::FindINearKey(KEY_t key, COMPARE_t& riCompareRes) const
        {
 
                ITERATE_t iHigh = this->GetSize() - 1;
                if (iHigh < 0)
                {
                        riCompareRes = COMPARE_Less;
                        return 0;
                }
 
                ITERATE_t iLow = 0;
                ITERATE_t i = 0;
                COMPARE_t iCompareRes = COMPARE_Less;
                while (iLow <= iHigh)
                {
                        i = (iHigh + iLow) / 2;
                        iCompareRes = CompareKey(key, this->ConstElementAt(i));
                        if (iCompareRes == COMPARE_Equal)
                                break;
                        if (iCompareRes > 0)
                        {
                                iLow = i + 1;
                        }
                        else
                        {
                                iHigh = i - 1;
                        }
                }
 
                riCompareRes = iCompareRes;
                return i;
        }
 
        //********************************************************************
 
        template<class TYPE>
        class cArraySortVal : public cArraySorted < TYPE, TYPE, TYPE >
        {
 
        public:
                typedef cArraySorted<TYPE, TYPE, TYPE> SUPER_t;
                typedef typename SUPER_t::KEY_t KEY_t;
                typedef typename SUPER_t::REF_t REF_t;
 
        protected:
                virtual COMPARE_t CompareData(REF_t Data1, REF_t Data2) const noexcept override
                {
                        return cValT::Compare(Data1, Data2);
                }
                virtual COMPARE_t CompareKey(KEY_t Data1, REF_t Data2) const override
                {
                        return cValT::Compare(Data1, Data2);
                }
 
        public:
                virtual ~cArraySortVal()
                {
                }
 
                bool RemoveArgKey(TYPE Data1)
                {
                        return SUPER_t::RemoveArgKey(Data1, Data1);
                }
        };
 
        template<class TYPE, typename _TYPECH = char >
        class cArraySortStructName : public cArraySorted < TYPE, const TYPE&, const _TYPECH* >
        {
 
        public:
                typedef cArraySorted<TYPE, const TYPE&, const _TYPECH*> SUPER_t;
                typedef typename SUPER_t::REF_t REF_t;
                typedef typename SUPER_t::KEY_t KEY_t;
 
        protected:
                virtual COMPARE_t CompareData(REF_t Data1, REF_t Data2) const noexcept override
                {
                        return StrT::CmpI<_TYPECH>(Data1.get_Name(), Data2.get_Name());
                }
                virtual COMPARE_t CompareKey(KEY_t key1, REF_t Data2) const  override
                {
                        return StrT::CmpI<_TYPECH>(key1, Data2.get_Name());
                }
 
        public:
                virtual ~cArraySortStructName()
                {}
 
                const TYPE* FindArgForKey(KEY_t key1) const
                {
                        ITERATE_t index = FindIForKey(key1);
                        if (index < 0)
                                return nullptr;
                        return &(this->ConstElementAt(index));
                }
        };
 
        template<class TYPE, typename TYPE_KEY = int >
        class cArraySortStructValue : public cArraySorted < TYPE, const TYPE&, TYPE_KEY >
        {
 
        public:
                typedef cArraySorted<TYPE, const TYPE&, TYPE_KEY> SUPER_t;
                typedef typename SUPER_t::REF_t REF_t;
                typedef typename SUPER_t::KEY_t KEY_t;
 
        protected:
                virtual COMPARE_t CompareData(REF_t Data1, REF_t Data2) const noexcept override
                {
                        TYPE_KEY key1 = Data1.get_SortValue();
                        TYPE_KEY key2 = Data2.get_SortValue();
                        COMPARE_t iDiff = cValT::Compare(key1, key2);
                        if (iDiff == COMPARE_Equal)     // allow duplicate get_SortValue() but NOT duplicate objects!
                                return cValT::Compare((INT_PTR)&Data1, (INT_PTR)&Data2);
                        return iDiff;
                }
                virtual COMPARE_t CompareKey(KEY_t key1, REF_t Base) const override
                {
                        TYPE_KEY key2 = Base.get_SortValue();
                        return cValT::Compare(key1, key2);
                }
        public:
                virtual ~cArraySortStructValue()
                {}
 
                const TYPE* FindArgForKey(KEY_t key1) const
                {
                        ITERATE_t index = FindIForKey(key1);
                        if (index < 0)
                                return nullptr;
                        return &(this->ConstElementAt(index));
                }
        };
 
        template<class TYPE, typename _TYPE_HASH = HASHCODE_t >
        class cArraySortStructHash : public cArraySorted < TYPE, const TYPE&, _TYPE_HASH >
        {
 
        public:
                typedef cArraySorted<TYPE, const TYPE&, _TYPE_HASH> SUPER_t;
                typedef typename SUPER_t::REF_t REF_t;
                typedef typename SUPER_t::KEY_t KEY_t;
 
        protected:
                virtual COMPARE_t CompareData(REF_t Data1, REF_t Data2) const noexcept override
                {
                        _TYPE_HASH key1 = Data1.get_HashCode();
                        _TYPE_HASH key2 = Data2.get_HashCode();
                        return cValT::Compare(key1, key2);
                }
                virtual COMPARE_t CompareKey(KEY_t key1, REF_t Data2) const override
                {
                        _TYPE_HASH key2 = Data2.get_HashCode();
                        return cValT::Compare(key1, key2);
                }
        public:
                virtual ~cArraySortStructHash()
                {}
 
                const TYPE* FindArgForKey(KEY_t key1) const
                {
                        ITERATE_t index = FindIForKey(key1);
                        if (index < 0)
                                return nullptr;
                        return &(this->ConstElementAt(index));
                }
        };
 
        //********************************************************************
 
        template<class TYPE, class TYPE_PTR = TYPE, typename TYPE_KEY = TYPE>
        class cArraySortFacade : public cArraySorted < TYPE, TYPE_PTR, TYPE_KEY >
        {
 
        public:
                typedef cArraySorted<TYPE, TYPE_PTR, TYPE_KEY> SUPER_t;
                typedef typename SUPER_t::REF_t REF_t;
                typedef typename SUPER_t::ELEM_t ELEM_t;                                //
 
        protected:
                virtual COMPARE_t CompareData(REF_t pData1, REF_t pData2) const noexcept override
                {
                        return ::memcmp(pData1, pData2, sizeof(*pData1));
                }
 
        public:
                virtual ~cArraySortFacade()
                {
                        // Make sure virtuals are called correctly if storing a facade.
                        this->RemoveAll();
                }
 
                bool IsValidIndex(ITERATE_t i) const noexcept
                {
                        if (!SUPER_t::IsValidIndex(i))
                                return false;
                        return this->GetAt(i) != nullptr ;
                }
 
                REF_t GetAt(ITERATE_t index) const noexcept
                {
                        return this->ConstElementAt(index);
                }
                REF_t GetAtCheck(ITERATE_t nIndex) const
                {
                        if (!this->IsValidIndex(nIndex))
                        {
                                return nullptr;
                        }
                        return this->ConstElementAt(nIndex);
                }
 
                TYPE_PTR FindArgForKey(TYPE_KEY key1) const noexcept
                {
                        ITERATE_t index = this->FindIForKey(key1);
                        if (index < 0)
                                return nullptr;
                        return this->GetAt(index);
                }
                ITERATE_t FindIForAC_BRUTEFORCE(const TYPE_PTR pData) const
                {
                        if (pData == nullptr)
                                return k_ITERATE_BAD;
                        for (ITERATE_t nIndex = 0; nIndex < this->GetSize(); nIndex++)
                        {
                                if (this->m_pData[nIndex] == pData)
                                        return nIndex;
                        }
                        return k_ITERATE_BAD;
                }
 
                ELEM_t PopHead()
                {
                        if (!this->GetSize())
                        {
                                return nullptr;
                        }
                        return SUPER_t::PopHead();
                }
                ELEM_t PopTail()
                {
                        if (!this->GetSize())
                        {
                                return nullptr;
                        }
                        return SUPER_t::PopTail();
                }
 
                void DeleteAll()
                {
                        // NOTE: this may not always be safe for the type!
                        for (int i = 0; i < this->GetSize(); i++)
                        {
                                delete this->GetAt(i);
                        }
                        SUPER_t::RemoveAll();
                }
        };
 
        template<class TYPE, class TYPE_PTR, typename TYPE_KEY>
        class cArraySortFacadeValue : public cArraySortFacade < TYPE, TYPE_PTR, TYPE_KEY >
        {
 
        public:
                typedef cArraySortFacade<TYPE, TYPE_PTR, TYPE_KEY> SUPER_t;
                typedef typename SUPER_t::REF_t REF_t;
                typedef typename SUPER_t::KEY_t KEY_t;
 
        protected:
                virtual COMPARE_t CompareData(REF_t pData1, REF_t pData2) const noexcept override
                {
                        ASSERT(pData1 != nullptr);
                        ASSERT(pData2 != nullptr);
                        KEY_t key1 = pData1->get_SortValue();
                        KEY_t key2 = pData2->get_SortValue();
                        COMPARE_t iDiff = cValT::Compare(key1, key2);
                        if (iDiff == COMPARE_Equal)     // allow duplicate get_SortValue() but NOT duplicate objects!
                                return cValT::Compare((INT_PTR)pData1, (INT_PTR)pData2);
                        return iDiff;
                }
                virtual COMPARE_t CompareKey(KEY_t key1, TYPE_PTR pBase) const override
                {
                        if (pBase == nullptr)
                                return COMPARE_Greater;
                        KEY_t key2 = pBase->get_SortValue();
                        return cValT::Compare(key1, key2);
                }
 
        public:
                virtual ~cArraySortFacadeValue()
                {}
 
                ITERATE_t FindIForAK(const TYPE_PTR pBase) const
                {
                        if (pBase == nullptr)
                                return k_ITERATE_BAD;
                        TYPE_KEY nKey = pBase->get_SortValue();
                        ITERATE_t i = this->FindIFirstForKey(nKey);
                        if (i < 0)
                                return k_ITERATE_BAD;
                        for (;;)
                        {
                                if (this->GetAt(i) == pBase) // since sorted values are allowed to duplicate.
                                        return i;
                                if (++i >= this->GetSize())
                                        break;
                        }
                        // This probably shouldn't happen? pBase is not in the array!
                        return k_ITERATE_BAD;   // FindIForAC(pBase);   // just do a brute force search.
                }
 
                bool RemoveArgKey(TYPE_PTR pBase)
                {
                        ITERATE_t i = FindIForAK(pBase);
                        if (i < 0)
                                return false;
                        SUPER_t::RemoveAt(i);
                        return true;
                }
        };
 
        template<class TYPE, typename TYPE_KEY>
        class cArraySortPtrValue : public cArraySortFacadeValue < TYPE*, TYPE*, TYPE_KEY >
        {
        };
 
        template<class TYPE, class TYPE_PTR, typename _TYPE_HASH = HASHCODE_t >
        class cArraySortFacadeHash : public cArraySortFacade < TYPE, TYPE_PTR, _TYPE_HASH >
        {
 
        public:
                typedef cArraySortFacade<TYPE, TYPE_PTR, _TYPE_HASH> SUPER_t;
                typedef typename SUPER_t::REF_t REF_t;
                typedef typename SUPER_t::KEY_t KEY_t;
 
        public:
                virtual ~cArraySortFacadeHash()
                {}
 
                virtual COMPARE_t CompareData(REF_t pData1, REF_t pData2) const noexcept override
                {
                        _TYPE_HASH key1 = pData1->get_HashCode();
                        _TYPE_HASH key2 = pData2->get_HashCode();
                        return cValT::Compare(key1, key2);
                }
                virtual COMPARE_t CompareKey(KEY_t key1, REF_t pData2) const override
                {
                        _TYPE_HASH key2 = pData2->get_HashCode();
                        return cValT::Compare(key1, key2);
                }
        };
 
        template<class TYPE, typename TYPE_KEY>
        class cArraySortPtrHash : public cArraySortFacadeHash < TYPE*, TYPE*, TYPE_KEY >
        {
        };
 
 
        template<class TYPE, typename _TYPECH = GChar_t>
        class cArraySortPtrName : public cArraySortFacade < TYPE*, TYPE*, const _TYPECH* >
        {
 
        public:
                typedef cArraySortFacade<TYPE*, TYPE*, const _TYPECH*> SUPER_t;
                typedef typename SUPER_t::REF_t REF_t;
                typedef typename SUPER_t::KEY_t KEY_t;
 
        protected:
                virtual COMPARE_t CompareData(REF_t pData1, REF_t pData2) const noexcept override
                {
                        ASSERT(pData1 != nullptr);
                        ASSERT(pData2 != nullptr);
                        return StrT::CmpI<_TYPECH>(pData1->get_Name(), pData2->get_Name());
                }
                virtual COMPARE_t CompareKey(KEY_t key1, REF_t pObj) const override
                {
                        ASSERT(key1 != nullptr);
                        ASSERT(pObj != nullptr);
                        return StrT::CmpI<_TYPECH>(key1, pObj->get_Name());
                }
 
        public:
                virtual ~cArraySortPtrName()
                {}
 
                ITERATE_t FindIForAK(REF_t pBase) const
                {
                        if (pBase == nullptr)
                                return k_ITERATE_BAD;
                        return SUPER_t::FindIForKey(pBase->get_Name());
                }
                bool RemoveArgKey(KEY_t pBase)
                {
                        if (pBase == nullptr)
                                return false;
                        return SUPER_t::RemoveArgKey(pBase, pBase->get_Name());
                }
        };
}
#endif // _INC_cArraySort_H