xset.h

BCB的学习资料

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

#ifndef XSetH
#define XSetH
#ifndef XArrayH
#include <XArray.h>
#endif
//---------------------------------------------------------------------------
namespace zdhsoft
{

/*
///////////////////////////////////////////////////////////////////////////////
[Name]XSet<T>
[Title]集合类
///////////////////////////////////////////////////////////////////////////////
[Description]
    修改了构造函数，让它能事情准备好一定的元素，到动态数组
    给一些方法增加了const，如==,!=，[]等操作运算符
    对大部分代码做了调整，优化了代码
[Version]2.2
[Author]Rex Winter
[Date]2005-6-22
[Test]
    2005-6-22　完成对XSet所有方法的测试
///////////////////////////////////////////////////////////////////////////////
[Description]
    新增了一个构造函数XSet<T>(const T &);
    修改了一些方法的参数，将其参数设为const T & 避免产生一些没有必要的代码
    修改了一个Bug
[Version]2.1
[Author]Rex Winter
[Date]2005-3-26
///////////////////////////////////////////////////////////////////////////////
[Description]
    这是一个集合类
    这个类的元素存放是一个有序的数组。
    这个类的元素查找方法为二分查找。
    这个类提供了类相关的所有功能
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
///////////////////////////////////////////////////////////////////////////////
*/
template<class T>
class XSet
{
public:
    XSet(int iPrepareLength = 0);
    XSet(const XSet<T> & rhs);
    XSet(const T & vMin,const T & vMAX,int iPrepareLength = 0);
    //XSet(const T & v,int iPrepareLength = 0);
    void Clear();   //清空集合
    XSet<T> & operator << (const T & data); //加入一个元素
    XSet<T> & operator >> (const T & data); //删除一个元素
    XSet<T> & operator << (const XSet<T> & rhs); //加入一个集合中的有元素
    XSet<T> & operator >> (const XSet<T> & rhs); //删除一个集合中的有元素
    void Add(const T & data);     //加入一个元素
    void Add(const XSet<T> & rhs); //加入一个集合中的有元素
    void Delete(const T & data);  //删除一个元素
    void Delete(const XSet<T> & rhs);//删除一个集合中的有元素
    bool Contains(const T & data) const;
    bool Contains(const XSet<T> & rhs) const;
    int GetLength() const { return m_Data.GetLength(); }
    T & operator[](int Index);
    const T & operator[](int Index) const;
    bool Empty() const;
    XSet<T> & operator=(const XSet<T> & rhs);

    XSet<T> operator-(const XSet<T> & rhs) const; //差集
    XSet<T> operator+(const XSet<T> & rhs) const; //合集
    XSet<T> operator*(const XSet<T> & rhs) const; //交集

    XSet<T> SubSet(const T & MinData,const T & MaxData) const;

    XSet<T> & operator-=(const XSet<T> & rhs); //差集
    XSet<T> & operator+=(const XSet<T> & rhs); //合集
    XSet<T> & operator*=(const XSet<T> & rhs); //交集


