annotate src/intervals.c @ 5623:d571ad3c796e

(show-paren-command-hook): Do nothing when in kbd macro.
author Richard M. Stallman <rms@gnu.org>
date Mon, 17 Jan 1994 22:43:40 +0000
parents 95882472f2da
children ceed2e32b303
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.
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
2 Copyright (C) 1993 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"
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
46
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
47 /* 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
48 #ifdef USE_TEXT_PROPERTIES
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
49
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
50 /* Factor for weight-balancing interval trees. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
51 Lisp_Object interval_balance_threshold;
5173
d48ba25b35bf (merge_properties_sticky): Declared.
Richard M. Stallman <rms@gnu.org>
parents: 5169
diff changeset
52
d48ba25b35bf (merge_properties_sticky): Declared.
Richard M. Stallman <rms@gnu.org>
parents: 5169
diff changeset
53 Lisp_Object merge_properties_sticky ();
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
54
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
55 /* Utility functions for intervals. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
56
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
57
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
58 /* Create the root interval of some object, a buffer or string. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
59
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
60 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
61 create_root_interval (parent)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
62 Lisp_Object parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
63 {
4962
99edf052bfa0 Include puresize.h.
Richard M. Stallman <rms@gnu.org>
parents: 4718
diff changeset
64 INTERVAL new;
99edf052bfa0 Include puresize.h.
Richard M. Stallman <rms@gnu.org>
parents: 4718
diff changeset
65
99edf052bfa0 Include puresize.h.
Richard M. Stallman <rms@gnu.org>
parents: 4718
diff changeset
66 CHECK_IMPURE (parent);
99edf052bfa0 Include puresize.h.
Richard M. Stallman <rms@gnu.org>
parents: 4718
diff changeset
67
99edf052bfa0 Include puresize.h.
Richard M. Stallman <rms@gnu.org>
parents: 4718
diff changeset
68 new = make_interval ();
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
69
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
70 if (XTYPE (parent) == Lisp_Buffer)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
71 {
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
72 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
73 - BUF_BEG (XBUFFER (parent)));
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
74 XBUFFER (parent)->intervals = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
75 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
76 else if (XTYPE (parent) == Lisp_String)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
77 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
78 new->total_length = XSTRING (parent)->size;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
79 XSTRING (parent)->intervals = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
80 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
81
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
82 new->parent = (INTERVAL) parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
83 new->position = 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
84
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
85 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
86 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
87
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
88 /* Make the interval TARGET have exactly the properties of SOURCE */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
89
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
90 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
91 copy_properties (source, target)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
92 register INTERVAL source, target;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
93 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
94 if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
95 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
96
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
97 COPY_INTERVAL_CACHE (source, target);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
98 target->plist = Fcopy_sequence (source->plist);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
99 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
100
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
101 /* 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
102 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
103 is added to TARGET if TARGET has no such property as yet. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
104
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
105 static void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
106 merge_properties (source, target)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
107 register INTERVAL source, target;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
108 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
109 register Lisp_Object o, sym, val;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
110
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
111 if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
112 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
113
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
114 MERGE_INTERVAL_CACHE (source, target);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
115
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
116 o = source->plist;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
117 while (! EQ (o, Qnil))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
118 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
119 sym = Fcar (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
120 val = Fmemq (sym, target->plist);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
121
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
122 if (NILP (val))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
123 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
124 o = Fcdr (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
125 val = Fcar (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
126 target->plist = Fcons (sym, Fcons (val, target->plist));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
127 o = Fcdr (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
128 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
129 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
130 o = Fcdr (Fcdr (o));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
131 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
132 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
133
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
134 /* 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
135 0 otherwise. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
136
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
137 int
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
138 intervals_equal (i0, i1)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
139 INTERVAL i0, i1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
140 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
141 register Lisp_Object i0_cdr, i0_sym, i1_val;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
142 register i1_len;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
143
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
144 if (DEFAULT_INTERVAL_P (i0) && DEFAULT_INTERVAL_P (i1))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
145 return 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
146
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
147 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
148 return 0;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
149
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
150 i1_len = XFASTINT (Flength (i1->plist));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
151 if (i1_len & 0x1) /* Paranoia -- plists are always even */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
152 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
153 i1_len /= 2;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
154 i0_cdr = i0->plist;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
155 while (!NILP (i0_cdr))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
156 {
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
157 /* Lengths of the two plists were unequal. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
158 if (i1_len == 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
159 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
160
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
161 i0_sym = Fcar (i0_cdr);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
162 i1_val = Fmemq (i0_sym, i1->plist);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
163
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
164 /* i0 has something i1 doesn't. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
165 if (EQ (i1_val, Qnil))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
166 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
167
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
168 /* 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
169 i0_cdr = Fcdr (i0_cdr);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
170 if (! EQ (Fcar (Fcdr (i1_val)), Fcar (i0_cdr)))
1157
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
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
173 i0_cdr = Fcdr (i0_cdr);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
174 i1_len--;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
175 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
176
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
177 /* Lengths of the two plists were unequal. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
178 if (i1_len > 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
179 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
180
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
181 return 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
182 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
183
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
184 static int icount;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
185 static int idepth;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
186 static int zero_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
187
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
188 /* 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
189 Pass FUNCTION two args: an interval, and ARG. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
190
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
191 void
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
192 traverse_intervals (tree, position, depth, function, arg)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
193 INTERVAL tree;
1412
6097878fbd46 * intervals.c (traverse_intervals): New parameter `depth'.
Joseph Arceneaux <jla@gnu.org>
parents: 1316
diff changeset
194 int position, depth;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
195 void (* function) ();
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
196 Lisp_Object arg;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
197 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
198 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
199 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
200
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
201 traverse_intervals (tree->left, position, depth + 1, function, arg);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
202 position += LEFT_TOTAL_LENGTH (tree);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
203 tree->position = position;
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
204 (*function) (tree, arg);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
205 position += LENGTH (tree);
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->right, position, depth + 1, function, arg);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
207 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
208
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
209 #if 0
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
210 /* These functions are temporary, for debugging purposes only. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
211
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
212 INTERVAL search_interval, found_interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
213
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
214 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
215 check_for_interval (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
216 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
217 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
218 if (i == search_interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
219 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
220 found_interval = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
221 icount++;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
222 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
223 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
224
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
225 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
226 search_for_interval (i, tree)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
227 register INTERVAL i, tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
228 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
229 icount = 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
230 search_interval = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
231 found_interval = NULL_INTERVAL;
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
232 traverse_intervals (tree, 1, 0, &check_for_interval, Qnil);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
233 return found_interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
234 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
235
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
236 static void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
237 inc_interval_count (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
238 INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
239 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
240 icount++;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
241 if (LENGTH (i) == 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
242 zero_length++;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
243 if (depth > idepth)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
244 idepth = depth;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
245 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
246
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
247 int
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
248 count_intervals (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
249 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
250 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
251 icount = 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
252 idepth = 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
253 zero_length = 0;
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
254 traverse_intervals (i, 1, 0, &inc_interval_count, Qnil);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
255
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
256 return icount;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
257 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
258
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
259 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
260 root_interval (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
261 INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
262 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
263 register INTERVAL i = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
264
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
265 while (! ROOT_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
266 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
267
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
268 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
269 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
270 #endif
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
271
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
272 /* Assuming that a left child exists, perform the following operation:
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
273
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
274 A B
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
275 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
276 B => A
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
277 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
278 c c
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
279 */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
280
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
281 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
282 rotate_right (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
283 INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
284 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
285 INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
286 INTERVAL B = interval->left;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
287 int old_total = interval->total_length;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
288
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
289 /* Deal with any Parent of A; make it point to B. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
290 if (! ROOT_INTERVAL_P (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
291 if (AM_LEFT_CHILD (interval))
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
292 interval->parent->left = B;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
293 else
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
294 interval->parent->right = B;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
295 B->parent = interval->parent;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
296
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
297 /* Make B the parent of A */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
298 i = B->right;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
299 B->right = interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
300 interval->parent = B;
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 A point to c */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
303 interval->left = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
304 if (! NULL_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
305 i->parent = interval;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
306
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
307 /* A's total length is decreased by the length of B and it's left child. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
308 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
309
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
310 /* 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
311 B->total_length = old_total;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
312
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
313 return B;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
314 }
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
315
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
316 /* Assuming that a right child exists, perform the following operation:
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
317
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
318 A B
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
319 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
320 B => A
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
321 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
322 c c
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
323 */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
324
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
325 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
326 rotate_left (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
327 INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
328 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
329 INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
330 INTERVAL B = interval->right;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
331 int old_total = interval->total_length;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
332
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
333 /* Deal with any parent of A; make it point to B. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
334 if (! ROOT_INTERVAL_P (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
335 if (AM_LEFT_CHILD (interval))
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
336 interval->parent->left = B;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
337 else
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
338 interval->parent->right = B;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
339 B->parent = interval->parent;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
340
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
341 /* Make B the parent of A */
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
342 i = B->left;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
343 B->left = interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
344 interval->parent = B;
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 A point to c */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
347 interval->right = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
348 if (! NULL_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
349 i->parent = interval;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
350
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
351 /* A's total length is decreased by the length of B and it's right child. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
352 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
353
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
354 /* 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
355 B->total_length = old_total;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
356
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
357 return B;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
358 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
359
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
360 /* 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
361 themselves are already balanced. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
362
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
363 static INTERVAL
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
364 balance_an_interval (i)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
365 INTERVAL i;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
366 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
367 register int old_diff, new_diff;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
368
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
369 while (1)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
370 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
371 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
372 if (old_diff > 0)
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 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
375 + 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
376 if (abs (new_diff) >= old_diff)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
377 break;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
378 i = rotate_right (i);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
379 balance_an_interval (i->right);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
380 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
381 else if (old_diff < 0)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
382 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
383 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
384 + 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
385 if (abs (new_diff) >= -old_diff)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
386 break;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
387 i = rotate_left (i);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
388 balance_an_interval (i->left);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
389 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
390 else
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 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
393 return i;
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
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
396 /* 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
397 Lisp Object. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
398
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
399 static INLINE INTERVAL
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
400 balance_possible_root_interval (interval)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
401 register INTERVAL interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
402 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
403 Lisp_Object parent;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
404
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
405 if (interval->parent == NULL_INTERVAL)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
406 return 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 parent = (Lisp_Object) (interval->parent);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
409 interval = balance_an_interval (interval);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
410
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
411 if (XTYPE (parent) == Lisp_Buffer)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
412 XBUFFER (parent)->intervals = interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
413 else if (XTYPE (parent) == Lisp_String)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
414 XSTRING (parent)->intervals = interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
416 return interval;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
417 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
418
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
419 /* 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
420 (the amount of text). */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
421
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
422 static INTERVAL
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
423 balance_intervals_internal (tree)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
424 register INTERVAL tree;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
425 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
426 /* Balance within each side. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
427 if (tree->left)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
428 balance_intervals (tree->left);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
429 if (tree->right)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
430 balance_intervals (tree->right);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
431 return balance_an_interval (tree);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
432 }
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
433
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
434 /* Advertised interface to balance intervals. */
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
435
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
436 INTERVAL
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
437 balance_intervals (tree)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
438 INTERVAL tree;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
439 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
440 if (tree == NULL_INTERVAL)
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
441 return NULL_INTERVAL;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
442
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
443 return balance_intervals_internal (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
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
446 /* 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
447 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
448 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
449 (second, lexicographically) is returned.
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
450
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
451 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
452 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
453 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
454 result.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
455
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
456 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
457 it is still a root after this operation. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
458
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
459 INTERVAL
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
460 split_interval_right (interval, offset)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
461 INTERVAL interval;
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
462 int offset;
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 new = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
465 int position = interval->position;
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
466 int new_length = LENGTH (interval) - offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
467
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
468 new->position = position + offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
469 new->parent = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
470
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
471 if (NULL_RIGHT_CHILD (interval))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
472 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
473 interval->right = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
474 new->total_length = new_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
475
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
476 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
477 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
478
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
479 /* Insert the new node between INTERVAL and its right child. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
480 new->right = interval->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
481 interval->right->parent = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
482 interval->right = new;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
483 new->total_length = new_length + new->right->total_length;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
484
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
485 balance_an_interval (new);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
486 balance_possible_root_interval (interval);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
487
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
488 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
489 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
490
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
491 /* 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
492 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
493 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
494 (first, lexicographically) is returned.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
495
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
496 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
497 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
498 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
499 result.
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
500
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
501 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
502 it is still a root after this operation. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
503
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
504 INTERVAL
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
505 split_interval_left (interval, offset)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
506 INTERVAL interval;
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
507 int offset;
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 new = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
510 int position = interval->position;
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
511 int new_length = offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
512
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
513 new->position = interval->position;
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
514 interval->position = interval->position + offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
515 new->parent = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
516
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
517 if (NULL_LEFT_CHILD (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
518 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
519 interval->left = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
520 new->total_length = new_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
521
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
522 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
523 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
524
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
525 /* Insert the new node between INTERVAL and its left child. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
526 new->left = interval->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
527 new->left->parent = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
528 interval->left = new;
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
529 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
530
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
531 balance_an_interval (new);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
532 balance_possible_root_interval (interval);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
533
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
534 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
535 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
536
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
537 /* 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
538 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
539 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
540 the buffer, return the interval containing the last character.
1157
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 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
543 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
544 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
545
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
546 INLINE INTERVAL
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
547 find_interval (tree, position)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
548 register INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
549 register int position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
550 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
551 /* 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
552 to POSITION. */
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
553 register int relative_position = position - BEG;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
554
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
555 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
556 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
557
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
558 if (relative_position > TOTAL_LENGTH (tree))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
559 abort (); /* Paranoia */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
560
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
561 tree = balance_possible_root_interval (tree);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
562
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
563 while (1)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
564 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
565 if (relative_position < LEFT_TOTAL_LENGTH (tree))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
566 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
567 tree = tree->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
568 }
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
569 else if (! NULL_RIGHT_CHILD (tree)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
570 && relative_position >= (TOTAL_LENGTH (tree)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
571 - RIGHT_TOTAL_LENGTH (tree)))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
572 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
573 relative_position -= (TOTAL_LENGTH (tree)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
574 - RIGHT_TOTAL_LENGTH (tree));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
575 tree = tree->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
576 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
577 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
578 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
579 tree->position =
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
580 (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
581 + 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
582
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
583 return tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
584 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
585 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
586 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
587
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
588 /* Find the succeeding interval (lexicographically) to INTERVAL.
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
589 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
590 find_interval). */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
591
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
592 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
593 next_interval (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
594 register INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
595 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
596 register INTERVAL i = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
597 register int next_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
598
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
599 if (NULL_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
600 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
601 next_position = interval->position + LENGTH (interval);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
602
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
603 if (! NULL_RIGHT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
604 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
605 i = i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
606 while (! NULL_LEFT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
607 i = i->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
608
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
609 i->position = next_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
610 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
611 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
612
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
613 while (! NULL_PARENT (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
614 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
615 if (AM_LEFT_CHILD (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 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
618 i->position = next_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
619 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
620 }
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 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
624
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
625 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
626 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
627
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
628 /* Find the preceding interval (lexicographically) to INTERVAL.
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
629 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
630 find_interval). */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
631
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
632 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
633 previous_interval (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
634 register INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
635 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
636 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
637 register position_of_previous;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
638
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
639 if (NULL_INTERVAL_P (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
640 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
641
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
642 if (! NULL_LEFT_CHILD (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
643 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
644 i = interval->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
645 while (! NULL_RIGHT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
646 i = i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
647
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
648 i->position = interval->position - LENGTH (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
649 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
650 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
651
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
652 i = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
653 while (! NULL_PARENT (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
654 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
655 if (AM_RIGHT_CHILD (i))
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 = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
658
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
659 i->position = interval->position - LENGTH (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
660 return 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
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
665 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
666 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
667
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
668 #if 0
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
669 /* Traverse a path down the interval tree TREE to the interval
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
670 containing POSITION, adjusting all nodes on the path for
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
671 an addition of LENGTH characters. Insertion between two intervals
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
672 (i.e., point == i->position, where i is second interval) means
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
673 text goes into second interval.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
674
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
675 Modifications are needed to handle the hungry bits -- after simply
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
676 finding the interval at position (don't add length going down),
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
677 if it's the beginning of the interval, get the previous interval
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
678 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
679 to the root. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
680
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
681 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
682 adjust_intervals_for_insertion (tree, position, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
683 INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
684 int position, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
685 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
686 register int relative_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
687 register INTERVAL this;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
688
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
689 if (TOTAL_LENGTH (tree) == 0) /* Paranoia */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
690 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
691
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
692 /* If inserting at point-max of a buffer, that position
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
693 will be out of range */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
694 if (position > TOTAL_LENGTH (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
695 position = TOTAL_LENGTH (tree);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
696 relative_position = position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
697 this = tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
698
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
699 while (1)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
700 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
701 if (relative_position <= LEFT_TOTAL_LENGTH (this))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
702 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
703 this->total_length += length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
704 this = this->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
705 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
706 else if (relative_position > (TOTAL_LENGTH (this)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
707 - RIGHT_TOTAL_LENGTH (this)))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
708 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
709 relative_position -= (TOTAL_LENGTH (this)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
710 - RIGHT_TOTAL_LENGTH (this));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
711 this->total_length += length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
712 this = this->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
713 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
714 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
715 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
716 /* 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
717 then this code will have to change. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
718 this->total_length += length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
719 this->position = LEFT_TOTAL_LENGTH (this)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
720 + position - relative_position + 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
721 return tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
722 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
723 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
724 }
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
725 #endif
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
726
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
727 /* Effect an adjustment corresponding to the addition of LENGTH characters
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
728 of text. Do this by finding the interval containing POSITION in the
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
729 interval tree TREE, and then adjusting all of it's ancestors by adding
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
730 LENGTH to them.
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 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
733 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
734 the interval which is "sticky".
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
735
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
736 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
737 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
738 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
739
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
740 static INTERVAL
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
741 adjust_intervals_for_insertion (tree, position, length)
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
742 INTERVAL tree;
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
743 int position, length;
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 register INTERVAL i;
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
746 register INTERVAL temp;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
747 int eobp = 0;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
748
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
749 if (TOTAL_LENGTH (tree) == 0) /* Paranoia */
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
750 abort ();
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
751
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
752 /* 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
753 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
754 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
755 position = BEG + TOTAL_LENGTH (tree);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
756 eobp = 1;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
757 }
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
758
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
759 i = find_interval (tree, position);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
760
4638
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
761 /* 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
762 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
763 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
764 if (! (position == i->position || eobp)
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
765 && END_NONSTICKY_P (i)
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
766 && ! FRONT_STICKY_P (i))
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
767 {
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
768 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
769 copy_properties (i, temp);
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
770 i = temp;
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
771 }
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
772
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
773 /* 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
774 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
775 if (position == i->position || eobp)
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
776 {
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
777 register INTERVAL prev;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
778
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
779 if (position == BEG)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
780 prev = 0;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
781 else if (eobp)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
782 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
783 prev = i;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
784 i = 0;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
785 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
786 else
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
787 prev = previous_interval (i);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
788
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
789 /* 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
790 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
791 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
792 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
793 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
794 temp->total_length += length;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
795 temp = balance_possible_root_interval (temp);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
796 }
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
797
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
798 /* 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
799 we check the stickyness property by property. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
800 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
801 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
802 Lisp_Object pleft = NULL_INTERVAL_P (prev) ? Qnil : prev->plist;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
803 Lisp_Object pright = NULL_INTERVAL_P (i) ? Qnil : i->plist;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
804 struct interval newi;
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
805
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
806 newi.plist = merge_properties_sticky (pleft, pright);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
807
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
808 if(! prev) /* i.e. position == BEG */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
809 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
810 if (! intervals_equal (i, &newi))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
811 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
812 i = split_interval_left (i, length);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
813 i->plist = newi.plist;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
814 }
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 else if (! intervals_equal (prev, &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 prev = split_interval_right (prev,
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
819 position - prev->position);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
820 prev->plist = newi.plist;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
821 if (! NULL_INTERVAL_P (i)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
822 && intervals_equal (prev, i))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
823 merge_interval_right (prev);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
824 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
825
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
826 /* 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
827 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
828 else if (! prev && ! NILP (i->plist))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
829 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
830 /* 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
831 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
832 i = split_interval_left (i, length);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
833 }
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
834 }
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
835
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
836 /* Otherwise just extend the interval. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
837 else
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
838 {
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
839 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
840 {
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
841 temp->total_length += length;
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
842 temp = balance_possible_root_interval (temp);
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
843 }
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
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
846 return tree;
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
847 }
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
848
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
849 Lisp_Object
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
850 merge_properties_sticky (pleft, pright)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
851 Lisp_Object pleft, pright;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
852 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
853 register Lisp_Object props = Qnil, front = Qnil, rear = Qnil;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
854
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
855 Lisp_Object lfront = textget (pleft, Qfront_sticky);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
856 Lisp_Object lrear = textget (pleft, Qrear_nonsticky);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
857 Lisp_Object rfront = textget (pright, Qfront_sticky);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
858 Lisp_Object rrear = textget (pright, Qrear_nonsticky);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
859
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
860 register Lisp_Object tail1, tail2, sym;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
861
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
862 /* Go through each element of PLEFT. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
863 for (tail1 = pleft; ! NILP (tail1); tail1 = Fcdr (Fcdr (tail1)))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
864 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
865 sym = Fcar (tail1);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
866
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
867 /* Sticky properties get special treatment. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
868 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
869 continue;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
870
4638
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
871 if (CONSP (lrear) ? NILP (Fmemq (sym, lrear)) : NILP (lrear))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
872 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
873 /* rear-sticky is dominant, we needn't search in PRIGHT. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
874
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
875 props = Fcons (sym, Fcons (Fcar (Fcdr (tail1)), props));
4638
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
876 if ((CONSP (lfront) || NILP (lfront))
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
877 && ! NILP (Fmemq (sym, lfront)))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
878 front = Fcons (sym, front);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
879 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
880 else
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
881 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
882 /* Go through PRIGHT, looking for sym. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
883 for (tail2 = pright; ! NILP (tail2); tail2 = Fcdr (Fcdr (tail2)))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
884 if (EQ (sym, Fcar (tail2)))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
885 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
886
4638
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
887 if (CONSP (rfront)
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
888 ? ! NILP (Fmemq (sym, rfront)) : ! NILP (rfront))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
889 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
890 /* Nonsticky at the left and sticky at the right,
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
891 so take the right one. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
892 props = Fcons (sym, Fcons (Fcar (Fcdr (tail2)), props));
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
893 front = Fcons (sym, front);
4638
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
894 if ((CONSP (rrear) || NILP (rrear))
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
895 && ! NILP (Fmemq (sym, rrear)))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
896 rear = Fcons (sym, rear);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
897 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
898 break;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
899 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
900 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
901 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
902 /* Now let's see what to keep from PRIGHT. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
903 for (tail2 = pright; ! NILP (tail2); tail2 = Fcdr (Fcdr (tail2)))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
904 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
905 sym = Fcar (tail2);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
906
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
907 /* Sticky properties get special treatment. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
908 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
909 continue;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
910
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
911 /* If it ain't sticky, we don't take it. */
4638
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
912 if (CONSP (rfront)
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
913 ? NILP (Fmemq (sym, rfront)) : NILP (rfront))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
914 continue;
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 /* If sym is in PLEFT we already got it. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
917 for (tail1 = pleft; ! NILP (tail1); tail1 = Fcdr (Fcdr (tail1)))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
918 if (EQ (sym, Fcar (tail1)))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
919 break;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
920
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
921 if (NILP (tail1))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
922 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
923 props = Fcons (sym, Fcons (Fcar (Fcdr (tail2)), props));
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
924 front = Fcons (sym, front);
4638
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
925 if ((CONSP (rrear) || NILP (rrear))
3872f91770fc (adjust_intervals_for_insertion): If inserting in middle
Richard M. Stallman <rms@gnu.org>
parents: 4383
diff changeset
926 && ! NILP (Fmemq (sym, rrear)))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
927 rear = Fcons (sym, rear);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
928 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
929 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
930 if (! NILP (front))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
931 props = Fcons (Qfront_sticky, Fcons (front, props));
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
932 if (! NILP (rear))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
933 props = Fcons (Qrear_nonsticky, Fcons (rear, props));
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
934 return props;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
935
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
936 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
937
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
938
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
939 /* 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
940 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
941 storing the resulting subtree into its parent. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
942
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
943 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
944 delete_node (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
945 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
946 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
947 register INTERVAL migrate, this;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
948 register int migrate_amt;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
949
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
950 if (NULL_INTERVAL_P (i->left))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
951 return i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
952 if (NULL_INTERVAL_P (i->right))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
953 return i->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
954
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
955 migrate = i->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
956 migrate_amt = i->left->total_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
957 this = i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
958 this->total_length += migrate_amt;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
959 while (! NULL_INTERVAL_P (this->left))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
960 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
961 this = this->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
962 this->total_length += migrate_amt;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
963 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
964 this->left = migrate;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
965 migrate->parent = this;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
966
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
967 return i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
968 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
969
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
970 /* Delete interval I from its tree by calling `delete_node'
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
971 and properly connecting the resultant subtree.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
972
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
973 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
974 for the length of I. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
975
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
976 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
977 delete_interval (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
978 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
979 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
980 register INTERVAL parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
981 int amt = LENGTH (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
982
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
983 if (amt > 0) /* Only used on zero-length intervals now. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
984 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
985
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
986 if (ROOT_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
987 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
988 Lisp_Object owner = (Lisp_Object) i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
989 parent = delete_node (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
990 if (! NULL_INTERVAL_P (parent))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
991 parent->parent = (INTERVAL) owner;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
992
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
993 if (XTYPE (owner) == Lisp_Buffer)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
994 XBUFFER (owner)->intervals = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
995 else if (XTYPE (owner) == Lisp_String)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
996 XSTRING (owner)->intervals = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
997 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
998 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
999
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1000 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1001 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1002
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1003 parent = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1004 if (AM_LEFT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1005 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1006 parent->left = delete_node (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1007 if (! NULL_INTERVAL_P (parent->left))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1008 parent->left->parent = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1009 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1010 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1011 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1012 parent->right = delete_node (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1013 if (! NULL_INTERVAL_P (parent->right))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1014 parent->right->parent = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1015 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1016 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1017
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1018 /* 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
1019 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
1020 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
1021 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
1022
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1023 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
1024 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
1025 recursively on subtrees.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1026
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1027 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
1028 deleting the appropriate amount of text. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1029
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1030 static int
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1031 interval_deletion_adjustment (tree, from, amount)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1032 register INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1033 register int from, amount;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1034 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1035 register int relative_position = from;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1036
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1037 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1038 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1039
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1040 /* Left branch */
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1041 if (relative_position < LEFT_TOTAL_LENGTH (tree))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1042 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1043 int subtract = interval_deletion_adjustment (tree->left,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1044 relative_position,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1045 amount);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1046 tree->total_length -= subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1047 return subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1048 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1049 /* Right branch */
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1050 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
1051 - RIGHT_TOTAL_LENGTH (tree)))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1052 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1053 int subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1054
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1055 relative_position -= (tree->total_length
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1056 - RIGHT_TOTAL_LENGTH (tree));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1057 subtract = interval_deletion_adjustment (tree->right,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1058 relative_position,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1059 amount);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1060 tree->total_length -= subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1061 return subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1062 }
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1063 /* Here -- this node. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1064 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1065 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1066 /* 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
1067 int my_amount = ((tree->total_length
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1068 - RIGHT_TOTAL_LENGTH (tree))
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1069 - relative_position);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1070
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1071 if (amount > my_amount)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1072 amount = my_amount;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1073
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1074 tree->total_length -= amount;
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1075 if (LENGTH (tree) == 0)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1076 delete_interval (tree);
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1077
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1078 return amount;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1079 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1080
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1081 /* Never reach here. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1082 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1083
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1084 /* 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
1085 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
1086 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
1087 buffer position, i.e. origin 1). */
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1088
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1089 static void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1090 adjust_intervals_for_deletion (buffer, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1091 struct buffer *buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1092 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1093 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1094 register int left_to_delete = length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1095 register INTERVAL tree = buffer->intervals;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1096 register int deleted;
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;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1100
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1101 if (start > BEG + TOTAL_LENGTH (tree)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1102 || start + length > BEG + TOTAL_LENGTH (tree))
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1103 abort ();
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1104
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1105 if (length == TOTAL_LENGTH (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1106 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1107 buffer->intervals = NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1108 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1109 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1110
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1111 if (ONLY_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1112 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1113 tree->total_length -= length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1114 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1115 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1116
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1117 if (start > BEG + TOTAL_LENGTH (tree))
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1118 start = BEG + TOTAL_LENGTH (tree);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1119 while (left_to_delete > 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1120 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1121 left_to_delete -= interval_deletion_adjustment (tree, start - 1,
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1122 left_to_delete);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1123 tree = buffer->intervals;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1124 if (left_to_delete == tree->total_length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1125 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1126 buffer->intervals = NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1127 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1128 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1129 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1130 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1131
3591
507f64624555 Apply typo patches from Paul Eggert.
Jim Blandy <jimb@redhat.com>
parents: 3490
diff changeset
1132 /* Make the adjustments necessary to the interval tree of BUFFER to
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1133 represent an addition or deletion of LENGTH characters starting
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1134 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
1135 of LENGTH. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1136
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1137 INLINE void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1138 offset_intervals (buffer, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1139 struct buffer *buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1140 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1141 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1142 if (NULL_INTERVAL_P (buffer->intervals) || length == 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1143 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1144
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1145 if (length > 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1146 adjust_intervals_for_insertion (buffer->intervals, start, length);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1147 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1148 adjust_intervals_for_deletion (buffer, start, -length);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1149 }
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1150
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1151 /* Merge interval I with its lexicographic successor. The resulting
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1152 interval is returned, and has the properties of the original
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1153 successor. The properties of I are lost. I is removed from the
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1154 interval tree.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1155
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1156 IMPORTANT:
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1157 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
1158 interval. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1159
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1160 INTERVAL
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1161 merge_interval_right (i)
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1162 register INTERVAL i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1163 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1164 register int absorb = LENGTH (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1165 register INTERVAL successor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1166
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1167 /* Zero out this interval. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1168 i->total_length -= absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1169
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1170 /* Find the succeeding interval. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1171 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
1172 as we descend. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1173 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1174 successor = i->right;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1175 while (! NULL_LEFT_CHILD (successor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1176 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1177 successor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1178 successor = successor->left;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1179 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1180
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1181 successor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1182 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1183 return successor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1184 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1185
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1186 successor = i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1187 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
1188 we ascend. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1189 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1190 if (AM_LEFT_CHILD (successor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1191 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1192 successor = successor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1193 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1194 return successor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1195 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1196
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1197 successor = successor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1198 successor->total_length -= absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1199 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1200
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1201 /* 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
1202 be merged right. The caller should have known. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1203 abort ();
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1204 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1205
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1206 /* Merge interval I with its lexicographic predecessor. The resulting
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1207 interval is returned, and has the properties of the original predecessor.
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1208 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
1209
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1210 IMPORTANT:
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1211 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
1212
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1213 INTERVAL
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1214 merge_interval_left (i)
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1215 register INTERVAL i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1216 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1217 register int absorb = LENGTH (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1218 register INTERVAL predecessor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1219
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1220 /* Zero out this interval. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1221 i->total_length -= absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1222
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1223 /* Find the preceding interval. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1224 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
1225 adding ABSORB as we go. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1226 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1227 predecessor = i->left;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1228 while (! NULL_RIGHT_CHILD (predecessor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1229 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1230 predecessor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1231 predecessor = predecessor->right;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1232 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1233
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1234 predecessor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1235 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1236 return predecessor;
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
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1239 predecessor = i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1240 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
1241 subtracting ABSORB. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1242 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1243 if (AM_RIGHT_CHILD (predecessor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1244 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1245 predecessor = predecessor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1246 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1247 return predecessor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1248 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1249
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1250 predecessor = predecessor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1251 predecessor->total_length -= absorb;
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
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1254 /* 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
1255 be merged left. The caller should have known. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1256 abort ();
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
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1259 /* Make an exact copy of interval tree SOURCE which descends from
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1260 PARENT. This is done by recursing through SOURCE, copying
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1261 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
1262 the pointers of the copy. */
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1263
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1264 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1265 reproduce_tree (source, parent)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1266 INTERVAL source, parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1267 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1268 register INTERVAL t = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1269
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1270 bcopy (source, t, INTERVAL_SIZE);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1271 copy_properties (source, t);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1272 t->parent = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1273 if (! NULL_LEFT_CHILD (source))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1274 t->left = reproduce_tree (source->left, t);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1275 if (! NULL_RIGHT_CHILD (source))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1276 t->right = reproduce_tree (source->right, t);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1277
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1278 return t;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1279 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1280
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1281 #if 0
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1282 /* 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
1283
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1284 /* Make a new interval of length LENGTH starting at START in the
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1285 group of intervals INTERVALS, which is actually an interval tree.
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1286 Returns the new interval.
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1287
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1288 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
1289 interval. */
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1290
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1291 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1292 make_new_interval (intervals, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1293 INTERVAL intervals;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1294 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1295 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1296 INTERVAL slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1297
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1298 slot = find_interval (intervals, start);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1299 if (start + length > slot->position + LENGTH (slot))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1300 error ("Interval would overlap");
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1301
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1302 if (start == slot->position && length == LENGTH (slot))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1303 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1304
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1305 if (slot->position == start)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1306 {
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1307 /* New right node. */
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1308 split_interval_right (slot, length);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1309 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1310 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1311
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1312 if (slot->position + LENGTH (slot) == start + length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1313 {
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1314 /* New left node. */
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1315 split_interval_left (slot, LENGTH (slot) - length);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1316 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1317 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1318
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1319 /* 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
1320 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
1321 split_interval_right (slot, length);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1322 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1323 }
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1324 #endif
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1325
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1326 /* 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
1327 LENGTH is the length of the text in SOURCE.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1328
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1329 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
1330 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
1331 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
1332 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
1333 shared.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1334
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1335 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
1336 want to inherit the surrounding text's properties, this function
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1337 simply returns -- offset_intervals should handle placing the
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
1338 text in the correct interval, depending on the sticky bits.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1339
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1340 If the inserted text had properties (intervals), then there are two
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1341 cases -- either insertion happened in the middle of some interval,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1342 or between two intervals.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1343
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1344 If the text goes into the middle of an interval, then new
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1345 intervals are created in the middle with only the properties of
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1346 the new text, *unless* the macro MERGE_INSERTIONS is true, in
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1347 which case the new text has the union of its properties and those
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1348 of the text into which it was inserted.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1349
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1350 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
1351 had its appropriate sticky property set (front_sticky, rear_sticky),
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
1352 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
1353 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
1354 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
1355 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
1356 only its properties, as if neither sticky property were set. Perhaps
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1357 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
1358 text... */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1359
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1360 void
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1361 graft_intervals_into_buffer (source, position, length, buffer, inherit)
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1362 INTERVAL source;
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1363 int position, length;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1364 struct buffer *buffer;
4718
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1365 int inherit;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1366 {
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1367 register INTERVAL under, over, this, prev;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1368 register INTERVAL tree = buffer->intervals;
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1369 int middle;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1370
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1371 /* 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
1372 interval it was inserted into. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1373 if (NULL_INTERVAL_P (source))
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1374 {
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1375 Lisp_Object buf;
5250
63a865489a1e (graft_intervals_into_buffer): If SOURCE is null
Richard M. Stallman <rms@gnu.org>
parents: 5173
diff changeset
1376 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
1377 {
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1378 XSET (buf, Lisp_Buffer, buffer);
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1379 Fset_text_properties (make_number (position),
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1380 make_number (position + length),
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1381 Qnil, buf);
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1382 }
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
1383 if (! NULL_INTERVAL_P (buffer->intervals))
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
1384 buffer->intervals = balance_an_interval (buffer->intervals);
5169
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1385 return;
d040c1a8ccbe (graft_intervals_into_buffer): New arg LENGTH.
Richard M. Stallman <rms@gnu.org>
parents: 4962
diff changeset
1386 }
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1387
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1388 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1389 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1390 /* 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
1391 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
1392 if ((BUF_Z (buffer) - BUF_BEG (buffer)) == TOTAL_LENGTH (source))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1393 {
4223
b044f6d3c4cb (graft_intervals_into_buffer): When TREE is null,
Richard M. Stallman <rms@gnu.org>
parents: 4135
diff changeset
1394 Lisp_Object buf;
b044f6d3c4cb (graft_intervals_into_buffer): When TREE is null,
Richard M. Stallman <rms@gnu.org>
parents: 4135
diff changeset
1395 XSET (buf, Lisp_Buffer, buffer);
b044f6d3c4cb (graft_intervals_into_buffer): When TREE is null,
Richard M. Stallman <rms@gnu.org>
parents: 4135
diff changeset
1396 buffer->intervals = reproduce_tree (source, buf);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1397 /* Explicitly free the old tree here. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1398
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1399 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1400 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1401
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1402 /* 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
1403 of the intervals of the inserted string. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1404 {
1307
b469633740b3 Fixed typos.
Joseph Arceneaux <jla@gnu.org>
parents: 1303
diff changeset
1405 Lisp_Object buf;
b469633740b3 Fixed typos.
Joseph Arceneaux <jla@gnu.org>
parents: 1303
diff changeset
1406 XSET (buf, Lisp_Buffer, buffer);
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1407 tree = create_root_interval (buf);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1408 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1409 }
4718
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1410 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
1411 /* 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
1412 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
1413 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
1414 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
1415 {
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1416 buffer->intervals = reproduce_tree (source, tree->parent);
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1417 /* Explicitly free the old tree here. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1418
4718
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1419 return;
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1420 }
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1421 /* 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
1422 should be of non-zero length. */
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1423 else if (TOTAL_LENGTH (tree) == 0)
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1424 abort ();
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1425
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1426 this = under = find_interval (tree, position);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1427 if (NULL_INTERVAL_P (under)) /* Paranoia */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1428 abort ();
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1429 over = find_interval (source, 1);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1430
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1431 /* 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
1432 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
1433 then don't bother with it any more. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1434
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1435 if (position > under->position)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1436 {
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1437 INTERVAL end_unchanged
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1438 = 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
1439 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
1440 under->position = position;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1441 prev = 0;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1442 middle = 1;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1443 }
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1444 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1445 {
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1446 prev = previous_interval (under);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1447 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
1448 prev = 0;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1449 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1450
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1451 /* Insertion is now at beginning of UNDER. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1452
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1453 /* 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
1454 which means it gets those properties.
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1455 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
1456 adjust_intervals_for_insertion, so stickyness has
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1457 already been taken care of. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1458
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1459 while (! NULL_INTERVAL_P (over))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1460 {
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1461 if (LENGTH (over) + 1 < LENGTH (under))
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1462 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1463 this = split_interval_left (under, LENGTH (over));
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1464 copy_properties (under, this);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1465 }
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1466 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1467 this = under;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1468 copy_properties (over, this);
4718
a05b833e61c4 (graft_intervals_into_buffer): New arg INHERIT.
Richard M. Stallman <rms@gnu.org>
parents: 4696
diff changeset
1469 if (inherit)
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1470 merge_properties (over, this);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1471 else
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1472 copy_properties (over, this);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1473 over = next_interval (over);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1474 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1475
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
1476 if (! NULL_INTERVAL_P (buffer->intervals))
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
1477 buffer->intervals = balance_an_interval (buffer->intervals);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1478 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1479 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1480
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1481 /* 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
1482 which is the plist of an interval.
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1483 We check for direct properties and for categories with property PROP. */
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1484
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1485 Lisp_Object
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1486 textget (plist, prop)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1487 Lisp_Object plist;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1488 register Lisp_Object prop;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1489 {
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1490 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
1491 fallback = Qnil;
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1492
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1493 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
1494 {
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1495 register Lisp_Object tem;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1496 tem = Fcar (tail);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1497 if (EQ (prop, tem))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1498 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
1499 if (EQ (tem, Qcategory))
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1500 fallback = Fget (Fcar (Fcdr (tail)), prop);
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1501 }
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1502
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1503 return fallback;
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1504 }
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1505
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1506 /* Get the value of property PROP from PLIST,
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1507 which is the plist of an interval.
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1508 We check for direct properties only! */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1509
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1510 Lisp_Object
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1511 textget_direct (plist, prop)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1512 Lisp_Object plist;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1513 register Lisp_Object prop;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1514 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1515 register Lisp_Object tail;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1516
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1517 for (tail = plist; !NILP (tail); tail = Fcdr (Fcdr (tail)))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1518 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1519 if (EQ (prop, Fcar (tail)))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1520 return Fcar (Fcdr (tail));
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1521 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1522
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1523 return Qnil;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1524 }
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1525
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1526 /* Set point in BUFFER to POSITION. If the target position is
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1527 before an invisible character which is not displayed with a special glyph,
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1528 move back to an ok place to display. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1529
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1530 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1531 set_point (position, buffer)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1532 register int position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1533 register struct buffer *buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1534 {
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1535 register INTERVAL to, from, toprev, fromprev, target;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1536 int buffer_point;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1537 register Lisp_Object obj;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1538 int backwards = (position < BUF_PT (buffer)) ? 1 : 0;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1539 int old_position = buffer->text.pt;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1540
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1541 if (position == buffer->text.pt)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1542 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1543
2779
857bb0f59668 * intervals.c (set_point): Check for point out of bounds before
Jim Blandy <jimb@redhat.com>
parents: 2090
diff changeset
1544 /* 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
1545 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
1546 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
1547 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
1548 abort ();
857bb0f59668 * intervals.c (set_point): Check for point out of bounds before
Jim Blandy <jimb@redhat.com>
parents: 2090
diff changeset
1549
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1550 if (NULL_INTERVAL_P (buffer->intervals))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1551 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1552 buffer->text.pt = position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1553 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1554 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1555
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1556 /* 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
1557 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
1558 Either one may be null. They may be equal. */
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1559 to = find_interval (buffer->intervals, position);
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1560 if (position == BUF_BEGV (buffer))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1561 toprev = 0;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1562 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
1563 toprev = previous_interval (to);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1564 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1565 toprev = to;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1566
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1567 buffer_point = (BUF_PT (buffer) == BUF_ZV (buffer)
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1568 ? 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
1569 : BUF_PT (buffer));
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1570
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1571 /* 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
1572 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
1573 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
1574 /* We could cache this and save time. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1575 from = find_interval (buffer->intervals, buffer_point);
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1576 if (buffer_point == BUF_BEGV (buffer))
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1577 fromprev = 0;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1578 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
1579 fromprev = previous_interval (from);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1580 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
1581 fromprev = from, from = 0;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1582 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1583 fromprev = from;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1584
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1585 /* 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
1586 if (to == from && toprev == fromprev && INTERVAL_VISIBLE_P (to))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1587 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1588 buffer->text.pt = position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1589 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1590 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1591
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1592 /* If the new position is before an invisible character
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1593 that has an `invisible' property of value `hidden',
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1594 move forward over all such. */
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1595 while (! NULL_INTERVAL_P (to)
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1596 && EQ (textget (to->plist, Qinvisible), Qhidden)
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1597 && ! DISPLAY_INVISIBLE_GLYPH (to))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1598 {
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1599 toprev = to;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1600 to = next_interval (to);
3734
5ada670e1fd8 (set_point): When moving over invis chars,
Richard M. Stallman <rms@gnu.org>
parents: 3591
diff changeset
1601 if (NULL_INTERVAL_P (to))
5ada670e1fd8 (set_point): When moving over invis chars,
Richard M. Stallman <rms@gnu.org>
parents: 3591
diff changeset
1602 position = BUF_ZV (buffer);
5ada670e1fd8 (set_point): When moving over invis chars,
Richard M. Stallman <rms@gnu.org>
parents: 3591
diff changeset
1603 else
5ada670e1fd8 (set_point): When moving over invis chars,
Richard M. Stallman <rms@gnu.org>
parents: 3591
diff changeset
1604 position = to->position;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1605 }
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1606
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1607 buffer->text.pt = position;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1608
1288
b05982e82d93 Various comment changes.
Joseph Arceneaux <jla@gnu.org>
parents: 1211
diff changeset
1609 /* We run point-left and point-entered hooks here, iff the
b05982e82d93 Various comment changes.
Joseph Arceneaux <jla@gnu.org>
parents: 1211
diff changeset
1610 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
1611 (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
1612 if (NILP (Vinhibit_point_motion_hooks)
23fe7f6c9ae4 (set_point): Test Vinhibit_point_motion_hooks.
Richard M. Stallman <rms@gnu.org>
parents: 4223
diff changeset
1613 && (! intervals_equal (from, to)
23fe7f6c9ae4 (set_point): Test Vinhibit_point_motion_hooks.
Richard M. Stallman <rms@gnu.org>
parents: 4223
diff changeset
1614 || ! intervals_equal (fromprev, toprev)))
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1615 {
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1616 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
1617
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1618 if (fromprev)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1619 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
1620 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1621 leave_after = Qnil;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1622 if (from)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1623 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
1624 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1625 leave_before = Qnil;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1626
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1627 if (toprev)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1628 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
1629 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1630 enter_after = Qnil;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1631 if (to)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1632 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
1633 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1634 enter_before = Qnil;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1635
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1636 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
1637 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
1638 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
1639 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
1640
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1641 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
1642 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
1643 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
1644 call2 (enter_after, old_position, position);
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1645 }
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1646 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1647
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1648 /* Set point temporarily, without checking any text properties. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1649
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1650 INLINE void
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1651 temp_set_point (position, buffer)
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1652 int position;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1653 struct buffer *buffer;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1654 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1655 buffer->text.pt = position;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1656 }
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1657
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1658 /* 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
1659 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
1660 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
1661
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1662 Lisp_Object
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1663 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
1664 register int position;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1665 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
1666 {
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1667 register INTERVAL interval;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1668 Lisp_Object prop, tem;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1669
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1670 if (NULL_INTERVAL_P (buffer->intervals))
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1671 return current_buffer->keymap;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1672
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1673 /* 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
1674 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
1675 abort ();
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1676
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1677 interval = find_interval (buffer->intervals, position);
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1678 prop = textget (interval->plist, Qlocal_map);
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1679 if (NILP (prop))
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1680 return current_buffer->keymap;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1681
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1682 /* Use the local map only if it is valid. */
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1683 tem = Fkeymapp (prop);
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1684 if (!NILP (tem))
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1685 return prop;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1686
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1687 return current_buffer->keymap;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1688 }
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1689
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1690 /* Call the modification hook functions in LIST, each with START and END. */
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1691
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1692 static void
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1693 call_mod_hooks (list, start, end)
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1694 Lisp_Object list, start, end;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1695 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1696 struct gcpro gcpro1;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1697 GCPRO1 (list);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1698 while (!NILP (list))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1699 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1700 call2 (Fcar (list), start, end);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1701 list = Fcdr (list);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1702 }
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1703 UNGCPRO;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1704 }
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1705
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1706 /* Check for read-only intervals and signal an error if we find one.
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1707 Then check for any modification hooks in the range START up to
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1708 (but not including) TO. Create a list of all these hooks in
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1709 lexicographic order, eliminating consecutive extra copies of the
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1710 same hook. Then call those hooks in order, with START and END - 1
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1711 as arguments. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1712
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1713 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1714 verify_interval_modification (buf, start, end)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1715 struct buffer *buf;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1716 int start, end;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1717 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1718 register INTERVAL intervals = buf->intervals;
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1719 register INTERVAL i, prev;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1720 Lisp_Object hooks;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1721 register Lisp_Object prev_mod_hooks;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1722 Lisp_Object mod_hooks;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1723 struct gcpro gcpro1;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1724
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1725 hooks = Qnil;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1726 prev_mod_hooks = Qnil;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1727 mod_hooks = Qnil;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1728
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1729 if (NULL_INTERVAL_P (intervals))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1730 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1731
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1732 if (start > end)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1733 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1734 int temp = start;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1735 start = end;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1736 end = temp;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1737 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1738
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1739 /* For an insert operation, check the two chars around the position. */
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1740 if (start == end)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1741 {
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1742 INTERVAL prev;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1743 Lisp_Object before, after;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1744
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1745 /* Set I to the interval containing the char after START,
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1746 and PREV to the interval containing the char before START.
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1747 Either one may be null. They may be equal. */
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1748 i = find_interval (intervals, start);
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1749
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1750 if (start == BUF_BEGV (buf))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1751 prev = 0;
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1752 else if (i->position == start)
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1753 prev = previous_interval (i);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1754 else if (i->position < start)
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1755 prev = i;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1756 if (start == BUF_ZV (buf))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1757 i = 0;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1758
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1759 /* If Vinhibit_read_only is set and is not a list, we can
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1760 skip the read_only checks. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1761 if (NILP (Vinhibit_read_only) || CONSP (Vinhibit_read_only))
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1762 {
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1763 /* If I and PREV differ we need to check for the read-only
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1764 property together with its stickyness. If either I or
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1765 PREV are 0, this check is all we need.
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1766 We have to take special care, since read-only may be
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1767 indirectly defined via the category property. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1768 if (i != prev)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1769 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1770 if (! NULL_INTERVAL_P (i))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1771 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1772 after = textget (i->plist, Qread_only);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1773
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1774 /* If interval I is read-only and read-only is
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1775 front-sticky, inhibit insertion.
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1776 Check for read-only as well as category. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1777 if (! NILP (after)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1778 && NILP (Fmemq (after, Vinhibit_read_only))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1779 && (! NILP (Fmemq (Qread_only,
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1780 textget (i->plist, Qfront_sticky)))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1781 || (NILP (textget_direct (i->plist, Qread_only))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1782 && ! NILP (Fmemq (Qcategory,
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1783 textget (i->plist,
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1784 Qfront_sticky))))))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1785 error ("Attempt to insert within read-only text");
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1786 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1787 else
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1788 after = Qnil;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1789 if (! NULL_INTERVAL_P (prev))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1790 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1791 before = textget (prev->plist, Qread_only);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1792
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1793 /* If interval PREV is read-only and read-only isn't
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1794 rear-nonsticky, inhibit insertion.
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1795 Check for read-only as well as category. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1796 if (! NILP (before)
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1797 && NILP (Fmemq (before, Vinhibit_read_only))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1798 && NILP (Fmemq (Qread_only,
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1799 textget (prev->plist, Qrear_nonsticky)))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1800 && (! NILP (textget_direct (prev->plist,Qread_only))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1801 || NILP (Fmemq (Qcategory,
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1802 textget (prev->plist,
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1803 Qrear_nonsticky)))))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1804 error ("Attempt to insert within read-only text");
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1805 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1806 else
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1807 before = Qnil;
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1808 }
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1809 else if (! NULL_INTERVAL_P (i))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1810 before = after = textget (i->plist, Qread_only);
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1811 if (! NULL_INTERVAL_P (i) && ! NULL_INTERVAL_P (prev))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1812 {
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1813 /* If I and PREV differ, neither of them has a sticky
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1814 read-only property. It only remains to check, whether
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1815 they have a common read-only property. */
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1816 if (! NILP (before) && EQ (before, after))
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1817 error ("Attempt to insert within read-only text");
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1818 }
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1819 }
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1820
4066
bb9478383bde (verify_interval_modification):
Richard M. Stallman <rms@gnu.org>
parents: 4005
diff changeset
1821 /* Run both insert hooks (just once if they're the same). */
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1822 if (!NULL_INTERVAL_P (prev))
4080
8200d631e3f3 (verify_interval_modification): Use Qinsert_in_front_hooks and
Richard M. Stallman <rms@gnu.org>
parents: 4066
diff changeset
1823 prev_mod_hooks = textget (prev->plist, Qinsert_behind_hooks);
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1824 if (!NULL_INTERVAL_P (i))
4080
8200d631e3f3 (verify_interval_modification): Use Qinsert_in_front_hooks and
Richard M. Stallman <rms@gnu.org>
parents: 4066
diff changeset
1825 mod_hooks = textget (i->plist, Qinsert_in_front_hooks);
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1826 GCPRO1 (mod_hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1827 if (! NILP (prev_mod_hooks))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1828 call_mod_hooks (prev_mod_hooks, make_number (start),
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1829 make_number (end));
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1830 UNGCPRO;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1831 if (! NILP (mod_hooks) && ! EQ (mod_hooks, prev_mod_hooks))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1832 call_mod_hooks (mod_hooks, make_number (start), make_number (end));
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1833 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1834 else
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1835 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1836 /* Loop over intervals on or next to START...END,
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1837 collecting their hooks. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1838
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1839 i = find_interval (intervals, start);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1840 do
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1841 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1842 if (! INTERVAL_WRITABLE_P (i))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1843 error ("Attempt to modify read-only text");
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1844
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1845 mod_hooks = textget (i->plist, Qmodification_hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1846 if (! NILP (mod_hooks) && ! EQ (mod_hooks, prev_mod_hooks))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1847 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1848 hooks = Fcons (mod_hooks, hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1849 prev_mod_hooks = mod_hooks;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1850 }
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1851
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1852 i = next_interval (i);
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1853 }
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1854 /* Keep going thru the interval containing the char before END. */
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1855 while (! NULL_INTERVAL_P (i) && i->position < end);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1856
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1857 GCPRO1 (hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1858 hooks = Fnreverse (hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1859 while (! EQ (hooks, Qnil))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1860 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1861 call_mod_hooks (Fcar (hooks), make_number (start),
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1862 make_number (end));
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1863 hooks = Fcdr (hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1864 }
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1865 UNGCPRO;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1866 }
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1867 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1868
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1869 /* 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
1870 TREE from START to START + LENGTH. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1871
1316
f09c5c6563b8 * intervals.c: `copy_intervals()' no longer static.
Joseph Arceneaux <jla@gnu.org>
parents: 1307
diff changeset
1872 INTERVAL
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1873 copy_intervals (tree, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1874 INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1875 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1876 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1877 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
1878 register int got, prevlen;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1879
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1880 if (NULL_INTERVAL_P (tree) || length <= 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1881 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1882
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1883 i = find_interval (tree, start);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1884 if (NULL_INTERVAL_P (i) || LENGTH (i) == 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1885 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1886
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1887 /* 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
1888 if ((start - i->position + 1 + length) < LENGTH (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1889 && DEFAULT_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1890 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1891
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1892 new = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1893 new->position = 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1894 got = (LENGTH (i) - (start - i->position));
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1895 new->total_length = length;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1896 copy_properties (i, new);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1897
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1898 t = new;
3490
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1899 prevlen = got;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1900 while (got < length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1901 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1902 i = next_interval (i);
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1903 t = split_interval_right (t, prevlen);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1904 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
1905 prevlen = LENGTH (i);
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1906 got += prevlen;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1907 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1908
5415
95882472f2da (rotate_right, rotate_left): Simplify
Richard M. Stallman <rms@gnu.org>
parents: 5250
diff changeset
1909 return balance_an_interval (new);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1910 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1911
4383
d4a36c1669e6 (adjust_intervals_for_insertion): Handle insertion
Richard M. Stallman <rms@gnu.org>
parents: 4243
diff changeset
1912 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1913
1288
b05982e82d93 Various comment changes.
Joseph Arceneaux <jla@gnu.org>
parents: 1211
diff changeset
1914 INLINE void
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1915 copy_intervals_to_string (string, buffer, position, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1916 Lisp_Object string, buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1917 int position, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1918 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1919 INTERVAL interval_copy = copy_intervals (XBUFFER (buffer)->intervals,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1920 position, length);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1921 if (NULL_INTERVAL_P (interval_copy))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1922 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1923
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1924 interval_copy->parent = (INTERVAL) string;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1925 XSTRING (string)->intervals = interval_copy;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1926 }
1301
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
1927
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
1928 #endif /* USE_TEXT_PROPERTIES */