1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
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();
}
|
