
//    ________________________________________________________________________
//   |             FLAG VALUE             |    DESCRIPTION     |  BITS | FLAG |
//   |____________________________________|____________________|_______|______|
//   |									  |					   |	   |      |
//   |00000000 00000000 00000000 00111111 | from square        | 1-6   |   0  |
//   |00000000 00000000 00001111 11000000 | to square          | 7-12  |   6  |
//   |00000000 00000000 01110000 00000000 | piece to move      | 13-15 |  12  |
//   |00000000 00000011 10000000 00000000 | capture            | 16-18 |  15  |   
//   |00000000 00000100 00000000 00000000 | EP capture bit     | 19    |  18  |
//   |00000000 00001000 00000000 00000000 | p2forward bit      | 20    |  19  |
//   |00000000 00010000 00000000 00000000 | castle bit         | 21    |  20  |
//   |00000000 00100000 00000000 00000000 | promotion bit      | 22    |  21  |
//   |00000000 11000000 00000000 00000000 | promotion piece    | 23-24 |  22  |
//   |11111111 00000000 00000000 00000000 | reserve            | 25-32 |  24  |
//   |____________________________________|____________________|_______|______|


#define SORT_ALL			       0,LIST_SIZE
#define DELETE_BEST_MOVE		   0
#define BEST_MOVE_VALUE(list)	   (list->value[0])
#define MOVES_EQUAL(m1, m2)        ((m1)->m == (m2)->m)
#define SQUARE_FROM_STRING(s)      (8 * (*(s+1)-'1') + *(s)-'a')
#define FILE_TO_CHAR(f)            ('a' + (f))
#define RANK_TO_CHAR(r)            ('1' + (r))
#define SQUARE_TO_STRING(sq, str)  {(str)[0] = FILE_TO_CHAR(File(sq));\
									(str)[1] = RANK_TO_CHAR(Rank(sq));\
									(str)[2] = '\0';\
}
#define NULLMOVE(m)                (m == 0)
#define MOVE_NONE(m)               (m == 1)

const uint ShCastSqTo[]   = {g1<<6, g8<<6};
const uint LCastSqTo[]    = {c1<<6, c8<<6};
const uint CastSqFrom[]	  = {e1, e8};

const char NullMoveString[] = "null";
const char MoveNoneString[] = "none";
const BitBoard pawn_7th[] = {Rank_7, Rank_2};

class Move {	
public:
	uint32 m;	
	
	inline uint From()						{return 0x3F & (m)					;}	// from square
	inline uint To()						{return 0x3F & (m>>6)				;}	// to square
	inline uint Piece()						{return 0x7 & (m>>12)				;}	// piece 
	inline uint Capture()					{return 0x7 & (m>>15)				;}	// capture piece		
	inline uint Promote()					{return 0x3 & (m>>22)				;}	// promote piece
	inline uint Removal()					{return 0xF & (m>>15)				;}	// see MakeMove() / UnmakeMove()
	inline uint IsCastle()					{return m & (1<<20)					;}	// is it a castle move?
	inline uint IsTwoForward()				{return m & (1<<19)					;}	// pawn two forward?
	inline uint IsPromote()					{return m & (1<<21)					;}	// promote?
	inline uint IsEnPassant()				{return m & (1<<18)					;}	// ep?
	inline uint IsCapProm()					{return m & ((7<<15)|(1<<21))		;}	// we captured piece or promoted pawn?
	inline uint IsQuiet()					{return IsCapProm() == 0			;}	// quiet moves only
	inline bool IsReal()					{return (m > 1)						;}	// not move_none / nullmove
	inline void Clear()						{(m = 1)							;}	// move_none
	inline bool Equal(Move m2)				{return (m == m2.m)					;}	// moves equal
	inline bool Equal(Move *m2)				{return (m == m2->m)				;}	// moves equal
	inline bool Copy(Move *source)			{return (m = source->m) > 1			;}	// copy from source
	inline bool Copy(Move source)			{return (m = source.m) > 1			;}	// copy from source	
	inline bool IsIrreversible()			{return Piece()==PAWN | Capture()	;}  // fifty moves rule		
	inline bool PawnTo7th(uint stm)			{return (Piece() == PAWN)
											&& (BIT(To()) & pawn_7th[stm])		;}  // is it a danger pawn move? 	
	void Parse(char *string, uint8 *type) {
		int from, to, pf, pt, dist;
		from = SQUARE_FROM_STRING(string);
		to = SQUARE_FROM_STRING(string+2);
		dist = ABS(to - from);
		m = from | (to << 6);
		switch(string[4]) {
			case '\0': break;
			case 'q' : m |= (1<<21) | (PROM_QUEEN  << 22); break;
			case 'n' : m |= (1<<21) | (PROM_KNIGHT << 22); break;
			case 'r' : m |= (1<<21) | (PROM_ROOK   << 22); break;
			case 'b' : m |= (1<<21) | (PROM_BISHOP << 22); break;
		}
		pf = type[from];
		pt = type[to];
		m |= (pf << 12); // piece to move
		m |= (pt << 15); // capture piece			
		if((pf == PAWN) && (pt == EMPTY)) {							
			if(dist == 7 || dist == 9)  m |= (PAWN<<15) | (1<<18);	// EP capture				
			if(dist == 16)				m |= (1<<19);               // Pawn 2 forward
		}		
		if(pf == KING && dist == 2)     m |= (1<<20);			    // Castling
	}
	void Print(FILE *file) {
		// nullmove & move none
		if(NULLMOVE(m))	 {	printf(NullMoveString);   return;}
		if(MOVE_NONE(m)) {	printf(MoveNoneString);   return;}
		// 'real' moves
		char str[8];
		char promote_str[] = "qnrb";
		SQUARE_TO_STRING(From(), str);	
		SQUARE_TO_STRING(To(), str+2);
		if(IsPromote()) {
			*(str+4) = promote_str[Promote()];
			*(str+5) = '\0';
		}
		fprintf(file, "%s ", str);
	}
	void Print()	{  Print(stdout)					;}
	void PrintN()	{  Print(stdout);	printf("\n")	;}
};

