TnbCollection.h

[詳解]

#pragma once
#include "TnbComparator.h"
#include "TnbStr.h"
#include "TnbSync.h"
#include "TnbException.h"
#include "TnbSerializer.h"
 
 
 
//TNB Library
namespace TNB
{
 
 
 
#ifndef _TnbDOXYGEN //Document作成用シンボル
 
// Input Iterator ベーステンプレート
template<typename COL, typename TYP> 
class CConstIteratorBaseT
{
    const COL * m_V;
    mutable INDEX   m_ind;
public:
    CConstIteratorBaseT(const COL* V = NULL, INDEX i = 0): m_V(V), m_ind(i) {}
    INDEX GetIndex(void) const { return m_ind; }
    TYP operator*(void) const { return m_V->Get(m_ind); }
    const TYP* operator->(void) const { return &(m_V->At(m_ind)); }
    bool operator==(const CConstIteratorBaseT& I) const
    {
        return m_V == I.m_V && m_ind == I.m_ind;
    }
    bool operator!=(const CConstIteratorBaseT& I) const
    {
        return m_V != I.m_V || m_ind != I.m_ind;
    }
    CConstIteratorBaseT& operator++(void) const
    {
        m_ind++;
        return *this;
    }
    CConstIteratorBaseT operator++(int) const
    {
        CConstIteratorBaseT I = *this;
        m_ind++;
        return I;
    }
    const TYP& operator[](INDEX i) const{ return m_V->At(m_ind+i);  }
    CConstIteratorBaseT& operator+=(INT_PTR i) {m_ind+=i; return *this;}
    CConstIteratorBaseT& operator-=(INT_PTR i) {m_ind-=i; return *this;}
};
 
// Randam Access Iterator ベースマクロ
#define _ITERATORCORE(NAME, COLL)                                       \
        COLL*   m_V;                                                    \
        mutable INDEX m_ind;                                            \
    public:                                                             \
        NAME(COLL* V = NULL, INDEX i = 0) : m_V(V), m_ind(i) {}         \
        INDEX GetIndex(void) const { return m_ind; }                    \
        bool operator==(const NAME& I) const {return m_ind==I.m_ind;}   \
        bool operator!=(const NAME& I) const {return m_ind!=I.m_ind;}   \
        bool operator<=(const NAME& I) const {return m_ind<=I.m_ind;}   \
        bool operator<(const NAME& I) const {return m_ind<I.m_ind;}     \
        bool operator>=(const NAME& I) const {return m_ind>=I.m_ind;}   \
        bool operator>(const NAME& I) const {return m_ind>I.m_ind;}     \
        NAME& operator+=(INT_PTR i)     {m_ind+=i; return *this;}       \
        NAME& operator-=(INT_PTR i)     {m_ind-=i; return *this;}       \
        NAME operator+(INT_PTR i) const {NAME I=*this; return I+=i;}    \
        NAME operator-(INT_PTR i) const {NAME I=*this; return I-=i;}    \
        INT_PTR operator-(const NAME& I) const {return m_ind-I.m_ind; } \
        NAME& operator++(void)      {m_ind++; return *this;}            \
        NAME& operator--(void)      {m_ind--; return *this;}            \
        NAME operator++(int)        {NAME I=*this; m_ind++; return I;}  \
        NAME operator--(int)        {NAME I=*this; m_ind--; return I;}
 
 
// Randam Access Iterator ベーステンプレート
template<typename COL, typename TYP> 
class CIteratorBaseT
{
    _ITERATORCORE(CIteratorBaseT, COL)
public:
    const TYP& operator*(void) const    { return m_V->At(m_ind);    }
    const TYP* operator->(void) const   { return &(m_V->At(m_ind)); }
    const TYP& operator[](INDEX i) const{ return m_V->At(m_ind+i);  }
    TYP& operator*(void)                { return m_V->Ref(m_ind);   }
    TYP* operator->(void)               { return &(m_V->Ref(m_ind));}
    TYP& operator[](INDEX i)            { return m_V->Ref(m_ind+i); }
};
 
#endif //_TnbDOXYGEN
 
 
 
template<typename TYP>
struct IConstCollectionT : ISynchronized, ISerializable, IComparableT<TNB::IConstCollectionT<TYP> >
{
    struct IChecker
    {
        virtual ~IChecker(void) {}  
        virtual bool IsValid(const TYP& T) const = 0;
    };
 
 
    //---------------------------------
 
 
    #ifndef _TnbDOXYGEN //Document作成用シンボル
    // const_iterator型
    typedef CConstIteratorBaseT<IConstCollectionT<TYP>, TYP> const_iterator;
    // value_type宣言
    typedef TYP value_type;
    #endif //_TnbDOXYEM
 
