Add C++ (17)

2 files changed, 144 insertions, 1 deletions

diff --git a/Makefile b/Makefile
index d5399b9..732fdf6 100644
--- a/Makefile
+++ b/Makefile
@@ -1,6 +1,7 @@
 BINARIES := \
 	mendeleev-c \
 	mendeleev-c-cpp \
+	mendeleev-cpp \
 	mendeleev-f \
 	mendeleev-hs \
 	mendeleev-py \
@@ -76,10 +77,20 @@ prof-%-c.txt: prof-%-c.gmon
 
 # C++
 CXX = g++
-CXXFLAGS = -std=c++98 -Wall -Wextra -O2
+CXXFLAGS = -std=c++17 -Wall -Wextra -O2
 %-c-cpp: %.c
 	$(CXX) $(CXXFLAGS) $< -o $@
 
+%-cpp: %.cpp
+	$(CXX) $(CXXFLAGS) $< -o $@
+
+CXXFLAGS_PROF = -O0 -g -pg
+prof-%-cpp: %.cpp
+	$(CXX) $(CXXFLAGS_PROF) $< -o $@
+
+prof-mendeleev-cpp.txt: prof-mendeleev-cpp.gmon
+	gprof --brief prof-mendeleev-cpp $< > $@
+
 
 # Fortran
 FC = gfortran
diff --git a/mendeleev.cpp b/mendeleev.cpp
new file mode 100644
index 0000000..cd2a8d3
--- /dev/null
+++ b/mendeleev.cpp
@@ -0,0 +1,132 @@
+#include <cstddef>
+#include <cstdlib>
+#include <iostream>
+#include <list>
+#include <optional>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+using std::list;
+using std::optional;
+using std::pair;
+using std::string_view;
+using std::vector;
+
+static const vector<string_view> 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"};
+
+typedef pair<size_t, string_view> Split;
+
+struct Element {
+  size_t eid;
+  optional<list<Element>> next;
+  Element(size_t eid_, optional<list<Element>> next_)
+      : eid(eid_), next(next_) {}
+};
+
+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 list<Split> split(string_view tail) {
+  auto x = list<Split>();
+
+  size_t start = 1;
+  size_t len = ELEMENTS.size() - 1;
+  size_t shift = 0;
+
+  while (shift < tail.length()) {
+    search(start, len, shift, tail[shift]);
+    if (!len)
+      break;
+
+    shift++;
+    if (shift == ELEMENTS[start].length()) {
+      x.emplace_back(start, tail.substr(shift));
+      start++;
+      len--;
+    }
+  }
+
+  if (x.empty())
+    x.emplace_back(0, tail.substr(1));
+
+  return x;
+}
+
+static list<Element> explode(string_view tail) {
+  auto x = list<Element>();
+  for (auto const &s : split(tail)) {
+    x.emplace_back(s.first, s.second.empty()
+                                ? std::nullopt
+                                : std::make_optional(explode(s.second)));
+  }
+  return x;
+}
+
+static void print_plain(list<Element> const &tree, vector<size_t> &formula) {
+  for (auto const &x : tree) {
+    formula.push_back(x.eid);
+    if (x.next)
+      print_plain(*x.next, formula);
+    else {
+      for (auto i : formula)
+        std::cout << " " << ELEMENTS[i];
+      std::cout << std::endl;
+    }
+    formula.pop_back();
+  }
+}
+
+int main(int argc, const char *argv[]) {
+  vector<size_t> formula;
+
+  for (int i = 1; i < argc; i++) {
+    string_view word = argv[i];
+    std::cout << word << ":" << std::endl;
+    if (auto len = word.length(); len) {
+      formula.reserve(len);
+      print_plain(explode(word), formula);
+    }
+  }
+
+  return EXIT_SUCCESS;
+}