xmap.h

BCB的学习资料

//---------------------------------------------------------------------------

#ifndef XMapH
#define XMapH
#ifndef XArrayH
#include <XArray.h>
#endif
//---------------------------------------------------------------------------
namespace zdhsoft
{
/*
///////////////////////////////////////////////////////////////////////////////
[Name]XMap<K,V>
[Title]Map类
///////////////////////////////////////////////////////////////////////////////
[Description]
    这个类提供一些基本的Map功能.该类是基于动态有序数组的,查找方式用二分查找.
    这个提供了两个属性,用于访问Key和Value.
    通过比较测试,性能和BCB中的std::map差不多.
    主要的方法:
    Clear();
    operator[]
    operator=
    DeleteByIndex
    DeleteByKey
    主要的属性
    Length
    Value[]
    Key[]
[Version]1.0
[Author]Rex Winter
[Date]2004-12-20
///////////////////////////////////////////////////////////////////////////////
*/
template<class K,class V>
class XMap
{
private:
    //定义一个Entry类,主要是为了方便存放元素
    //这是一个在XMap使用的类
    template<class K,class V>
    class XEntry
    {
    public:
        XEntry(const K & key)
            :Key(key)
        {}
        XEntry(const K & key,const V & value)
            :Key(key),Value(value)
        {}
    public:
        K Key;
        V Value;
    };
    //定义Entry类型和Entry *类型
    typedef XEntry<K,V> Entry;
    typedef Entry * EntryPointer;
public:
    //
    XMap();
    ~XMap();
    //common method
    void Clear();                   //清除所有元素
    V & operator[](const K & key);  //取得key对应的的Value
    XMap<K,V> & operator = (const XMap<K,V> & map); //

    void DeleteByKey(const K & key)  //删除关键字Key == key的元素
    {
        DeleteByIndex(GetIndexByKey(key));
    }
    void DeleteByIndex(int Index);    //删除下标为Index的元素
    bool Empty() const              //判断map是否为空,如果为空,则返回true,否则返回false
    {
        if( m_Data.GetLength()>0 ) return false;
        else return true;
    }
    bool Contains(const K & key ) const    //判断关键字Key==key的元素是否被包含
    {
        if( GetIndexByKey(key) != -1 ) return true;
        else return false;
    }
    int GetIndexByKey(const K & Key) const;
    //property
    __property int Length = { read = GetLength };               //元素个数
    __property V Value[int Index] = { read = GetValueByIndex }; //根据下标取Value
    __property const K Key[int Index] = { read = GetKeyByIndex }; //根据下标取Key

    //property method
    int GetLength() const { return m_Data.GetLength(); }
    V GetValueByIndex(int Index) const { return m_Data[Index]->Value; }
    const K GetKeyByIndex(int Index) const { return m_Data[Index]->Key; }
public:    
    //private method
    void _Insert(EntryPointer entry);
    //class field
    XDynamicArray<EntryPointer> m_Data;
};

/*
////////////////////////////////////////////////////////////////////////////////
[Name]_Insert
[Title]插入一个元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <EntryPointer entry>被插入的元素
[Description]
    向map中,插入一个元素
[Version]1.0
[Author]Rex Winter
[Date]2004-12-20
////////////////////////////////////////////////////////////////////////////////
*/
template<class K,class V>
void XMap<K,V>::_Insert(EntryPointer entry)
{
    const EntryPointer * dataArray = m_Data.Data();
    EntryPointer tmpEntry;
    int len = Length;
    if( len==0 )
    {
        m_Data.Append(entry);
        return;
    }
    int Low = 0,High = len-1,Mid;
    while ( Low <= High )
    {
        Mid = (Low + High)/2;
        tmpEntry = dataArray[Mid];
        if( tmpEntry->Key == entry->Key ) return;
        else if( tmpEntry->Key > entry->Key ) High = Mid - 1;
        else Low = Mid + 1;
    }
    if( dataArray[Mid]->Key > entry->Key ) m_Data.Insert(Mid,entry);
    else m_Data.Insert(Mid+1,entry);
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]GetIndexByKey
[Title]取Key的下标
////////////////////////////////////////////////////////////////////////////////
[param]
    <const K & key>Key 元素的Key
[Return]
    <int>如果Key该存在,则返回该元素的下标
        不存在的话返回-1
[Description]
    取元素的下标
[Version]1.0
[Author]Rex Winter
[Date]2004-12-20
////////////////////////////////////////////////////////////////////////////////
*/
template<class K,class V>
int XMap<K,V>::GetIndexByKey(const K & Key) const
{
    const EntryPointer * dataArray = m_Data.Data();
    int len = Length;
    int Low = 0,High = len-1,Mid;
    while( Low <= High )
    {
        Mid = (Low + High)/2;
        EntryPointer tmpEntry = dataArray[Mid];
        if( tmpEntry->Key == Key ) return Mid;
        else if( tmpEntry->Key > Key ) High = Mid - 1;
        else Low = Mid + 1;
    }
    return -1;
}

/*
////////////////////////////////////////////////////////////////////////////////
[Name]DeleteByIndex
[Title]删除指定下标的元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <int>Index 被删除元素的下标
[Description]
    删除指定下标的元素,如果被删除的元素,在有效的范围内,则执行删除
[Version]1.0
[Author]Rex Winter
[Date]2004-12-20
////////////////////////////////////////////////////////////////////////////////
*/
template<class K,class V>
void XMap<K,V>::DeleteByIndex(int Index)
{
    if(Index<Length && Index>=0)
    {
        delete m_Data[Index];
        m_Data.Delete(Index);
    }
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]XMap
[Title]构造函数
////////////////////////////////////////////////////////////////////////////////
[Description]
    构造函数
[Version]1.0
[Author]Rex Winter
[Date]2004-12-20
////////////////////////////////////////////////////////////////////////////////
*/

template<class K,class V>
XMap<K,V>::XMap()
{}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]~XMap
[Title]析构函数
////////////////////////////////////////////////////////////////////////////////
[Description]
    析构函数,这里会先清除所有元素