    bool operator == (const XSet<T> & rhs) const;
    bool operator != (const XSet<T> & rhs) const;
public:
    __property int Length = { read = GetCount };    
private:
    int _Contains(const T & data) const;//采用二分查找
    void _Insert(const T & data); //插入一个元素
    int GetCount() { return m_Data.GetLength(); } //这个主要供属Length使用
private:
    XDynamicArray<T> m_Data;//存放集合数据的数组
};
//---------------------------------------------------------------------------
/*
////////////////////////////////////////////////////////////////////////////////
[Name]Clear
[Title]清空集合
////////////////////////////////////////////////////////////////////////////////
[param]
[Description]
    清空集合
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
void XSet<T>::Clear()
{
    m_Data.Clear();
};
/*
////////////////////////////////////////////////////////////////////////////////
[Name]operator <<
[Title]插入一个元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <const T> data 将被插入的元素
[Return]
    <XSet<T> &> 返回当前集合的引用
[Description]
    向集合中，填加一个元素
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
XSet<T> & XSet<T>::operator << (const T & data)
{
    Add(data);
    return *this;
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]operator >>
[Title]删除一个元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <const T> data 将被删除的元素
[Return]
    <XSet<T> &> 返回当前集合的引用
[Description]
    向集合中，删除一个元素，如果该元素存在的话，那就删除
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
XSet<T> & XSet<T>::operator >> (const T & data)
{
    Delete(data);
    return *this;
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]operator <<
[Title]填加一个集合中元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <const XSet<T> &> rhs 将被添加的集合
[Return]
    <XSet<T> &> 返回当前集合的引用
[Description]
    将一个集合的元素添加到当前集合
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
XSet<T> & XSet<T>::operator << (const XSet<T> & rhs)
{
    Add(rhs);
    return *this;
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]operator >>
[Title]删除一个集合中元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <const XSet<T> &> rhs 将被删除的集合
[Return]
    <XSet<T> &> 返回当前集合的引用
[Description]
    从当前集合中，删除该集合拥有的元素
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
XSet<T> & XSet<T>::operator >> (const XSet<T> & rhs)
{
    Delete(rhs);
    return *this;
}

/*
////////////////////////////////////////////////////////////////////////////////
[Name]Add
[Title]插入一个元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <const T> data 将被插入的元素
[Description]
    向集合中，填加一个元素
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
void XSet<T>::Add(const T & data)
{
    _Insert(data);
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]Add
[Title]插入一个集合的元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <const XSet<T> &> rhs 将被插入的元素
[Description]
    当集合中，所有元素插入到当前集合中
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
void XSet<T>::Add(const XSet<T> & rhs)
{
    if( this != &rhs )
    {
        const T * Data = rhs.m_Data.Data();
        int iLength = rhs.GetLength();
        for( int i=0; i<iLength; i++) Add( *Data++ );
    }
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]Delete
[Title]删除元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <const T> data 将被删除的元素
[Description]
    删除当前集合中指定的元素
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
void XSet<T>::Delete(const T & data)
{
    int Index = _Contains(data);
    if( Index > -1 ) m_Data.Delete(Index);
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]Delete
[Title]删除一个集合中拥有的元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <const XSet<T> &> rhs被删除元素的集合
[Description]
    删除在集合中有的元素
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
void XSet<T>::Delete(const XSet<T> & rhs)
{
    if( this != &rhs )
    {
        const T * Data = rhs.m_Data.Data();
        int iLength = rhs.m_Data.GetLength();
        Data += iLength;
        for(int i=0; i<iLength; i++) Delete(*(--Data));
    }
    else Clear();
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]_Contains
[Title]包含元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <const T > data 被检查的元素
[Return]
    <int> 返回该元素所在下标，如果不存在则返回-1
[Description]
    检查该元素是否被包含，如果被包含，则返回其下标
    否则返回-1
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
int XSet<T>::_Contains(const T & data) const
{
    const T * DataArray = m_Data.Data();
    int Count = m_Data.GetLength();
    int Low = 0,High = Count-1,Mid;
    while( Low <= High )
    {
        Mid = (Low + High) /2;
        T Tmp = DataArray[Mid];
        if( Tmp == data ) return Mid;
        else if ( Tmp > data ) High = Mid -1;
        else Low = Mid + 1;
    }
    return -1;
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]Contains
[Title]包含元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <const T &> data 被检查的元素
[Return]
<bool> 如果该元素存在，则返回true,否则返回-1
[Description]
    检查该元素是否被包含
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
bool XSet<T>::Contains(const T & data) const
{
    if( _Contains(data) > -1 )  return true;
    else return false;
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]Contains
[Title]包含集合
////////////////////////////////////////////////////////////////////////////////
[param]
    <const XSet<T> &> rhs 被检查的集合
[Return]
<bool> 如果该集合被包含，则返回true,否则返回-1
[Description]
    检查该集合是否被包含
[Version]1.0
[Author]Rex Winter
[Date]2005-6-22
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
bool XSet<T>::Contains(const XSet<T> & rhs) const
{
    if( this == &rhs ) return true;
    if( rhs.Empty() ) return true;
    int iLength = rhs.m_Data.GetLength();
    if( iLength > m_Data.GetLength() ) return false;
    const T * Data = rhs.m_Data.Data();
    for(int i=0; i<iLength; i++,Data++)
    {
        if( !Contains(*Data) ) return false;
    }
    return true;
}

/*
////////////////////////////////////////////////////////////////////////////////
[Name]_Insert
[Title]插入一个元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <const T > data 被插入集合
[Description]
    向当前集合中，插入一个元素
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
void XSet<T>::_Insert(const T & data)
{
    int iLength = m_Data.GetLength();
    if( iLength == 0 )
    {
        m_Data.Append( data );
        return;
    }
    const T * DataArray = m_Data.Data();
    //查找插入的位置
    int Low = 0,High = iLength-1,Mid;
    while( Low <= High )
    {
        Mid = (Low + High) /2;
        T Tmp = DataArray[Mid];
        if( Tmp == data ) return; //如果已有该元素，则返回
        else if ( Tmp > data ) High = Mid -1;
        else Low = Mid + 1;
    }
    if( DataArray[Mid] > data ) m_Data.Insert(Mid,data);
    else m_Data.Insert(Mid+1,data);
}
/*
////////////////////////////////////////////////////////////////////////////////
[Name]operator[]
[Title]取元素
////////////////////////////////////////////////////////////////////////////////
[param]
    <int T > Index 要取的数组下标
[Return]
    <T>返回当前元素    
[Description]
    取指定下标的元素
[Version]2.0
[Author]Rex Winter
[Date]2004-12-9
////////////////////////////////////////////////////////////////////////////////
*/
template<class T>
T & XSet<T>::operator[](int Index)
{
    return m_Data[Index];
}
template<class T>
const T & XSet<T>::operator[](int Index) const