TnbSet.h

[詳解]

#pragma once
#include "TnbCollection.h"
 
 
 
//TNB Library
namespace TNB
{
 
 
 
template<typename TYP>
class CSingleSetT : public IConstCollectionT<TYP>, public ISequenceCollectionT<TYP>
{
public:
 
    explicit CSingleSetT(size_t size = 0) : m_data(size)
    {
    }
 
    CSingleSetT(const CSingleSetT<TYP>& other)
    {
        m_data = other.m_data;
    }
    
    CSingleSetT& operator=(const CSingleSetT& other)
    {
        m_data = other.m_data;
        return *this;
    }
 
    virtual bool Lock(DWORD dwTime = INFINITE) const
    {
        return m_data.Lock(dwTime);
    }
 
    virtual void Unlock(void) const
    {
        m_data.Unlock();
    }
 
    virtual const TYP* ReferBuffer(void) const
    {
        return m_data.ReferBuffer();
    }
 
    virtual size_t GetSize(void) const
    {
        return m_data.GetSize();
    }
 
    virtual const TYP& At(INDEX index) const
    {
        return m_data[index];
    }
 
    const TYP& operator[](INDEX index) const
    {
        return m_data.At(index);
    }
 
    bool Remove(INDEX index)
    {
        return m_data.Remove(index);
    }
 
    virtual bool RemoveAll(void)
    {
        return m_data.RemoveAll();
    }
 
    bool Delete(const TYP& t)
    {
        INDEX i = GetEqualIndex(t);
        if ( i != INVALID_INDEX )
        {
            return m_data.Remove(i);
        }
        return false;
    }
 
    bool Has(const TYP& t) const
    {
        return GetEqualIndex(t) != INVALID_INDEX;
    }
 
    INDEX GetEqualIndex(const TYP& t) const
    {
        if ( IsEmpty() )
        {
            return INVALID_INDEX;
        }
        size_t sz = m_data.GetSize();
        if ( t < m_data[0] || m_data[sz - 1] < t )
        {
            return INVALID_INDEX;
        }
        INDEX f = 0;
        INDEX z = sz;
        while ( z > 0 )
        {
            INDEX x = z / 2;
            if ( m_data[f + x] < t )
            {
                // 大きい
                f += (x + 1);
                z = (z - 1) / 2;
            }
            else if ( t < m_data[f + x] )
            {
                // 小さい
                z /= 2;
            }
            else
            {
                return f + x;
            }
        }
        return INVALID_INDEX;
    }
 
    INDEX Insert(const TYP& t)
    {
        INDEX r = m_Insert(t);
        #ifdef _DEBUG
            if ( r != INVALID_INDEX )
            {
                if ( r >= 1 )
                {
                    ASSERT( ! (t < At(r - 1)) );
                }
                if ( r + 1 < GetSize() )
                {
                    ASSERT( ! (At(r + 1) < t) );
                }
            }
        #endif
        return r;
    }
 
    INDEX InsertEx(const TYP& t)
    {
        EXCLUSIVE( this );
        return Insert(t);
    }
 
    bool Insert(const IConstCollectionT<TYP>& t)
    {
        EXCLUSIVE( this );
        loop ( i, t.GetSize() )
        {
            if ( Insert(t.At(i)) == INVALID_INDEX )
            {
                return false;
            }
        }
        return true;
    }
 
    size_t InsertElements(size_t size, const TYP* P)
    {
        EXCLUSIVE( this );
        size_t cnt = 0;
        loop ( i, size )
        {
            if ( ! Has(*P) )
            {
                if ( Insert(*P) == INVALID_INDEX )
                {
                    return INVALID_SIZE;
                }
                cnt++;
            }
            P++;
        }
        return cnt;
    }
 
protected:
    virtual INDEX OnFoundEqual(INDEX index)
    {
        return index;
    }
 
    CVectorT<TYP> m_data;   
 
private:
    INDEX m_Insert(const TYP& t)
    {
        if ( IsEmpty() )
        {
            return m_data.Add(t);
        }
        size_t sz = m_data.GetSize();
        if ( t < m_data[0] )
        {
            m_data.Insert(0, t);
            return 0;
        }
        if ( m_data[sz - 1] < t )
        {
            return m_data.Add(t);
        }
        INDEX f = 0;
        INDEX z = sz;
        while ( z > 0 )
        {
            INDEX x = z / 2;
            if ( m_data[f + x] < t )
            {
                // 大きい
                f += (x + 1);
                z = (z - 1) / 2;
            }
            else if ( t < m_data[f + x] )
            {
                // 小さい
                z /= 2;
            }
            else
            {
                // 同じ値発見
                m_data[f + x] = t;
                return OnFoundEqual(f + x);
            }
        }
        if ( m_data[f] < t )
        {
            f++;
        }
        m_data.Insert(f, t);
        return f;
    }
    friend class CSetTest;
};
 
 
 
#if 0
 
template<typename TYP>
class CMultiSetT : public CSingleSetT<TYP>
{
public:
 
    INDEX Insert(const TYP& v)
    {
        loop ( i, m_data.GetSize() )
        {
            if ( v < m_data[i] || ! (m_data[i] < v) )
            {
                //その要素より小さいか同じ
                m_data.Insert(i, v);
                return i;
            }
        }
        m_data.Add(v);
        return m_data.GetSize() - 1;
    }
 
    bool Delete(const TYP& t)
    {
        TRange r = GetEqualRange(t);
        if ( r.lower != INVALID_INDEX )
        {
            m_data.RemoveElement(r.lower, (r.upper - r.lower) + 1);
            return true;
        }
        return false;
    }
 
    struct TRange
    {
        INDEX lower;
        INDEX upper;
    };
 
    TRange GetEqualRange(const TYP& v) const
    {
        TRange r = { INVALID_INDEX, INVALID_INDEX };
        size_t sz = m_data.GetSize();
        for ( INDEX i = 0; i < sz; i++ )
        {
            if ( m_IsEqual(v, m_data[i]) )
            {
                //同じ
                r.lower = i;
                i++;
                for ( ; i < sz; i++ )
                {
                    if ( v < m_data[i] || m_data[i] < v )
                    {
                        r.upper = i - 1;
                        break;
                    }
                }
                break;
            }
        }
        return r;
    }
    bool m_IsEqual(const TYP& t1, const TYP& t2) const
    {
        return ! (t1 < t2) && ! (t2 < t1);
    }
 
};
 
#endif
 
 
 
}; //TNB