[Version]1.0
[Author]Rex Winter
[Date]2004-12-20
////////////////////////////////////////////////////////////////////////////////
*/

template<class K,class V>
XMap<K,V>::~XMap()
{
    Clear();
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]Clear
[Title]清除map中的所有元素
////////////////////////////////////////////////////////////////////////////////
[Description]
    清除map中的所有元素
[Version]1.0
[Author]Rex Winter
[Date]2004-12-20
////////////////////////////////////////////////////////////////////////////////
*/

template<class K,class V>
void XMap<K,V>::Clear()
{
    int len = Length;
    for(int i=0;i<len;i++)
    {
        delete m_Data[i];
    }
    m_Data.Clear();
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]operator []
[Title]取值
////////////////////////////////////////////////////////////////////////////////
[param]
    <const K & key>Key 元素的Key
[Return]
    <V &>如果有这个关键字的元素,则返回这个元素的值
         如果没有,则返回空,这个空,指元素值这个对象,缺省构造产生的值
[Description]
    取关键字为Key的值
[Version]1.0
[Author]Rex Winter
[Date]2004-12-20
////////////////////////////////////////////////////////////////////////////////
*/

template<class K,class V>
V & XMap<K,V>::operator[](const K & key)
{
    int Index = GetIndexByKey(key);
    if( Index != -1 ) return m_Data[Index]->Value;
    else
    {
        EntryPointer entry = new Entry(key);
        _Insert(entry);
        return entry->Value;
    }
}


/*
////////////////////////////////////////////////////////////////////////////////
[Name]operator =
[Title]复制map对象
////////////////////////////////////////////////////////////////////////////////
[param]
    <const XMap<K,V> &>map  被复制的对象
[Return]
    <XMap<K,V> &>返回当前对象的引用
[Description]
    复制map对象
[Version]1.0
[Author]Rex Winter
[Date]2004-12-20
////////////////////////////////////////////////////////////////////////////////
*/

template<class K,class V>
XMap<K,V> & XMap<K,V>::operator = (const XMap<K,V> & map)
{
    if( this == &map ) return *this; // if it is itself then return;
    int srcLen = map.m_Data.Length;
    int desLen = Length;
    int len = (srcLen>desLen)?desLen:srcLen;
    const EntryPointer * srcEntryArray, *desEntryArray;
    srcEntryArray = map.m_Data.Data();
    desEntryArray = m_Data.Data();
    EntryPointer srcEntry,desEntry;
    for(int i=0;i<len;i++)
    {
        srcEntry = *srcEntryArray++;
        desEntry = *desEntryArray++;
        desEntry->Key = srcEntry->Key;
        desEntry->Value = srcEntry->Value;
        srcEntryArray++;
        desEntryArray++;
    }
    //if need append element then
    if( srcLen > len )
    {
        for(int i=len;i<srcLen;i++)
        {
            srcEntry = *srcEntryArray++;
            EntryPointer = tmpEntry = new Entry(srcEntry->Key,srcEntry->Value);
            m_Data.Append(tmpEntry);
        }
    }
    else if( desLen > len )  //if need delete more than len
    {
        int BeginIndex = len,DeleteCount = desLen-len;
        for(int i=len;i<desLen;i++)
        {
            delete m_Data[i];
        }
        m_Data.DeleteRange(BeginIndex,DeleteCount);
    }
    return *this;
}



}
#endif