    const_iterator begin(void) const { return const_iterator(this, 0); }
 
    const_iterator end(void) const { return const_iterator(this, GetSize()); }
 
 
    //---------------------------------
 
 
    IConstCollectionT(void) 
    {
    }
 
    operator size_t(void) const 
    {
        return GetSize();
    }
 
    virtual size_t GetSize(void) const = 0;
 
    virtual const TYP& At(INDEX index) const = 0;
 
    virtual TYP Get(INDEX index) const
    {
        return At(index);
    }
 
    TYP GetEx(INDEX index) const
    {
        EXCLUSIVE(this);
        return At(index);
    }
 
    virtual size_t GetElements(size_t size, TYP* _P, INDEX offset = 0) const
    {
        EXCLUSIVE(this);
        if ( offset >= GetSize() )
        {
            return 0;
        }
        if ( size + offset > GetSize() )
        {
            size = GetSize() - offset;
        }
        for ( INDEX i = 0; i < size; i++ )
        {
            *_P++ = At(i + offset);
        }
        return size;
    }
 
    bool IsEmpty(void) const
    {
        return GetSize() == 0;
    }
 
    bool IsInRange(INDEX index) const
    {
        return TNB::IsInRange(index, GetSize());
    }
 
    virtual void Serialize(ISerializer& _sr) const
    {
        EXCLUSIVE(this);
        size_t l = GetSize();
        _sr << l << l;
        loop ( i, l )
        {
            _sr << At(i);
        }
    }
 
    virtual void Deserialize(const IDeserializer& ds)
    {
        throw CNotSupportException();
    }
 
    INDEX Find(const IChecker& checker, INDEX startIndex = 0, bool boIsReverse = false) const
    {
        EXCLUSIVE(this);
        if ( IsInRange(startIndex) )
        {
            size_t size = GetSize();
            for ( size_t i = startIndex; i < size; i++ )
            {
                if ( checker.IsValid(At(i)) ^ boIsReverse )
                {
                    return i;
                }
            }
        }
        return INVALID_INDEX;
    }
 
    INDEX Find(const IConstCollectionT<TYP>& t, const IComparatorT<TYP>& comparator, INDEX startIndex = 0) const
    {
        EXCLUSIVE(this);
        if ( IsInRange(startIndex) )
        {
            size_t size = GetSize();
            for ( size_t i = startIndex; i < size; i++ )
            {
                size_t tsz = t.GetSize();
                if ( i + tsz > size || tsz == 0 )
                {
                    break;
                }
                bool isFind = true;
                loop ( j, tsz )
                {
                    if ( ! comparator.IsEqualTo(At(i + j), t.At(j)) )
                    {
                        isFind = false;
                        break;
                    }
                }
                if ( isFind )
                {
                    return i;
                }
            }
        }
        return INVALID_INDEX;
    }
 
    INDEX Find(const IConstCollectionT<TYP>& t, INDEX startIndex = 0) const
    {
        return Find(t, IComparatorT<TYP>::GetDefault(), startIndex);
    }
 
    INDEX Find(const TYP& t, const IComparatorT<TYP>& comparator, INDEX startIndex = 0) const
    {
        EXCLUSIVE(this);
        if ( IsInRange(startIndex) )
        {
            size_t size = GetSize();
            for ( size_t i = startIndex; i < size; i++ )
            {
                if ( comparator.IsEqualTo(At(i), t) )
                {
                    return i;
                }
            }
        }
        return INVALID_INDEX;
    }
 
    INDEX Find(const TYP& t, INDEX startIndex = 0) const
    {
        return Find(t, IComparatorT<TYP>::GetDefault(), startIndex);
    }
 
    INDEX FindMax(const IComparatorT<TYP>& comparator, const TYP& def) const
    {
        EXCLUSIVE(this);
        TYP t = def;
        INDEX r = INVALID_INDEX;
        loop_dn ( i, GetSize() )
        {
            if ( comparator.CompareTo(At(i), t) >= 0 )
            {
                t = Get(i);
                r = i;
            }
        }
        return r;
    }
 
    INDEX FindMax(const TYP& def) const
    {
        return FindMax(IComparatorT<TYP>::GetDefault(), def);
    }
 
    INDEX FindMin(const IComparatorT<TYP>& comparator, const TYP& def) const
    {
        EXCLUSIVE(this);
        TYP t = def;
        INDEX r = INVALID_INDEX;
        loop_dn ( i, GetSize() )
        {
            if ( comparator.CompareTo(At(i), t) <= 0 )
            {
                t = Get(i);
                r = i;
            }
        }
        return r;
    }
 
