1 files changed, 125 insertions, 0 deletions
diff --git a/diff.cpp b/diff.cpp
new file mode 100644
index 0000000..b3ed5ce
--- /dev/null
+++ b/diff.cpp
@@ -0,0 +1,125 @@
+#include "diff.h"
+
+#include <algorithm>
+#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};
+
+ 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;
+ }
+
+ // 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);
+}
+
+boost::property_tree::ptree Diff::get_structure() const
+{
+ pt::ptree ptree;
+ ptree.put("diff.chunk.start", std::to_string(m_pos0));
+ ptree.put("diff.chunk.end", std::to_string(m_pos1));
+ ptree.put("diff.chunk.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();
+}
+