9 #include "abg-internal.h"
11 ABG_BEGIN_EXPORT_DECLARATIONS
33 const point& reverse_d_path_end)
35 return ((forward_d_path_end.x() - forward_d_path_end.y())
36 == (reverse_d_path_end.x() - reverse_d_path_end.y())
37 && forward_d_path_end.x() >= reverse_d_path_end.x());
57 && p.x() < (int) a_size
59 && p.y() < (int) b_size);
100 bool has_snake =
false;
101 int str1_size = strlen(str1), str2_size = strlen(str2);
105 str2 , str2 + str2_size,
132 int str1_size = strlen(str1), str2_size = strlen(str2);
135 return ses_len(str1, str1 + str1_size,
136 str2, str2 + str2_size,
159 vector<point> result;
163 str2, str2 + strlen(str2),
166 ses_len = ses.length();
168 for (
unsigned i = 0; i < result.size(); ++i)
170 int x = result[i].x(), y = result[i].y();
172 lcs.push_back(str1[x]);
191 str2, str2 + strlen(str2),
const point & intermediate() const
Getter for the end point of the non-diagonal edge of the snake.
The abstraction of the Snake concept, from the paper.
A class representing a vertex in an edit graph, as explained in the paper. A vertex is a basically a ...
bool point_is_valid_in_graph(point &p, unsigned a_size, unsigned b_size)
bool compute_middle_snake(const char *str1, const char *str2, snake &s, int &ses_len)
Returns the middle snake of two strings, as well as the length of their shortest editing script...
Toplevel namespace for libabigail.
The default equality functor used by the core diffing algorithms.
int ses_len(const char *str1, const char *str2, bool reverse)
Compute the length of the shortest edit script for two strings. This is done using the "Greedy LCS/SE...
void compute_lcs(const char *str1, const char *str2, int &ses_len, string &lcs)
Compute the longest common subsequence of two strings and return the length of the shortest edit scri...
This file declares types and operations implementing the "O(ND) Difference Algorithm" (aka diff2) fro...
void compute_ses(const char *str1, const char *str2, edit_script &ses)
Compute the shortest edit script for transforming a string into another.
#define ABG_ASSERT(cond)
This is a wrapper around the 'assert' glibc call. It allows for its argument to have side effects...
The abstraction of an edit script for transforming a sequence A into a sequence B.
const point & end() const
Getter for the end point of the last diagonal edge, aka snake end point. Note that if the snake has n...
bool snake_end_points(const snake &s, point &x, point &u)
Get the end points of the snake, as intended by the paper.
bool ends_of_furthest_d_paths_overlap(const point &forward_d_path_end, const point &reverse_d_path_end)
void compute_diff(RandomAccessOutputIterator a_base, RandomAccessOutputIterator a_begin, RandomAccessOutputIterator a_end, RandomAccessOutputIterator b_base, RandomAccessOutputIterator b_begin, RandomAccessOutputIterator b_end, vector< point > &lcs, edit_script &ses, int &ses_len)
Compute the longest common subsequence of two (sub-regions of) sequences as well as the shortest edit...
The array containing the furthest D-path end-points, for each value of K. MAX_D is the maximum value ...