    INDEX FindMin(const TYP& def) const
    {
        return FindMin(IComparatorT<TYP>::GetDefault(), def);
    }
 
    virtual INT_PTR Compare(const IConstCollectionT<TYP>& c) const
    {
        if ( this == &c )
        {
            return 0; 
        }
        EXCLUSIVE2(&c, this);
        const IComparatorT<TYP>& comparator = IComparatorT<TYP>::GetDefault();
        size_t mySize = GetSize();
        size_t youSize = c.GetSize();
        size_t size = (mySize < youSize) ? mySize : youSize;
        loop ( i, size )
        {
            INT_PTR r = comparator.CompareTo(At(i), c.At(i));
            if ( r != 0 )
            {
                return r;
            }
        }
        return mySize - youSize;
    }
 
    virtual bool IsEqual(const IConstCollectionT<TYP>& c) const
    {
        ASSERT( IComparatorT<TYP>::GetDefault().IsEqualTo(TYP(), TYP()) );
        if ( this == &c )
        { 
            return true; 
        }
        EXCLUSIVE2(&c, this);
        size_t size = GetSize();
        if ( size != c.GetSize() )
        {
            return false; 
        }
        const IComparatorT<TYP>& comparator = IComparatorT<TYP>::GetDefault();
        loop ( i, size )
        {
            if ( ! comparator.IsEqualTo(At(i), c.At(i)) )
            {
                return false;
            }
        }
        return true;
    }
 
private:
    void operator=(const IConstCollectionT& other);
};
 
 
 
template<typename TYP>
struct ICollectionT : IConstCollectionT<TYP>
{
    class CSort : CCopyImpossible
    {
        ICollectionT<TYP>*  m_piCollect;        
        const IComparatorT<TYP>*    m_piComparator;     
        bool                m_boIsReverse;      
        void m_qsort(size_t left, size_t right) 
        {
            if ( left >= right ){ return; }
            size_t j = left;
            for ( size_t i = left + 1; i <= right; i++ ) 
            {
                const TYP& c1 = m_piCollect->At(i);
                const TYP& c2 = m_piCollect->At(left);
                if ( (m_piComparator->CompareTo(c1, c2) < 0) ^ m_boIsReverse )
                {
                    m_piCollect->Swap(i, ++j);
                }
            }
            m_piCollect->Swap(left, j);
            //
            if ( j > 0 )
            {
                m_qsort(left, j - 1);
            }
            m_qsort(j + 1, right);
        }
 
    public:
    
        CSort(void) {}
 
        void QuickSort(ICollectionT<TYP>& _collect, const IComparatorT<TYP>& comp, bool boIsReverse = false)
        {
            m_piCollect     = &_collect;
            m_piComparator  = &comp;
            m_boIsReverse   = boIsReverse;
            size_t l = _collect.GetSize();
            if ( l > 0 )
            {
                m_qsort(0, l - 1);
            }
        }
 
        void BubbleSort(ICollectionT<TYP>& _collect, const IComparatorT<TYP>& comp, bool boIsReverse = false)
        {
            size_t size = _collect.GetSize();
            loop ( i, size )
            {
                for ( size_t j = size - 1; j > i; j-- )
                {
                    const TYP& c1 = _collect.At(j - 1);
                    const TYP& c2 = _collect.At(j);
                    if ( (comp.CompareTo(c1, c2) > 0) ^ boIsReverse )
                    {
                        _collect.Swap(j - 1, j);
                    }
                }
            }
        }
    };
 
 
    //------------------------------------
 
 
    #ifndef _TnbDOXYGEN //Document作成用シンボル
    // const_iterator型宣言
    typedef CConstIteratorBaseT<ICollectionT<TYP>, TYP> const_iterator;
    // iterator型宣言
    typedef CIteratorBaseT<ICollectionT<TYP>, TYP> iterator;
    #endif //_TnbDOXYEM
 
    const_iterator begin(void) const { return const_iterator(this, 0); }
 
    const_iterator end(void) const { return const_iterator(this, GetSize()); }
 
    iterator begin(void) { return iterator(this, 0); }
 
    iterator end(void) { return iterator(this, GetSize()); }
 
    void push_back(const TYP& t) { Add(t); }
 
 
    //------------------------------------
 
    
    ICollectionT(void) 
    {
    }
 
    virtual ~ICollectionT(void) 
    {
    }
 
    ICollectionT& operator=(const ICollectionT& other)
    {
        Copy(other);
        return *this;
    }
 
