//解析交換方式----------及第幾列的數據
#define MAX 0xff
//#define debug
#include"array.h"
void array::init1()
{
	int i=n/2,j=0,k;
	for(k=0;k<n*n;k++)
	{
head:
		if(head[i+j*n]==0)
		{
			head[j*n+i]=k+1;
		}
		else
		{
			j+=2;
			if(--i==-1)i=n-1;
			if(j>n)j-=n;
			goto head;
		}
		if(--j==-1)j=n-1;
		if(++i==n)i=0;
	}
}

void array::init()
{
	int i,j,end,temp,jg,flag;
	lbiao t;
	if(n!=n/2*2)
	{
		init1();
		return;
	}
	else
	{
		if(n!=n/4*4)end=n/2;
		else end=n/4;
	}
	for(i=0;i<end;i++)
	{
		for(j=0;j<n/2;j++)
		{
			temp=2*n*i+2*j;
			jg=n*i+j;
			head[temp]=jg+1;
			head[temp+1]=n*n-jg;
			head[temp+n]=n*n-jg-n/2;
			head[temp+n+1]=jg+n/2+1;
		}
	}
	for(;i<n/2;i++)
	{
		for(j=0;j<n/2;j++)
		{
			temp=2*n*i+n-1-2*j;
			jg=n*i+j;
			head[temp]=jg+1;
			head[temp-1]=n*n-jg;
			head[temp+n]=n*n-jg-n/2;
			head[temp+n-1]=jg+n/2+1;
		}
	}
	if(n/4*4!=n)
	{
		for(i=0;i<n/4;i++)
		{
			head[i*2]+=n*n/4;
			head[i*2+n*n/2+1]-=n*n/4;
		}
		head[i*2+n*n/2+n]+=n*n/4;
		head[i*2+n*n/2+n+1]-=n*n/4;
		for(i++;i<n/2;i++)
		{
			head[i*2+1]-=n*n/4;
			head[i*2+n*n/2]+=n*n/4;
		}
	}
	flag=3;
	if(n>7)flag=(1<<n)-1;
	flag=50;
	jian_lb(t,flag,*this);
	if(!e)zjh(*this,t.head,t.head,flag);

}
void array::jxi(char *a,int b)
{
	int temp=1<<(n-1);
	int i,j;//i循環變量，j為a的位數，temp用于檢驗位是否為真
	a[0]=1;
	for(i=1;i<sizeof(int)*8;i++)
	{
		a[i]=0;
	}
	if(b==temp*2-1||b==temp-1)
	{//橫豎全交換
		if(b>temp)a[0]=n;
		for(i=1;i<n+1;i++)
		{
			a[i]=i-1;
		}
		a[i]=char(MAX);
		return;
	}
	if(b>temp)
	{
		a[0]=n;//a[0]==n表示以行為基準,在交換時使用
		b-=temp;
	}
	temp=1;
	for(i=0,j=1;i<sizeof(int)*8;i++)
	{
		if(b&temp)a[j++]=i;
		temp<<=1;
	}
	a[j]=char(MAX);//結束標志
	return;
}

void array::jian_lb(lbiao &a,int flag,array &x)//建立交換行標的鏈表		
{
	int T=1<<(n-1);//T為2的n-1次方
	int i,j,t1,t2;
	char*xch=NULL;//記錄交換方式
	xch=new char[sizeof(int)*8];
	jxi(xch,flag);
	if(flag==T)return;
	if(flag==T-1||flag==T*2-1)//整行交換，第一行不需要與后半部分交換
	{//求第零行的方式
		for(j=1;j<n/2;j++)
		{
			a.add(new addrs(0,j));
		}
		for(i=1;i<n;i++)
			for(j=i+1;j<n;j++)
			{
				a.add(new addrs(i,j));
			}
		delete[] xch;
		return;
	}
	if(xch[2]==char(MAX))
	{
			delete[] xch;
			return;
	}
	for(i=0;i<n;i++)//n為行數；該函數為array的友元
	{
		t1=qh(x,xch,i);
		for(j=i+1;j<n;j++)
		{
			t2=qh(x,xch,j);
			if(t1==t2)
			{
				a.add(new addrs(i,j));
			}
		}
	}

	delete[] xch;
	return;
}//建立的鏈表中每一個節點都滿足fir與sec的xch規則和相同，可以按xch規則進行交換

int array::qh(array &a,char *xch,int k)
{
	int temp=0,bs1,bs2;

	bs2=xch[0];//倍數
	bs1=n+1-bs2;
	for(int i=1;xch[i]!=char(MAX);i++)
	{
		temp+=a.head[k*bs1+xch[i]*bs2];
	}
	return temp;
}//計算第k行（列）的xch規則和

//以下為實現交換的過程，在循環中調用
void array::jiaohuan(array &a,addrs &b,int flag)
{
	int i,bs1,bs2,temp;//bs的改變實現xch對應行或列的交換
	char *xch;//xch儲存交換的方式	
	xch=new char[sizeof(int)*8];
	jxi(xch,flag);//解析交換方式

	bs2=xch[0];
	bs1=n+1-bs2;
	for(i=1;xch[i]!=char(MAX);i++)
	{
		temp=a.head[b.fir*bs1+xch[i]*bs2];
		a.head[b.fir*bs1+xch[i]*bs2]=a.head[b.sec*bs1+xch[i]*bs2];
		a.head[b.sec*bs1+xch[i]*bs2]=temp;
	}
	delete[]xch;
}

//以下為主交換程序，遞歸
void array::zjh(array &x,addrs*head,addrs *bg,int flag)
{
	if(e)return;
	int temp=1<<n;
	lbiao t;
	addrs  *now=NULL;//h為新鏈表的頭
	array x1(x);
	if(bg==NULL)//x對此類交換已經完成
	{
		if(++flag==temp)return;
		jian_lb(t,flag,x);
		if(!e)zjh(x,t.head,t.head,flag);	
	}
	else
	{
		zjh(x,head,bg->next,flag);
		jiaohuan(x1,*bg,flag);
		if(x1.xright())
		{
			this->update(x1);
			e=true;
			return;
		}
		temp=bg->fir;
		now=head;
		while(now!=bg)
		{
			if(now->fir==temp||*now!=*bg)
			{
				t.add(*now);
			}
			now=now->next;
		}
		now=now->next;
		while(now!=NULL)
		{
			if(now->fir==temp)
			{
				t.add(*now);
			}
			now=now->next;
		}
//建立為x1的新鏈表
		zjh(x1,t.head,t.head,flag);
	}

}