git.ozlabs.org Git - ccan/blob - ccan/aga/test/api-lazytrie.c

   1 #include "config.h"
   2
   3 #include <stddef.h>
   4 #include <assert.h>
   5
   6 #include <ccan/ptrint/ptrint.h>
   7 #include <ccan/tal/tal.h>
   8 #include <ccan/tal/str/str.h>
   9 #include <ccan/take/take.h>
  10 #include <ccan/tal/grab_file/grab_file.h>
  11 #include <ccan/container_of/container_of.h>
  12
  13 #include <ccan/aga/aga.h>
  14
  15 #include <ccan/tap/tap.h>
  16
  17 #define NWORDS          1000
  18 #define LETTERS         "abcdefghijklmnopqrstuvwxyz"
  19 #define NLETTERS        (sizeof(LETTERS) - 1)
  20
  21 char **wordarray;
  22 char **wordarrayb; /* Word array sorted by length */
  23 int nwords;
  24
  25 struct trie_node {
  26         int start, end;
  27         const char *prefix;
  28         bool isword;
  29         struct trie_node *next[NLETTERS];
  30         struct aga_node agan;
  31 };
  32
  33 /* Sorts by length first, then alphabetically */
  34 static int lensort(const void *xv, const void *yv)
  35 {
  36         char *x = *((char **)xv);
  37         char *y = *((char **)yv);
  38         int xn = strlen(x);
  39         int yn = strlen(y);
  40
  41         if (xn < yn)
  42                 return -1;
  43         else if (xn > yn)
  44                 return 1;
  45         else
  46                 /* We need this because qsort is not stable */
  47                 return strcmp(x, y);
  48 }
  49
  50 static void setup_words(void)
  51 {
  52         char *wordfile;
  53
  54         /* read in the words */
  55         wordfile = grab_file(NULL, "test/api-lazytrie-words.txt");
  56         ok1(wordfile);
  57         wordarray = tal_strsplit(NULL, take(wordfile), "\n", STR_NO_EMPTY);
  58         ok1(wordarray);
  59         nwords = tal_count(wordarray) - 1;
  60         diag("lazytrie: %d words loaded", nwords);
  61         ok1(nwords == NWORDS);
  62
  63         wordarrayb = tal_arr(NULL, char *, nwords);
  64         memcpy(wordarrayb, wordarray, tal_count(wordarrayb) * sizeof(char *));
  65
  66         qsort(wordarrayb, nwords, sizeof(char *), lensort);
  67 }
  68
  69 struct lazytrie {
  70         struct trie_node root;
  71         struct aga_graph g;
  72 };
  73
  74 static void init_trie_node(struct trie_node *n, int start, int end,
  75                            const char *prefix)
  76 {
  77         int i;
  78
  79         n->start = start;
  80         n->end = end;
  81         n->prefix = prefix;
  82         n->isword = (strcmp(n->prefix, wordarray[n->start]) == 0);
  83
  84         for (i = 0; i < NLETTERS; i++)
  85                 n->next[i] = NULL;
  86
  87         aga_node_init(&n->agan);
  88 }
  89
  90 static ptrint_t *lazytrie_first_edge(const struct aga_graph *g,
  91                                      const struct aga_node *n)
  92 {
  93         return int2ptr(1);
  94 }
  95
  96 static ptrint_t *lazytrie_next_edge(const struct aga_graph *g,
  97                                     const struct aga_node *n,
  98                                     ptrint_t *e)
  99 {
 100         int index = ptr2int(e);
 101
 102         assert((index >= 1) && (index <= NLETTERS));
 103         if (index == NLETTERS)
 104                 return NULL;
 105         else
 106                 return int2ptr(index + 1);
 107 }
 108
 109 static int lazytrie_edge_info(const struct aga_graph *g,
 110                               const struct aga_node *n,
 111                               ptrint_t *e,
 112                               struct aga_edge_info *ei)
 113 {
 114         struct trie_node *tn = container_of(n, struct trie_node, agan);
 115         struct trie_node *next;
 116         int index = ptr2int(e);
 117
 118         assert((index >= 1) && (index <= NLETTERS));
 119
 120         next = tn->next[index - 1];
 121
 122         if (!next) {
 123                 int depth = strlen(tn->prefix);
 124                 int start, end;
 125
 126                 start = tn->start;
 127                 while (start < tn->end) {
 128                         if (wordarray[start][depth] >= LETTERS[index - 1])
 129                                 break;
 130                         start++;
 131                 }
 132
 133                 end = start;
 134                 while (end < tn->end) {
 135                         if (wordarray[end][depth] > LETTERS[index - 1])
 136                                 break;
 137                         end++;
 138                 }
 139
 140                 if (end > start) {
 141                         char plus[2] = { LETTERS[index - 1], '\0' };
 142                         next = tal(tn, struct trie_node);
 143                         init_trie_node(next, start, end,
 144                                        tal_strcat(next, tn->prefix, plus));
 145                 }
 146         }
 147
 148         if (next)
 149                 ei->to = &next->agan;
 150         return 0;
 151 }
 152
 153 static struct lazytrie *setup_trie(void)
 154 {
 155         struct lazytrie *lt;
 156
 157         lt = tal(NULL, struct lazytrie);
 158         init_trie_node(&lt->root, 0, nwords, "");
 159         aga_init_graph(&lt->g, lazytrie_first_edge, lazytrie_next_edge,
 160                        lazytrie_edge_info);
 161         return lt;
 162 }
 163
 164 int main(void)
 165 {
 166         struct lazytrie *lt;
 167         struct aga_node *an;
 168         int xn;
 169
 170         plan_tests(3 + NWORDS*2);
 171         setup_words();
 172
 173         lt = setup_trie();
 174
 175         aga_dfs_start(&lt->g);
 176
 177         xn = 0;
 178         aga_dfs(an, &lt->g, &lt->root.agan) {
 179                 struct trie_node *n = container_of(an, struct trie_node, agan);
 180
 181                 diag("Visited \"%s\"\n", n->prefix);
 182
 183                 if (n->isword) {
 184                         ok1(strcmp(n->prefix, wordarray[xn]) == 0);
 185                         xn++;
 186                 }
 187         }
 188
 189         aga_finish(&lt->g);
 190
 191         tal_free(lt);
 192
 193         lt = setup_trie();
 194
 195         aga_bfs_start(&lt->g);
 196
 197         xn = 0;
 198         aga_bfs(an, &lt->g, &lt->root.agan) {
 199                 struct trie_node *n = container_of(an, struct trie_node, agan);
 200
 201                 diag("Visited \"%s\"\n", n->prefix);
 202
 203                 if (n->isword) {
 204                         ok1(strcmp(n->prefix, wordarrayb[xn]) == 0);
 205                         xn++;
 206                 }
 207         }
 208
 209         /* This exits depending on whether all tests passed */
 210         return exit_status();
 211 }