    virtual TYP& Ref(INDEX index) = 0;
 
    virtual bool Set(INDEX index, const TYP& t) = 0;
 
    bool SetEx(INDEX index, const TYP& t)
    {
        EXCLUSIVE(this);
        return Set(index, t);
    }
 
    virtual INDEX Add(const TYP& t) = 0;
 
    INDEX AddEx(const TYP& t)
    {
        EXCLUSIVE(this);
        return Add(t);
    }
 
    virtual bool Insert(INDEX index, const TYP& t)
    {
        size_t nowSize = GetSize();
        if ( index >= nowSize + 1 )
        {
            return false;
        }
        INDEX r = Add(TYP());
        if ( r == INVALID_INDEX )
        {
            return false;
        }
        loop_dn( i, nowSize - index )
        {
            Set(index + i + 1, At(index + i));
        }
        Set(index, t);
        return true;
    }
 
    virtual bool InsertEx(INDEX index, const TYP& t)
    {
        EXCLUSIVE(this);
        return Insert(index, t);
    }
 
    virtual bool Remove(INDEX index) = 0;
 
    bool RemoveEx(INDEX index)
    {
        EXCLUSIVE(this);
        return Remove(index);
    }
 
    virtual size_t RemoveElements(INDEX index, size_t size = 0)
    {
        size_t r = 0;
        if ( size == 0 )
        {
            size = INVALID_SIZE;
        }
        loop ( i, size )
        {
            if ( ! Remove(index) )
            {
                break;
            }
            r++;
        }
        return r;
    }
 
    virtual bool RemoveAll(void)
    {
        EXCLUSIVE(this);
        while ( ! IsEmpty() )
        {
            if ( ! Remove(0) )
            {
                return false;
            }
        }
        return true;
    }
 
    virtual void Swap(INDEX index1, INDEX index2)
    {
        if ( index1 != index2 )
        {
            EXCLUSIVE(this);
            TYP t = Get(index1);
            Set(index1, At(index2));
            Set(index2, t);
        }
    }
 
    virtual size_t AddElements(size_t size, const TYP* P = NULL)
    {
        EXCLUSIVE(this);
        if ( P != NULL )
        {
            loop ( i, size )
            {
                if ( Add(*P++) == INVALID_INDEX )
                {
                    return INVALID_SIZE; 
                }
            }
        }
        else
        {
            loop ( i, size )
            {
                if ( Add(TYP()) == INVALID_INDEX )
                {
                    return INVALID_SIZE; 
                }
            }
        }
        return size;
    }
 
    virtual size_t Append(const IConstCollectionT<TYP>& c)
    {
        EXCLUSIVE2(&c, this);
        size_t r = 0;
        loop ( i, c.GetSize() )
        {
            if ( Add(c.At(i)) == INVALID_INDEX )
            {
                return INVALID_SIZE;
            }
            r++;
        }
        return r;
    }
 
    virtual size_t CopyElements(size_t size, const TYP* P = NULL)
    {
        return SetElements(size, P);
    }
 
    virtual size_t SetElements(size_t size, const TYP* P = NULL)
    {
        if ( ! RemoveAll() )
        {
            return INVALID_SIZE; 
        }
        return AddElements(size, P);
    }
 
    virtual size_t Copy(const IConstCollectionT<TYP>& c)
    {
        if ( this != &c )
        {
            EXCLUSIVE2(&c, this);
            size_t l = c.GetSize();
            if ( SetSize(l) )
            {
                loop ( i, l )
                {
                    Set(i, c.At(i));
                }
            }
            return l;
        }
        return c.GetSize();
    }
 
    virtual size_t Cull(const IChecker& checker, bool boIsReverse = false)
    {
        EXCLUSIVE(this);
        size_t r = 0;
        if ( ! IsEmpty() )
        {
            loop_dn ( i, GetSize() )
            {
                if ( ! checker.IsValid(At(i)) ^ boIsReverse )
                {
                    if ( ! Remove(i) )
                    {
                        return INVALID_SIZE; 
                    }
                    r++;
                }
            }
        }
        return r;
    }
 
    virtual bool SetSize(size_t size)
    {
        EXCLUSIVE(this);
        if ( size == 0 )
        {
            return RemoveAll();
        }
        else
        {
            size_t nowSize = GetSize();
            if ( nowSize > size )
            {
                //今より小さく
                for ( size_t i = nowSize - 1; i >= size; i-- )
                {
                    if ( ! Remove(i) )
                    {
                        return false; 
                    }
                }
            }
            else if ( nowSize < size )
            {
                //今より大きく
                size_t l = (size - nowSize);
                return AddElements(l) == l;
            }
        }
        return true;
    }
 
