judge/judge-shuff.c

   1 /*
   2  *      A judge comparing shuffled sequences of tokens
   3  *
   4  *      (c) 2007 Martin Krulis <bobrik@matfyz.cz>
   5  *      (c) 2007 Martin Mares <mj@ucw.cz>
   6  *
   7  *      FIXME: INCOMPLETE!
   8  */
   9
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12 #include <string.h>
  13 #include <getopt.h>
  14 #include <math.h>
  15
  16 #include "judge.h"
  17
  18 static int ignore_nl, ignore_empty, ignore_case;
  19 static int shuffle_lines, shuffle_words;
  20
  21 /*** Token buffer ***/
  22
  23 struct tokpage {
  24   struct tokpage *next;
  25   char *pos, *end;
  26   char buf[];
  27 };
  28
  29 struct tokbuf {
  30   // For writing:
  31   struct tokpage *first_page, *last_page;
  32   unsigned int num_tokens;
  33   // For reading:
  34   struct tokpage *this_page;
  35   char *read_pos;
  36 };
  37
  38 #define TOKBUF_PAGE 256
  39
  40 static void init_tokbuf(struct tokbuf *tb)
  41 {
  42   memset(tb, 0, sizeof(*tb));
  43 }
  44
  45 static void add_token(struct tokbuf *tb, char *token, int l)
  46 {
  47   l++;
  48   struct tokpage *pg = tb->last_page;
  49   if (!pg || pg->end - pg->pos < l)
  50     {
  51       int size = TOKBUF_PAGE - sizeof(struct tokbuf);
  52       if (l > size/5)
  53         size = l;
  54       pg = xmalloc(sizeof(struct tokbuf) + size);
  55       if (tb->last_page)
  56         tb->last_page->next = pg;
  57       else
  58         tb->first_page = pg;
  59       tb->last_page = pg;
  60       pg->next = NULL;
  61       pg->pos = pg->buf;
  62       pg->end = pg->buf + size;
  63     }
  64   memcpy(pg->pos, token, l);
  65   pg->pos += l;
  66   tb->num_tokens++;
  67 }
  68
  69 static char *get_next(struct tokbuf *tb)
  70 {
  71   struct tokpage *pg = tb->this_page;
  72   tb->read_pos += strlen(tb->read_pos) + 1;
  73   if (tb->read_pos >= pg->end)
  74     {
  75       tb->this_page = pg = pg->next;
  76       if (!pg)
  77         return NULL;
  78       tb->read_pos = pg->buf;
  79     }
  80   return tb->read_pos;
  81 }
  82
  83 static char *get_first(struct tokbuf *tb)
  84 {
  85   struct tokpage *pg = tb->first_page;
  86   if (!pg)
  87     return NULL;
  88   tb->this_page = pg;
  89   tb->read_pos = pg->buf;
  90   return pg->buf;
  91 }
  92
  93 /*** Reading of input ***/
  94
  95 struct tok {
  96   char *token;
  97   unsigned int hash;
  98 };
  99
 100 struct line {
 101   struct tok *toks;
 102   unsigned int num_toks;
 103   unsigned int hash;
 104 };
 105
 106 struct shouffle {
 107   struct tokbuf tb;
 108   struct tok *tok_array;
 109   struct line *line_array;
 110   unsigned int num_lines;
 111 };
 112
 113 static void read_input(struct tokenizer *t, struct tokbuf *tb)
 114 {
 115   char *tok;
 116   int nl = 1;
 117
 118   init_tokbuf(tb);
 119   while (tok = get_token(t))
 120     {
 121       if (tok[0])
 122         nl = 0;
 123       else
 124         {
 125           if (nl && ignore_nl)
 126             continue;
 127           nl = 1;
 128         }
 129       add_token(tb, tok, t->toksize);
 130     }
 131   if (!nl)
 132     add_token(tb, "", 0);
 133 }
 134
 135 static void slurp(struct tokenizer *t, struct shouffle *s)
 136 {
 137 }
 138
 139 /*** Main ***/
 140
 141 static void usage(void)
 142 {
 143   fprintf(stderr, "Usage: judge-shuff [<options>] <output> <correct>\n\
 144 \n\
 145 Options:\n\
 146 -n\t\tIgnore newlines and match the whole input as a single line\n\
 147 -e\t\tIgnore empty lines\n\
 148 -l\t\tShuffle lines (i.e., ignore their order)\n\
 149 -w\t\tShuffle words in each line\n\
 150 -i\t\tIgnore case\n\
 151 ");
 152   exit(2);
 153 }
 154
 155 int main(int argc, char **argv)
 156 {
 157   struct tokenizer t1, t2;
 158   int opt;
 159
 160   while ((opt = getopt(argc, argv, "nelwi")) >= 0)
 161     switch (opt)
 162       {
 163       case 'n':
 164         ignore_nl++;
 165         break;
 166       case 'e':
 167         ignore_empty++;
 168         break;
 169       case 'l':
 170         shuffle_lines++;
 171         break;
 172       case 'w':
 173         shuffle_words++;
 174         break;
 175       case 'i':
 176         ignore_case++;
 177         break;
 178       default:
 179         usage();
 180       }
 181   if (optind + 2 != argc)
 182     usage();
 183
 184   tok_init(&t1, sopen_read(argv[optind]));
 185   tok_init(&t2, sopen_read(argv[optind+1]));
 186   if (!ignore_nl)
 187     t1.flags = t2.flags = TF_REPORT_LINES;
 188
 189   struct tokbuf b1;
 190   read_input(&t1, &b1);
 191
 192   return 0;
 193 }