annotate src/intervals.c @ 13255:9e94f911f00c

(add-log-current-defun): Handle `private', `public' in C++ class definitions.
author Richard M. Stallman <rms@gnu.org>
date Fri, 20 Oct 1995 15:22:56 +0000
parents 49df58305295
children 621a575db6f7
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1 /* Code for doing intervals.
11235
e6bdaaa6ce1b Update copyright.
Karl Heuer <kwzh@gnu.org>
parents: 11133
diff changeset
2 Copyright (C) 1993, 1994, 1995 Free Software Foundation, Inc.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
3
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
4 This file is part of GNU Emacs.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
5
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
6 GNU Emacs is free software; you can redistribute it and/or modify
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
7 it under the terms of the GNU General Public License as published by
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
8 the Free Software Foundation; either version 2, or (at your option)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
9 any later version.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
10
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
11 GNU Emacs is distributed in the hope that it will be useful,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
14 GNU General Public License for more details.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
15
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
16 You should have received a copy of the GNU General Public License
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
17 along with GNU Emacs; see the file COPYING. If not, write to
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
19
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
20
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
21 /* NOTES:
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
22
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
23 Have to ensure that we can't put symbol nil on a plist, or some
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
24 functions may work incorrectly.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
25
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
26 An idea: Have the owner of the tree keep count of splits and/or
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
27 insertion lengths (in intervals), and balance after every N.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
28
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
29 Need to call *_left_hook when buffer is killed.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
30
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
31 Scan for zero-length, or 0-length to see notes about handling
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
32 zero length interval-markers.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
33
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
34 There are comments around about freeing intervals. It might be
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
35 faster to explicitly free them (put them on the free list) than
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
36 to GC them.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
37
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
38 */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
39
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
40
4696
1fc792473491 Include <config.h> instead of "config.h".
Roland McGrath <roland@gnu.org>
parents: 4638
diff changeset
41 #include <config.h>
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
42 #include "lisp.h"
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
43 #include "intervals.h"
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
44 #include "buffer.h"
4962
99edf052bfa0 Include puresize.h.
Richard M. Stallman <rms@gnu.org>
parents: 4718
diff changeset
45 #include "puresize.h"
8897
69cdecdaebf7 Add #include "keyboard.h"
Karl Heuer <kwzh@gnu.org>
parents: 8761
diff changeset
46 #include "keyboard.h"
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
47
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
48 /* The rest of the file is within this conditional. */
1301
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
49 #ifdef USE_TEXT_PROPERTIES
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
50
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
51 /* Test for membership, allowing for t (actually any non-cons) to mean the
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
52 universal set. */
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
53
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
54 #define TMEM(sym, set) (CONSP (set) ? ! NILP (Fmemq (sym, set)) : ! NILP (set))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
55
10113
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
56 #define min(x, y) ((x) < (y) ? (x) : (y))
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
57
5173
d48ba25b35bf (merge_properties_sticky): Declared.
Richard M. Stallman <rms@gnu.org>
parents: 5169
diff changeset
58 Lisp_Object merge_properties_sticky ();
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
59
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
60 /* Utility functions for intervals. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
61
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
62
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
63 /* Create the root interval of some object, a buffer or string. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
64
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
65 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
66 create_root_interval (parent)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
67 Lisp_Object parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
68 {
4962
99edf052bfa0 Include puresize.h.
Richard M. Stallman <rms@gnu.org>
parents: 4718
diff changeset
69 INTERVAL new;
99edf052bfa0 Include puresize.h.
Richard M. Stallman <rms@gnu.org>
parents: 4718
diff changeset
70
99edf052bfa0 Include puresize.h.
Richard M. Stallman <rms@gnu.org>
parents: 4718
diff changeset
71 CHECK_IMPURE (parent);
99edf052bfa0 Include puresize.h.
Richard M. Stallman <rms@gnu.org>
parents: 4718
diff changeset
72
99edf052bfa0 Include puresize.h.
Richard M. Stallman <rms@gnu.org>
parents: 4718
diff changeset
73 new = make_interval ();
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
74
9125
a78f02f76f03 (create_root_interval, balance_possible_root_interval, delete_interval): Use
Karl Heuer <kwzh@gnu.org>
parents: 9072
diff changeset
75 if (BUFFERP (parent))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
76 {
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
77 new->total_length = (BUF_Z (XBUFFER (parent))
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
78 - BUF_BEG (XBUFFER (parent)));
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
79 BUF_INTERVALS (XBUFFER (parent)) = new;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
80 }
9125
a78f02f76f03 (create_root_interval, balance_possible_root_interval, delete_interval): Use
Karl Heuer <kwzh@gnu.org>
parents: 9072
diff changeset
81 else if (STRINGP (parent))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
82 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
83 new->total_length = XSTRING (parent)->size;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
84 XSTRING (parent)->intervals = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
85 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
86
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
87 new->parent = (INTERVAL) parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
88 new->position = 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
89
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
90 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
91 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
92
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
93 /* Make the interval TARGET have exactly the properties of SOURCE */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
94
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
95 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
96 copy_properties (source, target)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
97 register INTERVAL source, target;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
98 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
99 if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
100 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
101
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
102 COPY_INTERVAL_CACHE (source, target);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
103 target->plist = Fcopy_sequence (source->plist);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
104 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
105
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
106 /* Merge the properties of interval SOURCE into the properties
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
107 of interval TARGET. That is to say, each property in SOURCE
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
108 is added to TARGET if TARGET has no such property as yet. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
109
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
110 static void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
111 merge_properties (source, target)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
112 register INTERVAL source, target;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
113 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
114 register Lisp_Object o, sym, val;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
115
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
116 if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
117 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
118
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
119 MERGE_INTERVAL_CACHE (source, target);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
120
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
121 o = source->plist;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
122 while (! EQ (o, Qnil))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
123 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
124 sym = Fcar (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
125 val = Fmemq (sym, target->plist);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
126
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
127 if (NILP (val))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
128 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
129 o = Fcdr (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
130 val = Fcar (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
131 target->plist = Fcons (sym, Fcons (val, target->plist));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
132 o = Fcdr (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
133 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
134 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
135 o = Fcdr (Fcdr (o));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
136 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
137 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
138
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
139 /* Return 1 if the two intervals have the same properties,
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
140 0 otherwise. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
141
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
142 int
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
143 intervals_equal (i0, i1)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
144 INTERVAL i0, i1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
145 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
146 register Lisp_Object i0_cdr, i0_sym, i1_val;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
147 register i1_len;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
148
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
149 if (DEFAULT_INTERVAL_P (i0) && DEFAULT_INTERVAL_P (i1))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
150 return 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
151
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
152 if (DEFAULT_INTERVAL_P (i0) || DEFAULT_INTERVAL_P (i1))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
153 return 0;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
154
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
155 i1_len = XFASTINT (Flength (i1->plist));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
156 if (i1_len & 0x1) /* Paranoia -- plists are always even */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
157 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
158 i1_len /= 2;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
159 i0_cdr = i0->plist;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
160 while (!NILP (i0_cdr))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
161 {
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
162 /* Lengths of the two plists were unequal. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
163 if (i1_len == 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
164 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
165
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
166 i0_sym = Fcar (i0_cdr);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
167 i1_val = Fmemq (i0_sym, i1->plist);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
168
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
169 /* i0 has something i1 doesn't. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
170 if (EQ (i1_val, Qnil))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
171 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
172
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
173 /* i0 and i1 both have sym, but it has different values in each. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
174 i0_cdr = Fcdr (i0_cdr);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
175 if (! EQ (Fcar (Fcdr (i1_val)), Fcar (i0_cdr)))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
176 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
177
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
178 i0_cdr = Fcdr (i0_cdr);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
179 i1_len--;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
180 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
181
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
182 /* Lengths of the two plists were unequal. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
183 if (i1_len > 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
184 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
185
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
186 return 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
187 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
188
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
189 static int icount;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
190 static int idepth;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
191 static int zero_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
192
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
193 /* Traverse an interval tree TREE, performing FUNCTION on each node.
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
194 Pass FUNCTION two args: an interval, and ARG. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
195
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
196 void
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
197 traverse_intervals (tree, position, depth, function, arg)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
198 INTERVAL tree;
1412
6097878fbd46 * intervals.c (traverse_intervals): New parameter `depth'.
Joseph Arceneaux <jla@gnu.org>
parents: 1316
diff changeset
199 int position, depth;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
200 void (* function) ();
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
201 Lisp_Object arg;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
202 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
203 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
204 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
205
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
206 traverse_intervals (tree->left, position, depth + 1, function, arg);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
207 position += LEFT_TOTAL_LENGTH (tree);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
208 tree->position = position;
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
209 (*function) (tree, arg);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
210 position += LENGTH (tree);
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
211 traverse_intervals (tree->right, position, depth + 1, function, arg);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
212 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
213
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
214 #if 0
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
215 /* These functions are temporary, for debugging purposes only. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
216
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
217 INTERVAL search_interval, found_interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
218
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
219 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
220 check_for_interval (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
221 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
222 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
223 if (i == search_interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
224 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
225 found_interval = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
226 icount++;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
227 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
228 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
229
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
230 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
231 search_for_interval (i, tree)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
232 register INTERVAL i, tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
233 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
234 icount = 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
235 search_interval = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
236 found_interval = NULL_INTERVAL;
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
237 traverse_intervals (tree, 1, 0, &check_for_interval, Qnil);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
238 return found_interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
239 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
240
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
241 static void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
242 inc_interval_count (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
243 INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
244 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
245 icount++;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
246 if (LENGTH (i) == 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
247 zero_length++;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
248 if (depth > idepth)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
249 idepth = depth;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
250 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
251
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
252 int
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
253 count_intervals (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
254 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
255 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
256 icount = 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
257 idepth = 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
258 zero_length = 0;
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
259 traverse_intervals (i, 1, 0, &inc_interval_count, Qnil);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
260
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
261 return icount;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
262 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
263
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
264 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
265 root_interval (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
266 INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
267 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
268 register INTERVAL i = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
269
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
270 while (! ROOT_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
271 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
272
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
273 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
274 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
275 #endif
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
276
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
277 /* Assuming that a left child exists, perform the following operation:
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
278
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
279 A B
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
280 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
281 B => A
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
282 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
283 c c
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
284 */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
285
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
286 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
287 rotate_right (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
288 INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
289 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
290 INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
291 INTERVAL B = interval->left;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
292 int old_total = interval->total_length;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
293
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
294 /* Deal with any Parent of A; make it point to B. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
295 if (! ROOT_INTERVAL_P (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
296 if (AM_LEFT_CHILD (interval))
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
297 interval->parent->left = B;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
298 else
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
299 interval->parent->right = B;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
300 B->parent = interval->parent;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
301
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
302 /* Make B the parent of A */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
303 i = B->right;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
304 B->right = interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
305 interval->parent = B;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
306
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
307 /* Make A point to c */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
308 interval->left = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
309 if (! NULL_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
310 i->parent = interval;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
311
5760
ffe89784cef2 (merge_properties_sticky): Preserve original order of properties.
Karl Heuer <kwzh@gnu.org>
parents: 5666
diff changeset
312 /* A's total length is decreased by the length of B and its left child. */
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
313 interval->total_length -= B->total_length - LEFT_TOTAL_LENGTH (interval);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
314
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
315 /* B must have the same total length of A. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
316 B->total_length = old_total;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
317
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
318 return B;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
319 }
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
320
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
321 /* Assuming that a right child exists, perform the following operation:
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
322
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
323 A B
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
324 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
325 B => A
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
326 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
327 c c
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
328 */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
329
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
330 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
331 rotate_left (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
332 INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
333 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
334 INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
335 INTERVAL B = interval->right;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
336 int old_total = interval->total_length;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
337
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
338 /* Deal with any parent of A; make it point to B. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
339 if (! ROOT_INTERVAL_P (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
340 if (AM_LEFT_CHILD (interval))
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
341 interval->parent->left = B;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
342 else
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
343 interval->parent->right = B;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
344 B->parent = interval->parent;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
345
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
346 /* Make B the parent of A */
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
347 i = B->left;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
348 B->left = interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
349 interval->parent = B;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
350
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
351 /* Make A point to c */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
352 interval->right = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
353 if (! NULL_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
354 i->parent = interval;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
355
5760
ffe89784cef2 (merge_properties_sticky): Preserve original order of properties.
Karl Heuer <kwzh@gnu.org>
parents: 5666
diff changeset
356 /* A's total length is decreased by the length of B and its right child. */
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
357 interval->total_length -= B->total_length - RIGHT_TOTAL_LENGTH (interval);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
358
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
359 /* B must have the same total length of A. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
360 B->total_length = old_total;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
361
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
362 return B;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
363 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
364
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
365 /* Balance an interval tree with the assumption that the subtrees
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
366 themselves are already balanced. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
367
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
368 static INTERVAL
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
369 balance_an_interval (i)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
370 INTERVAL i;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
371 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
372 register int old_diff, new_diff;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
373
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
374 while (1)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
375 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
376 old_diff = LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
377 if (old_diff > 0)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
378 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
379 new_diff = i->total_length - i->left->total_length
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
380 + RIGHT_TOTAL_LENGTH (i->left) - LEFT_TOTAL_LENGTH (i->left);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
381 if (abs (new_diff) >= old_diff)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
382 break;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
383 i = rotate_right (i);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
384 balance_an_interval (i->right);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
385 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
386 else if (old_diff < 0)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
387 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
388 new_diff = i->total_length - i->right->total_length
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
389 + LEFT_TOTAL_LENGTH (i->right) - RIGHT_TOTAL_LENGTH (i->right);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
390 if (abs (new_diff) >= -old_diff)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
391 break;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
392 i = rotate_left (i);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
393 balance_an_interval (i->left);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
394 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
395 else
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
396 break;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
397 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
398 return i;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
399 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
400
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
401 /* Balance INTERVAL, potentially stuffing it back into its parent
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
402 Lisp Object. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
403
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
404 static INLINE INTERVAL
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
405 balance_possible_root_interval (interval)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
406 register INTERVAL interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
407 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
408 Lisp_Object parent;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
409
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
410 if (interval->parent == NULL_INTERVAL)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
411 return interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
412
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
413 parent = (Lisp_Object) (interval->parent);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
414 interval = balance_an_interval (interval);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
415
9125
a78f02f76f03 (create_root_interval, balance_possible_root_interval, delete_interval): Use
Karl Heuer <kwzh@gnu.org>
parents: 9072
diff changeset
416 if (BUFFERP (parent))
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
417 BUF_INTERVALS (XBUFFER (parent)) = interval;
9125
a78f02f76f03 (create_root_interval, balance_possible_root_interval, delete_interval): Use
Karl Heuer <kwzh@gnu.org>
parents: 9072
diff changeset
418 else if (STRINGP (parent))
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
419 XSTRING (parent)->intervals = interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
420
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
421 return interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
422 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
423
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
424 /* Balance the interval tree TREE. Balancing is by weight
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
425 (the amount of text). */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
426
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
427 static INTERVAL
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
428 balance_intervals_internal (tree)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
429 register INTERVAL tree;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
430 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
431 /* Balance within each side. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
432 if (tree->left)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
433 balance_intervals (tree->left);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
434 if (tree->right)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
435 balance_intervals (tree->right);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
436 return balance_an_interval (tree);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
437 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
438
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
439 /* Advertised interface to balance intervals. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
440
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
441 INTERVAL
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
442 balance_intervals (tree)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
443 INTERVAL tree;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
444 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
445 if (tree == NULL_INTERVAL)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
446 return NULL_INTERVAL;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
447
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
448 return balance_intervals_internal (tree);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
449 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
450
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
451 /* Split INTERVAL into two pieces, starting the second piece at
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
452 character position OFFSET (counting from 0), relative to INTERVAL.
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
453 INTERVAL becomes the left-hand piece, and the right-hand piece
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
454 (second, lexicographically) is returned.
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
455
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
456 The size and position fields of the two intervals are set based upon
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
457 those of the original interval. The property list of the new interval
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
458 is reset, thus it is up to the caller to do the right thing with the
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
459 result.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
460
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
461 Note that this does not change the position of INTERVAL; if it is a root,
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
462 it is still a root after this operation. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
463
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
464 INTERVAL
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
465 split_interval_right (interval, offset)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
466 INTERVAL interval;
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
467 int offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
468 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
469 INTERVAL new = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
470 int position = interval->position;
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
471 int new_length = LENGTH (interval) - offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
472
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
473 new->position = position + offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
474 new->parent = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
475
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
476 if (NULL_RIGHT_CHILD (interval))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
477 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
478 interval->right = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
479 new->total_length = new_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
480
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
481 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
482 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
483
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
484 /* Insert the new node between INTERVAL and its right child. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
485 new->right = interval->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
486 interval->right->parent = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
487 interval->right = new;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
488 new->total_length = new_length + new->right->total_length;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
489
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
490 balance_an_interval (new);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
491 balance_possible_root_interval (interval);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
492
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
493 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
494 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
495
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
496 /* Split INTERVAL into two pieces, starting the second piece at
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
497 character position OFFSET (counting from 0), relative to INTERVAL.
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
498 INTERVAL becomes the right-hand piece, and the left-hand piece
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
499 (first, lexicographically) is returned.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
500
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
501 The size and position fields of the two intervals are set based upon
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
502 those of the original interval. The property list of the new interval
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
503 is reset, thus it is up to the caller to do the right thing with the
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
504 result.
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
505
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
506 Note that this does not change the position of INTERVAL; if it is a root,
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
507 it is still a root after this operation. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
508
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
509 INTERVAL
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
510 split_interval_left (interval, offset)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
511 INTERVAL interval;
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
512 int offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
513 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
514 INTERVAL new = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
515 int position = interval->position;
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
516 int new_length = offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
517
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
518 new->position = interval->position;
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
519 interval->position = interval->position + offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
520 new->parent = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
521
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
522 if (NULL_LEFT_CHILD (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
523 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
524 interval->left = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
525 new->total_length = new_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
526
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
527 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
528 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
529
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
530 /* Insert the new node between INTERVAL and its left child. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
531 new->left = interval->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
532 new->left->parent = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
533 interval->left = new;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
534 new->total_length = new_length + new->left->total_length;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
535
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
536 balance_an_interval (new);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
537 balance_possible_root_interval (interval);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
538
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
539 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
540 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
541
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
542 /* Find the interval containing text position POSITION in the text
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
543 represented by the interval tree TREE. POSITION is a buffer
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
544 position; the earliest position is 1. If POSITION is at the end of
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
545 the buffer, return the interval containing the last character.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
546
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
547 The `position' field, which is a cache of an interval's position,
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
548 is updated in the interval found. Other functions (e.g., next_interval)
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
549 will update this cache based on the result of find_interval. */
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
550
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
551 INLINE INTERVAL
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
552 find_interval (tree, position)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
553 register INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
554 register int position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
555 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
556 /* The distance from the left edge of the subtree at TREE
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
557 to POSITION. */
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
558 register int relative_position = position - BEG;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
559
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
560 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
561 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
562
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
563 if (relative_position > TOTAL_LENGTH (tree))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
564 abort (); /* Paranoia */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
565
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
566 tree = balance_possible_root_interval (tree);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
567
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
568 while (1)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
569 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
570 if (relative_position < LEFT_TOTAL_LENGTH (tree))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
571 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
572 tree = tree->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
573 }
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
574 else if (! NULL_RIGHT_CHILD (tree)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
575 && relative_position >= (TOTAL_LENGTH (tree)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
576 - RIGHT_TOTAL_LENGTH (tree)))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
577 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
578 relative_position -= (TOTAL_LENGTH (tree)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
579 - RIGHT_TOTAL_LENGTH (tree));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
580 tree = tree->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
581 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
582 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
583 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
584 tree->position =
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
585 (position - relative_position /* the left edge of *tree */
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
586 + LEFT_TOTAL_LENGTH (tree)); /* the left edge of this interval */
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
587
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
588 return tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
589 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
590 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
591 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
592
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
593 /* Find the succeeding interval (lexicographically) to INTERVAL.
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
594 Sets the `position' field based on that of INTERVAL (see
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
595 find_interval). */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
596
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
597 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
598 next_interval (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
599 register INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
600 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
601 register INTERVAL i = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
602 register int next_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
603
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
604 if (NULL_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
605 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
606 next_position = interval->position + LENGTH (interval);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
607
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
608 if (! NULL_RIGHT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
609 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
610 i = i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
611 while (! NULL_LEFT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
612 i = i->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
613
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
614 i->position = next_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
615 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
616 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
617
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
618 while (! NULL_PARENT (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
619 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
620 if (AM_LEFT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
621 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
622 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
623 i->position = next_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
624 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
625 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
626
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
627 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
628 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
629
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
630 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
631 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
632
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
633 /* Find the preceding interval (lexicographically) to INTERVAL.
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
634 Sets the `position' field based on that of INTERVAL (see
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
635 find_interval). */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
636
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
637 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
638 previous_interval (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
639 register INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
640 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
641 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
642 register position_of_previous;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
643
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
644 if (NULL_INTERVAL_P (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
645 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
646
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
647 if (! NULL_LEFT_CHILD (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
648 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
649 i = interval->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
650 while (! NULL_RIGHT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
651 i = i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
652
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
653 i->position = interval->position - LENGTH (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
654 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
655 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
656
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
657 i = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
658 while (! NULL_PARENT (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
659 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
660 if (AM_RIGHT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
661 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
662 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
663
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
664 i->position = interval->position - LENGTH (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
665 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
666 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
667 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
668 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
669
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
670 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
671 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
672
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
673 #if 0
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
674 /* Traverse a path down the interval tree TREE to the interval
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
675 containing POSITION, adjusting all nodes on the path for
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
676 an addition of LENGTH characters. Insertion between two intervals
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
677 (i.e., point == i->position, where i is second interval) means
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
678 text goes into second interval.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
679
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
680 Modifications are needed to handle the hungry bits -- after simply
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
681 finding the interval at position (don't add length going down),
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
682 if it's the beginning of the interval, get the previous interval
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
683 and check the hugry bits of both. Then add the length going back up
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
684 to the root. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
685
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
686 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
687 adjust_intervals_for_insertion (tree, position, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
688 INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
689 int position, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
690 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
691 register int relative_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
692 register INTERVAL this;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
693
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
694 if (TOTAL_LENGTH (tree) == 0) /* Paranoia */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
695 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
696
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
697 /* If inserting at point-max of a buffer, that position
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
698 will be out of range */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
699 if (position > TOTAL_LENGTH (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
700 position = TOTAL_LENGTH (tree);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
701 relative_position = position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
702 this = tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
703
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
704 while (1)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
705 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
706 if (relative_position <= LEFT_TOTAL_LENGTH (this))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
707 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
708 this->total_length += length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
709 this = this->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
710 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
711 else if (relative_position > (TOTAL_LENGTH (this)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
712 - RIGHT_TOTAL_LENGTH (this)))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
713 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
714 relative_position -= (TOTAL_LENGTH (this)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
715 - RIGHT_TOTAL_LENGTH (this));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
716 this->total_length += length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
717 this = this->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
718 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
719 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
720 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
721 /* If we are to use zero-length intervals as buffer pointers,
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
722 then this code will have to change. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
723 this->total_length += length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
724 this->position = LEFT_TOTAL_LENGTH (this)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
725 + position - relative_position + 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
726 return tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
727 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
728 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
729 }
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
730 #endif
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
731
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
732 /* Effect an adjustment corresponding to the addition of LENGTH characters
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
733 of text. Do this by finding the interval containing POSITION in the
5760
ffe89784cef2 (merge_properties_sticky): Preserve original order of properties.
Karl Heuer <kwzh@gnu.org>
parents: 5666
diff changeset
734 interval tree TREE, and then adjusting all of its ancestors by adding
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
735 LENGTH to them.
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
736
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
737 If POSITION is the first character of an interval, meaning that point
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
738 is actually between the two intervals, make the new text belong to
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
739 the interval which is "sticky".
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
740
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
741 If both intervals are "sticky", then make them belong to the left-most
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
742 interval. Another possibility would be to create a new interval for
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
743 this text, and make it have the merged properties of both ends. */
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
744
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
745 static INTERVAL
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
746 adjust_intervals_for_insertion (tree, position, length)
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
747 INTERVAL tree;
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
748 int position, length;
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
749 {
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
750 register INTERVAL i;
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
751 register INTERVAL temp;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
752 int eobp = 0;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
753
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
754 if (TOTAL_LENGTH (tree) == 0) /* Paranoia */
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
755 abort ();
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
756
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
757 /* If inserting at point-max of a buffer, that position will be out
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
758 of range. Remember that buffer positions are 1-based. */
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
759 if (position >= BEG + TOTAL_LENGTH (tree)){
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
760 position = BEG + TOTAL_LENGTH (tree);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
761 eobp = 1;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
762 }
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
763
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
764 i = find_interval (tree, position);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
765
4638
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
766 /* If in middle of an interval which is not sticky either way,
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
767 we must not just give its properties to the insertion.
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
768 So split this interval at the insertion point. */
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
769 if (! (position == i->position || eobp)
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
770 && END_NONSTICKY_P (i)
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
771 && ! FRONT_STICKY_P (i))
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
772 {
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
773 temp = split_interval_right (i, position - i->position);
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
774 copy_properties (i, temp);
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
775 i = temp;
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
776 }
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
777
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
778 /* If we are positioned between intervals, check the stickiness of
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
779 both of them. We have to do this too, if we are at BEG or Z. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
780 if (position == i->position || eobp)
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
781 {
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
782 register INTERVAL prev;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
783
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
784 if (position == BEG)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
785 prev = 0;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
786 else if (eobp)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
787 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
788 prev = i;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
789 i = 0;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
790 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
791 else
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
792 prev = previous_interval (i);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
793
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
794 /* Even if we are positioned between intervals, we default
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
795 to the left one if it exists. We extend it now and split
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
796 off a part later, if stickyness demands it. */
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
797 for (temp = prev ? prev : i;! NULL_INTERVAL_P (temp); temp = temp->parent)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
798 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
799 temp->total_length += length;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
800 temp = balance_possible_root_interval (temp);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
801 }
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
802
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
803 /* If at least one interval has sticky properties,
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
804 we check the stickyness property by property. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
805 if (END_NONSTICKY_P (prev) || FRONT_STICKY_P (i))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
806 {
6501
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
807 Lisp_Object pleft, pright;
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
808 struct interval newi;
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
809
6501
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
810 pleft = NULL_INTERVAL_P (prev) ? Qnil : prev->plist;
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
811 pright = NULL_INTERVAL_P (i) ? Qnil : i->plist;
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
812 newi.plist = merge_properties_sticky (pleft, pright);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
813
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
814 if(! prev) /* i.e. position == BEG */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
815 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
816 if (! intervals_equal (i, &newi))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
817 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
818 i = split_interval_left (i, length);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
819 i->plist = newi.plist;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
820 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
821 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
822 else if (! intervals_equal (prev, &newi))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
823 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
824 prev = split_interval_right (prev,
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
825 position - prev->position);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
826 prev->plist = newi.plist;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
827 if (! NULL_INTERVAL_P (i)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
828 && intervals_equal (prev, i))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
829 merge_interval_right (prev);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
830 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
831
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
832 /* We will need to update the cache here later. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
833 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
834 else if (! prev && ! NILP (i->plist))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
835 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
836 /* Just split off a new interval at the left.
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
837 Since I wasn't front-sticky, the empty plist is ok. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
838 i = split_interval_left (i, length);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
839 }
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
840 }
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
841
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
842 /* Otherwise just extend the interval. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
843 else
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
844 {
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
845 for (temp = i; ! NULL_INTERVAL_P (temp); temp = temp->parent)
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
846 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
847 temp->total_length += length;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
848 temp = balance_possible_root_interval (temp);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
849 }
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
850 }
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
851
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
852 return tree;
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
853 }
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
854
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
855 /* Any property might be front-sticky on the left, rear-sticky on the left,
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
856 front-sticky on the right, or rear-sticky on the right; the 16 combinations
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
857 can be arranged in a matrix with rows denoting the left conditions and
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
858 columns denoting the right conditions:
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
859 _ __ _
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
860 _ FR FR FR FR
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
861 FR__ 0 1 2 3
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
862 _FR 4 5 6 7
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
863 FR 8 9 A B
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
864 FR C D E F
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
865
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
866 left-props = '(front-sticky (p8 p9 pa pb pc pd pe pf)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
867 rear-nonsticky (p4 p5 p6 p7 p8 p9 pa pb)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
868 p0 L p1 L p2 L p3 L p4 L p5 L p6 L p7 L
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
869 p8 L p9 L pa L pb L pc L pd L pe L pf L)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
870 right-props = '(front-sticky (p2 p3 p6 p7 pa pb pe pf)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
871 rear-nonsticky (p1 p2 p5 p6 p9 pa pd pe)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
872 p0 R p1 R p2 R p3 R p4 R p5 R p6 R p7 R
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
873 p8 R p9 R pa R pb R pc R pd R pe R pf R)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
874
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
875 We inherit from whoever has a sticky side facing us. If both sides
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
876 do (cases 2, 3, E, and F), then we inherit from whichever side has a
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
877 non-nil value for the current property. If both sides do, then we take
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
878 from the left.
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
879
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
880 When we inherit a property, we get its stickiness as well as its value.
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
881 So, when we merge the above two lists, we expect to get this:
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
882
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
883 result = '(front-sticky (p6 p7 pa pb pc pd pe pf)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
884 rear-nonsticky (p6 pa)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
885 p0 L p1 L p2 L p3 L p6 R p7 R
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
886 pa R pb R pc L pd L pe L pf L)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
887
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
888 The optimizable special cases are:
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
889 left rear-nonsticky = nil, right front-sticky = nil (inherit left)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
890 left rear-nonsticky = t, right front-sticky = t (inherit right)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
891 left rear-nonsticky = t, right front-sticky = nil (inherit none)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
892 */
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
893
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
894 Lisp_Object
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
895 merge_properties_sticky (pleft, pright)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
896 Lisp_Object pleft, pright;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
897 {
6501
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
898 register Lisp_Object props, front, rear;
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
899 Lisp_Object lfront, lrear, rfront, rrear;
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
900 register Lisp_Object tail1, tail2, sym, lval, rval;
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
901 int use_left, use_right;
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
902
6501
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
903 props = Qnil;
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
904 front = Qnil;
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
905 rear = Qnil;
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
906 lfront = textget (pleft, Qfront_sticky);
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
907 lrear = textget (pleft, Qrear_nonsticky);
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
908 rfront = textget (pright, Qfront_sticky);
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
909 rrear = textget (pright, Qrear_nonsticky);
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
910
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
911 /* Go through each element of PRIGHT. */
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
912 for (tail1 = pright; ! NILP (tail1); tail1 = Fcdr (Fcdr (tail1)))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
913 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
914 sym = Fcar (tail1);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
915
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
916 /* Sticky properties get special treatment. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
917 if (EQ (sym, Qrear_nonsticky) || EQ (sym, Qfront_sticky))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
918 continue;
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
919
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
920 rval = Fcar (Fcdr (tail1));
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
921 for (tail2 = pleft; ! NILP (tail2); tail2 = Fcdr (Fcdr (tail2)))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
922 if (EQ (sym, Fcar (tail2)))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
923 break;
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
924 lval = (NILP (tail2) ? Qnil : Fcar( Fcdr (tail2)));
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
925
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
926 use_left = ! TMEM (sym, lrear);
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
927 use_right = TMEM (sym, rfront);
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
928 if (use_left && use_right)
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
929 {
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
930 use_left = ! NILP (lval);
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
931 use_right = ! NILP (rval);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
932 }
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
933 if (use_left)
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
934 {
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
935 /* We build props as (value sym ...) rather than (sym value ...)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
936 because we plan to nreverse it when we're done. */
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
937 if (! NILP (lval))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
938 props = Fcons (lval, Fcons (sym, props));
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
939 if (TMEM (sym, lfront))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
940 front = Fcons (sym, front);
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
941 if (TMEM (sym, lrear))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
942 rear = Fcons (sym, rear);
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
943 }
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
944 else if (use_right)
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
945 {
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
946 if (! NILP (rval))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
947 props = Fcons (rval, Fcons (sym, props));
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
948 if (TMEM (sym, rfront))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
949 front = Fcons (sym, front);
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
950 if (TMEM (sym, rrear))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
951 rear = Fcons (sym, rear);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
952 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
953 }
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
954
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
955 /* Now go through each element of PLEFT. */
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
956 for (tail2 = pleft; ! NILP (tail2); tail2 = Fcdr (Fcdr (tail2)))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
957 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
958 sym = Fcar (tail2);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
959
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
960 /* Sticky properties get special treatment. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
961 if (EQ (sym, Qrear_nonsticky) || EQ (sym, Qfront_sticky))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
962 continue;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
963
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
964 /* If sym is in PRIGHT, we've already considered it. */
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
965 for (tail1 = pright; ! NILP (tail1); tail1 = Fcdr (Fcdr (tail1)))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
966 if (EQ (sym, Fcar (tail1)))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
967 break;
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
968 if (! NILP (tail1))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
969 continue;
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
970
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
971 lval = Fcar (Fcdr (tail2));
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
972
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
973 /* Since rval is known to be nil in this loop, the test simplifies. */
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
974 if (! TMEM (sym, lrear))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
975 {
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
976 if (! NILP (lval))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
977 props = Fcons (lval, Fcons (sym, props));
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
978 if (TMEM (sym, lfront))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
979 front = Fcons (sym, front);
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
980 }
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
981 else if (TMEM (sym, rfront))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
982 {
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
983 /* The value is nil, but we still inherit the stickiness
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
984 from the right. */
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
985 front = Fcons (sym, front);
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
986 if (TMEM (sym, rrear))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
987 rear = Fcons (sym, rear);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
988 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
989 }
5760
ffe89784cef2 (merge_properties_sticky): Preserve original order of properties.
Karl Heuer <kwzh@gnu.org>
parents: 5666
diff changeset
990 props = Fnreverse (props);
5768
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
991 if (! NILP (rear))
ab11e2af95ef Add comments describing the rules used by the merge algorithm.
Karl Heuer <kwzh@gnu.org>
parents: 5760
diff changeset
992 props = Fcons (Qrear_nonsticky, Fcons (Fnreverse (rear), props));
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
993 if (! NILP (front))
5760
ffe89784cef2 (merge_properties_sticky): Preserve original order of properties.
Karl Heuer <kwzh@gnu.org>
parents: 5666
diff changeset
994 props = Fcons (Qfront_sticky, Fcons (Fnreverse (front), props));
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
995 return props;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
996 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
997
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
998
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
999 /* Delete an node I from its interval tree by merging its subtrees
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
1000 into one subtree which is then returned. Caller is responsible for
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1001 storing the resulting subtree into its parent. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1002
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1003 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1004 delete_node (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1005 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1006 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1007 register INTERVAL migrate, this;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1008 register int migrate_amt;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1009
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1010 if (NULL_INTERVAL_P (i->left))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1011 return i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1012 if (NULL_INTERVAL_P (i->right))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1013 return i->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1014
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1015 migrate = i->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1016 migrate_amt = i->left->total_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1017 this = i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1018 this->total_length += migrate_amt;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1019 while (! NULL_INTERVAL_P (this->left))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1020 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1021 this = this->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1022 this->total_length += migrate_amt;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1023 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1024 this->left = migrate;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1025 migrate->parent = this;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1026
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1027 return i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1028 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1029
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1030 /* Delete interval I from its tree by calling `delete_node'
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1031 and properly connecting the resultant subtree.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1032
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1033 I is presumed to be empty; that is, no adjustments are made
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1034 for the length of I. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1035
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1036 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1037 delete_interval (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1038 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1039 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1040 register INTERVAL parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1041 int amt = LENGTH (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1042
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1043 if (amt > 0) /* Only used on zero-length intervals now. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1044 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1045
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1046 if (ROOT_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1047 {
6501
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
1048 Lisp_Object owner;
d7ac9a417f87 (adjust_intervals_for_insertion, merge_properties_sticky, delete_interval):
Karl Heuer <kwzh@gnu.org>
parents: 5780
diff changeset
1049 owner = (Lisp_Object) i->parent;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1050 parent = delete_node (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1051 if (! NULL_INTERVAL_P (parent))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1052 parent->parent = (INTERVAL) owner;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1053
9125
a78f02f76f03 (create_root_interval, balance_possible_root_interval, delete_interval): Use
Karl Heuer <kwzh@gnu.org>
parents: 9072
diff changeset
1054 if (BUFFERP (owner))
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1055 BUF_INTERVALS (XBUFFER (owner)) = parent;
9125
a78f02f76f03 (create_root_interval, balance_possible_root_interval, delete_interval): Use
Karl Heuer <kwzh@gnu.org>
parents: 9072
diff changeset
1056 else if (STRINGP (owner))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1057 XSTRING (owner)->intervals = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1058 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1059 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1060
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1061 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1062 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1063
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1064 parent = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1065 if (AM_LEFT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1066 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1067 parent->left = delete_node (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1068 if (! NULL_INTERVAL_P (parent->left))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1069 parent->left->parent = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1070 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1071 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1072 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1073 parent->right = delete_node (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1074 if (! NULL_INTERVAL_P (parent->right))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1075 parent->right->parent = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1076 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1077 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1078
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1079 /* Find the interval in TREE corresponding to the relative position
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1080 FROM and delete as much as possible of AMOUNT from that interval.
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1081 Return the amount actually deleted, and if the interval was
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1082 zeroed-out, delete that interval node from the tree.
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1083
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1084 Note that FROM is actually origin zero, aka relative to the
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1085 leftmost edge of tree. This is appropriate since we call ourselves
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1086 recursively on subtrees.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1087
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1088 Do this by recursing down TREE to the interval in question, and
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1089 deleting the appropriate amount of text. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1090
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1091 static int
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1092 interval_deletion_adjustment (tree, from, amount)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1093 register INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1094 register int from, amount;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1095 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1096 register int relative_position = from;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1097
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1098 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1099 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1100
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1101 /* Left branch */
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1102 if (relative_position < LEFT_TOTAL_LENGTH (tree))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1103 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1104 int subtract = interval_deletion_adjustment (tree->left,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1105 relative_position,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1106 amount);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1107 tree->total_length -= subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1108 return subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1109 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1110 /* Right branch */
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1111 else if (relative_position >= (TOTAL_LENGTH (tree)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1112 - RIGHT_TOTAL_LENGTH (tree)))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1113 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1114 int subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1115
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1116 relative_position -= (tree->total_length
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1117 - RIGHT_TOTAL_LENGTH (tree));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1118 subtract = interval_deletion_adjustment (tree->right,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1119 relative_position,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1120 amount);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1121 tree->total_length -= subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1122 return subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1123 }
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1124 /* Here -- this node. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1125 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1126 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1127 /* How much can we delete from this interval? */
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1128 int my_amount = ((tree->total_length
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1129 - RIGHT_TOTAL_LENGTH (tree))
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1130 - relative_position);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1131
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1132 if (amount > my_amount)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1133 amount = my_amount;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1134
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1135 tree->total_length -= amount;
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1136 if (LENGTH (tree) == 0)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1137 delete_interval (tree);
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1138
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1139 return amount;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1140 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1141
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1142 /* Never reach here. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1143 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1144
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1145 /* Effect the adjustments necessary to the interval tree of BUFFER to
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1146 correspond to the deletion of LENGTH characters from that buffer
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1147 text. The deletion is effected at position START (which is a
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1148 buffer position, i.e. origin 1). */
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1149
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1150 static void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1151 adjust_intervals_for_deletion (buffer, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1152 struct buffer *buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1153 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1154 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1155 register int left_to_delete = length;
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1156 register INTERVAL tree = BUF_INTERVALS (buffer);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1157 register int deleted;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1158
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1159 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1160 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1161
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1162 if (start > BEG + TOTAL_LENGTH (tree)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1163 || start + length > BEG + TOTAL_LENGTH (tree))
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1164 abort ();
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1165
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1166 if (length == TOTAL_LENGTH (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1167 {
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1168 BUF_INTERVALS (buffer) = NULL_INTERVAL;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1169 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1170 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1171
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1172 if (ONLY_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1173 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1174 tree->total_length -= length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1175 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1176 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1177
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1178 if (start > BEG + TOTAL_LENGTH (tree))
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1179 start = BEG + TOTAL_LENGTH (tree);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1180 while (left_to_delete > 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1181 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1182 left_to_delete -= interval_deletion_adjustment (tree, start - 1,
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1183 left_to_delete);
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1184 tree = BUF_INTERVALS (buffer);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1185 if (left_to_delete == tree->total_length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1186 {
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1187 BUF_INTERVALS (buffer) = NULL_INTERVAL;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1188 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1189 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1190 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1191 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1192
3591
507f64624555 Apply typo patches from Paul Eggert.
Jim Blandy <jimb@redhat.com>
parents: 3490
diff changeset
1193 /* Make the adjustments necessary to the interval tree of BUFFER to
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1194 represent an addition or deletion of LENGTH characters starting
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1195 at position START. Addition or deletion is indicated by the sign
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1196 of LENGTH. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1197
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1198 INLINE void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1199 offset_intervals (buffer, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1200 struct buffer *buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1201 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1202 {
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1203 if (NULL_INTERVAL_P (BUF_INTERVALS (buffer)) || length == 0)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1204 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1205
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1206 if (length > 0)
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1207 adjust_intervals_for_insertion (BUF_INTERVALS (buffer), start, length);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1208 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1209 adjust_intervals_for_deletion (buffer, start, -length);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1210 }
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1212 /* Merge interval I with its lexicographic successor. The resulting
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1213 interval is returned, and has the properties of the original
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1214 successor. The properties of I are lost. I is removed from the
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1215 interval tree.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1216
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1217 IMPORTANT:
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1218 The caller must verify that this is not the last (rightmost)
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1219 interval. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1220
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1221 INTERVAL
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1222 merge_interval_right (i)
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1223 register INTERVAL i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1224 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1225 register int absorb = LENGTH (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1226 register INTERVAL successor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1227
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1228 /* Zero out this interval. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1229 i->total_length -= absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1230
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1231 /* Find the succeeding interval. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1232 if (! NULL_RIGHT_CHILD (i)) /* It's below us. Add absorb
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1233 as we descend. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1234 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1235 successor = i->right;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1236 while (! NULL_LEFT_CHILD (successor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1237 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1238 successor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1239 successor = successor->left;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1240 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1241
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1242 successor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1243 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1244 return successor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1245 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1246
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1247 successor = i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1248 while (! NULL_PARENT (successor)) /* It's above us. Subtract as
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1249 we ascend. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1250 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1251 if (AM_LEFT_CHILD (successor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1252 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1253 successor = successor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1254 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1255 return successor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1256 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1257
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1258 successor = successor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1259 successor->total_length -= absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1260 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1261
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1262 /* This must be the rightmost or last interval and cannot
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1263 be merged right. The caller should have known. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1264 abort ();
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1265 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1266
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1267 /* Merge interval I with its lexicographic predecessor. The resulting
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1268 interval is returned, and has the properties of the original predecessor.
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1269 The properties of I are lost. Interval node I is removed from the tree.
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1270
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1271 IMPORTANT:
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1272 The caller must verify that this is not the first (leftmost) interval. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1273
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1274 INTERVAL
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1275 merge_interval_left (i)
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1276 register INTERVAL i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1277 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1278 register int absorb = LENGTH (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1279 register INTERVAL predecessor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1280
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1281 /* Zero out this interval. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1282 i->total_length -= absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1283
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1284 /* Find the preceding interval. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1285 if (! NULL_LEFT_CHILD (i)) /* It's below us. Go down,
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1286 adding ABSORB as we go. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1287 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1288 predecessor = i->left;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1289 while (! NULL_RIGHT_CHILD (predecessor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1290 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1291 predecessor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1292 predecessor = predecessor->right;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1293 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1294
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1295 predecessor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1296 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1297 return predecessor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1298 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1299
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1300 predecessor = i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1301 while (! NULL_PARENT (predecessor)) /* It's above us. Go up,
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1302 subtracting ABSORB. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1303 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1304 if (AM_RIGHT_CHILD (predecessor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1305 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1306 predecessor = predecessor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1307 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1308 return predecessor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1309 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1310
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1311 predecessor = predecessor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1312 predecessor->total_length -= absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1313 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1314
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1315 /* This must be the leftmost or first interval and cannot
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1316 be merged left. The caller should have known. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1317 abort ();
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1318 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1319
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1320 /* Make an exact copy of interval tree SOURCE which descends from
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1321 PARENT. This is done by recursing through SOURCE, copying
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1322 the current interval and its properties, and then adjusting
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1323 the pointers of the copy. */
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1324
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1325 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1326 reproduce_tree (source, parent)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1327 INTERVAL source, parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1328 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1329 register INTERVAL t = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1330
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1331 bcopy (source, t, INTERVAL_SIZE);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1332 copy_properties (source, t);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1333 t->parent = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1334 if (! NULL_LEFT_CHILD (source))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1335 t->left = reproduce_tree (source->left, t);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1336 if (! NULL_RIGHT_CHILD (source))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1337 t->right = reproduce_tree (source->right, t);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1338
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1339 return t;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1340 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1341
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1342 #if 0
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1343 /* Nobody calls this. Perhaps it's a vestige of an earlier design. */
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1344
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1345 /* Make a new interval of length LENGTH starting at START in the
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1346 group of intervals INTERVALS, which is actually an interval tree.
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1347 Returns the new interval.
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1348
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1349 Generate an error if the new positions would overlap an existing
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1350 interval. */
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1351
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1352 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1353 make_new_interval (intervals, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1354 INTERVAL intervals;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1355 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1356 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1357 INTERVAL slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1358
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1359 slot = find_interval (intervals, start);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1360 if (start + length > slot->position + LENGTH (slot))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1361 error ("Interval would overlap");
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1362
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1363 if (start == slot->position && length == LENGTH (slot))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1364 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1365
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1366 if (slot->position == start)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1367 {
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1368 /* New right node. */
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1369 split_interval_right (slot, length);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1370 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1371 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1372
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1373 if (slot->position + LENGTH (slot) == start + length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1374 {
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1375 /* New left node. */
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1376 split_interval_left (slot, LENGTH (slot) - length);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1377 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1378 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1379
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1380 /* Convert interval SLOT into three intervals. */
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1381 split_interval_left (slot, start - slot->position);
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1382 split_interval_right (slot, length);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1383 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1384 }
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1385 #endif
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1386
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1387 /* Insert the intervals of SOURCE into BUFFER at POSITION.
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1388 LENGTH is the length of the text in SOURCE.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1389
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1390 This is used in insdel.c when inserting Lisp_Strings into the
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1391 buffer. The text corresponding to SOURCE is already in the buffer
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1392 when this is called. The intervals of new tree are a copy of those
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1393 belonging to the string being inserted; intervals are never
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1394 shared.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1395
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1396 If the inserted text had no intervals associated, and we don't
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1397 want to inherit the surrounding text's properties, this function
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1398 simply returns -- offset_intervals should handle placing the
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
1399 text in the correct interval, depending on the sticky bits.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1400
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1401 If the inserted text had properties (intervals), then there are two
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1402 cases -- either insertion happened in the middle of some interval,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1403 or between two intervals.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1404
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1405 If the text goes into the middle of an interval, then new
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1406 intervals are created in the middle with only the properties of
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1407 the new text, *unless* the macro MERGE_INSERTIONS is true, in
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1408 which case the new text has the union of its properties and those
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1409 of the text into which it was inserted.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1410
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1411 If the text goes between two intervals, then if neither interval
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
1412 had its appropriate sticky property set (front_sticky, rear_sticky),
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
1413 the new text has only its properties. If one of the sticky properties
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1414 is set, then the new text "sticks" to that region and its properties
3591
507f64624555 Apply typo patches from Paul Eggert.
Jim Blandy <jimb@redhat.com>
parents: 3490
diff changeset
1415 depend on merging as above. If both the preceding and succeeding
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
1416 intervals to the new text are "sticky", then the new text retains
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
1417 only its properties, as if neither sticky property were set. Perhaps
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1418 we should consider merging all three sets of properties onto the new
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1419 text... */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1420
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1421 void
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1422 graft_intervals_into_buffer (source, position, length, buffer, inherit)
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1423 INTERVAL source;
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1424 int position, length;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1425 struct buffer *buffer;
4718
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1426 int inherit;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1427 {
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1428 register INTERVAL under, over, this, prev;
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1429 register INTERVAL tree;
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1430 int middle;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1431
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1432 tree = BUF_INTERVALS (buffer);
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1433
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1434 /* If the new text has no properties, it becomes part of whatever
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1435 interval it was inserted into. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1436 if (NULL_INTERVAL_P (source))
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1437 {
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1438 Lisp_Object buf;
5250
63a865489a1e (graft_intervals_into_buffer): If SOURCE is null
Richard M. Stallman <rms@gnu.org>
parents: 5173
diff changeset
1439 if (!inherit && ! NULL_INTERVAL_P (tree))
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1440 {
9271
1971a6a8cdc0 (graft_intervals_into_buffer): Use new accessor macros instead of calling XSET
Karl Heuer <kwzh@gnu.org>
parents: 9125
diff changeset
1441 XSETBUFFER (buf, buffer);
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1442 Fset_text_properties (make_number (position),
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1443 make_number (position + length),
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1444 Qnil, buf);
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1445 }
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1446 if (! NULL_INTERVAL_P (BUF_INTERVALS (buffer)))
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1447 BUF_INTERVALS (buffer) = balance_an_interval (BUF_INTERVALS (buffer));
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1448 return;
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1449 }
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1450
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1451 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1452 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1453 /* The inserted text constitutes the whole buffer, so
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1454 simply copy over the interval structure. */
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1455 if ((BUF_Z (buffer) - BUF_BEG (buffer)) == TOTAL_LENGTH (source))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1456 {
4223
b044f6d3c4cb (graft_intervals_into_buffer): When TREE is null,
Richard M. Stallman <rms@gnu.org>
parents: 4135
diff changeset
1457 Lisp_Object buf;
9271
1971a6a8cdc0 (graft_intervals_into_buffer): Use new accessor macros instead of calling XSET
Karl Heuer <kwzh@gnu.org>
parents: 9125
diff changeset
1458 XSETBUFFER (buf, buffer);
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1459 BUF_INTERVALS (buffer) = reproduce_tree (source, buf);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1460 /* Explicitly free the old tree here. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1461
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1462 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1463 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1464
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1465 /* Create an interval tree in which to place a copy
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1466 of the intervals of the inserted string. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1467 {
1307
b469633740b3 Fixed typos.
Joseph Arceneaux <jla@gnu.org>
parents: 1303
diff changeset
1468 Lisp_Object buf;
9271
1971a6a8cdc0 (graft_intervals_into_buffer): Use new accessor macros instead of calling XSET
Karl Heuer <kwzh@gnu.org>
parents: 9125
diff changeset
1469 XSETBUFFER (buf, buffer);
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1470 tree = create_root_interval (buf);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1471 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1472 }
4718
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1473 else if (TOTAL_LENGTH (tree) == TOTAL_LENGTH (source))
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1474 /* If the buffer contains only the new string, but
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1475 there was already some interval tree there, then it may be
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1476 some zero length intervals. Eventually, do something clever
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1477 about inserting properly. For now, just waste the old intervals. */
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1478 {
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1479 BUF_INTERVALS (buffer) = reproduce_tree (source, tree->parent);
4718
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1480 /* Explicitly free the old tree here. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1481
4718
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1482 return;
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1483 }
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1484 /* Paranoia -- the text has already been added, so this buffer
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1485 should be of non-zero length. */
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1486 else if (TOTAL_LENGTH (tree) == 0)
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1487 abort ();
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1488
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1489 this = under = find_interval (tree, position);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1490 if (NULL_INTERVAL_P (under)) /* Paranoia */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1491 abort ();
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1492 over = find_interval (source, 1);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1493
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1494 /* Here for insertion in the middle of an interval.
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1495 Split off an equivalent interval to the right,
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1496 then don't bother with it any more. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1497
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1498 if (position > under->position)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1499 {
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1500 INTERVAL end_unchanged
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1501 = split_interval_left (this, position - under->position);
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1502 copy_properties (under, end_unchanged);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1503 under->position = position;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1504 prev = 0;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1505 middle = 1;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1506 }
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1507 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1508 {
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1509 prev = previous_interval (under);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1510 if (prev && !END_NONSTICKY_P (prev))
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1511 prev = 0;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1512 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1513
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1514 /* Insertion is now at beginning of UNDER. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1515
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1516 /* The inserted text "sticks" to the interval `under',
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1517 which means it gets those properties.
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1518 The properties of under are the result of
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1519 adjust_intervals_for_insertion, so stickyness has
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1520 already been taken care of. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1521
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1522 while (! NULL_INTERVAL_P (over))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1523 {
5666
ceed2e32b303 (graft_intervals_into_buffer): Fix one-off
Richard M. Stallman <rms@gnu.org>
parents: 5415
diff changeset
1524 if (LENGTH (over) < LENGTH (under))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1525 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1526 this = split_interval_left (under, LENGTH (over));
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1527 copy_properties (under, this);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1528 }
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1529 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1530 this = under;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1531 copy_properties (over, this);
4718
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1532 if (inherit)
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1533 merge_properties (over, this);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1534 else
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1535 copy_properties (over, this);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1536 over = next_interval (over);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1537 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1538
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1539 if (! NULL_INTERVAL_P (BUF_INTERVALS (buffer)))
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1540 BUF_INTERVALS (buffer) = balance_an_interval (BUF_INTERVALS (buffer));
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1541 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1542 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1543
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1544 /* Get the value of property PROP from PLIST,
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1545 which is the plist of an interval.
10927
7d02d12082ff (textget): Check default_properties vbl too.
Boris Goldowsky <boris@gnu.org>
parents: 10563
diff changeset
1546 We check for direct properties, for categories with property PROP,
11133
119880025e8f (Vdefault_text_properties): name changed from Vdefault_properties.
Boris Goldowsky <boris@gnu.org>
parents: 10927
diff changeset
1547 and for PROP appearing on the default-text-properties list. */
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1548
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1549 Lisp_Object
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1550 textget (plist, prop)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1551 Lisp_Object plist;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1552 register Lisp_Object prop;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1553 {
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1554 register Lisp_Object tail, fallback;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1555 fallback = Qnil;
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1556
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1557 for (tail = plist; !NILP (tail); tail = Fcdr (Fcdr (tail)))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1558 {
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1559 register Lisp_Object tem;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1560 tem = Fcar (tail);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1561 if (EQ (prop, tem))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1562 return Fcar (Fcdr (tail));
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1563 if (EQ (tem, Qcategory))
8611
65a058371675 (textget): Ignore category prop if not a symbol.
Richard M. Stallman <rms@gnu.org>
parents: 7307
diff changeset
1564 {
65a058371675 (textget): Ignore category prop if not a symbol.
Richard M. Stallman <rms@gnu.org>
parents: 7307
diff changeset
1565 tem = Fcar (Fcdr (tail));
65a058371675 (textget): Ignore category prop if not a symbol.
Richard M. Stallman <rms@gnu.org>
parents: 7307
diff changeset
1566 if (SYMBOLP (tem))
65a058371675 (textget): Ignore category prop if not a symbol.
Richard M. Stallman <rms@gnu.org>
parents: 7307
diff changeset
1567 fallback = Fget (tem, prop);
65a058371675 (textget): Ignore category prop if not a symbol.
Richard M. Stallman <rms@gnu.org>
parents: 7307
diff changeset
1568 }
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1569 }
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1570
10927
7d02d12082ff (textget): Check default_properties vbl too.
Boris Goldowsky <boris@gnu.org>
parents: 10563
diff changeset
1571 if (! NILP (fallback))
7d02d12082ff (textget): Check default_properties vbl too.
Boris Goldowsky <boris@gnu.org>
parents: 10563
diff changeset
1572 return fallback;
11133
119880025e8f (Vdefault_text_properties): name changed from Vdefault_properties.
Boris Goldowsky <boris@gnu.org>
parents: 10927
diff changeset
1573 if (CONSP (Vdefault_text_properties))
119880025e8f (Vdefault_text_properties): name changed from Vdefault_properties.
Boris Goldowsky <boris@gnu.org>
parents: 10927
diff changeset
1574 return Fplist_get (Vdefault_text_properties, prop);
10927
7d02d12082ff (textget): Check default_properties vbl too.
Boris Goldowsky <boris@gnu.org>
parents: 10563
diff changeset
1575 return Qnil;
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1576 }
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1577
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1578
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1579 /* Set point in BUFFER to POSITION. If the target position is
7104
9c99683eb6f0 Fix comment.
Karl Heuer <kwzh@gnu.org>
parents: 6753
diff changeset
1580 before an intangible character, move to an ok place. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1581
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1582 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1583 set_point (position, buffer)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1584 register int position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1585 register struct buffer *buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1586 {
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1587 register INTERVAL to, from, toprev, fromprev, target;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1588 int buffer_point;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1589 register Lisp_Object obj;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1590 int backwards = (position < BUF_PT (buffer)) ? 1 : 0;
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1591 int old_position = BUF_PT (buffer);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1592
10563
d35f5eca6dd5 (set_point): Set point_before_scroll to nil.
Richard M. Stallman <rms@gnu.org>
parents: 10313
diff changeset
1593 buffer->point_before_scroll = Qnil;
d35f5eca6dd5 (set_point): Set point_before_scroll to nil.
Richard M. Stallman <rms@gnu.org>
parents: 10313
diff changeset
1594
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1595 if (position == BUF_PT (buffer))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1596 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1597
2779
857bb0f59668 * intervals.c (set_point): Check for point out of bounds before
Jim Blandy <jimb@redhat.com>
parents: 2090
diff changeset
1598 /* Check this now, before checking if the buffer has any intervals.
857bb0f59668 * intervals.c (set_point): Check for point out of bounds before
Jim Blandy <jimb@redhat.com>
parents: 2090
diff changeset
1599 That way, we can catch conditions which break this sanity check
857bb0f59668 * intervals.c (set_point): Check for point out of bounds before
Jim Blandy <jimb@redhat.com>
parents: 2090
diff changeset
1600 whether or not there are intervals in the buffer. */
857bb0f59668 * intervals.c (set_point): Check for point out of bounds before
Jim Blandy <jimb@redhat.com>
parents: 2090
diff changeset
1601 if (position > BUF_Z (buffer) || position < BUF_BEG (buffer))
857bb0f59668 * intervals.c (set_point): Check for point out of bounds before
Jim Blandy <jimb@redhat.com>
parents: 2090
diff changeset
1602 abort ();
857bb0f59668 * intervals.c (set_point): Check for point out of bounds before
Jim Blandy <jimb@redhat.com>
parents: 2090
diff changeset
1603
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1604 if (NULL_INTERVAL_P (BUF_INTERVALS (buffer)))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1605 {
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1606
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1607 BUF_PT (buffer) = position;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1608 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1609 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1610
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1611 /* Set TO to the interval containing the char after POSITION,
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1612 and TOPREV to the interval containing the char before POSITION.
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1613 Either one may be null. They may be equal. */
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1614 to = find_interval (BUF_INTERVALS (buffer), position);
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1615 if (position == BUF_BEGV (buffer))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1616 toprev = 0;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1617 else if (to->position == position)
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1618 toprev = previous_interval (to);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1619 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1620 toprev = to;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1621
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1622 buffer_point = (BUF_PT (buffer) == BUF_ZV (buffer)
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1623 ? BUF_ZV (buffer) - 1
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1624 : BUF_PT (buffer));
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1625
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1626 /* Set FROM to the interval containing the char after PT,
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1627 and FROMPREV to the interval containing the char before PT.
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1628 Either one may be null. They may be equal. */
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1629 /* We could cache this and save time. */
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1630 from = find_interval (BUF_INTERVALS (buffer), buffer_point);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1631 if (buffer_point == BUF_BEGV (buffer))
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1632 fromprev = 0;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1633 else if (from->position == BUF_PT (buffer))
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1634 fromprev = previous_interval (from);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1635 else if (buffer_point != BUF_PT (buffer))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1636 fromprev = from, from = 0;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1637 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1638 fromprev = from;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1639
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1640 /* Moving within an interval. */
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1641 if (to == from && toprev == fromprev && INTERVAL_VISIBLE_P (to))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1642 {
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1643 BUF_PT (buffer) = position;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1644 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1645 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1646
11327
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1647 /* If the new position is between two intangible characters
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1648 with the same intangible property value,
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1649 move forward or backward until a change in that property. */
9072
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1650 if (NILP (Vinhibit_point_motion_hooks) && ! NULL_INTERVAL_P (to)
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1651 && ! NULL_INTERVAL_P (toprev))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1652 {
9072
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1653 if (backwards)
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1654 {
11327
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1655 Lisp_Object intangible_propval;
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1656 intangible_propval = textget (to->plist, Qintangible);
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1657
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1658 /* If following char is intangible,
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1659 skip back over all chars with matching intangible property. */
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1660 if (! NILP (intangible_propval))
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1661 while (to == toprev
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1662 || ((! NULL_INTERVAL_P (toprev)
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1663 && EQ (textget (toprev->plist, Qintangible),
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1664 intangible_propval))))
9072
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1665 {
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1666 to = toprev;
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1667 toprev = previous_interval (toprev);
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1668 if (NULL_INTERVAL_P (toprev))
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1669 position = BUF_BEGV (buffer);
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1670 else
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1671 /* This is the only line that's not
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1672 dual to the following loop.
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1673 That's because we want the position
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1674 at the end of TOPREV. */
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1675 position = to->position;
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1676 }
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1677 }
3734
5ada670e1fd8 (set_point): When moving over invis chars,
Richard M. Stallman <rms@gnu.org>
parents: 3591
diff changeset
1678 else
9072
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1679 {
11327
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1680 Lisp_Object intangible_propval;
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1681 intangible_propval = textget (toprev->plist, Qintangible);
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1682
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1683 /* If previous char is intangible,
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1684 skip fwd over all chars with matching intangible property. */
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1685 if (! NILP (intangible_propval))
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1686 while (to == toprev
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1687 || ((! NULL_INTERVAL_P (to)
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1688 && EQ (textget (to->plist, Qintangible),
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1689 intangible_propval))))
9072
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1690 {
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1691 toprev = to;
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1692 to = next_interval (to);
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1693 if (NULL_INTERVAL_P (to))
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1694 position = BUF_ZV (buffer);
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1695 else
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1696 position = to->position;
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1697 }
21517199cfae (set_point): If Vinhibit_point_motion_hooks, ignore intangible properties.
Richard M. Stallman <rms@gnu.org>
parents: 8897
diff changeset
1698 }
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1699 }
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1700
11327
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1701 /* Here TO is the interval after the stopping point
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1702 and TOPREV is the interval before the stopping point.
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1703 One or the other may be null. */
76908dad81a4 (set_point): When skipping intangible text,
Richard M. Stallman <rms@gnu.org>
parents: 11235
diff changeset
1704
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1705 BUF_PT (buffer) = position;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1706
1288
b05982e82d93 Various comment changes.
Joseph Arceneaux <jla@gnu.org>
parents: 1211
diff changeset
1707 /* We run point-left and point-entered hooks here, iff the
b05982e82d93 Various comment changes.
Joseph Arceneaux <jla@gnu.org>
parents: 1211
diff changeset
1708 two intervals are not equivalent. These hooks take
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1709 (old_point, new_point) as arguments. */
4243
23fe7f6c9ae4 (set_point): Test Vinhibit_point_motion_hooks.
Richard M. Stallman <rms@gnu.org>
parents: 4223
diff changeset
1710 if (NILP (Vinhibit_point_motion_hooks)
23fe7f6c9ae4 (set_point): Test Vinhibit_point_motion_hooks.
Richard M. Stallman <rms@gnu.org>
parents: 4223
diff changeset
1711 && (! intervals_equal (from, to)
23fe7f6c9ae4 (set_point): Test Vinhibit_point_motion_hooks.
Richard M. Stallman <rms@gnu.org>
parents: 4223
diff changeset
1712 || ! intervals_equal (fromprev, toprev)))
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1713 {
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1714 Lisp_Object leave_after, leave_before, enter_after, enter_before;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1715
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1716 if (fromprev)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1717 leave_after = textget (fromprev->plist, Qpoint_left);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1718 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1719 leave_after = Qnil;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1720 if (from)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1721 leave_before = textget (from->plist, Qpoint_left);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1722 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1723 leave_before = Qnil;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1724
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1725 if (toprev)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1726 enter_after = textget (toprev->plist, Qpoint_entered);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1727 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1728 enter_after = Qnil;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1729 if (to)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1730 enter_before = textget (to->plist, Qpoint_entered);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1731 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1732 enter_before = Qnil;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1733
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1734 if (! EQ (leave_before, enter_before) && !NILP (leave_before))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1735 call2 (leave_before, old_position, position);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1736 if (! EQ (leave_after, enter_after) && !NILP (leave_after))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1737 call2 (leave_after, old_position, position);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1738
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1739 if (! EQ (enter_before, leave_before) && !NILP (enter_before))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1740 call2 (enter_before, old_position, position);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1741 if (! EQ (enter_after, leave_after) && !NILP (enter_after))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1742 call2 (enter_after, old_position, position);
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1743 }
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1744 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1745
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1746 /* Set point temporarily, without checking any text properties. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1747
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1748 INLINE void
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1749 temp_set_point (position, buffer)
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1750 int position;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1751 struct buffer *buffer;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1752 {
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1753 BUF_PT (buffer) = position;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1754 }
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1755
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1756 /* Return the proper local map for position POSITION in BUFFER.
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1757 Use the map specified by the local-map property, if any.
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1758 Otherwise, use BUFFER's local map. */
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1759
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1760 Lisp_Object
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1761 get_local_map (position, buffer)
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1762 register int position;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1763 register struct buffer *buffer;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1764 {
11660
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1765 Lisp_Object prop, tem, lispy_position, lispy_buffer;
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1766 int old_begv, old_zv;
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1767
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1768 /* Perhaps we should just change `position' to the limit. */
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1769 if (position > BUF_Z (buffer) || position < BUF_BEG (buffer))
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1770 abort ();
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1771
11660
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1772 /* Ignore narrowing, so that a local map continues to be valid even if
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1773 the visible region contains no characters and hence no properties. */
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1774 old_begv = BUF_BEGV (buffer);
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1775 old_zv = BUF_ZV (buffer);
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1776 BUF_BEGV (buffer) = BUF_BEG (buffer);
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1777 BUF_ZV (buffer) = BUF_Z (buffer);
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1778
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1779 /* There are no properties at the end of the buffer, so in that case
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1780 check for a local map on the last character of the buffer instead. */
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1781 if (position == BUF_Z (buffer) && BUF_Z (buffer) > BUF_BEG (buffer))
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1782 --position;
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1783 XSETFASTINT (lispy_position, position);
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1784 XSETBUFFER (lispy_buffer, buffer);
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1785 prop = Fget_char_property (lispy_position, Qlocal_map, lispy_buffer);
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1786
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1787 BUF_BEGV (buffer) = old_begv;
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1788 BUF_ZV (buffer) = old_zv;
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1789
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1790 /* Use the local map only if it is valid. */
11660
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1791 if (!NILP (prop)
7c7519c2a45a (get_local_map): Use Fget_char_property, so that
Karl Heuer <kwzh@gnu.org>
parents: 11327
diff changeset
1792 && (tem = Fkeymapp (prop), !NILP (tem)))
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1793 return prop;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1794
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1795 return buffer->keymap;
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1796 }
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1797
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1798 /* Produce an interval tree reflecting the intervals in
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1799 TREE from START to START + LENGTH. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1800
1316
f09c5c6563b8 * intervals.c: `copy_intervals()' no longer static.
Joseph Arceneaux <jla@gnu.org>
parents: 1307
diff changeset
1801 INTERVAL
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1802 copy_intervals (tree, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1803 INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1804 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1805 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1806 register INTERVAL i, new, t;
3490
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1807 register int got, prevlen;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1808
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1809 if (NULL_INTERVAL_P (tree) || length <= 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1810 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1811
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1812 i = find_interval (tree, start);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1813 if (NULL_INTERVAL_P (i) || LENGTH (i) == 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1814 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1815
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1816 /* If there is only one interval and it's the default, return nil. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1817 if ((start - i->position + 1 + length) < LENGTH (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1818 && DEFAULT_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1819 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1820
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1821 new = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1822 new->position = 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1823 got = (LENGTH (i) - (start - i->position));
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1824 new->total_length = length;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1825 copy_properties (i, new);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1826
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1827 t = new;
3490
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1828 prevlen = got;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1829 while (got < length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1830 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1831 i = next_interval (i);
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1832 t = split_interval_right (t, prevlen);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1833 copy_properties (i, t);
3490
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1834 prevlen = LENGTH (i);
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1835 got += prevlen;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1836 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1837
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
1838 return balance_an_interval (new);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1839 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1840
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1841 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1842
1288
b05982e82d93 Various comment changes.
Joseph Arceneaux <jla@gnu.org>
parents: 1211
diff changeset
1843 INLINE void
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1844 copy_intervals_to_string (string, buffer, position, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1845 Lisp_Object string, buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1846 int position, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1847 {
10313
55ce83f36b30 Use BUF_INTERVALS throughout.
Richard M. Stallman <rms@gnu.org>
parents: 10113
diff changeset
1848 INTERVAL interval_copy = copy_intervals (BUF_INTERVALS (XBUFFER (buffer)),
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1849 position, length);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1850 if (NULL_INTERVAL_P (interval_copy))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1851 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1852
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1853 interval_copy->parent = (INTERVAL) string;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1854 XSTRING (string)->intervals = interval_copy;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1855 }
10113
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1856
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1857 /* Return 1 if string S1 and S2 have identical properties; 0 otherwise.
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1858 Assume they have identical characters. */
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1859
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1860 int
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1861 compare_string_intervals (s1, s2)
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1862 Lisp_Object s1, s2;
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1863 {
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1864 INTERVAL i1, i2;
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1865 int pos = 1;
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1866 int end = XSTRING (s1)->size + 1;
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1867
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1868 /* We specify 1 as position because the interval functions
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1869 always use positions starting at 1. */
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1870 i1 = find_interval (XSTRING (s1)->intervals, 1);
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1871 i2 = find_interval (XSTRING (s2)->intervals, 1);
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1872
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1873 while (pos < end)
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1874 {
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1875 /* Determine how far we can go before we reach the end of I1 or I2. */
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1876 int len1 = (i1 != 0 ? INTERVAL_LAST_POS (i1) : end) - pos;
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1877 int len2 = (i2 != 0 ? INTERVAL_LAST_POS (i2) : end) - pos;
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1878 int distance = min (len1, len2);
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1879
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1880 /* If we ever find a mismatch between the strings,
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1881 they differ. */
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1882 if (! intervals_equal (i1, i2))
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1883 return 0;
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1884
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1885 /* Advance POS till the end of the shorter interval,
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1886 and advance one or both interval pointers for the new position. */
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1887 pos += distance;
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1888 if (len1 == distance)
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1889 i1 = next_interval (i1);
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1890 if (len2 == distance)
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1891 i2 = next_interval (i2);
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1892 }
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1893 return 1;
9d72d79329c3 (compare_string_intervals): New function.
Richard M. Stallman <rms@gnu.org>
parents: 9461
diff changeset
1894 }
1301
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
1895
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
1896 #endif /* USE_TEXT_PROPERTIES */