/*
 * This file keeps track of the user's bad guesses.
 *
 * Why is this in a separate file? 'cause I'm going to attempt to make
 * a clean OO API for this functionality.
 *
 * The PURPOSE of this API, is to attempt to make "try this again"
 * repeating, be more appropriately distributed, favouring much-missed ones.
 *
 *
 * The nasty part of this code is that currently it implements
 * a "priority queue", with a static array.
 * Maybe I should have made this a linked list. ug.
 *
 * Since this is finicky, I put in a -DDEBUG main() routine
 */

#include <stdio.h>

#define BADCACHESIZE 100
#include "defs.h"

/* Here's the queue */
static TRANSLATION badcache[BADCACHESIZE];
static int maxbad=0;


/* delete item at position 'delpos'.
 * move items from start+1, to end-1, to cover up
 * You'll probably want to call with
 *  deletepos(position, maxbad)
 *
 * We do NOT adjust maxbad. Caller has to do that.
 */
static void deletepos(int delpos, int end){
	int ndx;
	for(ndx=delpos; ndx<end;ndx++){
		badcache[ndx]=badcache[ndx+1];
	}
}

static void insert(int, int, TRANSLATION);


/* This doesn't actually resort the entire array.
 * Just the item at the given start index
 *
 * The TRANSLATIONstruct referenced at the startpoint, could have
 * EITHER increased or decreased its count
 * And in theory, it might not move. 
 */
static void resort(int start)
{
	int newpos;
	TRANSLATION moveme=badcache[start];

	if(maxbad<2)
		return;

	/* increase?*/
	if(start>0){
		newpos=start-1;
		while(newpos>=0){
			if(badcache[newpos]->incorrect < moveme->incorrect){
				newpos-=1;
			} else break;
		}
		if(newpos < start-1){
			insert(newpos+1, start, badcache[start]);
			maxbad--;
			return;
		}
	}
	/* no? check for decrease */

	newpos=start+1;
	while(newpos<maxbad){
		if(badcache[newpos]->incorrect >= moveme->incorrect){
			newpos++;
		} else break;
	}
	if(newpos>start+1){
		deletepos(start, newpos);
		newpos-=1;
		badcache[newpos]=moveme;
	}
}

/* Subroutines are up here. Global routines are further down below */

/* pass in a TRANSLATIONS ptr, and a range of 
 * the cache we should play with.
 * For pure insert, internal functions should use
 *   insert(0, maxbad, whatever)
 * Except you should probably just want to use insertupdate() instead
 *
 * We allow the other syntax, for use with resort().
 *
 * We dont have to optimize this right now, cause the
 * cache is relatively tiny.
 *
 * We assume that there is one "empty" space at
 *  badcache[endndx]
 *
 * If tnum already exists, we will update existing slot, reguardless
 * of startndx and endndx
 *
 * We update maxbad here!!
 *
 */
static void insert(int startndx, int endndx, TRANSLATION trans)
{
	/* find place it SHOULD go, between startndx and endndx*/
	int idx,shuffleidx;

	if(endndx>=BADCACHESIZE){
		/* cache full */
		return;
	}
	idx=startndx;

	while(idx<endndx){
		if((badcache[idx]->incorrect) < (trans->incorrect)){
			break;
		}
		idx++;
	}

	/* Now make a "space" in middle of array, if needed */
	if(idx<endndx){
		shuffleidx=endndx;
	} else {
		shuffleidx=idx;
	}
	while(shuffleidx>idx){
		badcache[shuffleidx]=badcache[shuffleidx-1];
		shuffleidx--;
	}
	badcache[idx]=trans;

	maxbad++;
}

/* insert at right place, or update existing one and resort*/
static void insertupdate(TRANSLATION trans)
{
	int idx;

	/* first search for pre-exist, in ENTIRE CACHE*/
	for(idx=0;idx<maxbad;idx++){
		if(badcache[idx]==trans){
			resort(idx);
			return;
		}
	}
	insert(0,maxbad,trans);
}


/************************************************************/

/* return -1 if not in cache */
static int findindex(TRANSLATION trans){
	int idx=0;
	while(idx<maxbad){
		if(badcache[idx]==trans)
			return idx;
		idx++;
	}
	return -1;
}

static void deletebad(TRANSLATION trans){
	int pos=findindex(trans);
	if(pos==-1){
		return;
	}
	deletepos(pos,maxbad);
	maxbad--;
}

#ifdef DEBUG
/* debug */
static void print(){
	int idx;
	puts("Dumping badcache");
	for(idx=0;idx<maxbad;idx++){
		printf("Translation #%d, badcount=%d\n",(int)badcache[idx],
		       badcache[idx]->incorrect);
	}
}
#endif

/**********************************************************************/
 /*  Here are the globally visible thingies    */
 /**********************************************/

/* If you like an explicit "remove" call, here it is. But normally,
 * this is not used directly by outsiders
 */
void RemoveBadCache(TRANSLATION trans){
	deletebad(trans);
}

/* This tells us to insert or update or REMOVE a translation, from
 * our cache of missed translations. We assume the caller has
 * just changed the trans->incorrect value
 *
 */
void AdjustBadCache(TRANSLATION trans){
		if(trans->incorrect==0){
			RemoveBadCache(trans);
			return;
		}
		insertupdate(trans);
}

/* basically, just returns first missed one, or a random one */
TRANSLATION GetRepeat(){
	if(maxbad==0){
		return NULL;
	}
	return badcache[0];
}


#ifdef DEBUGMAIN
TRANSLATION translations[6];
main(){
	int tc;

	for(tc=0;tc<6;tc++){
		translations[tc]=(TRANSLATION)malloc(sizeof (struct translationstruct));
	}
	translations[0]->incorrect=0;
	translations[1]->incorrect=1;
	translations[2]->incorrect=2;
	translations[3]->incorrect=3;
	translations[4]->incorrect=4;
	translations[5]->incorrect=5;
	
	AdjustBadCache(translations[3]);
	print();
	AdjustBadCache(translations[5]);
	print();
	AdjustBadCache(translations[2]);
	print();
	AdjustBadCache(translations[3]);
	print();
	AdjustBadCache(translations[4]);
	print();
	AdjustBadCache(translations[1]);
	print();

	printf("updating tnum5, %d\n", translations[5]);
	translations[5]->incorrect-=2;
	AdjustBadCache(translations[5]);
	print();

	printf("updating tnum3, %d\n", translations[5]);
	translations[5]->incorrect+=2;
	AdjustBadCache(translations[5]);
	print();

	printf("deleting tnum2, %d\n", translations[2]);
	RemoveBadCache(translations[2]);
	print();
	
}

#endif /* DEBUG */