//頭文件:		Chrom.hpp
//目的:			為染色體提供基類
//語言:			VC++ 6.0
//時間:			1999年6月~2000年1月
//作者:			劉康
//環境:			Win32
//////////////////////////////////////////////////////////////////////

#include <stdlib.h>
#include <time.h>
#include <math.h>
#include "chrom.hpp"

//染色體初始化種子初始化
unsigned Chromosome::Seed = 0;

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

//構造函數
Chromosome::Chromosome()
{
	GeneLen = 0;
	Gene = NULL;
	geneStr = NULL;
}
Chromosome::Chromosome(int l)
{
	GeneLen = l;
	geneStr = new char[GeneLen+1];
	Init();
}
Chromosome::Chromosome(const Chromosome &c)
{
	ChromNum = c.ChromNum;
	GeneLen = c.GeneLen;
	Gene = new OneChmType[ChromNum];
	geneStr = new char[GeneLen+1];
	for(int i=0; i<ChromNum; i++)
		Gene[i] = c.Gene[i];
}

//析構函數
Chromosome::~Chromosome()
{
	if(Gene) delete []Gene;
	if(geneStr) delete[]geneStr;
}

/////////////////////////////////////////////////////////////////////
//私有函數
/////////////////////////////////////////////////////////////////////

//染色體初始化
void Chromosome::Init()
{
	ChromNum = GeneLen/(sizeof(OneChmType)*8)+1;
	Gene = new OneChmType[ChromNum];
	for(int i=0; i<ChromNum; i++)	Gene[i] ^= Gene[i];
	if(!Seed) Seed = (unsigned)time(NULL);
	srand(Seed);
	Seed = Seed+(unsigned)time(NULL);
	for(i=0; i<GeneLen; i++)
	{
		int cNum = i/(sizeof(OneChmType)*8);
		if(rand()>=RAND_MAX/2) 
		{
			Gene[cNum] <<= 1;
			Gene[cNum] |= 0x1;
		}
		else Gene[cNum] <<= 1;
	}
}

/////////////////////////////////////////////////////////////////////
//公有函數
/////////////////////////////////////////////////////////////////////

//設置染色體長度
void Chromosome::SetLen(int l)
{
	if(Gene) delete []Gene;
	GeneLen = l;
	if(geneStr) delete []geneStr;
	geneStr = new char[GeneLen+1];
	Init();
}

//返回字符串形式基因
const char* Chromosome::GetGeneStr()
{
	for(int i=0; i<GeneLen; i++)
	{
		int cNum = i/(sizeof(OneChmType)*8);
		int bit = i-cNum*(sizeof(OneChmType)*8);
		__int64 tmp = 0x1;
		tmp <<= bit;
		if(Gene[cNum] & tmp) geneStr[GeneLen-1-i] = '1';
		else geneStr[GeneLen-1-i] = '0';
	}
	geneStr[GeneLen] = '\0';
	return geneStr;
}

//返回i1位到i2位的整型值,包含i1,i2位
unsigned __int64 Chromosome::GetInt(int i1, int i2)
{
	if((i2-i1)<0 || (i2-i1)>=64 || i1<1) return -1;
	unsigned __int64 tmp=0;
	for(int i=i2-1; i>=i1-1; i--)
	{
		int cNum = i/(sizeof(OneChmType)*8);		//i位所在組
		int bits = i-cNum*(sizeof(OneChmType)*8);	//組內偏移
		OneChmType bit = (0x1<<bits);
		if(Gene[cNum]&bit)
		{
			tmp <<= 1;
			tmp |= 0x1;
		}
		else
			tmp <<= 1;
	}
	return tmp;
}

//=號重載函數
Chromosome& Chromosome::operator = (const Chromosome &c)
{
	if(Gene) delete []Gene;
	GeneLen = c.GeneLen;
	ChromNum = c.ChromNum;
	Gene = new OneChmType[ChromNum];
	for(int i=0; i<ChromNum; i++) Gene[i] = c.Gene[i];
	return *this;
}

//==號重載
bool Chromosome::operator == (const Chromosome &c)
{
	if(GeneLen!=c.GeneLen) return false;
	for(int i=0; i<ChromNum; i++)
		if(Gene[i] != c.Gene[i]) return false;
	return true;
}

//位變異函數
Chromosome Chromosome::Mutation(double prob)
{
	Chromosome temp(*this);
	for(int i=0; i<GeneLen; i++)
	{
		int cNum = i/(sizeof(OneChmType)*8);		//所在組
		int bit = i-cNum*(sizeof(OneChmType)*8);	//組內偏移
		OneChmType bits = (0x1<<bit);
		if(((double)rand()/RAND_MAX)<prob) temp.Gene[cNum] ^= bits;
	}
	return temp;
}

