Mercurial > gnulib

annotate lib/diffseq.h @ 40186:8964917f9574

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
autoupdate
author Karl Berry <karl@freefriends.org>
date Mon, 18 Feb 2019 08:02:49 -0800
parents b06060465f09
children
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
40057
b06060465f09 maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents: 19484
diff changeset
3 Copyright (C) 1988-1989, 1992-1995, 2001-2004, 2006-2019 Free Software
12559
c2cbabec01dd update nearly all FSF copyright year lists to include 2010
Jim Meyering <meyering@redhat.com>
parents: 12421
diff changeset
4 Foundation, Inc.
9147
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
19190
9759915b2aca all: prefer https: URLs
Paul Eggert <eggert@cs.ucla.edu>
parents: 18965
diff changeset
17 along with this program. If not, see <https://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:
17619
d09167851e07 diffseq: remove TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 17576
diff changeset
29 "An O(ND) Difference Algorithm and its Variations", Eugene W. Myers,
d09167851e07 diffseq: remove TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 17576
diff changeset
30 Algorithmica Vol. 1, 1986, pp. 251-266,
d09167851e07 diffseq: remove TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 17576
diff changeset
31 <http://dx.doi.org/10.1007/BF01840446>.
d09167851e07 diffseq: remove TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 17576
diff changeset
32 See especially section 4.2, which describes the variation used below.
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
33
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
34 The basic algorithm was independently discovered as described in:
17619
d09167851e07 diffseq: remove TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 17576
diff changeset
35 "Algorithms for Approximate String Matching", Esko Ukkonen,
d09167851e07 diffseq: remove TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 17576
diff changeset
36 Information and Control Vol. 64, 1985, pp. 100-118,
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
37 <http://dx.doi.org/10.1016/S0019-9958(85)80046-2>.
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
38
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
39 Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
40 heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
41 at the price of producing suboptimal output for large inputs with
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
42 many differences. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
43
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
44 /* Before including this file, you need to define:
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
45 ELEMENT The element type of the vectors being compared.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
46 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
47 equality.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
48 OFFSET A signed integer type sufficient to hold the
17895
5aab9ce8ce71 diffseq: prefer ptrdiff_t to ssize_t
Paul Eggert <eggert@cs.ucla.edu>
parents: 17848
diff changeset
49 difference between two indices. Usually
5aab9ce8ce71 diffseq: prefer ptrdiff_t to ssize_t
Paul Eggert <eggert@cs.ucla.edu>
parents: 17848
diff changeset
50 something like ptrdiff_t.
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
51 EXTRA_CONTEXT_FIELDS Declarations of fields for 'struct context'.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
52 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
53 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
54 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
55 early abort of the computation.
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
56 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
57 heuristic for large vectors.
13246
89fadace6a88 Fix typo in comment.
Bruno Haible <bruno@clisp.org>
parents: 13243
diff changeset
58 It is also possible to use this file with abstract arrays. In this case,
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
59 xvec and yvec are not represented in memory. They only exist conceptually.
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
60 In this case, the list of defines above is amended as follows:
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
61 ELEMENT Undefined.
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
62 EQUAL Undefined.
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
63 XVECREF_YVECREF_EQUAL(ctxt, xoff, yoff)
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
64 A three-argument macro: References xvec[xoff] and
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
65 yvec[yoff] and tests these elements for equality.
9669
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
66 Before including this file, you also need to include:
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
67 #include <limits.h>
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
68 #include <stdbool.h>
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
69 #include "minmax.h"
8b484b0c3ae6 Add comments about required includes.
Bruno Haible <bruno@clisp.org>
parents: 9309
diff changeset
70 */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
71
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
72 /* Maximum value of type OFFSET. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
73 #define OFFSET_MAX \
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
74 ((((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
75
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
76 /* Default to no early abort. */
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
77 #ifndef EARLY_ABORT
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
78 # define EARLY_ABORT(ctxt) false
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
79 #endif
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
80
16235
18a38c9615f0 In commentary, do not use ` to quote.
Paul Eggert <eggert@cs.ucla.edu>
parents: 16201
diff changeset
81 /* Use this to suppress gcc's "...may be used before initialized" warnings.
12336
90584cfd31a4 Add comment.
Bruno Haible <bruno@clisp.org>
parents: 12334
diff changeset
82 Beware: The Code argument must not contain commas. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
83 #ifndef IF_LINT
18325
33db65a13e67 Use GCC_LINT, not lint
Paul Eggert <eggert@cs.ucla.edu>
parents: 18189
diff changeset
84 # if defined GCC_LINT || defined lint
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
85 # define IF_LINT(Code) Code
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
86 # else
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
87 # define IF_LINT(Code) /* empty */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
88 # endif
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
89 #endif
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
90
12334
911f28ebb9c4 diffseq: avoid spurious gcc warnings
Jim Meyering <meyering@redhat.com>
parents: 12331
diff changeset
91 /* As above, but when Code must contain one comma. */
911f28ebb9c4 diffseq: avoid spurious gcc warnings
Jim Meyering <meyering@redhat.com>
parents: 12331
diff changeset
92 #ifndef IF_LINT2
18325
33db65a13e67 Use GCC_LINT, not lint
Paul Eggert <eggert@cs.ucla.edu>
parents: 18189
diff changeset
93 # if defined GCC_LINT || defined lint
12334
911f28ebb9c4 diffseq: avoid spurious gcc warnings
Jim Meyering <meyering@redhat.com>
parents: 12331
diff changeset
94 # define IF_LINT2(Code1, Code2) Code1, Code2
911f28ebb9c4 diffseq: avoid spurious gcc warnings
Jim Meyering <meyering@redhat.com>
parents: 12331
diff changeset
95 # else
911f28ebb9c4 diffseq: avoid spurious gcc warnings
Jim Meyering <meyering@redhat.com>
parents: 12331
diff changeset
96 # define IF_LINT2(Code1, Code2) /* empty */
911f28ebb9c4 diffseq: avoid spurious gcc warnings
Jim Meyering <meyering@redhat.com>
parents: 12331
diff changeset
97 # endif
911f28ebb9c4 diffseq: avoid spurious gcc warnings
Jim Meyering <meyering@redhat.com>
parents: 12331
diff changeset
98 #endif
911f28ebb9c4 diffseq: avoid spurious gcc warnings
Jim Meyering <meyering@redhat.com>
parents: 12331
diff changeset
99
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
100 /*
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
101 * Context of comparison operation.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
102 */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
103 struct context
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
104 {
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
105 #ifdef ELEMENT
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
106 /* Vectors being compared. */
9685
2858c91c7452 Avoid gcc warnings due to misplaced 'const'.
Bruno Haible <bruno@clisp.org>
parents: 9669
diff changeset
107 ELEMENT const *xvec;
2858c91c7452 Avoid gcc warnings due to misplaced 'const'.
Bruno Haible <bruno@clisp.org>
parents: 9669
diff changeset
108 ELEMENT const *yvec;
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
109 #endif
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
110
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
111 /* Extra fields. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
112 EXTRA_CONTEXT_FIELDS
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
113
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
114 /* 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
115 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
116 matrix. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
117 OFFSET *fdiag;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
118
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
119 /* 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
120 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
121 matrix. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
122 OFFSET *bdiag;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
123
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
124 #ifdef USE_HEURISTIC
17619
d09167851e07 diffseq: remove TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 17576
diff changeset
125 /* This corresponds to the diff --speed-large-files flag. With this
d09167851e07 diffseq: remove TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 17576
diff changeset
126 heuristic, for vectors with a constant small density of changes,
d09167851e07 diffseq: remove TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 17576
diff changeset
127 the algorithm is linear in the vector size. */
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
128 bool heuristic;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
129 #endif
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
130
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
131 /* Edit scripts longer than this are too expensive to compute. */
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
132 OFFSET too_expensive;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
133
16235
18a38c9615f0 In commentary, do not use ` to quote.
Paul Eggert <eggert@cs.ucla.edu>
parents: 16201
diff changeset
134 /* Snakes bigger than this are considered "big". */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
135 #define SNAKE_LIMIT 20
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
136 };
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
137
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
138 struct partition
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
139 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
140 /* Midpoints of this partition. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
141 OFFSET xmid;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
142 OFFSET ymid;
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
143
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
144 /* True if low half will be analyzed minimally. */
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
145 bool lo_minimal;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
146
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
147 /* Likewise for high half. */
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
148 bool hi_minimal;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
149 };
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
150
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
151
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
152 /* 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
153 of the two vectors.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
154
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
155 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
156 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
157 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
158 edit sequence.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
159
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
160 If FIND_MINIMAL is true, find the minimal edit script regardless of
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
161 expense. Otherwise, if the search is too expensive, use heuristics to
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
162 stop the search and report a suboptimal answer.
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
163
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
164 Set PART->(xmid,ymid) to the midpoint (XMID,YMID). The diagonal number
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
165 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
166 of deleted elements (counting only elements before the midpoint).
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
167
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
168 Set PART->lo_minimal to true iff the minimal edit script for the
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
169 left half of the partition is known; similarly for PART->hi_minimal.
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
170
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
171 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
172 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
173 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
174 of the portions it is going to specify.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
175
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
176 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
177 suboptimal diff output. It cannot cause incorrect diff output. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
178
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
179 static void
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
180 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
181 struct partition *part, struct context *ctxt)
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
182 {
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
183 OFFSET *const fd = ctxt->fdiag; /* Give the compiler a chance. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
184 OFFSET *const bd = ctxt->bdiag; /* Additional help for the compiler. */
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
185 #ifdef ELEMENT
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
186 ELEMENT const *const xv = ctxt->xvec; /* Still more help for the compiler. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
187 ELEMENT const *const yv = ctxt->yvec; /* And more and more . . . */
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
188 #define XREF_YREF_EQUAL(x,y) EQUAL (xv[x], yv[y])
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
189 #else
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
190 #define XREF_YREF_EQUAL(x,y) XVECREF_YVECREF_EQUAL (ctxt, x, y)
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
191 #endif
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
192 const OFFSET dmin = xoff - ylim; /* Minimum valid diagonal. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
193 const OFFSET dmax = xlim - yoff; /* Maximum valid diagonal. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
194 const OFFSET fmid = xoff - yoff; /* Center diagonal of top-down search. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
195 const OFFSET bmid = xlim - ylim; /* Center diagonal of bottom-up search. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
196 OFFSET fmin = fmid;
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
197 OFFSET fmax = fmid; /* Limits of top-down search. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
198 OFFSET bmin = bmid;
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
199 OFFSET bmax = bmid; /* Limits of bottom-up search. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
200 OFFSET c; /* Cost. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
201 bool odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
202 diagonal with respect to the northwest. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
203
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
204 fd[fmid] = xoff;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
205 bd[bmid] = xlim;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
206
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
207 for (c = 1;; ++c)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
208 {
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
209 OFFSET d; /* Active diagonal. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
210 bool big_snake = false;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
211
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
212 /* 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
213 if (fmin > dmin)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
214 fd[--fmin - 1] = -1;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
215 else
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
216 ++fmin;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
217 if (fmax < dmax)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
218 fd[++fmax + 1] = -1;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
219 else
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
220 --fmax;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
221 for (d = fmax; d >= fmin; d -= 2)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
222 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
223 OFFSET x;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
224 OFFSET y;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
225 OFFSET tlo = fd[d - 1];
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
226 OFFSET thi = fd[d + 1];
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
227 OFFSET x0 = tlo < thi ? thi : tlo + 1;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
228
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
229 for (x = x0, y = x0 - d;
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
230 x < xlim && y < ylim && XREF_YREF_EQUAL (x, y);
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
231 x++, y++)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
232 continue;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
233 if (x - x0 > SNAKE_LIMIT)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
234 big_snake = true;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
235 fd[d] = x;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
236 if (odd && bmin <= d && d <= bmax && bd[d] <= x)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
237 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
238 part->xmid = x;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
239 part->ymid = y;
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
240 part->lo_minimal = part->hi_minimal = true;
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
241 return;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
242 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
243 }
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
244
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
245 /* Similarly extend the bottom-up search. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
246 if (bmin > dmin)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
247 bd[--bmin - 1] = OFFSET_MAX;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
248 else
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
249 ++bmin;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
250 if (bmax < dmax)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
251 bd[++bmax + 1] = OFFSET_MAX;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
252 else
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
253 --bmax;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
254 for (d = bmax; d >= bmin; d -= 2)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
255 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
256 OFFSET x;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
257 OFFSET y;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
258 OFFSET tlo = bd[d - 1];
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
259 OFFSET thi = bd[d + 1];
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
260 OFFSET x0 = tlo < thi ? tlo : thi - 1;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
261
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
262 for (x = x0, y = x0 - d;
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
263 xoff < x && yoff < y && XREF_YREF_EQUAL (x - 1, y - 1);
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
264 x--, y--)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
265 continue;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
266 if (x0 - x > SNAKE_LIMIT)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
267 big_snake = true;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
268 bd[d] = x;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
269 if (!odd && fmin <= d && d <= fmax && x <= fd[d])
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
270 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
271 part->xmid = x;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
272 part->ymid = y;
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
273 part->lo_minimal = part->hi_minimal = true;
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
274 return;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
275 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
276 }
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
277
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
278 if (find_minimal)
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
279 continue;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
280
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
281 #ifdef USE_HEURISTIC
18965
29e32f674c6c diffseq: port to GCC 7 with --enable-gcc-warnings
Paul Eggert <eggert@cs.ucla.edu>
parents: 18626
diff changeset
282 bool heuristic = ctxt->heuristic;
29e32f674c6c diffseq: port to GCC 7 with --enable-gcc-warnings
Paul Eggert <eggert@cs.ucla.edu>
parents: 18626
diff changeset
283 #else
29e32f674c6c diffseq: port to GCC 7 with --enable-gcc-warnings
Paul Eggert <eggert@cs.ucla.edu>
parents: 18626
diff changeset
284 bool heuristic = false;
29e32f674c6c diffseq: port to GCC 7 with --enable-gcc-warnings
Paul Eggert <eggert@cs.ucla.edu>
parents: 18626
diff changeset
285 #endif
29e32f674c6c diffseq: port to GCC 7 with --enable-gcc-warnings
Paul Eggert <eggert@cs.ucla.edu>
parents: 18626
diff changeset
286
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
287 /* Heuristic: check occasionally for a diagonal that has made lots
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
288 of progress compared with the edit distance. If we have any
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
289 such, find the one that has made the most progress and return it
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
290 as if it had succeeded.
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
291
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
292 With this heuristic, for vectors with a constant small density
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
293 of changes, the algorithm is linear in the vector size. */
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
294
18965
29e32f674c6c diffseq: port to GCC 7 with --enable-gcc-warnings
Paul Eggert <eggert@cs.ucla.edu>
parents: 18626
diff changeset
295 if (200 < c && big_snake && heuristic)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
296 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
297 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
298 OFFSET best = 0;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
299
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
300 for (d = fmax; d >= fmin; d -= 2)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
301 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
302 OFFSET dd = d - fmid;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
303 OFFSET x = fd[d];
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
304 OFFSET y = x - d;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
305 OFFSET v = (x - xoff) * 2 - dd;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
306
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
307 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
308 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
309 if (v > best
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
310 && xoff + SNAKE_LIMIT <= x && x < xlim
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
311 && yoff + SNAKE_LIMIT <= y && y < ylim)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
312 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
313 /* We have a good enough best diagonal; now insist
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
314 that it end with a significant snake. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
315 int k;
12331
dfb465b19291 diffseq: reduce scope of variable 'best'.
Bruno Haible <bruno@clisp.org>
parents: 12330
diff changeset
316
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
317 for (k = 1; XREF_YREF_EQUAL (x - k, y - k); k++)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
318 if (k == SNAKE_LIMIT)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
319 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
320 best = v;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
321 part->xmid = x;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
322 part->ymid = y;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
323 break;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
324 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
325 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
326 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
327 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
328 if (best > 0)
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
329 {
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
330 part->lo_minimal = true;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
331 part->hi_minimal = false;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
332 return;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
333 }
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
334 }
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
335
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
336 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
337 OFFSET best = 0;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
338
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
339 for (d = bmax; d >= bmin; d -= 2)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
340 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
341 OFFSET dd = d - bmid;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
342 OFFSET x = bd[d];
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
343 OFFSET y = x - d;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
344 OFFSET v = (xlim - x) * 2 + dd;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
345
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
346 if (v > 12 * (c + (dd < 0 ? -dd : dd)))
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
347 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
348 if (v > best
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
349 && xoff < x && x <= xlim - SNAKE_LIMIT
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
350 && yoff < y && y <= ylim - SNAKE_LIMIT)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
351 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
352 /* We have a good enough best diagonal; now insist
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
353 that it end with a significant snake. */
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
354 int k;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
355
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
356 for (k = 0; XREF_YREF_EQUAL (x + k, y + k); k++)
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
357 if (k == SNAKE_LIMIT - 1)
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
358 {
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
359 best = v;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
360 part->xmid = x;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
361 part->ymid = y;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
362 break;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
363 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
364 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
365 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
366 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
367 if (best > 0)
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
368 {
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
369 part->lo_minimal = false;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
370 part->hi_minimal = true;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
371 return;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
372 }
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
373 }
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
374 }
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
375
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
376 /* Heuristic: if we've gone well beyond the call of duty, give up
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
377 and report halfway between our best results so far. */
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
378 if (c >= ctxt->too_expensive)
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
379 {
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
380 OFFSET fxybest;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
381 OFFSET fxbest IF_LINT (= 0);
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
382 OFFSET bxybest;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
383 OFFSET bxbest IF_LINT (= 0);
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
384
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
385 /* Find forward diagonal that maximizes X + Y. */
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
386 fxybest = -1;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
387 for (d = fmax; d >= fmin; d -= 2)
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
388 {
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
389 OFFSET x = MIN (fd[d], xlim);
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
390 OFFSET y = x - d;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
391 if (ylim < y)
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
392 {
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
393 x = ylim + d;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
394 y = ylim;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
395 }
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
396 if (fxybest < x + y)
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
397 {
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
398 fxybest = x + y;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
399 fxbest = x;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
400 }
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
401 }
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
402
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
403 /* Find backward diagonal that minimizes X + Y. */
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
404 bxybest = OFFSET_MAX;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
405 for (d = bmax; d >= bmin; d -= 2)
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
406 {
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
407 OFFSET x = MAX (xoff, bd[d]);
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
408 OFFSET y = x - d;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
409 if (y < yoff)
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
410 {
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
411 x = yoff + d;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
412 y = yoff;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
413 }
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
414 if (x + y < bxybest)
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
415 {
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
416 bxybest = x + y;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
417 bxbest = x;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
418 }
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
419 }
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
420
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
421 /* Use the better of the two diagonals. */
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
422 if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
423 {
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
424 part->xmid = fxbest;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
425 part->ymid = fxybest - fxbest;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
426 part->lo_minimal = true;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
427 part->hi_minimal = false;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
428 }
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
429 else
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
430 {
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
431 part->xmid = bxbest;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
432 part->ymid = bxybest - bxbest;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
433 part->lo_minimal = false;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
434 part->hi_minimal = true;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
435 }
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
436 return;
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
437 }
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
438 }
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
439 #undef XREF_YREF_EQUAL
9147
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
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
442
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
443 /* Compare in detail contiguous subsequences of the two vectors
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
444 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
445
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
446 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
447
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
448 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
449 are origin-0.
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
450
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
451 If FIND_MINIMAL, find a minimal difference no matter how
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
452 expensive it is.
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
453
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
454 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
455
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
456 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
457 abort. */
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
458
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
459 static bool
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
460 compareseq (OFFSET xoff, OFFSET xlim, OFFSET yoff, OFFSET ylim,
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
461 bool find_minimal, struct context *ctxt)
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
462 {
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
463 #ifdef ELEMENT
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
464 ELEMENT const *xv = ctxt->xvec; /* Help the compiler. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
465 ELEMENT const *yv = ctxt->yvec;
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
466 #define XREF_YREF_EQUAL(x,y) EQUAL (xv[x], yv[y])
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
467 #else
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
468 #define XREF_YREF_EQUAL(x,y) XVECREF_YVECREF_EQUAL (ctxt, x, y)
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
469 #endif
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
470
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
471 /* Slide down the bottom initial diagonal. */
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
472 while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xoff, yoff))
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
473 {
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
474 xoff++;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
475 yoff++;
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
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
478 /* Slide up the top initial diagonal. */
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
479 while (xoff < xlim && yoff < ylim && XREF_YREF_EQUAL (xlim - 1, ylim - 1))
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 xlim--;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
482 ylim--;
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
483 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
484
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
485 /* Handle simple cases. */
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
486 if (xoff == xlim)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
487 while (yoff < ylim)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
488 {
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
489 NOTE_INSERT (ctxt, yoff);
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
490 if (EARLY_ABORT (ctxt))
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
491 return true;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
492 yoff++;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
493 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
494 else if (yoff == ylim)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
495 while (xoff < xlim)
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
496 {
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
497 NOTE_DELETE (ctxt, xoff);
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
498 if (EARLY_ABORT (ctxt))
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
499 return true;
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
500 xoff++;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
501 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
502 else
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
503 {
12334
911f28ebb9c4 diffseq: avoid spurious gcc warnings
Jim Meyering <meyering@redhat.com>
parents: 12331
diff changeset
504 struct partition part IF_LINT2 (= { .xmid = 0, .ymid = 0 });
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
505
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
506 /* Find a point of correspondence in the middle of the vectors. */
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
507 diag (xoff, xlim, yoff, ylim, find_minimal, &part, ctxt);
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
508
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
509 /* Use the partitions to split this problem into subproblems. */
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
510 if (compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal, ctxt))
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
511 return true;
18477
8d64577babf5 diffseq: restore TOO_EXPENSIVE heuristic
Paul Eggert <eggert@cs.ucla.edu>
parents: 18325
diff changeset
512 if (compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal, ctxt))
12421
e8d2c6fc33ad Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents: 12336
diff changeset
513 return true;
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
514 }
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
515
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
516 return false;
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
517 #undef XREF_YREF_EQUAL
9147
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
518 }
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
519
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
520 #undef ELEMENT
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
521 #undef EQUAL
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
522 #undef OFFSET
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
523 #undef EXTRA_CONTEXT_FIELDS
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
524 #undef NOTE_DELETE
d5c437e55b50 * MODULES.html.sh: Add diffseq.
Paul Eggert <eggert@cs.ucla.edu>
parents:
diff changeset
525 #undef NOTE_INSERT
10436
74c36e9e4884 Add an "early abort" facility to diffseq.
Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
parents: 9685
diff changeset
526 #undef EARLY_ABORT
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
527 #undef USE_HEURISTIC
13243
97c81b93ec7c diffseq: Accommodate use-case with abstract arrays.
Bruno Haible <bruno@clisp.org>
parents: 12559
diff changeset
528 #undef XVECREF_YVECREF_EQUAL
9149
3d5b34d43010 - Comment style.
Bruno Haible <bruno@clisp.org>
parents: 9147
diff changeset
529 #undef OFFSET_MAX