#include  <algorithm>
#include  "afxtempl.h"

//TYPE类必须有<
template<class TYPE, class ARG_TYPE>
void Sort(CArray<TYPE,ARG_TYPE>& dest)
{
 std::sort(dest.GetData(),dest.GetData()+dest.GetSize());
}

//构造一个有序序列，该序列仅保留第一个序列中存在的而第二个中不存在的元素。
//src1,src2必须已排序
template<class TYPE, class ARG_TYPE>
void SetDifference(CArray<TYPE,ARG_TYPE>& dest,const CArray<TYPE,ARG_TYPE>& src1,const CArray<TYPE,ARG_TYPE>& src2)
{
 dest.SetSize(src1.GetSize());
 const TYPE* p = std::set_difference(src1.GetData(),src1.GetData()+src1.GetSize(),
   src2.GetData(),src2.GetData()+src2.GetSize(),
   dest.GetData());
 dest.SetSize(p-dest.GetData());
};

//构造一个有序序列，包含两个序列中所有的不重复元素。
//src1,src2必须已排序
template<class TYPE, class ARG_TYPE>
void SetUnion(CArray<TYPE,ARG_TYPE>& dest,const CArray<TYPE,ARG_TYPE>& src1,const CArray<TYPE,ARG_TYPE>& src2)
{
 dest.SetSize(src1.GetSize()+src2.GetSize());
 const TYPE* p = std::set_union(src1.GetData(),src1.GetData()+src1.GetSize(),
   src2.GetData(),src2.GetData()+src2.GetSize(),
   dest.GetData());
 dest.SetSize(p-dest.GetData());
};

//构造一个有序序列，其中元素在两个序列中都存在。
//src1,src2必须已排序
template<class TYPE, class ARG_TYPE>
void SetIntersection(CArray<TYPE,ARG_TYPE>& dest,const CArray<TYPE,ARG_TYPE>& src1,const CArray<TYPE,ARG_TYPE>& src2)
{
 dest.SetSize(min(src1.GetSize(),src2.GetSize()));
 const TYPE* p = std::set_intersection(src1.GetData(),src1.GetData()+src1.GetSize(),
   src2.GetData(),src2.GetData()+src2.GetSize(),
   dest.GetData());
 dest.SetSize(p-dest.GetData());
};

//构造一个有序序列，该序列取两个序列的对称差集(并集-交集)
//src1,src2必须已排序
template<class TYPE, class ARG_TYPE>
void SetSymmetricDifference(CArray<TYPE,ARG_TYPE>& dest,const CArray<TYPE,ARG_TYPE>& src1,const CArray<TYPE,ARG_TYPE>& src2)
{
 dest.SetSize(src1.GetSize()+src2.GetSize());
 const TYPE* p = std::set_symmetric_difference(src1.GetData(),src1.GetData()+src1.GetSize(),
   src2.GetData(),src2.GetData()+src2.GetSize(),
   dest.GetData());
 dest.SetSize(p-dest.GetData());
};

 

CString LngArrToStr(const CArray<long,const long&>& src)//将long数组转成str，方便排错
{
 CString str;
 str.Format("%d个元素 ",src.GetSize());
 for(int i = 0 ; i < src.GetSize() ; i++ )
 {
  CString s;
  s.Format("%d ",src[i]);
  str += s;
 }
 return str;
}

void GongNengCeShi()//功能测试
{
 srand(GetTickCount());
    const int iNum = 11;
 CArray<long,const long&> src1,src2;
 src1.SetSize(iNum);
 src2.SetSize(iNum);
 for( int i = 0 ; i < iNum ; i++)
 {
  src1[i] = rand()%10;
  src2[i] = rand()%10;
 }

 const CString str1 = LngArrToStr(src1);
 const CString str2 = LngArrToStr(src2);

 Sort(src1);
 Sort(src2);

 const CString str3 = LngArrToStr(src1);
 const CString str4 = LngArrToStr(src2);

 CArray<long,const long&> dst;
 SetDifference(dst,src1,src2);
 const CString str5 = LngArrToStr(dst);

 SetUnion(dst,src1,src2);
 const CString str6 = LngArrToStr(dst);
 
 SetIntersection(dst,src1,src2);
 const CString str7 = LngArrToStr(dst);

 SetSymmetricDifference(dst,src1,src2);
 const CString str8 = LngArrToStr(dst);
}

//给数组增加元素，可以连续调用。
template<class TYPE, class ARG_TYPE>
class CTestArray : public CArray<TYPE,ARG_TYPE>
{
public:
 CTestArray<TYPE,ARG_TYPE>& AddLianXu(ARG_TYPE newElement)
 {
  Add(newElement);
  return *this;
 };
};

void BianJieCheShi()//边界测试
{
 CTestArray<long,const long&> src1,src2;
 src1.AddLianXu(1).AddLianXu(2).AddLianXu(3);
 Sort(src1);
 Sort(src2);

 CArray<long,const long&> dst;
 //结果就是src1
 SetDifference(dst,src1,src2);
 const CString str1 = LngArrToStr(dst);
 //结果为空
 SetDifference(dst,src1,src1);
 const CString str2 = LngArrToStr(dst);

 CTestArray<long,const long&> src3;
 src3.AddLianXu(4).AddLianXu(5);
 //无重无元素
 SetUnion(dst,src1,src3);
 const CString str3 = LngArrToStr(dst);
 //全部是重复元素
 SetUnion(dst,src1,src1);
 const CString str4 = LngArrToStr(dst);

 //无重无元素
 SetIntersection(dst,src1,src3);
 const CString str5 = LngArrToStr(dst);
 //全部是重复元素
 SetIntersection(dst,src1,src1);
 const CString str6 = LngArrToStr(dst);

 //无重无元素
 SetSymmetricDifference(dst,src1,src3);
 const CString str7 = LngArrToStr(dst);
 //全部是重复元素
 SetSymmetricDifference(dst,src1,src1);
 const CString str8 = LngArrToStr(dst);

}