2 * A judge comparing shuffled sequences of tokens
4 * (c) 2007 Martin Mares <mj@ucw.cz>
15 static int ignore_nl, ignore_empty, ignore_case;
16 static int shuffle_lines, shuffle_words;
18 typedef unsigned int uns;
20 /*** Token buffer ***/
30 struct tokpage *first_page, *last_page;
31 uns num_tokens, num_lines;
33 struct tokpage *this_page;
37 #define TOKBUF_PAGE 256
39 static void init_tokbuf(struct tokbuf *tb)
41 memset(tb, 0, sizeof(*tb));
44 static void add_token(struct tokbuf *tb, char *token, int l)
47 struct tokpage *pg = tb->last_page;
48 if (!pg || pg->end - pg->pos < l)
50 int size = TOKBUF_PAGE - sizeof(struct tokbuf);
53 pg = xmalloc(sizeof(struct tokbuf) + size);
55 tb->last_page->next = pg;
61 pg->end = pg->buf + size;
63 memcpy(pg->pos, token, l);
70 static void close_tokens(struct tokbuf *tb)
73 tb->last_page->end = tb->last_page->pos;
76 static char *get_next(struct tokbuf *tb)
78 struct tokpage *pg = tb->this_page;
79 tb->read_pos += strlen(tb->read_pos) + 1;
80 if (tb->read_pos >= pg->end)
82 tb->this_page = pg = pg->next;
85 tb->read_pos = pg->buf;
90 static char *get_first(struct tokbuf *tb)
92 struct tokpage *pg = tb->first_page;
96 tb->read_pos = pg->buf;
100 /*** Reading and shuffling ***/
116 struct tok *tok_array;
117 struct line *line_array;
121 static void read_input(struct tokenizer *t, struct tokbuf *tb)
127 while (tok = get_token(t))
133 for (char *c=tok; *c; c++)
134 if (*c >= 'a' && *c <= 'z')
143 add_token(tb, tok, t->toksize);
146 add_token(tb, "", 0);
150 static inline uns string_hash(unsigned char *x)
154 h = (h * 0x6011) + *x++;
158 static inline uns line_hash(struct tok *t, uns cnt)
162 h = (h * 0x6011) + (t++)->hash;
166 static int compare_toks(struct tok *x, struct tok *y)
168 if (x->hash < y->hash)
170 if (x->hash > y->hash)
172 return strcmp(x->token, y->token);
175 static int compare_lines(struct line *x, struct line *y)
177 if (x->hash < y->hash)
179 if (x->hash > y->hash)
187 for (uns i=0; i < x->len; i++)
189 int c = compare_toks(&x->toks[i], &y->toks[i]);
196 static void slurp(struct tokenizer *t, struct shouffle *s)
198 read_input(t, &s->tb);
199 s->tok_array = xmalloc(sizeof(struct tok) * s->tb.num_tokens);
200 s->line_array = xmalloc(sizeof(struct line) * (s->tb.num_lines+1));
203 struct tok *tok = s->tok_array;
204 struct line *line = s->line_array;
206 for (char *x = get_first(&s->tb); x; x = get_next(&s->tb))
210 tok->hash = string_hash(x);
215 line->len = tok - line->toks;
217 qsort(line->toks, line->len, sizeof(struct tok), (int(*)(const void *, const void *)) compare_toks);
218 line->hash = line_hash(line->toks, line->len);
219 line->orig_line = ++s->num_lines;
221 for (struct tok *t=line->toks; t<tok; t++)
222 printf("<%08x|%s>", t->hash, t->token);
223 printf(" -> %08x (%d)\n", line->hash, line->orig_line);
228 if (line->toks != tok)
229 die("Bug #41: unterminated line");
230 if (s->num_lines != s->tb.num_lines)
231 die("Bug #42: got %d lines, expected %d", s->num_lines, s->tb.num_lines);
234 qsort(s->line_array, s->num_lines, sizeof(struct line), (int(*)(const void *, const void *)) compare_lines);
237 static void compare(struct shouffle *s1, struct shouffle *s2)
239 if (s1->num_lines != s2->num_lines)
241 printf("Output has %d lines, expecting %d\n", s1->num_lines, s2->num_lines);
246 for (uns i=0; i<s1->num_lines; i++)
248 struct line *l1 = &s1->line_array[i], *l2 = &s2->line_array[i];
249 if (compare_lines(l1, l2))
251 printf("Line %d does not match\n", l1->orig_line);
252 printf(" %08x(%d) vs. %08x(%d)\n", l1->hash, l1->orig_line, l2->hash, l2->orig_line);
262 static void usage(void)
264 fprintf(stderr, "Usage: judge-shuff [<options>] <output> <correct>\n\
267 -n\t\tIgnore newlines and match the whole input as a single line\n\
268 -e\t\tIgnore empty lines\n\
269 -l\t\tShuffle lines (i.e., ignore their order)\n\
270 -w\t\tShuffle words in each line\n\
276 int main(int argc, char **argv)
278 struct tokenizer t1, t2;
281 while ((opt = getopt(argc, argv, "nelwi")) >= 0)
302 if (optind + 2 != argc)
305 tok_init(&t1, sopen_read(argv[optind]));
306 tok_init(&t2, sopen_read(argv[optind+1]));
308 t1.flags = t2.flags = TF_REPORT_LINES;
310 struct shouffle s1, s2;