annotate lib/diffseq.h @ 12331:dfb465b19291

diffseq: reduce scope of variable 'best'.
author Bruno Haible <bruno@clisp.org>
date Sat, 21 Nov 2009 14:37:46 +0100 (2009-11-21)
parents de232f8c8d7f
children 911f28ebb9c4
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
12331
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
3 Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2009 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 {
12331
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
265 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
266 OFFSET best = 0;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
267
12331
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
268 for (d = fmax; d >= fmin; d -= 2)
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
269 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
270 OFFSET dd = d - fmid;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
271 OFFSET x = fd[d];
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
272 OFFSET y = x - d;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
273 OFFSET v = (x - xoff) * 2 - dd;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
274
12331
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
275 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
276 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
277 if (v > best
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
278 && xoff + SNAKE_LIMIT <= x && x < xlim
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
279 && yoff + SNAKE_LIMIT <= y && y < ylim)
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
280 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
281 /* We have a good enough best diagonal; now insist
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
282 that it end with a significant snake. */
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
283 int k;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
284
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
285 for (k = 1; EQUAL (xv[x - k], yv[y - k]); k++)
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
286 if (k == SNAKE_LIMIT)
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
287 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
288 best = v;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
289 part->xmid = x;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
290 part->ymid = y;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
291 break;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
292 }
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
293 }
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
294 }
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
295 }
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
296 if (best > 0)
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
297 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
298 part->lo_minimal = true;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
299 part->hi_minimal = false;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
300 return;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
301 }
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
302 }
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
303
12331
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
304 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
305 OFFSET best = 0;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
306
12331
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
307 for (d = bmax; d >= bmin; d -= 2)
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
308 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
309 OFFSET dd = d - bmid;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
310 OFFSET x = bd[d];
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
311 OFFSET y = x - d;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
312 OFFSET v = (xlim - x) * 2 + dd;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
313
12331
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
314 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
315 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
316 if (v > best
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
317 && xoff < x && x <= xlim - SNAKE_LIMIT
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
318 && yoff < y && y <= ylim - SNAKE_LIMIT)
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
319 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
320 /* We have a good enough best diagonal; now insist
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
321 that it end with a significant snake. */
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
322 int k;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
323
12331
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
324 for (k = 0; EQUAL (xv[x + k], yv[y + k]); k++)
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
325 if (k == SNAKE_LIMIT - 1)
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
326 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
327 best = v;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
328 part->xmid = x;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
329 part->ymid = y;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
330 break;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
331 }
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
332 }
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
333 }
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
334 }
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
335 if (best > 0)
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
336 {
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
337 part->lo_minimal = false;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
338 part->hi_minimal = true;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
339 return;
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
340 }
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
341 }
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
342 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
343 #endif /* USE_HEURISTIC */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
344
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
345 /* 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
346 and report halfway between our best results so far. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
347 if (c >= ctxt->too_expensive)
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 OFFSET fxybest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
350 OFFSET fxbest IF_LINT (= 0);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
351 OFFSET bxybest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
352 OFFSET bxbest IF_LINT (= 0);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
353
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
354 /* Find forward diagonal that maximizes X + Y. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
355 fxybest = -1;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
356 for (d = fmax; d >= fmin; d -= 2)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
357 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
358 OFFSET x = MIN (fd[d], xlim);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
359 OFFSET y = x - d;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
360 if (ylim < 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 x = ylim + d;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
363 y = ylim;
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 if (fxybest < x + y)
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 fxybest = x + y;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
368 fxbest = x;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
369 }
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
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
372 /* Find backward diagonal that minimizes X + Y. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
373 bxybest = OFFSET_MAX;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
374 for (d = bmax; d >= bmin; d -= 2)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
375 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
376 OFFSET x = MAX (xoff, bd[d]);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
377 OFFSET y = x - d;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
378 if (y < yoff)
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 x = yoff + d;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
381 y = yoff;
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 if (x + y < bxybest)
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 bxybest = x + y;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
386 bxbest = x;
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 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
389
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
390 /* Use the better of the two diagonals. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
391 if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
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 part->xmid = fxbest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
394 part->ymid = fxybest - fxbest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
395 part->lo_minimal = true;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
396 part->hi_minimal = false;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
397 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
398 else
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 part->xmid = bxbest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
401 part->ymid = bxybest - bxbest;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
402 part->lo_minimal = false;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
403 part->hi_minimal = true;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
404 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
405 return;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
406 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
407 }
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
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
410
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
411 /* Compare in detail contiguous subsequences of the two vectors
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
412 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
413
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
414 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
415
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
416 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
417 are origin-0.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
418
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
419 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
420 expensive it is.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
421
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
422 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
423
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
424 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
425 abort. */
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
426
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
427 static bool
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
428 compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
429 bool find_minimal, struct context *ctxt)
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
430 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
431 ELEMENT const *xv = ctxt->xvec; /* Help the compiler. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
432 ELEMENT const *yv = ctxt->yvec;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
433
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
434 /* Slide down the bottom initial diagonal. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
435 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
436 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
437 xoff++;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
438 yoff++;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
439 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
440
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
441 /* Slide up the top initial diagonal. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
442 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
443 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
444 xlim--;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
445 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
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
448 /* Handle simple cases. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
449 if (xoff == xlim)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
450 while (yoff < ylim)
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 NOTE_INSERT (ctxt, yoff);
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
453 if (EARLY_ABORT (ctxt))
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
454 return true;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
455 yoff++;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
456 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
457 else if (yoff == ylim)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
458 while (xoff < xlim)
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 NOTE_DELETE (ctxt, xoff);
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
461 if (EARLY_ABORT (ctxt))
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
462 return true;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
463 xoff++;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
464 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
465 else
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 struct partition part;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
468
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
469 /* 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
470 diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
471
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
472 /* 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
473 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
474 return true;
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
475 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
476 return true;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
477 }
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
478
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
479 return false;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
480 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
481
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
482 #undef ELEMENT
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
483 #undef EQUAL
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
484 #undef OFFSET
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
485 #undef EXTRA_CONTEXT_FIELDS
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
486 #undef NOTE_DELETE
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
487 #undef NOTE_INSERT
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
488 #undef EARLY_ABORT
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
489 #undef USE_HEURISTIC
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
490 #undef OFFSET_MAX