yavom

Yet Another Variation of Myers for generic containers (for example std::vector)

This is an implementation of a quasi-Myers algorithm to determine the differences between two generic containers. Everything is included in diff.h. Its usage is quite simple, for example:

using namespace orgsyscall::yavom;
std::vector<std::string> arrayOne;
std::vector<std::string> arrayTwo;
// Fill the arrays
auto moves = myers(arrayOne,arrayTwo);

The return value moves is a vector of Move objects. The myers function accepts an additional long parameter which defines the maximum time (in nanoseconds) that the algorithm is allowed to spend at each iteration (an iteration is one step d in Myers algorithm): this is useful when dealing with very large containers (by default the value is -1, meaning that no time limit is set). You can apply moves to the array as follows:

for (const auto& m : moves) {
  apply_move(m, arrayOne);
}
// now arrayOne contents are the same as arrayTwo

You can serialize / deserialize Move objects as you deem necessary. To do so please consider the following definitions (found in diff.h):

enum class OP {INSERT, DELETE};
using Point=std::tuple<long,long>;

template<typename K>
using Move=std::tuple<OP,Point,Point,std::vector<K>>;

The std::vector field stores the values to be inserted.

If you are interested in knowning how many moves will be necessary but do not want to generate complete moves (with complete insert data), you can use the myers_unfilled function:

auto moves = myers_unfilled(a,b, 1000);
std::cerr << moves.size() << " moves\n";

Subsequently you can fill the insertion data:

myers_fill(a, b, moves);

Credits & License

This code is Copyright (C) 2021 Amos Brocco ([email protected])

BSD 3-Clause License