struct undo_t {
  
	uint64 key;
	uint64 pawn_key;

	sint32 opening;
	sint32 endgame;
	sint32 mat_diff;
	uint32 mat_key;

	uint16 ply;

	uint8 fifty;
	uint8 ksq[2];
    uint8 ep_file;
    uint8 castle;                       
    uint8 stm; 	
};

class MoveList {
public:	
	uint32 pointer;
	sint32 value[LIST_SIZE];
	Move move[LIST_SIZE][1];	
	MoveList()													{pointer = 0	                        								    ;}
	inline uint32 Size()										{return pointer																;}	
	inline void Clear()											{pointer = 0																;}	
	inline void Add(Move m)										{*move[pointer++] = m                    								    ;}
	inline void Add(Move *m)									{*move[pointer++] = *m                    								    ;}
	inline void DeleteMove(uint32 nb)							{*move[nb] = *move[--pointer];		value[nb] = value[pointer]				;}
	inline void AddOneForward(uint f,uint t)					{move[pointer++]->m = f | (t<<6) | (PAWN<<12)                               ;}
	inline void AddTwoForward(uint f,uint t)				    {move[pointer++]->m = f | (t<<6) | (PAWN<<12)  | (1<<19)                    ;}
	inline void AddPawnCapture(uint f,uint t,uint c)			{move[pointer++]->m = f | (t<<6) | (PAWN<<12)  | (c<<15)                    ;}
	inline void AddPromoteCapture(uint f,uint t,uint r,uint c)	{move[pointer++]->m = f | (t<<6) | (PAWN<<12)  | (c<<15) | (1<<21) | (r<<22);}
	inline void AddPromoteStraight(uint f,uint t,uint r)		{move[pointer++]->m = f | (t<<6) | (PAWN<<12)  |           (1<<21) | (r<<22);}
	inline void AddEnPassant(uint f,uint t)						{move[pointer++]->m = f | (t<<6) | (PAWN<<12)  | (PAWN<<15) | (1<<18)       ;}
	inline void AddPieceMove(uint f,uint t,uint c, uint piece)  {move[pointer++]->m = f | (t<<6) | (piece<<12) | (c<<15)				    ;}	
	inline void AddKnightMove(uint f,uint t,uint c)				{move[pointer++]->m = f | (t<<6) | (KNIGHT<<12)| (c<<15)                    ;}
	inline void AddBishopMove(uint f,uint t,uint c)				{move[pointer++]->m = f | (t<<6) | (BISHOP<<12)| (c<<15)			        ;}
	inline void AddRookMove(uint f,uint t,uint c)				{move[pointer++]->m = f | (t<<6) | (ROOK<<12)  | (c<<15)			        ;}
	inline void AddQueenMove(uint f,uint t,uint c)				{move[pointer++]->m = f | (t<<6) | (QUEEN<<12) | (c<<15)			        ;}
	inline void AddKingMove(uint f,uint t,uint c)				{move[pointer++]->m = f | (t<<6) | (KING<<12)  | (c<<15)			        ;}			
	inline void AddShortCastle(uint c)							{move[pointer++]->m = (KING<<12) | (1<<20) | CastSqFrom[c] | ShCastSqTo[c]  ;}
	inline void AddLongCastle(uint c)							{move[pointer++]->m = (KING<<12) | (1<<20) | CastSqFrom[c] | LCastSqTo[c]   ;}
	
	void InsertSort(int lower, int upper) {
		int i, j;		
		Move tmp_move;
		sint32 tmp_value;
		upper = MIN(upper+1, pointer);
		for (i = lower + 1; i < upper; i++) {
			tmp_move  = *move[i];
			tmp_value = value[i];
			for (j = i-1; (j >= lower) && (value[j] < tmp_value); j--) {
				*move[j+1] = *move[j];
				value[j+1] = value[j];
			}
			*move[j+1] = tmp_move;
			value[j+1] = tmp_value; 
		}
	}	
	void QuickSort(int lower, int upper) {		
		sint32 best_value = value[lower];
		upper = MIN(upper+1, pointer);
		int best_i = lower;
		Move tmp_move;
		while(--upper > lower)
			if(value[upper] > best_value)
				best_value = value[best_i = upper];			
		if(best_i != lower) {			
			tmp_move = *move[best_i];			
			value[best_i] = value[lower];
			*move[best_i] = *move[lower];
			value[lower] = best_value;
			*move[lower] = tmp_move;			
		}
	}	
	inline void Print() {		
		for(int i = 0; i < pointer; i++) {
			printf("(%3d) move ",i+1);
			move[i]->Print();
		}
		printf("\n");
	}
};
