More things.

[wordchain] / chain.cc

diff --git a/chain.cc b/chain.cc
index 0fd7e6e1c471e14f041bad84ac11deea9fae4d4e..a21dc89aa180f274f665000ad65ec918475f5869 100644 (file)
--- a/chain.cc
+++ b/chain.cc
@@ -43,20 +43,24 @@ static void bail(const char *msg, ...)
   std::exit(2);
 }
 
-static void print_chain(WordNode *node)
+static void print_chain(WordNode *wnode)
 {
-  if (!node->second.right) {
-    std::fputs(node->first.c_str(), stdout);
-    if (node->second.down)
-      { std::putchar(' '); print_chain(node->second.down); }
+  const std::string *word = &wnode->first;
+  Node *node = &wnode->second;
+
+  if (!node->right) {
+    std::fputs(word->c_str(), stdout);
+    if (node->down)
+      { std::putchar(' '); print_chain(node->down); }
   } else {
     std::fputs("{ ", stdout);
     for (;;) {
-      std::fputs(node->first.c_str(), stdout);
-      if (node->second.down)
-       { std::putchar(' '); print_chain(node->second.down); }
-      node = node->second.right; if (!node) break;
+      std::fputs(word->c_str(), stdout);
+      if (node->down)
+       { std::putchar(' '); print_chain(node->down); }
+      wnode = node->right; if (!wnode) break;
       std::fputs(" | ", stdout);
+      word = &wnode->first; node = &wnode->second;
     }
     std::fputs(" }", stdout);
   }
@@ -66,51 +70,59 @@ int main(void)
 {
   Map map{};
   char buf[WORDMAX]; size_t n;
-  int ch, max;
 
   for (;;) {
     if (!std::fgets(buf, WORDMAX, stdin)) break;
     n = std::strlen(buf); assert(n);
     if (buf[n - 1] == '\n') buf[--n] = 0;
     else if (n == WORDMAX - 1) bail("word too long");
-    else if (ch = std::getchar(), ch != EOF)
-      bail("short read, found `%c'", ch);
+    else {
+      int ch;
+      if (ch = std::getchar(), ch != EOF)
+       bail("short read, found `%c'", ch);
+    }
 
     auto r = map.insert(WordNode(std::string(buf, n), Node{}));
     if (!r.second) printf(";; duplicate `%s'\n", buf);
     else {
-      WordNode *w = &*r.first;
-      w->second.up = w->second.down = w->second.right = 0;
-      w->second.len = 1;
+      Node *node = &r.first->second;
+      node->len = 1; node->up = node->down = node->right = 0;
     }
   }
 
-  max = 0;
+  int max = 0;
 
   for (auto p = map.begin(); p != map.end(); ++p) {
-/* std::fprintf(stderr, ";; ponder `%.*s'\n",
-               p->first.length(), p->first.c_str()); */
-    WordNode *w = &*p, *parent;
-    if (w->first.length() <= 1)
-      parent = 0;
+    /* std::fprintf(stderr, ";; ponder `%.*s'\n",
+                   p->first.length(), p->first.c_str()); */
+    WordNode *wnode = &*p, *pwnode;
+    const std::string *word = &wnode->first;
+    Node *node = &wnode->second;
+    if (word->length() <= 1)
+      pwnode = 0;
     else {
-/* std::fprintf(stderr, ";; search `%.*s'\n",
-               w->first.length(), w->first.c_str()); */
-      std::string prefix{w->first, 0, w->first.length() - 1};
-      auto p = map.find(prefix); parent = p == map.end() ? 0 : &*p;
+      /* std::fprintf(stderr, ";; search `%.*s'\n",
+                     w->first.length(), w->first.c_str()); */
+      std::string prefix{*word, 0, word->length() - 1};
+      auto p = map.find(prefix); pwnode = p == map.end() ? 0 : &*p;
     }
-    w->second.up = parent;
-    while (parent) {
-      if (parent->second.len > w->second.len + 1) break;
-      if (parent->second.len < w->second.len + 1) parent->second.down = 0;
-      if (parent->second.down != w) {
-       w->second.right = parent->second.down;
-       parent->second.down = w;
+    int nlen = node->len;
+    node->up = pwnode;
+    while (pwnode) {
+      Node *parent = &pwnode->second;
+      nlen++; int plen = parent->len;
+      if (plen > nlen)
+       break;
+      else if (plen == nlen) {
+       node->right = parent->down; parent->down = wnode;
+       break;
+      } else {
+       parent->down = wnode; node->right = 0;
+       parent->len = nlen;
+       wnode = pwnode; node = &wnode->second; pwnode = node->up;
       }
-      parent->second.len = w->second.len + 1;
-      if (parent->second.len > max) max = parent->second.len;
-      w = parent; parent = w->second.up;
     }
+    if (nlen > max) max = nlen;
   }
 
   for (auto p = map.begin(); p != map.end(); ++p)