1 files changed, 188 insertions, 0 deletions
diff --git a/diff.cpp b/diff.cpp
new file mode 100644
index 0000000..6ac24e7
--- /dev/null
+++ b/diff.cpp
@@ -0,0 +1,188 @@
+#include "diff.h"
+
+#include <algorithm>
+#include <iostream>
+#include <sstream>
+
+#include <boost/property_tree/xml_parser.hpp>
+
+namespace pt = boost::property_tree;
+
+Diff::Diff()
+{
+}
+
+Diff::Diff(const std::string& old_version, const std::string& new_version)
+{
+ create(old_version, new_version);
+}
+
+std::string Diff::apply(const std::string& old_version) const
+{
+ std::string result{old_version};
+
+ if (m_pos0 <= m_pos1 && m_pos1 <= old_version.size()) {
+  result.erase(m_pos0, m_pos1 - m_pos0);
+  result.insert(m_pos0, m_data);
+ }
+ 
+ return result;
+}
+
+void Diff::create(const std::string& old_version, const std::string& new_version)
+{
+ auto front_mismatch{std::mismatch(old_version.cbegin(), old_version.cend(), new_version.cbegin(), new_version.cend())};
+ std::string::difference_type old_pos0 {front_mismatch.first - old_version.cbegin()};
+ auto& new_pos0 {old_pos0};
+
+ // equal
+ if (old_pos0 == old_version.size() && new_pos0 == new_version.size()) {
+  m_pos0 = 0;
+  m_pos1 = 0;
+  m_data.clear();
+  return;
+ }
+
+ // append at end
+ if (old_pos0 == old_version.size()) {
+  m_pos0 = old_pos0;
+  m_pos1 = old_pos0;
+  m_data = new_version.substr(new_pos0);
+  return;
+ }
+
+ // remove from end
+ if (new_pos0 == new_version.size()) {
+  m_pos0 = old_pos0;
+  m_pos1 = old_version.size();
+  m_data.clear();
+  return;
+ }
+
+ auto back_mismatch{std::mismatch(old_version.crbegin(), old_version.crend(), new_version.crbegin(), new_version.crend())};
+ // i.e. the indices starting from which we can assume equality
+ size_t old_pos1 {old_version.size() - (back_mismatch.first - old_version.crbegin())};
+ size_t new_pos1 {new_version.size() - (back_mismatch.second - new_version.crbegin())};
+
+ // complete equality is already handled above
+ 
+ // insert at start
+ if (old_pos1 == 0) {
+  m_pos0 = 0;
+  m_pos1 = 0;
+  m_data = new_version.substr(0, new_pos1);
+  return;
+ }
+
+ // remove from start
+ if (new_pos1 == 0) {
+  m_pos0 = 0;
+  m_pos1 = old_pos1;
+  m_data.clear();
+  return;
+ }
+
+ // re-adjust if search crossed
+ if (old_pos0 > old_pos1) {
+  old_pos0 = old_pos1;
+  new_pos0 = old_pos1;
+ }
+ if (new_pos0 > new_pos1) {
+  old_pos0 = new_pos1;
+  new_pos0 = new_pos1;
+ }
+
+ // insert in the middle
+ if (old_pos0 == old_pos1) {
+  m_pos0 = old_pos0;
+  m_pos1 = old_pos0;
+  m_data = new_version.substr(new_pos0, new_pos1 - new_pos0);
+  return;
+ }
+ 
+ // remove from the middle
+ if (new_pos0 == new_pos1) {
+  m_pos0 = old_pos0;
+  m_pos1 = old_pos1;
+  m_data.clear();
+  return;
+ }
+
+ // last resort: remove and add in the middle
+ m_pos0 = old_pos0;
+ m_pos1 = old_pos1;
+ m_data = new_version.substr(old_pos0, new_pos1 - new_pos0);
+}
+
+Diff::Diff(const boost::property_tree::ptree& ptree)
+{
+ create(ptree);
+}
+
+void Diff::create(const boost::property_tree::ptree& ptree)
+{
+ m_pos0 = ptree.get<int>("diff.start");
+ m_pos1 = ptree.get<int>("diff.end");
+
+ if (m_pos0 > m_pos1)
+  throw std::runtime_error("Bad range in diff");
+
+ m_data = ptree.get<std::string>("diff.data");
+}
+
+Diff::Diff(const std::string& xml)
+{
+ create(xml);
+}
+
+void Diff::create(const std::string& xml)
+{
+ pt::ptree ptree;
+ std::istringstream ss{xml};
+ pt::read_xml(ss, ptree);
+
+ create(ptree);
+}
+
+bool Diff::empty() const
+{
+ return m_pos0 == m_pos1 && m_data.empty();
+}
+
+boost::property_tree::ptree Diff::get_structure() const
+{
+ pt::ptree ptree;
+ ptree.put("diff.start", std::to_string(m_pos0));
+ ptree.put("diff.end", std::to_string(m_pos1));
+ ptree.put("diff.data", m_data);
+
+ return ptree;
+}
+
+std::string Diff::get_xml() const
+{
+ pt::ptree ptree{get_structure()};
+
+ std::ostringstream oss;
+ // write_xml_element instead of write_xml to omit <!xml...> header
+ //pt::xml_parser::write_xml(oss, xml);
+ pt::xml_parser::write_xml_element(oss, {}, ptree, -1, boost::property_tree::xml_writer_settings<pt::ptree::key_type>{});
+ return oss.str();
+}
+
+extern "C" {
+
+ const char* diff_create(const char* old_version, const char* new_version)
+ {
+  Diff diff{old_version, new_version};
+  return strdup(diff.get_xml().c_str());
+ }
+
+ const char* diff_apply(const char* old_version, const char* diff)
+ {
+  Diff d{diff};
+
+  return strdup(d.apply(old_version).c_str());
+ }
+
+}