-
Notifications
You must be signed in to change notification settings - Fork 1
/
labels.c
444 lines (350 loc) · 10.3 KB
/
labels.c
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
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
/************************************************************************
* *
* Program packages 'lvq_pak' and 'som_pak' : *
* *
* labels.c *
* - routines for manipulating labels *
* *
* Version 3.2 *
* Date: 21 Aug 1995 *
* *
* NOTE: This program package is copyrighted in the sense that it *
* may be used for scientific purposes. The package as a whole, or *
* parts thereof, cannot be included or used in any commercial *
* application without written permission granted by its producents. *
* No programs contained in this package may be copied for commercial *
* distribution. *
* *
* All comments concerning this program package may be sent to the *
* e-mail address 'lvq@cochlea.hut.fi'. *
* *
************************************************************************/
#include <string.h>
#include "lvq_pak.h"
#include "labels.h"
#include "errors.h"
/*******************************************************************
* Conversion between labels and indices *
*******************************************************************/
#ifndef LABEL_ARRAY_SIZE
#define LABEL_ARRAY_SIZE 100
#endif /* LABEL_ARRAY_SIZE */
static char **labels = NULL;
static int num_labs = 0;
static int lab_array_size = 0;
/* enlarge_array - enlarges (or allocates) the array used to store
the labels. */
static int enlarge_array(void);
static int enlarge_array(void)
{
char **labs = NULL;
lab_array_size += LABEL_ARRAY_SIZE;
labs = realloc(labels, sizeof(char *) * lab_array_size);
if (labs == NULL)
{
fprintf(stderr, "Can't allocate memory for labeltable \n");
return ERR_NOMEM;
}
labels = labs;
return 0;
}
/* free_labels - Free all the memory used by label list */
void free_labels()
{
if (labels)
free(labels);
labels = NULL;
num_labs = lab_array_size = 0;
}
/* find_conv_to_ind - Give the corresponding index; if the label is
not yet there, add it to table. Empty label is always 0 */
int find_conv_to_ind(char *lab)
{
int i, label;
char *tmp;
/* no string == empty label */
if (lab == NULL)
return LABEL_EMPTY;
/* empty string == empty label */
if (lab[0] == '\0')
return LABEL_EMPTY;
/* check if the label is already in the table */
label = -1;
for (i = 0; i < num_labs; i++)
if (strcmp(labels[i], lab) == 0)
{
label = i;
break;
}
if (label < 0)
{
/* label not found in array. Add it. */
label = num_labs;
if (label >= lab_array_size)
if (enlarge_array())
return -1;
if ((tmp = ostrdup(lab)) == NULL)
return -1;
labels[label] = tmp;
num_labs++;
}
return(label + 1);
}
/* find_conv_to_lab - Give the corresponding label; if the index is
not yet there, return NULL */
char *find_conv_to_lab(int ind)
{
if (ind == LABEL_EMPTY)
return NULL;
if ((ind > num_labs) || (ind < 0))
return NULL;
return labels[ind - 1];
}
/* number_of_labels - Give the number of entries in the label table
(including the empty label *) */
int number_of_labels()
{
return (num_labs + 1); /* number of labels in array + empty label */
}
/* ********** Routines for manipulating labels ******************** */
/* labes are stored in the following way: If there is only one label,
store it in the labels pointer. If there are multiple labels, the
labels entry is a pointer to an array of labels. The num_labs field
in the entry tells the number of labels in that entry */
/* set_entry_label - sets the label on one data entry. All previous
labels are discarded. */
int set_entry_label(struct data_entry *entry, int label)
{
clear_entry_labels(entry); /* remove previous labels if any */
if (label != LABEL_EMPTY) /* empty label == no label */
{
entry->lab.label = label;
entry->num_labs = 1;
}
return 0;
}
/* get_entry_labels - get i:th label from entry (i starts from 0). */
int get_entry_labels(struct data_entry *entry, int i)
{
if ((entry->num_labs <= 1) && (i == 0))
return entry->lab.label;
if (i >= entry->num_labs)
return LABEL_EMPTY;
else
return entry->lab.label_array[i];
}
/* clear_entry_label - remove all labels from entry. */
void clear_entry_labels(struct data_entry *entry)
{
if (entry->num_labs > 1)
free(entry->lab.label_array);
entry->num_labs = 0;
entry->lab.label = LABEL_EMPTY;
}
#ifndef ATABLE_INCREMENT
#define ATABLE_INCREMENT 8
#endif
/* add_entry_label - add a label to entry. Returns non-zero on error. */
int add_entry_label(struct data_entry *entry, int label)
{
int *atable = NULL;
clear_err();
/* adding an empty label does nothing */
if (label == LABEL_EMPTY)
return 0;
/* add first label to entry */
if (entry->num_labs == 0)
{
entry->num_labs = 1;
entry->lab.label = label;
return 0;
}
/* if there is already one label, we need to allocate a table for the
labels */
if (entry->num_labs == 1)
{
atable = malloc(sizeof(int) * ATABLE_INCREMENT);
if (atable == NULL)
return ERR_NOMEM;
/* move old entry to table and add the new label */
entry->num_labs++;
atable[0] = entry->lab.label;
atable[1] = label;
entry->lab.label_array = atable;
return 0;
}
atable = entry->lab.label_array;
/* enlarge label array if needed */
if ((entry->num_labs % ATABLE_INCREMENT) == 0)
{
/* need more space */
atable = realloc(atable,
sizeof(int) * (entry->num_labs + ATABLE_INCREMENT));
if (atable == NULL)
return ERR_NOMEM;
entry->lab.label_array = atable;
}
atable[entry->num_labs++] = label;
return 0;
}
/* copy_entry_labels - copy all labels from one entry to the other. */
int copy_entry_labels(struct data_entry *dest, struct data_entry *source)
{
int blocks, size, *atable;
clear_err();
clear_entry_labels(dest); /* remove old labels first */
if (source->num_labs <= 1)
dest->lab.label = source->lab.label;
else
{
blocks = (source->num_labs + ATABLE_INCREMENT - 1) / ATABLE_INCREMENT;
size = sizeof(int) * blocks * ATABLE_INCREMENT;
atable = malloc(size);
if (atable == NULL)
return ERR_NOMEM;
memcpy(atable, source->lab.label_array, size);
dest->lab.label_array = atable;
}
dest->num_labs = source->num_labs;
return 0;
}
/* ********************************************************************** */
/* hitlists - hitlist is a list of label,frequency pairs that is kept sorted
so that the label with the highest frequency is always the first in the
list. */
/* initialize a new hitlist */
struct hitlist *new_hitlist(void)
{
struct hitlist *hl;
clear_err();
hl = malloc(sizeof(struct hitlist));
if (hl == NULL)
{
ERROR(ERR_NOMEM);
return NULL;
}
hl->head = hl->tail = NULL;
hl->entries = 0;
return hl;
}
/* clear_hitlist - clears all entries from a hitlist */
void clear_hitlist(struct hitlist *hl)
{
struct hit_entry *he, *next;
if (hl)
{
for (he = hl->head; he; he = next)
{
next = he->next;
free(he);
}
hl->head = hl->tail = NULL;
hl->entries = 0;
}
}
/* free_hitlist - deallocate a hitlist */
void free_hitlist(struct hitlist *hl)
{
if (hl)
{
clear_hitlist(hl); /* deallocate hits */
free(hl);
}
}
/* find_hit - find a hit_entry corresponding to a certain label from
list. Returns NULL if there is no entry for the label */
struct hit_entry *find_hit(struct hitlist *hl, long label)
{
struct hit_entry *he;
for(he = hl->head; he; he = he->next)
if (label == he->label)
break;
return he;
}
/* hit_swapwprev - (internal) exchange a hit entry with the previous
hit in the list. Used to keep the list in order */
static struct hit_entry *hit_swapwprev(struct hitlist *hl, struct hit_entry *he)
{
struct hit_entry *prev;
prev = he->prev;
if (prev)
{
prev->next = he->next;
he->prev = prev->prev;
he->next = prev;
prev->prev = he;
if (prev->next == NULL)
hl->tail = prev;
else
prev->next->prev = prev;
if (he->prev == NULL)
hl->head = he;
else
he->prev->next = he;
}
return he;
}
/* add_hit - add a hit in the list for a label */
long add_hit(struct hitlist *hl, long label)
{
struct hit_entry *he;
he = find_hit(hl, label);
if (he)
{
/* found in list, increase counter */
he->freq++;
/* keep list in order, higher frequencies are in the beginning. */
while (he->prev)
if (he->prev->freq < he->freq)
he = hit_swapwprev(hl, he);
else
break;
}
else
{
he = malloc(sizeof(struct hit_entry));
if (he == NULL)
{
ERROR(ERR_NOMEM);
return 0;
}
/* add to end of list */
he->next = NULL;
he->prev = hl->tail;
he->label = label;
he->freq = 1;
hl->tail = he;
if (he->prev)
he->prev->next = he;
else
hl->head = he;
hl->entries++;
}
return he->freq;
}
/* print_hitlist - prints the contents of a hitlist */
void print_hitlist(struct hitlist *hl, FILE *fp)
{
struct hit_entry *he;
int lab;
for (he = hl->head; he; he = he->next)
{
lab = he->label;
fprintf(fp, "%s,%ld",
(lab != LABEL_EMPTY) ? find_conv_to_lab(lab) : "EMPTY",
he->freq);
if (he->next)
fputs(", ", fp);
}
fputs("\n", fp);
}
/* hitlist_label_freq - returns the counter value for a label. If the
label is not in the list returns 0 (naturally) */
long hitlist_label_freq(struct hitlist *hl, long label)
{
struct hit_entry *he;
for (he = hl->head; he != NULL; he = he->next)
if (he->label == label)
return he->freq;
return 0;
}