/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *
 * This file is part of SanKit -- A multiplatform set of C code
 * for reading and writing PGN formatted chess games. In addition
 * it can be used as an engine to determine in real time if proposed
 * moves are legal or not. It appears to generate near perfect PGN
 * from incorrectly formatted files.
 *
 * Copyright 1994 Steven J. Edwards All Rights Reserved.
 * Copyright 2009-2011 David Hoerl All Rights Reserved.
 *
 *
 * Redistribution and use in source and binary forms, with or without modification, are
 * permitted provided that the following conditions are met:
 *
 *    1. Redistributions of source code must retain the above copyright notice, this list of
 *       conditions and the following disclaimer.
 *
 *    2. Redistributions in binary form must reproduce the above copyright notice, this list
 *       of conditions and the following disclaimer in the documentation and/or other materials
 *       provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY David Hoerl ''AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL David Hoerl OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/*>>> sansrt.c: SAN project move list sorting routines */

/* Revised: 1994.02.10 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "sandef.h"
#include "sanvar.h"

#include "sanmlm.h"
#include "sanmne.h"
#include "sanmsc.h"
#include "sansrt.h"
#include "sanutl.h"

/*--> SANEvalComp: comparison routine for move evaluations */
nonstatic
int SANEvalComp(mptrT mptr0, mptrT mptr1)
{
	int flag;

	if(mptr0->m_eval == mptr1->m_eval) {
		flag = 0;
	} else
	if(mptr0->m_eval < mptr1->m_eval) {
		flag = 1;
	} else {
		flag = -1;
	}

	return flag;
}

/*--> SANSortEval: sort move list according to evaluation */
nonstatic
void SANSortEval(void)
{
	typedef int (*mcfptrT)(const void *, const void *);

	if(curr_g.g_gmvc > 1) {
		qsort(curr_g.g_base, curr_g.g_gmvc, sizeof(mT), (mcfptrT) SANEvalComp);
	}

	return;
}

/*--> SANSortSAN: ASCII SAN sort move list */
nonstatic
void SANSortSAN(void)
{
	mptrT mptr, mptr0, mptr1;
	siT i, j, pair, pass, flag;
	sanptrT sanptr, sptr0, sptr1;
	char t_ch;
	mT t_m;

/* point to current generation */

	if(!(curr_g.g_flag & gf_sort)) {
		curr_g.g_flag |= gf_sort;
		SANMLDisambiguate();

		/* allocate the SAN string vector */

		sanptr = (sanptrT) SANMemGrab(sizeof(sanT) * curr_g.g_gmvc);

		/* construct the SAN string entries */

		mptr = curr_g.g_base;
		for(i = 0; i < curr_g.g_gmvc; i++) {
			SANEncode(mptr++, *(sanptr + i));
		}

		/* a lo-tech bubble sort */

		flag = 1;
		pass = 0;
		while(flag && (pass < (curr_g.g_gmvc - 1))) {
			sptr0 = sanptr;
			sptr1 = sanptr + 1;
			mptr0 = curr_g.g_base;
			mptr1 = curr_g.g_base + 1;
			flag = 0;
			pair = 0;
			while(pair < (curr_g.g_gmvc - pass - 1)) {
				/* case sensitive ascending order */

				if(strcmp((charptrT) sptr0, (charptrT) sptr1) > 0) {
					flag = 1;
					for(j = 0; j < sanL; j++) {
						t_ch = (*sptr0)[j];
						(*sptr0)[j] = (*sptr1)[j];
						(*sptr1)[j] = t_ch;
					}
					t_m = *mptr0;
					*mptr0 = *mptr1;
					*mptr1 = t_m;
				}
				sptr0++;
				sptr1++;
				mptr0++;
				mptr1++;
				pair++;
			}
			pass++;
		}

		SANMemFree(sanptr);
	}

	return;
}

/*--> SANLocateOrdinal: locate the canonical move ordinal for a move */
nonstatic
siT SANLocateOrdinal(mptrT mptr)
{
	siT ord;
	siT i, j, pair, pass, flag;
	sanptrT sanbaseptr, sptr0, sptr1;
	mptrT mbaseptr, mptr0, mptr1;
	char t_ch;
	mT t_m;

/* set default return value */

	ord = -1;

/* allocate the SAN string vector and the move vector */

	sanbaseptr = (sanptrT) SANMemGrab(sizeof(sanT) * curr_g.g_gmvc);
	mbaseptr = (mptrT) SANMemGrab(sizeof(mT) * curr_g.g_gmvc);

/* copy the moves from the current generation vector and convert */

	for(i = 0; i < curr_g.g_gmvc; i++) {
		*(mbaseptr + i) = *(curr_g.g_base + i);
		SANEncode((mbaseptr + i), *(sanbaseptr + i));
	}

/* sort the SAN vector in ASCII order */

	flag = 1;
	pass = 0;
	while(flag && (pass < (curr_g.g_gmvc - 1))) {
		sptr0 = sanbaseptr;
		sptr1 = sanbaseptr + 1;
		mptr0 = mbaseptr;
		mptr1 = mbaseptr + 1;
		flag = 0;
		pair = 0;
		while(pair < (curr_g.g_gmvc - pass - 1)) {
			/* case sensitive ascending order */

			if(strcmp((charptrT) sptr0, (charptrT) sptr1) > 0) {
				flag = 1;
				for(j = 0; j < sanL; j++) {
					t_ch = (*sptr0)[j];
					(*sptr0)[j] = (*sptr1)[j];
					(*sptr1)[j] = t_ch;
				}
				t_m = *mptr0;
				*mptr0 = *mptr1;
				*mptr1 = t_m;
			}
			sptr0++;
			sptr1++;
			mptr0++;
			mptr1++;
			pair++;
		}
		pass++;
	}

/* search for the matching move */

	i = 0;
	while((ord == -1) && (i < curr_g.g_gmvc)) {
		if(SANSameMove(mptr, (mbaseptr + i))) {
			ord = i;
		} else {
			i++;
		}
	}

/* free the allocated vectors */

	SANMemFree(sanbaseptr);
	SANMemFree(mbaseptr);

	return ord;
}

/*<<< sansrt.c: EOF */
