File: badguess.c

package info (click to toggle)
kdrill 6.5deb2-12
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 1,340 kB
  • sloc: ansic: 7,636; makefile: 47
file content (272 lines) | stat: -rw-r--r-- 5,874 bytes parent folder | download | duplicates (7)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
/*
 * 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 */