chiark - git - mdw - wordchain/blob - chain.cc

   1 #include <cassert>
   2 #include <cstdarg>
   3 #include <cstdio>
   4 #include <cstdlib>
   5 #include <cstring>
   6
   7 #include <string>
   8 #include <utility>
   9
  10 #define CXX_MAP 1
  11 #define CXX_UOMAP 2
  12
  13 struct Node;
  14 typedef std::pair<const std::string, Node> WordNode;
  15 struct Node {
  16   WordNode *down, *right, *up;
  17   int len;
  18 };
  19
  20 #if !TREE
  21 #  error "`TREE' not defined or bungled constant setting"
  22 #elif TREE == CXX_MAP
  23 #  include <map>
  24    typedef std::map<std::string, Node> Map;
  25 #elif TREE == CXX_UOMAP
  26 #  include <unordered_map>
  27    typedef std::unordered_map<std::string, Node> Map;
  28 #else
  29 #  error "unknown `TREE' value"
  30 #endif
  31
  32 #define WORDMAX 64
  33
  34 static void bail(const char *msg, ...)
  35 {
  36   va_list ap;
  37   long pos;
  38
  39   va_start(ap, msg); std::vfprintf(stderr, msg, ap); va_end(ap);
  40   pos = std::ftell(stdin);
  41   if (pos >= 0) std::fprintf(stderr, " (input pos = %ld)", pos);
  42   std::fputc('\n', stderr);
  43   std::exit(2);
  44 }
  45
  46 static void print_chain(WordNode *wnode)
  47 {
  48   const std::string *word = &wnode->first;
  49   Node *node = &wnode->second;
  50
  51   if (!node->right) {
  52     std::fputs(word->c_str(), stdout);
  53     if (node->down)
  54       { std::putchar(' '); print_chain(node->down); }
  55   } else {
  56     std::fputs("{ ", stdout);
  57     for (;;) {
  58       std::fputs(word->c_str(), stdout);
  59       if (node->down)
  60         { std::putchar(' '); print_chain(node->down); }
  61       wnode = node->right; if (!wnode) break;
  62       std::fputs(" | ", stdout);
  63       word = &wnode->first; node = &wnode->second;
  64     }
  65     std::fputs(" }", stdout);
  66   }
  67 }
  68
  69 int main(void)
  70 {
  71   Map map{};
  72   char buf[WORDMAX]; size_t n;
  73
  74   for (;;) {
  75     if (!std::fgets(buf, WORDMAX, stdin)) break;
  76     n = std::strlen(buf); assert(n);
  77     if (buf[n - 1] == '\n') buf[--n] = 0;
  78     else if (n == WORDMAX - 1) bail("word too long");
  79     else {
  80       int ch;
  81       if (ch = std::getchar(), ch != EOF)
  82         bail("short read, found `%c'", ch);
  83     }
  84
  85     auto r = map.insert(WordNode(std::string(buf, n), Node{}));
  86     if (!r.second) printf(";; duplicate `%s'\n", buf);
  87     else {
  88       Node *node = &r.first->second;
  89       node->len = 1; node->up = node->down = node->right = 0;
  90     }
  91   }
  92
  93   int max = 0;
  94
  95   for (auto p = map.begin(); p != map.end(); ++p) {
  96     /* std::fprintf(stderr, ";; ponder `%.*s'\n",
  97                     p->first.length(), p->first.c_str()); */
  98     WordNode *wnode = &*p, *pwnode;
  99     const std::string *word = &wnode->first;
 100     Node *node = &wnode->second;
 101     if (word->length() <= 1)
 102       pwnode = 0;
 103     else {
 104       /* std::fprintf(stderr, ";; search `%.*s'\n",
 105                       w->first.length(), w->first.c_str()); */
 106       std::string prefix{*word, 0, word->length() - 1};
 107       auto p = map.find(prefix); pwnode = p == map.end() ? 0 : &*p;
 108     }
 109     int nlen = node->len;
 110     node->up = pwnode;
 111     while (pwnode) {
 112       Node *parent = &pwnode->second;
 113       nlen++; int plen = parent->len;
 114       if (plen > nlen)
 115         break;
 116       else if (plen == nlen) {
 117         node->right = parent->down; parent->down = wnode;
 118         break;
 119       } else {
 120         parent->down = wnode; node->right = 0;
 121         parent->len = nlen;
 122         wnode = pwnode; node = &wnode->second; pwnode = node->up;
 123       }
 124     }
 125     if (nlen > max) max = nlen;
 126   }
 127
 128   for (auto p = map.begin(); p != map.end(); ++p)
 129     if (p->second.len == max) { print_chain(&*p); std::putchar('\n'); }
 130   return (0);
 131 }