Make primary a tree-based implementation

3 files changed, 80 insertions, 265 deletions

diff --git a/Makefile b/Makefile
index 51fcc76..49a7570 100644
--- a/Makefile
+++ b/Makefile
@@ -4,7 +4,6 @@ BINARIES := \
 	mendeleev-f \
 	mendeleev-hs \
 	mendeleev-py \
-	mendeleev-tree-c \
 
 LISP := \
 	clisp:mendeleev.lisp \
@@ -53,7 +52,6 @@ prof: \
 	prof-mendeleev-f.txt \
 	prof-mendeleev-hs.txt \
 	prof-mendeleev-py.txt \
-	prof-mendeleev-tree-c.txt \
 
 %.gmon: %
 	$(RM) $<-gmon.*
diff --git a/mendeleev-tree.c b/mendeleev-tree.c
deleted file mode 100644
index 2ab20e1..0000000
--- a/mendeleev-tree.c
+++ /dev/null
@@ -1,182 +0,0 @@
-#include<stdio.h>
-#include<stdlib.h>
-#include<string.h>
-
-static const char *const ELEMENTS[] = { "?",
-  "Ac", "Ag", "Al", "Am", "Ar", "As", "At", "Au", "B", "Ba", "Be", "Bh",
-  "Bi", "Bk", "Br", "C", "Ca", "Cd", "Ce", "Cf", "Cl", "Cm", "Cn", "Co",
-  "Cr", "Cs", "Cu", "Db", "Ds", "Dy", "Er", "Es", "Eu", "F", "Fe", "Fl",
-  "Fm", "Fr", "Ga", "Gd", "Ge", "H", "He", "Hf", "Hg", "Ho", "Hs", "I",
-  "In", "Ir", "K", "Kr", "La", "Li", "Lr", "Lu", "Lv", "Mc", "Md", "Mg",
-  "Mn", "Mo", "Mt", "N", "Na", "Nb", "Nd", "Ne", "Nh", "Ni", "No", "Np",
-  "O", "Og", "Os", "P", "Pa", "Pb", "Pd", "Pm", "Po", "Pr", "Pt", "Pu",
-  "Ra", "Rb", "Re", "Rf", "Rg", "Rh", "Rn", "Ru", "S", "Sb", "Sc", "Se",
-  "Sg", "Si", "Sm", "Sn", "Sr", "Ta", "Tb", "Tc", "Te", "Th", "Ti", "Tl",
-  "Tm", "Ts", "U", "V", "W", "Xe", "Y", "Yb", "Zn", "Zr"
-};
-
-static const size_t NELEMENTS = sizeof (ELEMENTS) / sizeof (const char *) - 1;
-
-typedef struct element
-{
-  size_t n;
-  const char *tail;
-  struct element *sibs;
-  struct element *next;
-} element_t;
-
-static void
-search (size_t *start, size_t *len, size_t shift, char c)
-{
-  size_t l, m, u;
-  c |= ' ';
-
-  u = *start + *len;
-  l = *start;
-  while (l < u)
-    {
-      m = (l + u) / 2;
-      if ((ELEMENTS[m][shift] | ' ') < c)
-        l = m + 1;
-      else
-        u = m;
-    }
-
-  if ((l == *start + *len) || ((ELEMENTS[l][shift] | ' ') != c))
-    {
-      *len = 0;
-      return;
-    }
-
-  u = *start + *len;
-  *start = l;
-  while (l < u)
-    {
-      m = (l + u) / 2;
-      if (c < (ELEMENTS[m][shift] | ' '))
-        u = m;
-      else
-        l = m + 1;
-    }
-
-  *len = u - *start;
-}
-
-static element_t *
-divide (const char *tail)
-{
-  element_t *head = NULL;
-  element_t *last = NULL;
-
-  size_t start = 1;
-  size_t len = NELEMENTS;
-  size_t shift = 0;
-
-  while (tail[shift])
-    {
-      search (&start, &len, shift, tail[shift]);
-      if (!len)
-        break;
-
-      shift++;
-      if (!ELEMENTS[start][shift])
-        {
-          element_t *el = (element_t *) malloc (sizeof (element_t));
-          if (!el)
-            break;
-
-          if (!head)
-            head = el;
-
-          if (last)
-            last->sibs = el;
-
-          last = el;
-          last->n = start;
-          last->tail = &tail[shift];
-          start++;
-          len--;
-        }
-    }
-
-  if (!head)
-    {
-      head = (element_t *) malloc (sizeof (element_t));
-      if (!head)
-        return NULL;
-      head->n = 0;
-      head->tail = &tail[1];
-      last = head;
-    }
-
-  last->sibs = NULL;
-
-  return head;
-}
-
-static element_t *
-explode (const char *word)
-{
-  element_t *root = divide (word);
-  for (element_t * el = root; el; el = el->sibs)
-    el->next = *el->tail ? explode (el->tail) : NULL;
-  return root;
-}
-
-static void
-free_elements (element_t * el)
-{
-  while (el)
-    {
-      if (el->next)
-        free_elements (el->next);
-      element_t *sib = el->sibs;
-      free (el);
-      el = sib;
-    }
-}
-
-static void
-print_plain (const element_t * current, size_t *formula, size_t n)
-{
-  for (const element_t * el = current; el; el = el->sibs)
-    {
-      formula[n] = el->n;
-      if (el->next)
-        print_plain (el->next, formula, n + 1);
-      else
-        {
-          for (size_t i = 0; i <= n; i++)
-            printf (" %s", ELEMENTS[formula[i]]);
-          printf ("\n");
-        }
-    }
-}
-
-int
-main (int argc, const char *argv[])
-{
-  for (int i = 1; i < argc; i++)
-    {
-      const char *word = argv[i];
-      printf ("%s:\n", word);
-
-      size_t len = strlen (word);
-      if (!len)
-        continue;
-
-      element_t *root = explode (word);
-      if (!root)
-        return EXIT_FAILURE;
-
-      size_t *formula = (size_t *) malloc (len * sizeof (size_t));
-      if (!formula)
-        return EXIT_FAILURE;
-
-      print_plain (root, formula, 0);
-      free (formula);
-      free_elements (root);
-    }
-
-  return EXIT_SUCCESS;
-}
diff --git a/mendeleev.c b/mendeleev.c
index e48b129..2ab20e1 100644
--- a/mendeleev.c
+++ b/mendeleev.c
@@ -17,14 +17,13 @@ static const char *const ELEMENTS[] = { "?",
 
 static const size_t NELEMENTS = sizeof (ELEMENTS) / sizeof (const char *) - 1;
 
-typedef struct formula
+typedef struct element
 {
-  const char *tail;
   size_t n;
-  size_t *els;
-  struct formula *next;
-} formula_t;
-
+  const char *tail;
+  struct element *sibs;
+  struct element *next;
+} element_t;
 
 static void
 search (size_t *start, size_t *len, size_t shift, char c)