    virtual void Deserialize(const IDeserializer& ds)
    {
        EXCLUSIVE(this);
        size_t l1, l2;
        ds >> l1 >> l2;
        if ( l1 != l2 )
        {
            throw CInvalidParamException();
        }
        RemoveAll();
        TYP t;
        loop ( i, l1 )
        {
            ds >> t;
            Add(t);
        }
    }
 
    bool Sort(const IComparatorT<TYP>& comparator, bool boIsReverse = false, bool boIsBubble = false)
    {
        EXCLUSIVE(this);
        CSort sort;
        bool boRc = true;
        try
        {
            if ( boIsBubble )
            {
                sort.BubbleSort(*this, comparator, boIsReverse);
            }
            else
            {
                sort.QuickSort(*this, comparator, boIsReverse);
            }
        }
        catch(CTnbException& e)
        {
            e.OnCatch();
            boRc = false;
        }
        return boRc;
    }
 
    bool Sort(bool boIsReverse = false, bool boIsBubble = false)
    {   
        return Sort(IComparatorT<TYP>::GetDefault(), boIsReverse, boIsBubble);
    }
 
    bool Shuffle(int iDepth = 1)
    {
        EXCLUSIVE(this);
        bool boRc = true;
        try
        {
            size_t size = GetSize();
            if ( size > 1 )
            {
                loop ( j, iDepth )
                {
                    loop ( i, size )
                    {
                        size_t r = rand() % size;
                        if ( r == i )
                        {
                            r = rand() % size; 
                        } 
                        Swap(i, r);
                    }
                }
            }
        }
        catch(CTnbException& e)
        {
            e.OnCatch();
            boRc = false;
        }
        return boRc;
    }
 
    size_t TrimBottom(const TYP& t, const IComparatorT<TYP>& comparator)
    {
        EXCLUSIVE(this);
        size_t len = GetSize();
        if ( len > 0 )
        {
            loop ( i, len ) 
            {
                if ( ! comparator.IsEqualTo(At(len - 1 - i), t) )
                {
                    SetSize(len - i);
                    return len - i;
                }
            }
            RemoveAll();
            return 0;
        }
        return len;
    }
 
    size_t TrimBottom(const TYP& t)
    {
        return TrimBottom(t, IComparatorT<TYP>::GetDefault());
    }
};
 
 
 
template<typename TYP>
class ICollectionMidT : public ICollectionT<TYP>
{
    DEFSUPER(ICollectionT<TYP>);
protected:
 
    virtual const TYP* m_GetConstPointer(INDEX index) const = 0;
 
    virtual TYP* m_GetPointer(INDEX index) = 0;
 
public:
 
    ICollectionMidT(void) : _super()
    {
    }
 
    virtual TYP Get(INDEX index) const
    {
        const TYP* P = m_GetConstPointer(index);
        if ( P != NULL )
        {
            return *P; 
        }
        throw CIndexOutOfBoundsException();
    }
 
    virtual const TYP& At(INDEX index) const
    {
        const TYP* P = m_GetConstPointer(index);
        if ( P != NULL )
        {
            return *P;
        }
        throw CIndexOutOfBoundsException();
    }
 
    virtual TYP& Ref(INDEX index)
    {
        TYP* P = m_GetPointer(index);
        if ( P == NULL )
        {
            throw CNotSupportException();
        }
        return *P;
    }
 
    virtual bool Set(INDEX index, const TYP& t)
    {
        TYP* P = m_GetPointer(index);
        if ( P == NULL )
        {
            return false; 
        }
        *P = t;
        return true;
    }
 
    const TYP& operator[](INDEX index) const
    {
        return At(index);
    }
 
    TYP& operator[](INDEX index)
    {
        TYP* P = m_GetPointer(index);
        if ( P != NULL )
        {
            return *P;
        }
        throw CIndexOutOfBoundsException();
    }
};
 
 
 
template<typename TYP>
struct ISequenceCollectionT
{
    virtual ~ISequenceCollectionT(void) {}
 
    virtual const TYP* ReferBuffer(void) const = 0;
 
    virtual size_t GetSize(void) const = 0;
};
 
 
 
namespace HASH
{
    template<typename TYP>
    inline DWORD CalcHash(const IConstCollectionT<TYP>& c)
    {
        EXCLUSIVE(&c);
        DWORD dwRc = 0;
        loop ( i, c.GetSize() )
        {
            dwRc += c.At(i) << (i & 0x0F);
        }
        return dwRc;
    }
};
 
 
 
}; // TNB