Mercurial > hg > octave-kai > gnulib-hg

annotate lib/diffseq.h @ 10436:74c36e9e4884

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add an "early abort" facility to diffseq.
author Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
date Sun, 14 Sep 2008 18:34:59 +0200
parents 2858c91c7452
children de232f8c8d7f
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
1 /* Analyze differences between two vectors.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
2
9669
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
3 Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2008 Free
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
4 Software Foundation, Inc.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
5
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 9149
diff changeset
6 This program is free software: you can redistribute it and/or modify
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
7 it under the terms of the GNU General Public License as published by
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 9149
diff changeset
8 the Free Software Foundation; either version 3 of the License, or
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 9149
diff changeset
9 (at your option) any later version.
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
10
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
11 This program is distributed in the hope that it will be useful,
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
14 GNU General Public License for more details.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
15
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
16 You should have received a copy of the GNU General Public License
9309
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+.
Bruno Haible <bruno@clisp.org>
parents: 9149
diff changeset
17 along with this program. If not, see <http://www.gnu.org/licenses/>. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
18
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
19
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
20 /* The basic idea is to consider two vectors as similar if, when
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
21 transforming the first vector into the second vector through a
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
22 sequence of edits (inserts and deletes of one element each),
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
23 this sequence is short - or equivalently, if the ordered list
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
24 of elements that are untouched by these edits is long. For a
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
25 good introduction to the subject, read about the "Levenshtein
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
26 distance" in Wikipedia.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
27
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
28 The basic algorithm is described in:
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
29 "An O(ND) Difference Algorithm and its Variations", Eugene Myers,
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
30 Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
31 see especially section 4.2, which describes the variation used below.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
32
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
33 The basic algorithm was independently discovered as described in:
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
34 "Algorithms for Approximate String Matching", E. Ukkonen,
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
35 Information and Control Vol. 64, 1985, pp. 100-118.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
36
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
37 Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
38 heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
39 at the price of producing suboptimal output for large inputs with
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
40 many differences. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
41
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
42 /* Before including this file, you need to define:
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
43 ELEMENT The element type of the vectors being compared.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
44 EQUAL A two-argument macro that tests two elements for
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
45 equality.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
46 OFFSET A signed integer type sufficient to hold the
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
47 difference between two indices. Usually
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
48 something like ssize_t.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
49 EXTRA_CONTEXT_FIELDS Declarations of fields for 'struct context'.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
50 NOTE_DELETE(ctxt, xoff) Record the removal of the object xvec[xoff].
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
51 NOTE_INSERT(ctxt, yoff) Record the insertion of the object yvec[yoff].
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
52 EARLY_ABORT(ctxt) (Optional) A boolean expression that triggers an
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
53 early abort of the computation.
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
54 USE_HEURISTIC (Optional) Define if you want to support the
9669
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
55 heuristic for large vectors.
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
56 Before including this file, you also need to include:
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
57 #include <limits.h>
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
58 #include <stdbool.h>
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
59 #include "minmax.h"
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
60 */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
61
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
62 /* Maximum value of type OFFSET. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
63 #define OFFSET_MAX \
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
64 ((((OFFSET)1 << (sizeof (OFFSET) * CHAR_BIT - 2)) - 1) * 2 + 1)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
65
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
66 /* Default to no early abort. */
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
67 #ifndef EARLY_ABORT
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
68 # define EARLY_ABORT(ctxt) false
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
69 #endif
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
70
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
71 /* Use this to suppress gcc's `...may be used before initialized' warnings. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
72 #ifndef IF_LINT
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
73 # ifdef lint
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
74 # define IF_LINT(Code) Code
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
75 # else
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
76 # define IF_LINT(Code) /* empty */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
77 # endif
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
78 #endif
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
79
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
80 /*
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
81 * Context of comparison operation.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
82 */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
83 struct context
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
84 {
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
85 /* Vectors being compared. */
9685
2858c91c7452 Avoid gcc warnings due to misplaced 'const'.
Bruno Haible <bruno@clisp.org>
parents: 9669
diff changeset
86 ELEMENT const *xvec;
2858c91c7452 Avoid gcc warnings due to misplaced 'const'.
Bruno Haible <bruno@clisp.org>
parents: 9669
diff changeset
87 ELEMENT const *yvec;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
88
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
89 /* Extra fields. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
90 EXTRA_CONTEXT_FIELDS
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
91
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
92 /* Vector, indexed by diagonal, containing 1 + the X coordinate of the point
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
93 furthest along the given diagonal in the forward search of the edit
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
94 matrix. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
95 OFFSET *fdiag;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
96
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
97 /* Vector, indexed by diagonal, containing the X coordinate of the point
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
98 furthest along the given diagonal in the backward search of the edit
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
99 matrix. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
100 OFFSET *bdiag;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
101
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
102 #ifdef USE_HEURISTIC
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
103 /* This corresponds to the diff -H flag. With this heuristic, for
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
104 vectors with a constant small density of changes, the algorithm is
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
105 linear in the vectors size. */
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
106 bool heuristic;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
107 #endif
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
108
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
109 /* Edit scripts longer than this are too expensive to compute. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
110 OFFSET too_expensive;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
111
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
112 /* Snakes bigger than this are considered `big'. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
113 #define SNAKE_LIMIT 20
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
114 };
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
115
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
116 struct partition
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
117 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
118 /* Midpoints of this partition. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
119 OFFSET xmid;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
120 OFFSET ymid;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
121
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
122 /* True if low half will be analyzed minimally. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
123 bool lo_minimal;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
124
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
125 /* Likewise for high half. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
126 bool hi_minimal;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
127 };
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
128
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
129
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
130 /* Find the midpoint of the shortest edit script for a specified portion
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
131 of the two vectors.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
132
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
133 Scan from the beginnings of the vectors, and simultaneously from the ends,
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
134 doing a breadth-first search through the space of edit-sequence.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
135 When the two searches meet, we have found the midpoint of the shortest
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
136 edit sequence.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
137
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
138 If FIND_MINIMAL is true, find the minimal edit script regardless of
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
139 expense. Otherwise, if the search is too expensive, use heuristics to
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
140 stop the search and report a suboptimal answer.
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
141
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
142 Set PART->(xmid,ymid) to the midpoint (XMID,YMID). The diagonal number
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
143 XMID - YMID equals the number of inserted elements minus the number
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
144 of deleted elements (counting only elements before the midpoint).
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
145
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
146 Set PART->lo_minimal to true iff the minimal edit script for the
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
147 left half of the partition is known; similarly for PART->hi_minimal.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
148
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
149 This function assumes that the first elements of the specified portions
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
150 of the two vectors do not match, and likewise that the last elements do not
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
151 match. The caller must trim matching elements from the beginning and end
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
152 of the portions it is going to specify.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
153
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
154 If we return the "wrong" partitions, the worst this can do is cause
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
155 suboptimal diff output. It cannot cause incorrect diff output. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
156
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
157 static void
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
158 diag (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim, bool find_minimal,
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
159 struct partition *part, struct context *ctxt)
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
160 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
161 OFFSET *const fd = ctxt->fdiag; /* Give the compiler a chance. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
162 OFFSET *const bd = ctxt->bdiag; /* Additional help for the compiler. */
9685
2858c91c7452 Avoid gcc warnings due to misplaced 'const'.
Bruno Haible <bruno@clisp.org>
parents: 9669
diff changeset
163 ELEMENT const *const xv = ctxt->xvec; /* Still more help for the compiler. */
2858c91c7452 Avoid gcc warnings due to misplaced 'const'.
Bruno Haible <bruno@clisp.org>
parents: 9669
diff changeset
164 ELEMENT const *const yv = ctxt->yvec; /* And more and more . . . */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
165 const OFFSET dmin = xoff - ylim; /* Minimum valid diagonal. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
166 const OFFSET dmax = xlim - yoff; /* Maximum valid diagonal. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
167 const OFFSET fmid = xoff - yoff; /* Center diagonal of top-down search. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
168 const OFFSET bmid = xlim - ylim; /* Center diagonal of bottom-up search. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
169 OFFSET fmin = fmid;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
170 OFFSET fmax = fmid; /* Limits of top-down search. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
171 OFFSET bmin = bmid;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
172 OFFSET bmax = bmid; /* Limits of bottom-up search. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
173 OFFSET c; /* Cost. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
174 bool odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
175 diagonal with respect to the northwest. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
176
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
177 fd[fmid] = xoff;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
178 bd[bmid] = xlim;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
179
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
180 for (c = 1;; ++c)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
181 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
182 OFFSET d; /* Active diagonal. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
183 bool big_snake = false;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
184
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
185 /* Extend the top-down search by an edit step in each diagonal. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
186 if (fmin > dmin)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
187 fd[--fmin - 1] = -1;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
188 else
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
189 ++fmin;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
190 if (fmax < dmax)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
191 fd[++fmax + 1] = -1;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
192 else
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
193 --fmax;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
194 for (d = fmax; d >= fmin; d -= 2)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
195 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
196 OFFSET x;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
197 OFFSET y;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
198 OFFSET tlo = fd[d - 1];
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
199 OFFSET thi = fd[d + 1];
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
200 OFFSET x0 = tlo < thi ? thi : tlo + 1;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
201
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
202 for (x = x0, y = x0 - d;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
203 x < xlim && y < ylim && EQUAL (xv[x], yv[y]);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
204 x++, y++)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
205 continue;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
206 if (x - x0 > SNAKE_LIMIT)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
207 big_snake = true;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
208 fd[d] = x;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
209 if (odd && bmin <= d && d <= bmax && bd[d] <= x)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
210 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
211 part->xmid = x;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
212 part->ymid = y;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
213 part->lo_minimal = part->hi_minimal = true;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
214 return;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
215 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
216 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
217
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
218 /* Similarly extend the bottom-up search. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
219 if (bmin > dmin)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
220 bd[--bmin - 1] = OFFSET_MAX;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
221 else
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
222 ++bmin;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
223 if (bmax < dmax)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
224 bd[++bmax + 1] = OFFSET_MAX;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
225 else
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
226 --bmax;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
227 for (d = bmax; d >= bmin; d -= 2)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
228 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
229 OFFSET x;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
230 OFFSET y;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
231 OFFSET tlo = bd[d - 1];
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
232 OFFSET thi = bd[d + 1];
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
233 OFFSET x0 = tlo < thi ? tlo : thi - 1;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
234
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
235 for (x = x0, y = x0 - d;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
236 xoff < x && yoff < y && EQUAL (xv[x - 1], yv[y - 1]);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
237 x--, y--)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
238 continue;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
239 if (x0 - x > SNAKE_LIMIT)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
240 big_snake = true;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
241 bd[d] = x;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
242 if (!odd && fmin <= d && d <= fmax && x <= fd[d])
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
243 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
244 part->xmid = x;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
245 part->ymid = y;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
246 part->lo_minimal = part->hi_minimal = true;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
247 return;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
248 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
249 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
250
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
251 if (find_minimal)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
252 continue;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
253
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
254 #ifdef USE_HEURISTIC
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
255 /* Heuristic: check occasionally for a diagonal that has made lots
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
256 of progress compared with the edit distance. If we have any
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
257 such, find the one that has made the most progress and return it
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
258 as if it had succeeded.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
259
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
260 With this heuristic, for vectors with a constant small density
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
261 of changes, the algorithm is linear in the vector size. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
262
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
263 if (200 < c && big_snake && ctxt->heuristic)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
264 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
265 OFFSET best = 0;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
266
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
267 for (d = fmax; d >= fmin; d -= 2)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
268 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
269 OFFSET dd = d - fmid;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
270 OFFSET x = fd[d];
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
271 OFFSET y = x - d;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
272 OFFSET v = (x - xoff) * 2 - dd;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
273
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
274 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
275 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
276 if (v > best
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
277 && xoff + SNAKE_LIMIT <= x && x < xlim
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
278 && yoff + SNAKE_LIMIT <= y && y < ylim)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
279 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
280 /* We have a good enough best diagonal; now insist
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
281 that it end with a significant snake. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
282 int k;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
283
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
284 for (k = 1; EQUAL (xv[x - k], yv[y - k]); k++)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
285 if (k == SNAKE_LIMIT)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
286 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
287 best = v;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
288 part->xmid = x;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
289 part->ymid = y;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
290 break;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
291 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
292 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
293 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
294 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
295 if (best > 0)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
296 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
297 part->lo_minimal = true;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
298 part->hi_minimal = false;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
299 return;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
300 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
301
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
302 best = 0;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
303 for (d = bmax; d >= bmin; d -= 2)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
304 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
305 OFFSET dd = d - bmid;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
306 OFFSET x = bd[d];
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
307 OFFSET y = x - d;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
308 OFFSET v = (xlim - x) * 2 + dd;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
309
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
310 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
311 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
312 if (v > best
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
313 && xoff < x && x <= xlim - SNAKE_LIMIT
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
314 && yoff < y && y <= ylim - SNAKE_LIMIT)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
315 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
316 /* We have a good enough best diagonal; now insist
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
317 that it end with a significant snake. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
318 int k;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
319
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
320 for (k = 0; EQUAL (xv[x + k], yv[y + k]); k++)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
321 if (k == SNAKE_LIMIT - 1)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
322 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
323 best = v;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
324 part->xmid = x;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
325 part->ymid = y;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
326 break;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
327 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
328 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
329 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
330 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
331 if (best > 0)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
332 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
333 part->lo_minimal = false;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
334 part->hi_minimal = true;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
335 return;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
336 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
337 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
338 #endif /* USE_HEURISTIC */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
339
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
340 /* Heuristic: if we've gone well beyond the call of duty, give up
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
341 and report halfway between our best results so far. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
342 if (c >= ctxt->too_expensive)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
343 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
344 OFFSET fxybest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
345 OFFSET fxbest IF_LINT (= 0);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
346 OFFSET bxybest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
347 OFFSET bxbest IF_LINT (= 0);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
348
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
349 /* Find forward diagonal that maximizes X + Y. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
350 fxybest = -1;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
351 for (d = fmax; d >= fmin; d -= 2)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
352 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
353 OFFSET x = MIN (fd[d], xlim);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
354 OFFSET y = x - d;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
355 if (ylim < y)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
356 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
357 x = ylim + d;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
358 y = ylim;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
359 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
360 if (fxybest < x + y)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
361 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
362 fxybest = x + y;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
363 fxbest = x;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
364 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
365 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
366
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
367 /* Find backward diagonal that minimizes X + Y. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
368 bxybest = OFFSET_MAX;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
369 for (d = bmax; d >= bmin; d -= 2)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
370 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
371 OFFSET x = MAX (xoff, bd[d]);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
372 OFFSET y = x - d;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
373 if (y < yoff)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
374 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
375 x = yoff + d;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
376 y = yoff;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
377 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
378 if (x + y < bxybest)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
379 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
380 bxybest = x + y;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
381 bxbest = x;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
382 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
383 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
384
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
385 /* Use the better of the two diagonals. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
386 if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
387 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
388 part->xmid = fxbest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
389 part->ymid = fxybest - fxbest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
390 part->lo_minimal = true;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
391 part->hi_minimal = false;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
392 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
393 else
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
394 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
395 part->xmid = bxbest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
396 part->ymid = bxybest - bxbest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
397 part->lo_minimal = false;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
398 part->hi_minimal = true;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
399 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
400 return;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
401 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
402 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
403 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
404
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
405
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
406 /* Compare in detail contiguous subsequences of the two vectors
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
407 which are known, as a whole, to match each other.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
408
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
409 The subsequence of vector 0 is [XOFF, XLIM) and likewise for vector 1.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
410
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
411 Note that XLIM, YLIM are exclusive bounds. All indices into the vectors
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
412 are origin-0.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
413
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
414 If FIND_MINIMAL, find a minimal difference no matter how
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
415 expensive it is.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
416
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
417 The results are recorded by invoking NOTE_DELETE and NOTE_INSERT.
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
418
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
419 Return false if terminated normally, or true if terminated through early
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
420 abort. */
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
421
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
422 static bool
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
423 compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
424 bool find_minimal, struct context *ctxt)
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
425 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
426 ELEMENT const *xv = ctxt->xvec; /* Help the compiler. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
427 ELEMENT const *yv = ctxt->yvec;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
428
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
429 /* Slide down the bottom initial diagonal. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
430 while (xoff < xlim && yoff < ylim && EQUAL (xv[xoff], yv[yoff]))
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
431 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
432 xoff++;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
433 yoff++;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
434 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
435
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
436 /* Slide up the top initial diagonal. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
437 while (xoff < xlim && yoff < ylim && EQUAL (xv[xlim - 1], yv[ylim - 1]))
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
438 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
439 xlim--;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
440 ylim--;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
441 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
442
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
443 /* Handle simple cases. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
444 if (xoff == xlim)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
445 while (yoff < ylim)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
446 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
447 NOTE_INSERT (ctxt, yoff);
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
448 if (EARLY_ABORT (ctxt))
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
449 return true;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
450 yoff++;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
451 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
452 else if (yoff == ylim)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
453 while (xoff < xlim)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
454 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
455 NOTE_DELETE (ctxt, xoff);
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
456 if (EARLY_ABORT (ctxt))
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
457 return true;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
458 xoff++;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
459 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
460 else
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
461 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
462 struct partition part;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
463
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
464 /* Find a point of correspondence in the middle of the vectors. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
465 diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
466
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
467 /* Use the partitions to split this problem into subproblems. */
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
468 if (compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt))
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
469 return true;
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
470 if (compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt))
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
471 return true;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
472 }
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
473
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
474 return false;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
475 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
476
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
477 #undef ELEMENT
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
478 #undef EQUAL
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
479 #undef OFFSET
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
480 #undef EXTRA_CONTEXT_FIELDS
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
481 #undef NOTE_DELETE
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
482 #undef NOTE_INSERT
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
483 #undef EARLY_ABORT
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
484 #undef USE_HEURISTIC
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
485 #undef OFFSET_MAX