@@ -63,48 +62,11 @@ search (size_t *start, size_t *len, size_t shift, char c)
   *len = u - *start;
 }
 
-static formula_t *
-new_formula (const char *tail, size_t n, const size_t *els)
-{
-  formula_t *f = (formula_t *) malloc (sizeof (formula_t));
-  if (!f)
-    return NULL;
-
-  f->els = (size_t *) malloc (sizeof (*f->els) * (n + strlen (tail)));
-  if (!f->els)
-    {
-      free (f);
-      return NULL;
-    }
-
-  if (n > 0)
-    (void) memcpy (f->els, els, n * sizeof (*f->els));
-
-  f->n = n;
-  f->tail = tail;
-  f->next = NULL;
-
-  return f;
-}
-
-static void
-free_formula (formula_t * f)
+static element_t *
+divide (const char *tail)
 {
-  while (f)
-    {
-      formula_t *next = f->next;
-      if (f->els)
-        free (f->els);
-      free (f);
-      f = next;
-    }
-}
-
-static void
-advance (formula_t * f)
-{
-  const char *tail = f->tail;
-  size_t n = f->n;
+  element_t *head = NULL;
+  element_t *last = NULL;
 
   size_t start = 1;
   size_t len = NELEMENTS;
@@ -119,64 +81,101 @@ advance (formula_t * f)
       shift++;
       if (!ELEMENTS[start][shift])
         {
-          if (n != f->n)
-            {
-              formula_t *g = new_formula (tail, n, f->els);
-              if (!g)
-                break;
-              g->next = f->next;
-              f->next = g;
-              f = g;
-            }
-
-          f->els[f->n++] = start;
-          f->tail = &tail[shift];
+          element_t *el = (element_t *) malloc (sizeof (element_t));
+          if (!el)
+            break;
+
+          if (!head)
+            head = el;
+
+          if (last)
+            last->sibs = el;
+
+          last = el;
+          last->n = start;
+          last->tail = &tail[shift];
           start++;
           len--;
         }
     }
 
-  if (n == f->n)
+  if (!head)
     {
-      f->els[f->n++] = 0;
-      f->tail += 1;
+      head = (element_t *) malloc (sizeof (element_t));
+      if (!head)
+        return NULL;
+      head->n = 0;
+      head->tail = &tail[1];
+      last = head;
     }
+
+  last->sibs = NULL;
+
+  return head;
 }
 
-static formula_t *
+static element_t *
 explode (const char *word)
 {
-  formula_t *formula = new_formula (word, 0, NULL);
-  if (!formula)
-    return NULL;
+  element_t *root = divide (word);
+  for (element_t * el = root; el; el = el->sibs)
+    el->next = *el->tail ? explode (el->tail) : NULL;
+  return root;
+}
 
-  for (formula_t * f = formula; f; f = f->next)
-    while (*f->tail)
-      advance (f);
+static void
+free_elements (element_t * el)
+{
+  while (el)
+    {
+      if (el->next)
+        free_elements (el->next);
+      element_t *sib = el->sibs;
+      free (el);
+      el = sib;
+    }
+}
 
-  return formula;
+static void
+print_plain (const element_t * current, size_t *formula, size_t n)
+{
+  for (const element_t * el = current; el; el = el->sibs)
+    {
+      formula[n] = el->n;
+      if (el->next)
+        print_plain (el->next, formula, n + 1);
+      else
+        {
+          for (size_t i = 0; i <= n; i++)
+            printf (" %s", ELEMENTS[formula[i]]);
+          printf ("\n");
+        }
+    }
 }
 
 int
 main (int argc, const char *argv[])
 {
-  for (int w = 1; w < argc; w++)
+  for (int i = 1; i < argc; i++)
     {
-      const char *word = argv[w];
+      const char *word = argv[i];
       printf ("%s:\n", word);
 
-      formula_t *formula = explode (word);
+      size_t len = strlen (word);
+      if (!len)
+        continue;
+
+      element_t *root = explode (word);
+      if (!root)
+        return EXIT_FAILURE;
+
+      size_t *formula = (size_t *) malloc (len * sizeof (size_t));
       if (!formula)
         return EXIT_FAILURE;
 
-      for (formula_t * f = formula; f; f = f->next)
-        {
-          for (size_t i = 0; i < f->n; i++)
-            printf (" %s", ELEMENTS[f->els[i]]);
-          if (f->n)
-            printf ("\n");
-        }
-      free_formula (formula);
+      print_plain (root, formula, 0);
+      free (formula);
+      free_elements (root);
     }
 
   return EXIT_SUCCESS;