C: add version using a tree

2 files changed, 191 insertions, 8 deletions

diff --git a/Makefile b/Makefile
index 1bc79ff..9a3f9cd 100644
--- a/Makefile
+++ b/Makefile
@@ -4,6 +4,7 @@ BINARIES := \
 	mendeleev-f \
 	mendeleev-hs \
 	mendeleev-py \
+	mendeleev-tree-c \
 
 SCRIPTS := \
 	python2:mendeleev.py \
@@ -44,7 +45,8 @@ prof: \
 	prof-mendeleev-c.txt \
 	prof-mendeleev-f.txt \
 	prof-mendeleev-hs.txt \
-	prof-mendeleev-py.txt
+	prof-mendeleev-py.txt \
+	prof-mendeleev-tree-c.txt \
 
 %.gmon: %
 	$(RM) $<-gmon.*
@@ -55,21 +57,21 @@ prof: \
 # C
 CC = gcc
 CFLAGS = -std=c99 -Wall -Wextra -O2
-mendeleev-c: mendeleev.c
+%-c: %.c
 	$(CC) $(CFLAGS) $< -o $@
 
 CFLAGS_PROF = -O0 -g -pg
-prof-mendeleev-c: mendeleev.c
+prof-%-c: %.c
 	$(CC) $(CFLAGS_PROF) $< -o $@
 
-prof-mendeleev-c.txt: prof-mendeleev-c.gmon
-	gprof --brief prof-mendeleev-c $< > $@
+prof-%-c.txt: prof-%-c.gmon
+	gprof --brief prof-$*-c $< > $@
 
 
 # C++
 CXX = g++
 CXXFLAGS = -std=c++98 -Wall -Wextra -O2
-mendeleev-c-cpp: mendeleev.c
+%-c-cpp: %.c
 	$(CXX) $(CXXFLAGS) $< -o $@
 
 
@@ -101,6 +103,7 @@ prof-mendeleev-hs.txt: prof-mendeleev-hs
 	./$< +RTS -p -RTS $(PROF_TEST) > /dev/null
 	$(MV) $<.prof $@
 
+
 # Python
 NUITKA = nuitka3
 NUITKA_FLAGS = --quiet --remove-output --follow-imports
@@ -113,5 +116,3 @@ prof-mendeleev-py.dat: mendeleev.py
 prof-mendeleev-py.txt: prof-mendeleev-py.dat
 	python3 -c 'import pstats; pstats.Stats("$<").sort_stats("tottime").print_stats()' > $@
 
-
-
diff --git a/mendeleev-tree.c b/mendeleev-tree.c
new file mode 100644
index 0000000..2ab20e1
--- /dev/null
+++ b/mendeleev-tree.c
@@ -0,0 +1,182 @@
+#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;
+}