NCBI C++ ToolKit
diff.cpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /* $Id: diff.cpp 87529 2019-09-09 18:00:06Z ivanov $
2  * ===========================================================================
3  *
4  * PUBLIC DOMAIN NOTICE
5  * National Center for Biotechnology Information
6  *
7  * This software/database is a "United States Government Work" under the
8  * terms of the United States Copyright Act. It was written as part of
9  * the author's official duties as a United States Government employee and
10  * thus cannot be copyrighted. This software/database is freely available
11  * to the public for use. The National Library of Medicine and the U.S.
12  * Government have not placed any restriction on its use or reproduction.
13  *
14  * Although all reasonable efforts have been taken to ensure the accuracy
15  * and reliability of the software and data, the NLM and the U.S.
16  * Government do not and cannot warrant the performance or results that
17  * may be obtained by using this software or data. The NLM and the U.S.
18  * Government disclaim all warranties, express or implied, including
19  * warranties of performance, merchantability or fitness for any particular
20  * purpose.
21  *
22  * Please cite the author in any work or product based on this material.
23  *
24  * ===========================================================================
25  *
26  * Author: Vladimir Ivanov
27  * File Description:
28  * API to diff two texts and finds the differences.
29  *
30  */
31 
32 #include <ncbi_pch.hpp>
33 #include <corelib/ncbistl.hpp>
34 #include <util/diff/diff.hpp>
35 #include <unordered_map>
36 #include "dtl/dtl/dtl.hpp"
37 
38 
39 #define NCBI_USE_ERRCODE_X Util_Diff
40 
42 
43 
44 // Macro to check bits
45 #define F_ISSET(mask) (((flags) & (mask)) == (mask))
46 
47 // Local defines to simplicity a reading the code
48 #define DIFF_DELETE CDiffOperation::eDelete
49 #define DIFF_EQUAL CDiffOperation::eEqual
50 #define DIFF_INSERT CDiffOperation::eInsert
51 
52 
53 /////////////////////////////////////////////////////////////////////////////
54 //
55 // CDiffOperation
56 //
57 
59  : m_Operation(operation),
60  m_String(str),
61  m_Length(str.length())
62 { }
63 
64 
65 /////////////////////////////////////////////////////////////////////////////
66 //
67 // CDiffList
68 //
69 
71 {
72  const CDiffList::TList& diffs = GetList();
73  if (diffs.empty()) {
74  NCBI_THROW(CDiffException, eEmpty, "The diff list is empty");
75  }
76  size_type edit_distance = 0;
77  size_type len_insert = 0;
78  size_type len_delete = 0;
79 
80  ITERATE(CDiffList::TList, it, diffs) {
81  switch (it->GetOperation()) {
82  case DIFF_INSERT:
83  len_insert += it->GetString().length();
84  break;
85  case DIFF_DELETE:
86  len_delete += it->GetString().length();
87  break;
88  case DIFF_EQUAL:
89  // A deletion and an insertion is one substitution.
90  edit_distance += max(len_insert, len_delete);
91  len_insert = 0;
92  len_delete = 0;
93  break;
94  }
95  }
96  edit_distance += max(len_insert, len_delete);
97  return edit_distance;
98 }
99 
100 
102 {
103  const CDiffList::TList& diffs = GetList();
104  if (diffs.empty()) {
105  NCBI_THROW(CDiffException, eEmpty, "The diff list is empty");
106  }
107  TList::const_iterator max_pos = diffs.end();
108  size_type max_len = 0;
109  ITERATE(CDiffList::TList, it, diffs) {
110  if (it->IsEqual()) {
111  size_type len = it->GetString().length();
112  if (len > max_len) {
113  max_len = len;
114  max_pos = it;
115  }
116  }
117  }
118  if (!max_len || max_pos == diffs.end()) {
119  return CTempString();
120  }
121  return max_pos->GetString();
122 }
123 
124 
126 {
127  // Check on incorrect usage
128  ITERATE(TList, it, m_List) {
129  if (it->GetString().length() != it->GetLength()) {
130  // Possible the line-based diff with fRemoveEOL flag was used,
131  // It is impossible to cleanup and merge equalities in this mode.
132  NCBI_THROW(CDiffException, eBadFlags,
133  "Possible fRemoveEOL flag was used, it is impossible "
134  "to perform cleanup and merge in this mode");
135  }
136  }
137  bool changes;
138  do {
139  // First pass: merge adjacent parts with the same operation
141  // Second pass: look for single edits surrounded on both sides
142  // by equalities which can be shifted sideways to eliminate
143  // an equality. e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
144  changes = x_CleanupAndMerge_SingleEdits();
145  }
146  // If shifts were made, the diff needs reordering and another shift sweep
147  while (changes);
148  return;
149 }
150 
151 
153 {
154  CDiffList::TList& diffs = m_List;
155  if (diffs.empty()) {
156  NCBI_THROW(CDiffException, eEmpty, "The diff list is empty");
157  }
158  size_type off_first = 0;
159  size_type off_second = 0;
160 
161  NON_CONST_ITERATE(CDiffList::TList, it, diffs) {
162  switch (it->GetOperation()) {
163  case DIFF_INSERT:
164  it->SetOffset(CDiffOperation::SPos(NPOS, off_second));
165  off_second += it->GetLength();
166  break;
167  case DIFF_DELETE:
168  it->SetOffset(CDiffOperation::SPos(off_first, NPOS));
169  off_first += it->GetLength();
170  break;
171  case DIFF_EQUAL:
172  it->SetOffset(CDiffOperation::SPos(off_first, off_second));
173  off_first += it->GetLength();
174  off_second += it->GetLength();
175  break;
176  }
177  }
178  return;
179 }
180 
181 
183 {
184  // Counters for inserted/deleted parts
185  size_t count_delete = 0;
186  size_t count_insert = 0;
187  // Assign iterators to current, insertion, deletion and equal diffs
188  CDiffList::TList::iterator this_diff = m_List.begin();
189  CDiffList::TList::iterator ins_diff = m_List.end();
190  CDiffList::TList::iterator del_diff = m_List.end();
191  CDiffList::TList::iterator equal_diff = m_List.end();
192 
193  while (this_diff != m_List.end()) {
194  const CTempString& current = this_diff->GetString();
195  switch (this_diff->GetOperation()) {
196 
197  case DIFF_INSERT:
198  // Merge insertions
199  if (count_insert) {
200  CTempString s = ins_diff->GetString();
201  ins_diff->SetString(CTempString(s.data(), s.length() + current.length()));
202  this_diff = m_List.erase(this_diff);
203  } else {
204  ins_diff = this_diff++;
205  }
206  count_insert++;
207  break;
208 
209  case DIFF_DELETE:
210  // Merge deletions
211  if (count_delete) {
212  CTempString s = del_diff->GetString();
213  del_diff->SetString(CTempString(s.data(), s.length() + current.length()));
214  this_diff = m_List.erase(this_diff);
215  } else {
216  del_diff = this_diff++;
217  }
218  count_delete++;
219  break;
220 
221  case DIFF_EQUAL:
222  // Have INSERT or DELETE previously?
223  if (count_delete + count_insert >= 1) {
224  // Have both INSERT and DELETE?
225  if (count_delete != 0 && count_insert != 0) {
226  // Factor out common prefix
227  CTempString ins_str = ins_diff->GetString();
228  CTempString del_str = del_diff->GetString();
229  size_type common_prefix_len = NStr::CommonPrefixSize(ins_str, del_str);
230  if (common_prefix_len) {
231  // Append common prefix to the previous equal part
232  if (equal_diff == m_List.end()) {
233  // If no EQUAL node before, insert common prefix before any INSERT or DELETE
234  Prepend(DIFF_EQUAL, ins_str.substr(0, common_prefix_len));
235  } else {
236  CTempString s = equal_diff->GetString();
237  equal_diff->SetString(CTempString(s.data(), s.length() + common_prefix_len));
238  }
239  ins_str = ins_str.substr(common_prefix_len);
240  del_str = del_str.substr(common_prefix_len);
241  }
242 
243  // Factor out common suffix
244  size_type common_suffix_len = NStr::CommonSuffixSize(ins_str, del_str);
245  if (common_suffix_len) {
246  // Append suffix to the current node
247  CTempString common_suffix = ins_str.substr(ins_str.length() - common_suffix_len);
248  this_diff->SetString(
249  CTempString(common_suffix.data(),
250  common_suffix.length() + current.length()));
251  // Cut off suffix from INSERT and DELETE strings
252  ins_str = ins_str.substr(0, ins_str.length() - common_suffix_len);
253  del_str = del_str.substr(0, del_str.length() - common_suffix_len);
254  }
255  // Update nodes
256  if (common_prefix_len || common_suffix_len) {
257  ins_diff->SetString(ins_str);
258  del_diff->SetString(del_str);
259  }
260  }
261  // Save pointer to the first equal part to merge
262  equal_diff = this_diff++;
263 
264  } else {
265  // EQUAL, and not an INSERT or DELETE before
266  if (equal_diff == m_List.end()) {
267  // Save pointer to the first equality to merge
268  equal_diff = this_diff++;
269  } else {
270  // Merge current equality with previous
271  CTempString s = equal_diff->GetString();
272  equal_diff->SetString(CTempString(s.data(), s.length() + current.length()));
273  this_diff = m_List.erase(this_diff);
274  }
275  }
276  count_insert = 0;
277  count_delete = 0;
278  break;
279 
280  } // switch
281  } // while
282 
283  return;
284 }
285 
286 
288 {
289  if (m_List.size() < 3) {
290  // Don't meet algorithm criteria
291  return false;
292  }
293  // Assign iterators to previous, current and next diffs
294  CDiffList::TList::iterator next_diff = m_List.begin();
295  CDiffList::TList::iterator prev_diff = next_diff++;
296  CDiffList::TList::iterator this_diff = next_diff++;
297 
298  bool changes = false;
299 
300  while (next_diff != m_List.end()) {
301  // Intentionally ignore the first and last element (don't need checking)
302  if (prev_diff->GetOperation() == DIFF_EQUAL &&
303  next_diff->GetOperation() == DIFF_EQUAL)
304  {
305  _VERIFY(this_diff->GetOperation() != DIFF_EQUAL);
306 
307  CTempString prev_str = prev_diff->GetString();
308  CTempString this_str = this_diff->GetString();
309  CTempString next_str = next_diff->GetString();
310 
311  // NOTE:
312  // CTempString data should be contiguous and be a part of
313  // the same source string.
314  // If the middle (this_diff) is inserted, always use 'this_str'
315  // (new based tmp string) as base for expanding/shifting strings,
316  // if deleted - any (old based).
317 
318  // This is a single edit surrounded by equalities.
319  if (NStr::StartsWith(this_str, next_str)) {
320  // Case: A<CB>C --> AC<BC>
321  // Shift the edit over the next equality.
322  // 1) A -> AC
323  prev_diff->SetString(
324  CTempString(this_str.data() - prev_str.length(),
325  prev_str.length() + next_str.length()));
326  // 2) CB -> BC
327  this_diff->SetString(
328  CTempString(this_str.data() + next_str.length(), this_str.length()));
329  // 3) Delete next_diff and move to next element
330  next_diff = m_List.erase(next_diff);
331  if (next_diff == m_List.end()) {
332  next_diff = this_diff;
333  }
334  changes = true;
335 
336  } else if (NStr::EndsWith(this_str, prev_str)) {
337  // Case: A<BA>C --> <AB>AC
338  // Shift the edit over the previous equality (starting from the back).
339  // 1) C -> AC
340  next_diff->SetString(
341  CTempString(this_str.data() + this_str.length() - prev_str.length(),
342  prev_str.length() + next_str.length()));
343  // 2) BA -> AB
344  this_diff->SetString(
345  CTempString(this_str.data() - prev_str.length(), this_str.length()));
346  // 3) Delete prev_diff
347  m_List.erase(prev_diff);
348  changes = true;
349  }
350  }
351  prev_diff = this_diff;
352  this_diff = next_diff;
353  next_diff++;
354  }
355  return changes;
356 }
357 
358 
359 //////////////////////////////////////////////////////////////////////////////
360 //
361 // CDiff
362 //
363 
365 {
366  Reset();
367 
368  // Set deadline time if timeout is specified
369  unique_ptr<CDeadline> real_deadline;
370  if (!m_Timeout.IsInfinite()) {
371  real_deadline.reset(new CDeadline(m_Timeout));
372  m_Deadline = real_deadline.get();
373  }
374 
375  // Check for equality (speedup)
376  if (s1 == s2) {
377  if (!s1.empty()) {
379  }
380  return m_Diffs;
381  }
382 
383  // Trim off common prefix (speedup)
384  size_type common_prefix_len = NStr::CommonPrefixSize(s1, s2);
385  CTempString common_prefix;
386  if (common_prefix_len) {
387  common_prefix = s1.substr(0, common_prefix_len);
388  s1 = s1.substr(common_prefix_len);
389  s2 = s2.substr(common_prefix_len);
390  }
391 
392  // Trim off common suffix (speedup).
393  size_type common_suffix_len = NStr::CommonSuffixSize(s1, s2);
394  CTempString common_suffix;
395  if (common_suffix_len) {
396  common_suffix = s1.substr(s1.length() - common_suffix_len);
397  s1 = s1.substr(0, s1.length() - common_suffix_len);
398  s2 = s2.substr(0, s2.length() - common_suffix_len);
399  }
400 
401  // Compute the diff on the middle block.
402  x_Diff(s1, s2, m_Diffs);
403  // Restore the prefix and suffix.
404  if (common_prefix_len) {
405  m_Diffs.Prepend(DIFF_EQUAL, common_prefix);
406  }
407  if (common_suffix_len) {
408  m_Diffs.Append(DIFF_EQUAL, common_suffix);
409  }
410 
411  // Post-process diff list
412  if ( !F_ISSET(fNoCleanup) ) {
413  if ( !IsTimeoutExpired() ) {
415  }
416  }
417  if ( F_ISSET(fCalculateOffsets) ) {
418  // Do not check timeout here, it is fast and
419  // can be executed even in this case
421  }
422  // Cleanup
423  m_Deadline = NULL;
424  // Return result
425  return m_Diffs;
426 }
427 
428 
429 /// Do the two texts share a substring which is at least half the length
430 /// of the longer text? This speedup can produce non-minimal diffs.
431 /// @param s1
432 /// First string.
433 /// @param s2
434 /// Second string.
435 /// @param hm
436 /// Five element array, containing the prefix of 's1', the suffix of 's1',
437 /// the prefix of 's2', the suffix of 's2' and the common middle.
438 /// @return
439 /// FALSE if there was no match.
440 /// @sa Diff
441 /// @private
443 {
444  if ( m_Timeout.IsInfinite() ) {
445  // Don't risk returning a non-optimal diff if we have unlimited time.
446  return false;
447  }
448 
449  const CTempString long_str = s1.length() > s2.length() ? s1 : s2;
450  const CTempString short_str = s1.length() > s2.length() ? s2 : s1;
451  if (long_str.length() < 4 || short_str.length() * 2 < long_str.length()) {
452  return false; // Pointless
453  }
454 
455  // Reserve 5 elements
456  TDiffHalfMatchList hm1(5), hm2(5);
457 
458  // First check if the second quarter is the seed for a half-match.
459  bool hm1_res = x_DiffHalfMatchI(long_str, short_str, (long_str.length() + 3) / 4, hm1);
460  // Check again based on the third quarter.
461  bool hm2_res = x_DiffHalfMatchI(long_str, short_str, (long_str.length() + 1) / 2, hm2);
462  if (!hm1_res && !hm2_res) {
463  return false;
464  } else if (!hm1_res) {
465  hm = hm2;
466  } else if (!hm2_res) {
467  hm = hm1;
468  } else {
469  // Both matched. Select the longest.
470  hm = hm1[4].length() > hm2[4].length() ? hm1 : hm2;
471  }
472  // A half-match was found, sort out the return data.
473  if (s1.length() > s2.length()) {
474  // return hm;
475  } else {
477  tmp[0] = hm[2];
478  tmp[1] = hm[3];
479  tmp[2] = hm[0];
480  tmp[3] = hm[1];
481  tmp[4] = hm[4];
482  hm.swap(tmp);
483  }
484  return true;
485 }
486 
487 
488 /// Does a substring of short string exist within long string such that
489 /// the substring is at least half the length of long string?
490 ///
491 /// @param long_str
492 /// Longer string.
493 /// @param short_str
494 /// Shorter string.
495 /// @param i
496 /// Start index of quarter length substring within long string.
497 /// @param hm
498 /// Five element Array, containing the prefix of 'long_str', the suffix
499 /// of 'long_str', the prefix of 'short_str', the suffix of 'short_str'
500 /// and the common middle.
501 /// @return
502 /// FALSE if there was no match.
503 /// @sa Diff, x_DiffHalfMatch
504 /// @private
506  size_type i, TDiffHalfMatchList& hm) const
507 {
508  // Start with a 1/4 length substring at position i as a seed.
509  const CTempString seed = long_str.substr(i, long_str.length() / 4);
510  size_type j = NPOS;
511  CTempString best_common;
512  CTempString best_longtext_a, best_longtext_b;
513  CTempString best_shorttext_a, best_shorttext_b;
514 
515  while ((j = short_str.find(seed, j + 1)) != NPOS) {
516  const size_type prefix_len =
517  NStr::CommonPrefixSize(long_str.substr(i), short_str.substr(j));
518  const size_type suffix_len =
519  NStr::CommonSuffixSize(long_str.substr(0, i), short_str.substr(0, j));
520  if (best_common.length() < suffix_len + prefix_len) {
521  best_common = short_str.substr(j - suffix_len, suffix_len + prefix_len);
522  best_longtext_a = long_str.substr(0, i - suffix_len);
523  best_longtext_b = long_str.substr(i + prefix_len);
524  best_shorttext_a = short_str.substr(0, j - suffix_len);
525  best_shorttext_b = short_str.substr(j + prefix_len);
526  }
527  }
528  if (best_common.length() * 2 >= long_str.length()) {
529  hm[0] = best_longtext_a;
530  hm[1] = best_longtext_b;
531  hm[2] = best_shorttext_a;
532  hm[3] = best_shorttext_b;
533  hm[4] = best_common;
534  return true;
535  }
536  return false;
537 }
538 
539 
540 /// Find the 'middle snake' of a diff, split the problem in two
541 /// and return the recursively constructed diff.
542 /// See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.
543 /// @param s1
544 /// Old string to be diffed.
545 /// @param s2
546 /// New string to be diffed.
547 /// @param diffs
548 /// Resulting list of the diff operations.
549 /// @sa Diff
550 /// @private
552 {
553  // Cache the text lengths to prevent multiple calls.
554  const int s1_len = (int)s1.length();
555  const int s2_len = (int)s2.length();
556  const int max_d = (s1_len + s2_len + 1) / 2;
557  const int v_offset = max_d;
558  const int v_length = 2 * max_d;
559  int *v1 = new int[v_length];
560  int *v2 = new int[v_length];
561  for (int x = 0; x < v_length; x++) {
562  v1[x] = -1;
563  v2[x] = -1;
564  }
565  v1[v_offset + 1] = 0;
566  v2[v_offset + 1] = 0;
567  const int delta = s1_len - s2_len;
568  // If the total number of characters is odd, then the front path will
569  // collide with the reverse path.
570  const bool front = (delta % 2 != 0);
571  // Offsets for start and end of k loop.
572  // Prevents mapping of space beyond the grid.
573  int k1start = 0;
574  int k1end = 0;
575  int k2start = 0;
576  int k2end = 0;
577 
578  for (int d = 0; d < max_d; d++)
579  {
580  if ( IsTimeoutExpired() ) {
581  break;
582  }
583  // Walk the front path one step.
584  for (int k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {
585  const int k1_offset = v_offset + k1;
586  int x1;
587  if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) {
588  x1 = v1[k1_offset + 1];
589  } else {
590  x1 = v1[k1_offset - 1] + 1;
591  }
592  int y1 = x1 - k1;
593  while (x1 < s1_len && y1 < s2_len && s1[x1] == s2[y1]) {
594  x1++;
595  y1++;
596  }
597  v1[k1_offset] = x1;
598  if (x1 > s1_len) {
599  // Ran off the right of the graph.
600  k1end += 2;
601  } else if (y1 > s2_len) {
602  // Ran off the bottom of the graph.
603  k1start += 2;
604  } else if (front) {
605  int k2_offset = v_offset + delta - k1;
606  if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {
607  // Mirror x2 onto top-left coordinate system.
608  int x2 = s1_len - v2[k2_offset];
609  if (x1 >= x2) {
610  // Overlap detected.
611  delete [] v1;
612  delete [] v2;
613  x_DiffBisectSplit(s1, s2, x1, y1, diffs);
614  return;
615  }
616  }
617  }
618  }
619 
620  // Walk the reverse path one step.
621  for (int k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {
622  const int k2_offset = v_offset + k2;
623  int x2;
624  if (k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])) {
625  x2 = v2[k2_offset + 1];
626  } else {
627  x2 = v2[k2_offset - 1] + 1;
628  }
629  int y2 = x2 - k2;
630  while (x2 < s1_len && y2 < s2_len &&
631  s1[s1_len - x2 - 1] == s2[s2_len - y2 - 1]) {
632  x2++;
633  y2++;
634  }
635  v2[k2_offset] = x2;
636  if (x2 > s1_len) {
637  // Ran off the left of the graph.
638  k2end += 2;
639  } else if (y2 > s2_len) {
640  // Ran off the top of the graph.
641  k2start += 2;
642  } else if (!front) {
643  int k1_offset = v_offset + delta - k2;
644  if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {
645  int x1 = v1[k1_offset];
646  int y1 = v_offset + x1 - k1_offset;
647  // Mirror x2 onto top-left coordinate system.
648  x2 = s1_len - x2;
649  if (x1 >= x2) {
650  // Overlap detected.
651  delete [] v1;
652  delete [] v2;
653  x_DiffBisectSplit(s1, s2, x1, y1, diffs);
654  return;
655  }
656  }
657  }
658  }
659  }
660  delete [] v1;
661  delete [] v2;
662  // Diff took too long and hit the deadline or
663  // number of diffs equals number of characters, no commonality at all.
664  diffs.Append(DIFF_DELETE, s1);
665  diffs.Append(DIFF_INSERT, s2);
666 }
667 
668 
669 /// Given the location of the 'middle snake', split the diff in two parts
670 /// and recurse.
671 /// @param s1
672 /// Old string to be diffed.
673 /// @param s2
674 /// New string to be diffed.
675 /// @param x
676 /// Index of split point in 's1'.
677 /// @param y
678 /// Index of split point in 's2'.
679 /// @param diffs
680 /// Resulting list of the diff operations.
681 /// @sa Diff, x_DiffBisect
682 /// @private
683 void CDiff::x_DiffBisectSplit(CTempString s1, CTempString s2, int x, int y, CDiffList& diffs) const
684 {
685  CTempString s1a = s1.substr(0, x);
686  CTempString s2a = s2.substr(0, y);
687  CTempString s1b = s1.substr(x);
688  CTempString s2b = s2.substr(y);
689  // Compute both diffs serially.
690  x_Diff(s1a, s2a, diffs);
691  x_Diff(s1b, s2b, diffs);
692 }
693 
694 
695 /// Find the differences between two texts.
696 /// Assumes that the texts do not have any common prefix or suffix.
697 /// @param s1
698 /// Old string to be diffed.
699 /// @param s2
700 /// New string to be diffed.
701 /// @param diffs
702 /// Resulting list of the diff operations.
703 /// @sa Diff
704 /// @private
705 void CDiff::x_Diff(CTempString s1, CTempString s2, CDiffList& diffs) const
706 {
707  if (s1.empty()) {
708  // Just add some text (speedup)
709  diffs.Append(DIFF_INSERT, s2);
710  return;
711  }
712  if (s2.empty()) {
713  // Just delete some text (speedup)
714  diffs.Append(DIFF_DELETE, s1);
715  return;
716  }
717  {
718  // Shorter text is inside the longer text (speedup).
719  const CTempString long_str = s1.length() > s2.length() ? s1 : s2;
720  const CTempString short_str = s1.length() > s2.length() ? s2 : s1;
721  const size_type i = long_str.find(short_str);
722  if ( i != NPOS) {
723  const CDiffOperation::EType op = (s1.length() > s2.length()) ? DIFF_DELETE : DIFF_INSERT;
724  diffs.Append(op, long_str.substr(0, i));
725  diffs.Append(DIFF_EQUAL, short_str);
726  diffs.Append(op, long_str.substr(i + short_str.length()));
727  return;
728  }
729  if (short_str.length() == 1) {
730  // Single character string.
731  // After the previous speedup, the character can't be an equality.
732  diffs.Append(DIFF_DELETE, s1);
733  diffs.Append(DIFF_INSERT, s2);
734  return;
735  }
736  }
737 
738  // Check to see if the problem can be split in two
739  TDiffHalfMatchList hm(5);
740  if ( x_DiffHalfMatch(s1, s2, hm) ) {
741  // A half-match was found. Send both pairs off for separate processing
742  CDiffList diffs_a, diffs_b;
743  x_Diff(hm[0], hm[2], diffs_a);
744  x_Diff(hm[1], hm[3], diffs_b);
745  // Merge the results
746  diffs.m_List = diffs_a.m_List;
747  diffs.Append(DIFF_EQUAL, hm[4]);
748  // difs += diffs_b
749  diffs.m_List.insert(diffs.m_List.end(), diffs_b.m_List.begin(), diffs_b.m_List.end());
750  return;
751  }
752 
753  // Perform a real diff
754  x_DiffBisect(s1, s2, diffs);
755  return;
756 }
757 
758 
759 // Hash map to convert strings to line numbers.
760 // We use std::string here instead of CTempString because
761 // to have full compatibility with 'patch' utility we need
762 // a "correct" diff. to get that we should add "\n" to all
763 // hashed strings in the text except last one.
764 typedef unordered_map<string, CDiffList::size_type > TStringToLineNumMap;
765 
767 {
768  // Check incompatible flags
769  if ( F_ISSET(fCleanup + fRemoveEOL) ) {
770  NCBI_THROW(CDiffException, eBadFlags, "Usage of incompatible flags fCleanup and fRemoveEOL");
771  }
772  Reset();
773 
774  // Set deadline time if timeout is specified
775  unique_ptr<CDeadline> real_deadline;
776  if (!m_Timeout.IsInfinite()) {
777  real_deadline.reset(new CDeadline(m_Timeout));
778  m_Deadline = real_deadline.get();
779  }
780 
781  // Split both strings to lines
782  // (use '\n' as delimiter, for CRLF cases '\r' will be part of CTempString)
783  vector<CTempString> lines;
784  size_type s1_num_lines, s2_num_lines;
785  NStr::Split(s1, "\n", lines);
786  s1_num_lines = lines.size();
787  NStr::Split(s2, "\n", lines);
788  s2_num_lines = lines.size() - s1_num_lines;
789 
790  // Create a map of unique strings with its positions in lines[].
791  TStringToLineNumMap hm(lines.size());
792  for (size_type i = 0; i < lines.size(); i++) {
793  string s = lines[i];
794  size_type len = s.length();
795  if (F_ISSET(fIgnoreEOL) && len && s[len-1] == '\r') {
796  // Remove trailing 'r' if present
797  s.resize(len-1);
798  }
799  // Add trailing "\n" back to all lines except last one.
800  if (i != s1_num_lines-1 && i != lines.size()-1) {
801  s += "\n";
802  }
803  hm.insert(TStringToLineNumMap::value_type(s, i));
804  }
805 
806  // "Convert" both our texts to an array of integer indexes of
807  // each line in lines[]. Each number/index represent unique string.
808  typedef vector<size_type> TSequence;
809  TSequence idx1(s1_num_lines);
810  TSequence idx2(s2_num_lines);
811 
812  for (size_type i = 0; i < s1_num_lines; i++) {
813  TStringToLineNumMap::const_iterator it;
814  string s = lines[i];
815  size_type len = s.length();
816  if (F_ISSET(fIgnoreEOL) && len && s[len-1] == '\r') {
817  // Remove trailing 'r' if present
818  s.resize(len-1);
819  }
820  // Add trailing "\n" back to all lines except last one.
821  if (i < s1_num_lines-1) {
822  s += "\n";
823  }
824  it = hm.find(s);
825  _VERIFY(it != hm.end());
826  idx1[i] = it->second;
827  }
828  for (size_type i = 0; i < s2_num_lines; i++) {
829  size_type pos = s1_num_lines + i;
830  TStringToLineNumMap::const_iterator it;
831  string s = lines[pos];
832  size_type len = s.length();
833  if (F_ISSET(fIgnoreEOL) && len && s[len-1] == '\r') {
834  // Remove trailing 'r' if present
835  s.resize(len-1);
836  }
837  // Add trailing "\n" back to all lines except last one.
838  if (i < s2_num_lines-1) {
839  s += "\n";
840  }
841  it = hm.find(s);
842  _VERIFY(it != hm.end());
843  idx2[i] = it->second;
844  }
845 
846  // Run a diff for integer vectors
847  dtl::Diff<size_type> d(idx1, idx2);
848  if (s1_num_lines > 10000 && s2_num_lines > 10000) {
849  d.onHuge();
850  }
851  d.compose();
852  vector< pair<size_type, dtl::elemInfo> > ses_seq = d.getSes().getSequence();
853  vector< pair<size_type, dtl::elemInfo> >::iterator it;
854 
855  // Convert obtained line-num-based diff to string-based.
856  // We cannot use strings from an unordered_map directly,
857  // as well as indexes to get line from lines[], because "equal"
858  // lines can have a difference in EOLs, and accordingly
859  // -- different lengths, that can be fatal for CTempString.
860  // Instead, we will use our own counters for line positions for
861  // both texts, assuming that DELETE and COMMON parts refers
862  // to the first text, and ADD -- to the second.
863  // Resulting diff should have all lines from both texts anyway.
864 
865  // Positions in the lines[] for 's1' and 's2'
866  size_type pos1 = 0;
867  size_type pos2 = s1_num_lines;
868 
869  // Lists of insertions and deletions
870  CDiffList::TList insertions, deletions;
871 
872  for (it = ses_seq.begin(); it != ses_seq.end(); it++)
873  {
874  // Type of current difference
875  dtl::edit_t d_type = it->second.type;
877  // Position of the current string in lines[]
878  size_type pos = 0;
880  bool is_last_line = false;
881 
882  switch (d_type) {
883  case dtl::SES_ADD :
884  _VERIFY(pos2 < lines.size());
885  op_type = DIFF_INSERT;
886  pos = pos2;
887  line2 = pos2 - s1_num_lines + 1;
888  is_last_line = (line2 >= s2_num_lines);
889  break;
890  case dtl::SES_DELETE :
891  _VERIFY(pos1 < s1_num_lines);
892  op_type = DIFF_DELETE;
893  pos = pos1;
894  line1 = pos1 + 1;
895  is_last_line = (line1 >= s1_num_lines);
896  break;
897  case dtl::SES_COMMON :
898  _VERIFY(pos1 < s1_num_lines);
899  _VERIFY(pos2 < lines.size());
900  op_type = DIFF_EQUAL;
901  pos = pos1;
902  line1 = pos1 + 1;
903  line2 = pos2 - s1_num_lines + 1;
904  is_last_line = (line2 >= s2_num_lines);
905  break;
906  default :
907  _TROUBLE;
908  }
909 
910  // Get string
911  CTempString& s = lines[pos];
912  size_type len = s.length();
913  size_type real_len = len;
914  if (!is_last_line) {
915  real_len++;
916  }
917  if ( F_ISSET(fRemoveEOL) ) {
918  if (s[len-1] == '\r') {
919  len--;
920  }
921  } else {
922  // Restore truncated '\n' on NStr::Tokenize()
923  len = real_len;
924  }
925  CTempString str(s.data(), len);
926 
927  // Add a difference into the list. Use Append(CDiffOperation),
928  // 'str' can be an empty line and Append("") will be ignored.
929  // The dtl::Diff() produce a diff where insertions go before
930  // deletions -- we will fix this, swapping it in the result.
931 
932  CDiffOperation op(op_type, str);
933  op.SetLength(real_len);
935 
936  switch (d_type) {
937  case dtl::SES_ADD :
938  insertions.push_back(op);
939  pos2++;
940  break;
941  case dtl::SES_DELETE :
942  deletions.push_back(op);
943  pos1++;
944  break;
945  case dtl::SES_COMMON :
946  if (!deletions.empty()) {
947  m_Diffs.m_List.insert(m_Diffs.m_List.end(), deletions.begin(), deletions.end());
948  deletions.clear();
949  }
950  if (!insertions.empty()) {
951  m_Diffs.m_List.insert(m_Diffs.m_List.end(), insertions.begin(), insertions.end());
952  insertions.clear();
953  }
954  m_Diffs.Append(op);
955  pos1++;
956  pos2++;
957  break;
958  }
959  }
960  if (!deletions.empty()) {
961  m_Diffs.m_List.insert(m_Diffs.m_List.end(), deletions.begin(), deletions.end());
962  }
963  if (!insertions.empty()) {
964  m_Diffs.m_List.insert(m_Diffs.m_List.end(), insertions.begin(), insertions.end());
965  }
966  _VERIFY(pos1 == s1_num_lines);
967  _VERIFY(pos2 == lines.size());
968 
969  // Post-process diff list
970  if ( F_ISSET(fCleanup) ) {
971  if ( !IsTimeoutExpired() ) {
973  }
974  }
975  if ( F_ISSET(fCalculateOffsets) ) {
976  // Do not check timeout here, it is fast and
977  // can be executed even in this case
979  }
980  // Cleanup
981  m_Deadline = NULL;
982  // Return result
983  return m_Diffs;
984 }
985 
986 
987 // Print the hunk, ranged with iterators, in unified format to 'out'.
988 //
990  CDiffList::TList::const_iterator start_iter,
991  CDiffList::TList::const_iterator end_iter,
992  CDiffList::size_type hunk_s1,
993  CDiffList::size_type hunk_s2)
994 {
995  const char eol = '\n';
996  unsigned long n1 = 0; // Number of lines in first text
997  unsigned long n2 = 0; // Number of lines in second text
998  _VERIFY(hunk_s1);
999  _VERIFY(hunk_s2);
1000 
1001  // Find numbers for header
1002  CDiffList::TList::const_iterator it = start_iter;
1003  while (it != end_iter)
1004  {
1005  string op;
1006  switch (it->GetOperation()) {
1007  case DIFF_INSERT:
1008  n2++;
1009  break;
1010  case DIFF_DELETE:
1011  n1++;
1012  break;
1013  case DIFF_EQUAL:
1014  n1++;
1015  n2++;
1016  break;
1017  }
1018  it++;
1019  }
1020 
1021  // @@ -s1,n1 +s2,n2 @@
1022  out << "@@ -" << (unsigned long)hunk_s1 << "," << n1 << " +"
1023  << (unsigned long)hunk_s2 << "," << n2 << " @@" << eol;
1024 
1025  // Print lines
1026  it = start_iter;
1027  while (it != end_iter)
1028  {
1029  string op;
1030  switch (it->GetOperation()) {
1031  case DIFF_INSERT:
1032  op = "+";
1033  break;
1034  case DIFF_DELETE:
1035  op = "-";
1036  break;
1037  case DIFF_EQUAL:
1038  op = " ";
1039  break;
1040  }
1041  out << op << it->GetString() << eol;
1042  it++;
1043  }
1044  return out;
1045 }
1046 
1047 
1049  CTempString text1, CTempString text2,
1050  unsigned int num_common_lines)
1051 {
1052  if (!out.good()) {
1053  return out;
1054  }
1055  const CDiffList::TList& diffs = Diff(text1, text2, fRemoveEOL).GetList();
1056  if (diffs.empty()) {
1057  return out;
1058  }
1059 
1060  // Assign iterators to current, insertion, deletion and equal diffs
1061  CDiffList::TList::const_iterator it = diffs.begin();
1062  CDiffList::TList::const_iterator hunk_start = diffs.end();
1063  CDiffList::TList::const_iterator hunk_end = diffs.end();
1064 
1065  bool is_hunk = false; // TRUE if we found a hunk
1066  unsigned int num_equal = 0; // Current number of common lines
1067 
1068  // Line numbers (current and hunk's start).
1069  // We cannot get it from CDiffOperation in common case, so we should
1070  // calculate it, counting all operations.
1071  size_type s1 = 0;
1072  size_type s2 = 0;
1073  size_type hunk_s1 = 0;
1074  size_type hunk_s2 = 0;
1075 
1076  // Find hunks
1077  while (it != diffs.end()) {
1078  switch (it->GetOperation()) {
1079  case DIFF_INSERT:
1080  case DIFF_DELETE:
1081  if (it->GetOperation() == DIFF_DELETE) {
1082  s1++;
1083  } else {
1084  s2++;
1085  }
1086  if (!is_hunk) {
1087  // Difference found, start new hunk
1088  is_hunk = true;
1089  if (!num_common_lines || !num_equal) {
1090  // Show only differences or don't have equal lines before at all:
1091  hunk_start = it;
1092  hunk_s1 = s1;
1093  hunk_s2 = s2;
1094  if (it->GetOperation() == DIFF_DELETE) {
1095  // Don't have INSERT or EQUAL blocks, the line number
1096  // for second text need to be updated
1097  hunk_s2++;
1098  } else {
1099  // Don't have DELETE or EQUAL blocks, the line number
1100  // for second text need to be updated
1101  hunk_s1++;
1102  }
1103  }
1104  }
1105  num_equal = 0;
1106  break;
1107  case DIFF_EQUAL:
1108  s1++;
1109  s2++;
1110  if (is_hunk) {
1111  // Try to find end of the current hunk
1112  if (num_common_lines == 0) {
1113  hunk_end = it;
1114  if (!s_PrintUnifiedHunk(out, hunk_start, hunk_end, hunk_s1, hunk_s2)) {
1115  return out;
1116  }
1117  is_hunk = false;
1118  } else if (!num_equal) {
1119  hunk_end = it;
1120  num_equal++;
1121  } else if (num_equal <= num_common_lines) {
1122  hunk_end = it;
1123  num_equal++;
1124  } else {
1125  // Found new hunk -- write it
1126  if (!s_PrintUnifiedHunk(out, hunk_start, hunk_end, hunk_s1, hunk_s2)) {
1127  return out;
1128  }
1129  is_hunk = false;
1130  num_equal = 0;
1131  }
1132  } else {
1133  // Update iterator to the first common line that can be a part of next hunk
1134  if (!num_equal) {
1135  hunk_start = it;
1136  hunk_s1 = s1;
1137  hunk_s2 = s2;
1138  num_equal++;
1139  } else if (num_equal < num_common_lines) {
1140  num_equal++;
1141  } else {
1142  hunk_start++;
1143  hunk_s1++;
1144  hunk_s2++;
1145  }
1146  }
1147  break;
1148  } // switch
1149  it++;
1150  } // while
1151 
1152  if (is_hunk) {
1153  s_PrintUnifiedHunk(out, hunk_start, diffs.end(), hunk_s1, hunk_s2);
1154  }
1155  return out;
1156 }
1157 
1158 
1159 //////////////////////////////////////////////////////////////////////////////
1160 //
1161 // CDiffException
1162 //
1163 
1164 const char* CDiffException::GetErrCodeString(void) const
1165 {
1166  switch ( GetErrCode() ) {
1167  case eEmpty: return "eEmpty";
1168  case eBadFlags: return "eBadFlags";
1169  default: return CException::GetErrCodeString();
1170  }
1171 }
1172 
1173 
@ eEmpty
no filtering at all.
CDeadline.
Definition: ncbitime.hpp:1830
CDiffException –.
Definition: diff.hpp:473
CDiffList – the list of diff operations.
Definition: diff.hpp:185
CDiffOperation – The storage class for one diff operation.
Definition: diff.hpp:66
CTempString implements a light-weight string on top of a storage buffer whose lifetime management is ...
Definition: tempstr.hpp:65
diff class template sequence must support random_access_iterator.
Definition: Diff.hpp:49
void compose()
compose Longest Common Subsequence and Shortest Edit Script.
Definition: Diff.hpp:258
Ses< elem > getSes() const
Definition: Diff.hpp:111
void onHuge()
Definition: Diff.hpp:124
static uch flags
#define DIFF_DELETE
Definition: diff.cpp:48
#define DIFF_EQUAL
Definition: diff.cpp:49
#define DIFF_INSERT
Definition: diff.cpp:50
#define F_ISSET(mask)
Definition: diff.cpp:45
unordered_map< string, CDiffList::size_type > TStringToLineNumMap
Definition: diff.cpp:764
CNcbiOstream & s_PrintUnifiedHunk(CNcbiOstream &out, CDiffList::TList::const_iterator start_iter, CDiffList::TList::const_iterator end_iter, CDiffList::size_type hunk_s1, CDiffList::size_type hunk_s2)
Definition: diff.cpp:989
API to diff strings/texts and to find the differences.
std::ofstream out("events_result.xml")
main entry point for tests
static char line1[1024 *16]
Definition: t0016.c:98
static char line2[1024 *16]
Definition: t0016.c:99
static const char * str(char *buf, int n)
Definition: stats.c:84
static char tmp[3200]
Definition: utf8.c:42
#define ITERATE(Type, Var, Cont)
ITERATE macro to sequence through container elements.
Definition: ncbimisc.hpp:815
#define NON_CONST_ITERATE(Type, Var, Cont)
Non constant version of ITERATE macro.
Definition: ncbimisc.hpp:822
#define NULL
Definition: ncbistd.hpp:225
#define _VERIFY(expr)
Definition: ncbidbg.hpp:161
void CalculateOffsets(void)
Calculate offsets for all substrings in the difference list and find its position from the start of t...
Definition: diff.cpp:152
CDeadline * m_Deadline
Deadline for processing (NULL if not set)
Definition: diff.hpp:319
void x_DiffBisect(CTempString s1, CTempString s2, CDiffList &diffs) const
Find the 'middle snake' of a diff, split the problem in two and return the recursively constructed di...
Definition: diff.cpp:551
void Prepend(CDiffOperation::EType operation, CTempString str)
Add element to the front of the list.
Definition: diff.hpp:564
bool x_DiffHalfMatch(CTempString s1, CTempString s2, TDiffHalfMatchList &hm) const
Do the two texts share a substring which is at least half the length of the longer text?...
Definition: diff.cpp:442
unsigned int TFlags
Bitwise OR of "Flags".
Definition: diff.hpp:407
void CleanupAndMerge(void)
Reorder and merge like edit sections, merge equalities.
Definition: diff.cpp:125
CDiffList & Diff(CTempString text1, CTempString text2, TFlags flags=0)
Find the differences between two texts (line mode).
Definition: diff.cpp:766
virtual const char * GetErrCodeString(void) const override
Get error code interpreted as text.
Definition: diff.cpp:1164
unsigned int TFlags
Bitwise OR of "EFlags".
Definition: diff.hpp:346
bool x_CleanupAndMerge_SingleEdits(void)
Look for single edits surrounded on both sides by equalities which can be shifted sideways to elimina...
Definition: diff.cpp:287
CTempString GetLongestCommonSubstring(void) const
Find the longest common substring for current difference list.
Definition: diff.cpp:101
void x_CleanupAndMerge_Equities(void)
Merge adjacent parts with the same operation.
Definition: diff.cpp:182
void Reset(void)
Reset internal state and prepare to next Diff()
Definition: diff.hpp:603
bool x_DiffHalfMatchI(CTempString long_str, CTempString short_str, size_type i, TDiffHalfMatchList &hm) const
Does a substring of short string exist within long string such that the substring is at least half th...
Definition: diff.cpp:505
void x_DiffBisectSplit(CTempString s1, CTempString s2, int x, int y, CDiffList &diffs) const
Given the location of the 'middle snake', split the diff in two parts and recurse.
Definition: diff.cpp:683
void SetLine(SPos line)
Definition: diff.hpp:547
void Append(CDiffOperation::EType operation, CTempString str)
Add element to the end of the list.
Definition: diff.hpp:578
vector< CTempString > TDiffHalfMatchList
Five element array for the list of strings, returned by x_DiffHalfMatch()
Definition: diff.hpp:363
bool IsTimeoutExpired() const
Check if timeout is expired.
Definition: diff.hpp:610
CDiffList m_Diffs
The list of differences from the last diff.
Definition: diff.hpp:317
list< CDiffOperation > TList
Storage class type for the list of diff operations.
Definition: diff.hpp:190
CDiffList & Diff(CTempString s1, CTempString s2, TFlags flags=0)
Find the differences between two texts (character mode).
Definition: diff.cpp:364
void x_Diff(CTempString s1, CTempString s2, CDiffList &diffs) const
Find the differences between two texts.
Definition: diff.cpp:705
CDiffOperation::size_type size_type
Size type definition.
Definition: diff.hpp:188
size_type GetEditDistance(void) const
Compute the edit distance (Levenshtein distance).
Definition: diff.cpp:70
TList m_List
List of the differences.
Definition: diff.hpp:276
CDiffOperation::size_type size_type
Type definition.
Definition: diff.hpp:292
EType
Type of the current diff operation.
Definition: diff.hpp:72
CDiffOperation(EType operation, CTempString str)
Constructor.
Definition: diff.cpp:58
CTimeout m_Timeout
Relative timeout for processing.
Definition: diff.hpp:318
const TList & GetList(void) const
Get list of the diff operations as list<>.
Definition: diff.hpp:558
void SetLength(size_type length)
Definition: diff.hpp:528
CNcbiOstream & PrintUnifiedDiff(CNcbiOstream &out, CTempString text1, CTempString text2, unsigned int num_common_lines=3)
Find the differences between two texts and print result into output stream in unified-like format.
Definition: diff.cpp:1048
@ fCalculateOffsets
Automatically call CalculateOffests() for the generated list of differences.
Definition: diff.hpp:344
@ fNoCleanup
By default Diff() automatically call CleanupAndMerge() for the generated list of differences to have ...
Definition: diff.hpp:341
@ fCleanup
Automatically call CleanupAndMerge() for the generated list of differences after Diff() to have a sho...
Definition: diff.hpp:392
@ fCalculateOffsets
Automatically call CalculateOffests() for the generated list of differences.
Definition: diff.hpp:395
@ fIgnoreEOL
Ignore differences in end-of-line types on string comparison.
Definition: diff.hpp:397
@ fRemoveEOL
Remove end-of-line symbols from each string added to the list, which can be obtained using CDiffOpera...
Definition: diff.hpp:405
TErrCode GetErrCode(void) const
Get error code.
Definition: ncbiexpt.cpp:453
#define NCBI_THROW(exception_class, err_code, message)
Generic macro to throw an exception, given the exception class, error code and message string.
Definition: ncbiexpt.hpp:704
virtual const char * GetErrCodeString(void) const
Get error code interpreted as text.
Definition: ncbiexpt.cpp:444
const CVect2< U > & v2
Definition: globals.hpp:440
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
IO_PREFIX::ostream CNcbiOstream
Portable alias for ostream.
Definition: ncbistre.hpp:149
static list< string > & Split(const CTempString str, const CTempString delim, list< string > &arr, TSplitFlags flags=0, vector< SIZE_TYPE > *token_pos=NULL)
Split a string using specified delimiters.
Definition: ncbistr.cpp:3461
static bool EndsWith(const CTempString str, const CTempString end, ECase use_case=eCase)
Check if a string ends with a specified suffix value.
Definition: ncbistr.hpp:5430
#define NPOS
Definition: ncbistr.hpp:133
static SIZE_TYPE CommonSuffixSize(const CTempString s1, const CTempString s2)
Determine the common suffix of two strings.
Definition: ncbistr.hpp:5462
const char * data(void) const
Return a pointer to the array represented.
Definition: tempstr.hpp:313
bool empty(void) const
Return true if the represented string is empty (i.e., the length is zero)
Definition: tempstr.hpp:334
static bool StartsWith(const CTempString str, const CTempString start, ECase use_case=eCase)
Check if a string starts with a specified prefix value.
Definition: ncbistr.hpp:5412
size_type length(void) const
Return the length of the represented array.
Definition: tempstr.hpp:320
CTempString substr(size_type pos) const
Obtain a substring from this string, beginning at a given offset.
Definition: tempstr.hpp:776
size_type find(const CTempString match, size_type pos=0) const
Find the first instance of the entire matching string within the current string, beginning at an opti...
Definition: tempstr.hpp:655
static SIZE_TYPE CommonPrefixSize(const CTempString s1, const CTempString s2)
Determine the common prefix of two strings.
Definition: ncbistr.hpp:5450
bool IsInfinite() const
Definition: ncbitime.hpp:2729
operation
Bit operations.
Definition: bmconst.h:191
virtual void Reset(void)
Reset the whole object.
Definition: Diff_.cpp:147
unsigned int
A callback function used to compare two keys in a database.
Definition: types.hpp:1210
int i
int len
constexpr auto front(list< Head, As... >, T=T()) noexcept -> Head
int edit_t
type of edit for SES
Definition: variables.hpp:71
const edit_t SES_ADD
Definition: variables.hpp:74
const edit_t SES_COMMON
Definition: variables.hpp:73
const edit_t SES_DELETE
Definition: variables.hpp:72
double value_type
The numeric datatype used by the parser.
Definition: muParserDef.h:228
The NCBI C++/STL use hints.
T max(T x_, T y_)
Int4 delta(size_t dimension_, const Int4 *score_)
Structure to save offset/length in the compared strings.
Definition: diff.hpp:79
#define _TROUBLE
static int seed
Definition: test_table.cpp:132
Modified on Wed Jun 19 17:04:28 2024 by modify_doxy.py rev. 669887