//兩性繁殖函數,一點交叉算子
bool Chromosome::OneCross(Chromosome& lover, Chromosome& chld1, Chromosome& chld2)
{
	if(GeneLen != lover.GeneLen) return false;
	int bits, bit;
	bits = (int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);	//產生交叉點
	int cNum = bits/(sizeof(OneChmType)*8);		//交叉點所在的數組下標
	bit = bits-cNum*(sizeof(OneChmType)*8);		//交叉點數組內叉點
	OneChmType high, low;
	high = 0xffffffffffffffff<<bit;			//交叉點數組運算
	low = ~high;
	chld1.GeneLen = GeneLen;	chld1.Gene[cNum] = 0;
	chld2.GeneLen = GeneLen;	chld2.Gene[cNum] = 0;
	chld1.Gene[cNum] = (Gene[cNum]&high)+(lover.Gene[cNum]&low);
	chld2.Gene[cNum] = (lover.Gene[cNum]&high)+(Gene[cNum]&low);
	for(int i=0; i<ChromNum; i++)				//其它數組運算
	{
		if(i != cNum)
		{
			chld1.Gene[i] = lover.Gene[i];
			chld2.Gene[i] = Gene[i];
		}
	}
	return true;
}
//兩性繁殖,兩點交叉算子
bool Chromosome::TwoCross(Chromosome &lover, Chromosome &chld1, Chromosome &chld2)
{
	if(GeneLen != lover.GeneLen) return false;
	int bit1, bit2, bitt;
	bit1 = (int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);	//產生交叉點1,2
	bit2 = (int)((float)rand()/RAND_MAX*(GeneLen-1)+.5);
	if(bit1 > bit2) {
		bitt = bit1;
		bit1 = bit2;
		bit2 = bitt;
	}
	int cNum1 = bit1/(sizeof(OneChmType)*8);	//交叉點1,2數組下標
	int cNum2 = bit2/(sizeof(OneChmType)*8);
	for(int i=0; i<ChromNum; i++)		//其它組運算
	{
		if(i<cNum1 || i>cNum2)			//1,2點兩邊
		{
			chld1.Gene[i] = lover.Gene[i];
			chld2.Gene[i] = Gene[i];
		}
		else if(i!=cNum1 && i!=cNum2)	//1,2點中間
		{
			chld1.Gene[i] = Gene[i];
			chld2.Gene[i] = lover.Gene[i];
		}
	}
	//兩個交叉數組運算
	int bbit1 = bit1-cNum1*(sizeof(OneChmType)*8);	//1,2交叉數組內叉點
	int bbit2 = bit2-cNum2*(sizeof(OneChmType)*8);
	chld1.Gene[cNum1] = Gene[cNum1];		//交叉點1運算
	chld2.Gene[cNum1] = lover.Gene[cNum1];
	OneChmType bits;
	bits = 0xfffffffffffffff<<bbit1;
	chld1.Gene[cNum1] = (chld1.Gene[cNum1]&bits) | (lover.Gene[cNum1]&~bits);
	chld2.Gene[cNum1] = (chld2.Gene[cNum1]&bits) | (Gene[cNum1]&~bits);
	if(cNum1!=cNum2)						//交叉點2運算
	{
		chld1.Gene[cNum2] = lover.Gene[cNum2];
		chld2.Gene[cNum2] = Gene[cNum2];
	}
	bits = 0xfffffffffffffff<<bbit2;
	chld1.Gene[cNum2] = (chld1.Gene[cNum2]&bits) | (Gene[cNum2]&~bits);
	chld2.Gene[cNum2] = (chld2.Gene[cNum2]&bits) | (lover.Gene[cNum2]&~bits);
	return true;
}

//兩性繁殖,均勻交叉算子
bool Chromosome::UniCross(Chromosome& lover,Chromosome& chld1, Chromosome& chld2)
{
	if(GeneLen != lover.GeneLen) return false;
	OneChmType bit;
	for(int i=0; i<GeneLen; i++)
	{
		int cNum = i/(sizeof(OneChmType)*8);
		if((i-cNum*(sizeof(OneChmType)*8))==0) bit = 0x1;
		if(((float)rand()/RAND_MAX)>.5)
		{
			chld1.Gene[cNum] |= (this->Gene[cNum] & bit);
			chld2.Gene[cNum] |= (lover.Gene[cNum] & bit);
		}
		else
		{
			chld1.Gene[cNum] |= (lover.Gene[cNum] & bit);
			chld2.Gene[cNum] |= (this->Gene[cNum] & bit);
		}
		bit <<= 1;
	}
	return true;
}