/*

File DepthFirstSearch.m

This search is a standard depth first one.  At each step, the variable with the highest efficiency is selected and filled.  The search backtracks when a variable has no remaining values.

It is the responsibility of the variables to implement any special heuristics like backjumping and leapfrogging.

*/

#import <appkit/appkit.h>

#import "DepthFirstSearch.h"


/* 行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行  */


#define variable(i)		([variables  objectAt: i])


/* 行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行  */


@implementation DepthFirstSearch


- (BOOL) startSearch: (id) theVariables
{
	variables = theVariables;
	next = 0;
	ok = YES;
	last = nil;
	count = [variables  count];
	
	return [self  continue];
}


- (BOOL) continue
{
	while ([NXApp	getNextEvent: NX_KEYDOWNMASK
					waitFor: 0
					threshold: NX_MODALRESPTHRESHOLD] == NULL)
		
		if ([self  step] == NO) return NO;
	
	return YES;
}


- (BOOL) step
{
	if (ok) [self  findBest];
	ok = [self  fill: variable(next)];
	
	if (!ok && (next-- == 0)) return [self  done];
	else if (ok && (++next == count)) return [self  done];
	else return YES;
}


- (BOOL) done
{
	[last  unhilight];
	return NO;
}


- (BOOL) fill: (id) variable
{
	BOOL	status;
	
	[last  unhilight];
	[variable  hilight];
	status = [last = variable  fillNext];
	
	return status;
}


/* 行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行行  */


- findBest
{
	float	value, current;
	int		best, i;
	id		temp;
	
	for (best = 0, value = -1.0, i = next; i < count; i++)
	{
		if ((current = [variable(i)  efficiency]) > value)
		{
			value = current;
			best = i;
		}
	}
	
	temp = variable(next);
	[variables  replaceObjectAt: next  with: variable(best)];
	[variables  replaceObjectAt: best  with: temp];
	
	return self;
}


@end