annotate src/intervals.c @ 4223:b044f6d3c4cb

(graft_intervals_into_buffer): When TREE is null, pass buffer as 2nd arg to reproduce_tree.
author Richard M. Stallman <rms@gnu.org>
date Thu, 22 Jul 1993 08:06:55 +0000
parents 84ea8ebc9858
children 23fe7f6c9ae4
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
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
8 the Free Software Foundation; either version 1, or (at your option)
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
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
41 #include "config.h"
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"
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
45
1301
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
46 /* The rest of the file is within this conditional. */
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
47 #ifdef USE_TEXT_PROPERTIES
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
48
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
49 /* Factor for weight-balancing interval trees. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
50 Lisp_Object interval_balance_threshold;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
51
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
52 /* Utility functions for intervals. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
53
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
54
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
55 /* Create the root interval of some object, a buffer or string. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
56
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
57 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
58 create_root_interval (parent)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
59 Lisp_Object parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
60 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
61 INTERVAL new = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
62
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
63 if (XTYPE (parent) == Lisp_Buffer)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
64 {
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
65 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
66 - BUF_BEG (XBUFFER (parent)));
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
67 XBUFFER (parent)->intervals = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
68 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
69 else if (XTYPE (parent) == Lisp_String)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
70 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
71 new->total_length = XSTRING (parent)->size;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
72 XSTRING (parent)->intervals = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
73 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
74
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
75 new->parent = (INTERVAL) parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
76 new->position = 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
77
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
78 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
79 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
80
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
81 /* Make the interval TARGET have exactly the properties of SOURCE */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
82
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
83 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
84 copy_properties (source, target)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
85 register INTERVAL source, target;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
86 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
87 if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
88 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
89
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
90 COPY_INTERVAL_CACHE (source, target);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
91 target->plist = Fcopy_sequence (source->plist);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
92 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
93
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
94 /* 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
95 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
96 is added to TARGET if TARGET has no such property as yet. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
97
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
98 static void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
99 merge_properties (source, target)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
100 register INTERVAL source, target;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
101 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
102 register Lisp_Object o, sym, val;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
103
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
104 if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
105 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
106
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
107 MERGE_INTERVAL_CACHE (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 o = source->plist;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
110 while (! EQ (o, Qnil))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
111 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
112 sym = Fcar (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
113 val = Fmemq (sym, target->plist);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
114
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
115 if (NILP (val))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
116 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
117 o = Fcdr (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
118 val = Fcar (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
119 target->plist = Fcons (sym, Fcons (val, target->plist));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
120 o = Fcdr (o);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
121 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
122 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
123 o = Fcdr (Fcdr (o));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
124 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
125 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
126
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
127 /* Return 1 if the two intervals have the same properties,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
128 0 otherwise. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
129
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
130 int
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
131 intervals_equal (i0, i1)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
132 INTERVAL i0, i1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
133 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
134 register Lisp_Object i0_cdr, i0_sym, i1_val;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
135 register i1_len;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
136
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
137 if (DEFAULT_INTERVAL_P (i0) && DEFAULT_INTERVAL_P (i1))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
138 return 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
139
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
140 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
141 return 0;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
142
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
143 i1_len = XFASTINT (Flength (i1->plist));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
144 if (i1_len & 0x1) /* Paranoia -- plists are always even */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
145 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
146 i1_len /= 2;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
147 i0_cdr = i0->plist;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
148 while (!NILP (i0_cdr))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
149 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
150 /* Lengths of the two plists were unequal */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
151 if (i1_len == 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
152 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
153
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
154 i0_sym = Fcar (i0_cdr);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
155 i1_val = Fmemq (i0_sym, i1->plist);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
156
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
157 /* i0 has something i1 doesn't */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
158 if (EQ (i1_val, Qnil))
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 and i1 both have sym, but it has different values in each */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
162 i0_cdr = Fcdr (i0_cdr);
3998
c0560357c84e Compare the values of text properties using EQ, not Fequal.
Jim Blandy <jimb@redhat.com>
parents: 3995
diff changeset
163 if (! EQ (i1_val, Fcar (i0_cdr)))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
164 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
165
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
166 i0_cdr = Fcdr (i0_cdr);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
167 i1_len--;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
168 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
169
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
170 /* Lengths of the two plists were unequal */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
171 if (i1_len > 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
172 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
173
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
174 return 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
175 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
176
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
177 static int icount;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
178 static int idepth;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
179 static int zero_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
180
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
181 /* 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
182 Pass FUNCTION two args: an interval, and ARG. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
183
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
184 void
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
185 traverse_intervals (tree, position, depth, function, arg)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
186 INTERVAL tree;
1412
6097878fbd46 * intervals.c (traverse_intervals): New parameter `depth'.
Joseph Arceneaux <jla@gnu.org>
parents: 1316
diff changeset
187 int position, depth;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
188 void (* function) ();
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
189 Lisp_Object 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 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
192 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
193
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
194 traverse_intervals (tree->left, position, depth + 1, function, arg);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
195 position += LEFT_TOTAL_LENGTH (tree);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
196 tree->position = position;
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
197 (*function) (tree, arg);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
198 position += LENGTH (tree);
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
199 traverse_intervals (tree->right, position, depth + 1, function, arg);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
200 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
201
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
202 #if 0
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
203 /* These functions are temporary, for debugging purposes only. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
204
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
205 INTERVAL search_interval, found_interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
206
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
207 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
208 check_for_interval (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
209 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
210 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
211 if (i == search_interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
212 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
213 found_interval = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
214 icount++;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
215 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
216 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
217
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
218 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
219 search_for_interval (i, tree)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
220 register INTERVAL i, tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
221 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
222 icount = 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
223 search_interval = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
224 found_interval = NULL_INTERVAL;
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
225 traverse_intervals (tree, 1, 0, &check_for_interval, Qnil);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
226 return found_interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
227 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
228
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
229 static void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
230 inc_interval_count (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
231 INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
232 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
233 icount++;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
234 if (LENGTH (i) == 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
235 zero_length++;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
236 if (depth > idepth)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
237 idepth = depth;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
238 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
239
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
240 int
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
241 count_intervals (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
242 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
243 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
244 icount = 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
245 idepth = 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
246 zero_length = 0;
1958
8bc716df45e3 (traverse_intervals): New arg ARG.
Richard M. Stallman <rms@gnu.org>
parents: 1412
diff changeset
247 traverse_intervals (i, 1, 0, &inc_interval_count, Qnil);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
248
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
249 return icount;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
250 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
251
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
252 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
253 root_interval (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
254 INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
255 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
256 register INTERVAL i = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
257
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
258 while (! ROOT_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
259 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
260
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
261 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
262 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
263 #endif
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
264
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
265 /* Assuming that a left child exists, perform the following operation:
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
266
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
267 A B
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
268 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
269 B => A
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
270 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
271 c c
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
272 */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
273
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
274 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
275 rotate_right (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
276 INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
277 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
278 INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
279 INTERVAL B = interval->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
280 int len = LENGTH (interval);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
281
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
282 /* Deal with any Parent of A; make it point to B. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
283 if (! ROOT_INTERVAL_P (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
284 if (AM_LEFT_CHILD (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
285 interval->parent->left = interval->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
286 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
287 interval->parent->right = interval->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
288 interval->left->parent = interval->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
289
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
290 /* B gets the same length as A, since it get A's position in the tree. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
291 interval->left->total_length = interval->total_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
292
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
293 /* B becomes the parent of A. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
294 i = interval->left->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
295 interval->left->right = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
296 interval->parent = interval->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
297
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
298 /* A gets c as left child. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
299 interval->left = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
300 if (! NULL_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
301 i->parent = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
302 interval->total_length = (len + LEFT_TOTAL_LENGTH (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
303 + RIGHT_TOTAL_LENGTH (interval));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
304
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
305 return B;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
306 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
307
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
308 /* Assuming that a right child exists, perform the following operation:
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
309
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
310 A B
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
311 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
312 B => A
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
313 / \ / \
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
314 c c
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
315 */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
316
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
317 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
318 rotate_left (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
319 INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
320 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
321 INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
322 INTERVAL B = interval->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
323 int len = LENGTH (interval);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
324
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
325 /* Deal with the parent of A. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
326 if (! ROOT_INTERVAL_P (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
327 if (AM_LEFT_CHILD (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
328 interval->parent->left = interval->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
329 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
330 interval->parent->right = interval->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
331 interval->right->parent = interval->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
332
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
333 /* B must have the same total length of A. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
334 interval->right->total_length = interval->total_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
335
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
336 /* Make B the parent of A */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
337 i = interval->right->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
338 interval->right->left = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
339 interval->parent = interval->right;
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 A point to c */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
342 interval->right = i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
343 if (! NULL_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
344 i->parent = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
345 interval->total_length = (len + LEFT_TOTAL_LENGTH (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
346 + RIGHT_TOTAL_LENGTH (interval));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
347
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
348 return B;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
349 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
350
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
351 /* 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
352 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
353 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
354 (second, lexicographically) is returned.
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
355
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
356 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
357 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
358 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
359 result.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
360
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
361 Note that this does not change the position of INTERVAL; if it is a root,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
362 it is still a root after this operation. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
363
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
364 INTERVAL
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
365 split_interval_right (interval, offset)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
366 INTERVAL interval;
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
367 int offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
368 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
369 INTERVAL new = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
370 int position = interval->position;
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
371 int new_length = LENGTH (interval) - offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
372
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
373 new->position = position + offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
374 new->parent = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
375
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
376 if (LEAF_INTERVAL_P (interval) || NULL_RIGHT_CHILD (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
377 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
378 interval->right = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
379 new->total_length = new_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
380
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
381 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
382 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
383
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
384 /* Insert the new node between INTERVAL and its right child. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
385 new->right = interval->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
386 interval->right->parent = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
387 interval->right = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
388
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
389 new->total_length = new_length + new->right->total_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
390
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
391 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
392 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
393
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
394 /* 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
395 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
396 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
397 (first, lexicographically) is returned.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
398
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
399 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
400 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
401 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
402 result.
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
403
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
404 Note that this does not change the position of INTERVAL; if it is a root,
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
405 it is still a root after this operation. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
406
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
407 INTERVAL
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
408 split_interval_left (interval, offset)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
409 INTERVAL interval;
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
410 int offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
411 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
412 INTERVAL new = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
413 int position = interval->position;
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
414 int new_length = offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
415
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
416 new->position = interval->position;
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
417 interval->position = interval->position + offset;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
418 new->parent = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
419
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
420 if (NULL_LEFT_CHILD (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
421 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
422 interval->left = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
423 new->total_length = new_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
424
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
425 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
426 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
427
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
428 /* Insert the new node between INTERVAL and its left child. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
429 new->left = interval->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
430 new->left->parent = new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
431 interval->left = new;
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
432 new->total_length = new_length + LEFT_TOTAL_LENGTH (new);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
433
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
434 return new;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
435 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
436
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
437 /* 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
438 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
439 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
440 the buffer, return the interval containing the last character.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
441
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
442 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
443 is updated in the interval found. Other functions (e.g., next_interval)
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
444 will update this cache based on the result of find_interval. */
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
445
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
446 INLINE INTERVAL
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
447 find_interval (tree, position)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
448 register INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
449 register int position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
450 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
451 /* 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
452 to POSITION. */
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
453 register int relative_position = position - BEG;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
454
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
455 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
456 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
457
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
458 if (relative_position > TOTAL_LENGTH (tree))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
459 abort (); /* Paranoia */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
460
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
461 while (1)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
462 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
463 if (relative_position < LEFT_TOTAL_LENGTH (tree))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
464 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
465 tree = tree->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
466 }
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
467 else if (! NULL_RIGHT_CHILD (tree)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
468 && relative_position >= (TOTAL_LENGTH (tree)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
469 - RIGHT_TOTAL_LENGTH (tree)))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
470 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
471 relative_position -= (TOTAL_LENGTH (tree)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
472 - RIGHT_TOTAL_LENGTH (tree));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
473 tree = tree->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
474 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
475 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
476 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
477 tree->position =
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
478 (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
479 + 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
480
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
481 return tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
482 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
483 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
484 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
485
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
486 /* Find the succeeding interval (lexicographically) to INTERVAL.
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
487 Sets the `position' field based on that of INTERVAL (see
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
488 find_interval). */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
489
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
490 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
491 next_interval (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
492 register INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
493 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
494 register INTERVAL i = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
495 register int next_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
496
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
497 if (NULL_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
498 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
499 next_position = interval->position + LENGTH (interval);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
500
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
501 if (! NULL_RIGHT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
502 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
503 i = i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
504 while (! NULL_LEFT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
505 i = i->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
506
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
507 i->position = next_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
508 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
509 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
510
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
511 while (! NULL_PARENT (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
512 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
513 if (AM_LEFT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
514 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
515 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
516 i->position = next_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
517 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
518 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
519
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
520 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
521 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
522
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
523 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
524 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
525
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
526 /* Find the preceding interval (lexicographically) to INTERVAL.
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
527 Sets the `position' field based on that of INTERVAL (see
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
528 find_interval). */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
529
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
530 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
531 previous_interval (interval)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
532 register INTERVAL interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
533 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
534 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
535 register position_of_previous;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
536
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
537 if (NULL_INTERVAL_P (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
538 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
539
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
540 if (! NULL_LEFT_CHILD (interval))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
541 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
542 i = interval->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
543 while (! NULL_RIGHT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
544 i = i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
545
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
546 i->position = interval->position - LENGTH (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
547 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
548 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
549
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
550 i = interval;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
551 while (! NULL_PARENT (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
552 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
553 if (AM_RIGHT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
554 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
555 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
556
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
557 i->position = interval->position - LENGTH (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
558 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
559 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
560 i = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
561 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
562
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
563 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
564 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
565
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
566 #if 0
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
567 /* Traverse a path down the interval tree TREE to the interval
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
568 containing POSITION, adjusting all nodes on the path for
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
569 an addition of LENGTH characters. Insertion between two intervals
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
570 (i.e., point == i->position, where i is second interval) means
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
571 text goes into second interval.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
572
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
573 Modifications are needed to handle the hungry bits -- after simply
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
574 finding the interval at position (don't add length going down),
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
575 if it's the beginning of the interval, get the previous interval
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
576 and check the hugry bits of both. Then add the length going back up
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
577 to the root. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
578
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
579 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
580 adjust_intervals_for_insertion (tree, position, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
581 INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
582 int position, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
583 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
584 register int relative_position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
585 register INTERVAL this;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
586
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
587 if (TOTAL_LENGTH (tree) == 0) /* Paranoia */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
588 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
589
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
590 /* If inserting at point-max of a buffer, that position
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
591 will be out of range */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
592 if (position > TOTAL_LENGTH (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
593 position = TOTAL_LENGTH (tree);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
594 relative_position = position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
595 this = tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
596
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
597 while (1)
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 (relative_position <= LEFT_TOTAL_LENGTH (this))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
600 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
601 this->total_length += length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
602 this = this->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
603 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
604 else if (relative_position > (TOTAL_LENGTH (this)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
605 - RIGHT_TOTAL_LENGTH (this)))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
606 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
607 relative_position -= (TOTAL_LENGTH (this)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
608 - RIGHT_TOTAL_LENGTH (this));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
609 this->total_length += length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
610 this = this->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
611 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
612 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
613 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
614 /* If we are to use zero-length intervals as buffer pointers,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
615 then this code will have to change. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
616 this->total_length += length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
617 this->position = LEFT_TOTAL_LENGTH (this)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
618 + position - relative_position + 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
619 return tree;
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 }
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
623 #endif
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
624
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
625 /* Effect an adjustment corresponding to the addition of LENGTH characters
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
626 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
627 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
628 LENGTH to them.
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
629
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
630 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
631 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
632 the interval which is "sticky".
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
633
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
634 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
635 interval. Another possibility would be to create a new interval for
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
636 this text, and make it have the merged properties of both ends. */
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
637
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
638 static INTERVAL
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
639 adjust_intervals_for_insertion (tree, position, length)
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
640 INTERVAL tree;
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
641 int position, length;
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
642 {
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
643 register INTERVAL i;
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
644
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
645 if (TOTAL_LENGTH (tree) == 0) /* Paranoia */
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
646 abort ();
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
647
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
648 /* 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
649 of range. Remember that buffer positions are 1-based. */
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
650 if (position > BEG + TOTAL_LENGTH (tree))
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
651 position = BEG + TOTAL_LENGTH (tree);
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
652
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
653 i = find_interval (tree, position);
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
654 /* If we are positioned between intervals, check the stickiness of
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
655 both of them. */
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
656 if (position == i->position
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
657 && position != BEG)
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
658 {
1307
b469633740b3 Fixed typos.
Joseph Arceneaux <jla@gnu.org>
parents: 1303
diff changeset
659 register INTERVAL prev = previous_interval (i);
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
660
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
661 /* If both intervals are sticky here, then default to the
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
662 left-most one. But perhaps we should create a new
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
663 interval here instead... */
3736
dea4ce3d7a4d (adjust_intervals_for_insertion): By default, copy
Richard M. Stallman <rms@gnu.org>
parents: 3734
diff changeset
664 if (END_STICKY_P (prev) || ! FRONT_STICKY_P (i))
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
665 i = prev;
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
666 }
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
667
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
668 while (! NULL_INTERVAL_P (i))
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
669 {
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
670 i->total_length += length;
1307
b469633740b3 Fixed typos.
Joseph Arceneaux <jla@gnu.org>
parents: 1303
diff changeset
671 i = i->parent;
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
672 }
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
673
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
674 return tree;
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
675 }
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
676
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
677 /* 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
678 into one subtree which is then returned. Caller is responsible for
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
679 storing the resulting subtree into its parent. */
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 delete_node (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
683 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
684 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
685 register INTERVAL migrate, this;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
686 register int migrate_amt;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
687
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
688 if (NULL_INTERVAL_P (i->left))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
689 return i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
690 if (NULL_INTERVAL_P (i->right))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
691 return i->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
692
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
693 migrate = i->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
694 migrate_amt = i->left->total_length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
695 this = i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
696 this->total_length += migrate_amt;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
697 while (! NULL_INTERVAL_P (this->left))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
698 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
699 this = this->left;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
700 this->total_length += migrate_amt;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
701 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
702 this->left = migrate;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
703 migrate->parent = this;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
704
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
705 return i->right;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
706 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
707
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
708 /* Delete interval I from its tree by calling `delete_node'
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
709 and properly connecting the resultant subtree.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
710
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
711 I is presumed to be empty; that is, no adjustments are made
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
712 for the length of I. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
713
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
714 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
715 delete_interval (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
716 register INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
717 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
718 register INTERVAL parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
719 int amt = LENGTH (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
720
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
721 if (amt > 0) /* Only used on zero-length intervals now. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
722 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
723
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
724 if (ROOT_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
725 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
726 Lisp_Object owner = (Lisp_Object) i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
727 parent = delete_node (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
728 if (! NULL_INTERVAL_P (parent))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
729 parent->parent = (INTERVAL) owner;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
730
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
731 if (XTYPE (owner) == Lisp_Buffer)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
732 XBUFFER (owner)->intervals = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
733 else if (XTYPE (owner) == Lisp_String)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
734 XSTRING (owner)->intervals = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
735 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
736 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
737
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
738 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
739 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
740
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
741 parent = i->parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
742 if (AM_LEFT_CHILD (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
743 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
744 parent->left = delete_node (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
745 if (! NULL_INTERVAL_P (parent->left))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
746 parent->left->parent = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
747 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
748 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
749 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
750 parent->right = delete_node (i);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
751 if (! NULL_INTERVAL_P (parent->right))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
752 parent->right->parent = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
753 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
754 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
755
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
756 /* 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
757 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
758 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
759 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
760
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
761 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
762 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
763 recursively on subtrees.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
764
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
765 Do this by recursing down TREE to the interval in question, and
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
766 deleting the appropriate amount of text. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
767
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
768 static int
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
769 interval_deletion_adjustment (tree, from, amount)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
770 register INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
771 register int from, amount;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
772 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
773 register int relative_position = from;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
774
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
775 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
776 return 0;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
777
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
778 /* Left branch */
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
779 if (relative_position < LEFT_TOTAL_LENGTH (tree))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
780 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
781 int subtract = interval_deletion_adjustment (tree->left,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
782 relative_position,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
783 amount);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
784 tree->total_length -= subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
785 return subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
786 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
787 /* Right branch */
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
788 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
789 - RIGHT_TOTAL_LENGTH (tree)))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
790 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
791 int subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
792
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
793 relative_position -= (tree->total_length
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
794 - RIGHT_TOTAL_LENGTH (tree));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
795 subtract = interval_deletion_adjustment (tree->right,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
796 relative_position,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
797 amount);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
798 tree->total_length -= subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
799 return subtract;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
800 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
801 /* Here -- this node */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
802 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
803 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
804 /* 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
805 int my_amount = ((tree->total_length
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
806 - RIGHT_TOTAL_LENGTH (tree))
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
807 - relative_position);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
808
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
809 if (amount > my_amount)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
810 amount = my_amount;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
811
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
812 tree->total_length -= amount;
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
813 if (LENGTH (tree) == 0)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
814 delete_interval (tree);
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
815
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
816 return amount;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
817 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
818
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
819 /* Never reach here */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
820 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
821
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
822 /* 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
823 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
824 text. The deletion is effected at position START (which is a
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
825 buffer position, i.e. origin 1). */
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
826
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
827 static void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
828 adjust_intervals_for_deletion (buffer, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
829 struct buffer *buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
830 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
831 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
832 register int left_to_delete = length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
833 register INTERVAL tree = buffer->intervals;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
834 register int deleted;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
835
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
836 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
837 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
838
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
839 if (start > BEG + TOTAL_LENGTH (tree)
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
840 || start + length > BEG + TOTAL_LENGTH (tree))
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
841 abort ();
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
842
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
843 if (length == TOTAL_LENGTH (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
844 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
845 buffer->intervals = NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
846 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
847 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
848
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
849 if (ONLY_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
850 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
851 tree->total_length -= length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
852 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
853 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
854
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
855 if (start > BEG + TOTAL_LENGTH (tree))
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
856 start = BEG + TOTAL_LENGTH (tree);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
857 while (left_to_delete > 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
858 {
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
859 left_to_delete -= interval_deletion_adjustment (tree, start - 1,
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
860 left_to_delete);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
861 tree = buffer->intervals;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
862 if (left_to_delete == tree->total_length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
863 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
864 buffer->intervals = NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
865 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
866 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
867 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
868 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
869
3591
507f64624555 Apply typo patches from Paul Eggert.
Jim Blandy <jimb@redhat.com>
parents: 3490
diff changeset
870 /* Make the adjustments necessary to the interval tree of BUFFER to
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
871 represent an addition or deletion of LENGTH characters starting
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
872 at position START. Addition or deletion is indicated by the sign
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
873 of LENGTH. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
874
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
875 INLINE void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
876 offset_intervals (buffer, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
877 struct buffer *buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
878 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
879 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
880 if (NULL_INTERVAL_P (buffer->intervals) || length == 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
881 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
882
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
883 if (length > 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
884 adjust_intervals_for_insertion (buffer->intervals, start, length);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
885 else
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
886 adjust_intervals_for_deletion (buffer, start, -length);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
887 }
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
888
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
889 /* Merge interval I with its lexicographic successor. The resulting
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
890 interval is returned, and has the properties of the original
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
891 successor. The properties of I are lost. I is removed from the
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
892 interval tree.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
893
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
894 IMPORTANT:
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
895 The caller must verify that this is not the last (rightmost)
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
896 interval. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
897
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
898 INTERVAL
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
899 merge_interval_right (i)
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
900 register INTERVAL i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
901 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
902 register int absorb = LENGTH (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
903 register INTERVAL successor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
904
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
905 /* Zero out this interval. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
906 i->total_length -= absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
907
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
908 /* Find the succeeding interval. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
909 if (! NULL_RIGHT_CHILD (i)) /* It's below us. Add absorb
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
910 as we descend. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
911 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
912 successor = i->right;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
913 while (! NULL_LEFT_CHILD (successor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
914 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
915 successor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
916 successor = successor->left;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
917 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
918
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
919 successor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
920 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
921 return successor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
922 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
923
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
924 successor = i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
925 while (! NULL_PARENT (successor)) /* It's above us. Subtract as
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
926 we ascend. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
927 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
928 if (AM_LEFT_CHILD (successor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
929 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
930 successor = successor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
931 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
932 return successor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
933 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
934
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
935 successor = successor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
936 successor->total_length -= absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
937 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
938
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
939 /* This must be the rightmost or last interval and cannot
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
940 be merged right. The caller should have known. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
941 abort ();
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
942 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
943
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
944 /* Merge interval I with its lexicographic predecessor. The resulting
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
945 interval is returned, and has the properties of the original predecessor.
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
946 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
947
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
948 IMPORTANT:
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
949 The caller must verify that this is not the first (leftmost) interval. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
950
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
951 INTERVAL
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
952 merge_interval_left (i)
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
953 register INTERVAL i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
954 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
955 register int absorb = LENGTH (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
956 register INTERVAL predecessor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
957
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
958 /* Zero out this interval. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
959 i->total_length -= absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
960
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
961 /* Find the preceding interval. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
962 if (! NULL_LEFT_CHILD (i)) /* It's below us. Go down,
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
963 adding ABSORB as we go. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
964 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
965 predecessor = i->left;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
966 while (! NULL_RIGHT_CHILD (predecessor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
967 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
968 predecessor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
969 predecessor = predecessor->right;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
970 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
971
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
972 predecessor->total_length += absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
973 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
974 return predecessor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
975 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
976
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
977 predecessor = i;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
978 while (! NULL_PARENT (predecessor)) /* It's above us. Go up,
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
979 subtracting ABSORB. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
980 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
981 if (AM_RIGHT_CHILD (predecessor))
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
982 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
983 predecessor = predecessor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
984 delete_interval (i);
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
985 return predecessor;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
986 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
987
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
988 predecessor = predecessor->parent;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
989 predecessor->total_length -= absorb;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
990 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
991
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
992 /* This must be the leftmost or first interval and cannot
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
993 be merged left. The caller should have known. */
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
994 abort ();
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
995 }
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
996
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
997 /* Make an exact copy of interval tree SOURCE which descends from
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
998 PARENT. This is done by recursing through SOURCE, copying
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
999 the current interval and its properties, and then adjusting
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1000 the pointers of the copy. */
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1001
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1002 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1003 reproduce_tree (source, parent)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1004 INTERVAL source, parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1005 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1006 register INTERVAL t = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1007
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1008 bcopy (source, t, INTERVAL_SIZE);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1009 copy_properties (source, t);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1010 t->parent = parent;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1011 if (! NULL_LEFT_CHILD (source))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1012 t->left = reproduce_tree (source->left, t);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1013 if (! NULL_RIGHT_CHILD (source))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1014 t->right = reproduce_tree (source->right, t);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1015
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1016 return t;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1017 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1018
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1019 #if 0
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1020 /* 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
1021
1189
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1022 /* Make a new interval of length LENGTH starting at START in the
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1023 group of intervals INTERVALS, which is actually an interval tree.
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1024 Returns the new interval.
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1025
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1026 Generate an error if the new positions would overlap an existing
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1027 interval. */
164176515d2a comment changes
Joseph Arceneaux <jla@gnu.org>
parents: 1164
diff changeset
1028
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1029 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1030 make_new_interval (intervals, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1031 INTERVAL intervals;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1032 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1033 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1034 INTERVAL slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1035
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1036 slot = find_interval (intervals, start);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1037 if (start + length > slot->position + LENGTH (slot))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1038 error ("Interval would overlap");
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1039
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1040 if (start == slot->position && length == LENGTH (slot))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1041 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1042
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1043 if (slot->position == start)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1044 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1045 /* New right node. */
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1046 split_interval_right (slot, length);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1047 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1048 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1049
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1050 if (slot->position + LENGTH (slot) == start + length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1051 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1052 /* New left node. */
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1053 split_interval_left (slot, LENGTH (slot) - length);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1054 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1055 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1056
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1057 /* 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
1058 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
1059 split_interval_right (slot, length);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1060 return slot;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1061 }
4005
da8962f65741 * intervals.c (find_interval): Doc fixes, computation of
Jim Blandy <jimb@redhat.com>
parents: 3998
diff changeset
1062 #endif
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1063
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1064 /* Insert the intervals of SOURCE into BUFFER at POSITION.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1065
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1066 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
1067 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
1068 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
1069 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
1070 shared.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1071
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1072 If the inserted text had no intervals associated, this function
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1073 simply returns -- offset_intervals should handle placing the
1164
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
1074 text in the correct interval, depending on the sticky bits.
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1075
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1076 If the inserted text had properties (intervals), then there are two
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1077 cases -- either insertion happened in the middle of some interval,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1078 or between two intervals.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1079
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1080 If the text goes into the middle of an interval, then new
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1081 intervals are created in the middle with only the properties of
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1082 the new text, *unless* the macro MERGE_INSERTIONS is true, in
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1083 which case the new text has the union of its properties and those
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1084 of the text into which it was inserted.
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1085
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1086 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
1087 had its appropriate sticky property set (front_sticky, rear_sticky),
adfaeccad01d entered into RCS
Joseph Arceneaux <jla@gnu.org>
parents: 1157
diff changeset
1088 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
1089 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
1090 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
1091 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
1092 only its properties, as if neither sticky property were set. Perhaps
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1093 we should consider merging all three sets of properties onto the new
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1094 text... */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1095
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1096 void
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1097 graft_intervals_into_buffer (source, position, buffer)
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1098 INTERVAL source;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1099 int position;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1100 struct buffer *buffer;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1101 {
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1102 register INTERVAL under, over, this, prev;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1103 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
1104 int middle;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1105
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1106 /* If the new text has no properties, it becomes part of whatever
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1107 interval it was inserted into. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1108 if (NULL_INTERVAL_P (source))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1109 return;
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 (NULL_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 /* The inserted text constitutes the whole buffer, so
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1114 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
1115 if ((BUF_Z (buffer) - BUF_BEG (buffer)) == TOTAL_LENGTH (source))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1116 {
4223
b044f6d3c4cb (graft_intervals_into_buffer): When TREE is null,
Richard M. Stallman <rms@gnu.org>
parents: 4135
diff changeset
1117 Lisp_Object buf;
b044f6d3c4cb (graft_intervals_into_buffer): When TREE is null,
Richard M. Stallman <rms@gnu.org>
parents: 4135
diff changeset
1118 XSET (buf, Lisp_Buffer, buffer);
b044f6d3c4cb (graft_intervals_into_buffer): When TREE is null,
Richard M. Stallman <rms@gnu.org>
parents: 4135
diff changeset
1119 buffer->intervals = reproduce_tree (source, buf);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1120 /* Explicitly free the old tree here. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1121
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1122 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1123 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1124
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1125 /* Create an interval tree in which to place a copy
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1126 of the intervals of the inserted string. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1127 {
1307
b469633740b3 Fixed typos.
Joseph Arceneaux <jla@gnu.org>
parents: 1303
diff changeset
1128 Lisp_Object buf;
b469633740b3 Fixed typos.
Joseph Arceneaux <jla@gnu.org>
parents: 1303
diff changeset
1129 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
1130 tree = create_root_interval (buf);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1131 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1132 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1133 else
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1134 if (TOTAL_LENGTH (tree) == TOTAL_LENGTH (source))
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1135 /* If the buffer contains only the new string, but
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1136 there was already some interval tree there, then it may be
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1137 some zero length intervals. Eventually, do something clever
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1138 about inserting properly. For now, just waste the old intervals. */
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1139 {
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1140 buffer->intervals = reproduce_tree (source, tree->parent);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1141 /* Explicitly free the old tree here. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1142
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1143 return;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1144 }
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1145 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1146 /* Paranoia -- the text has already been added, so this buffer
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1147 should be of non-zero length. */
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1148 if (TOTAL_LENGTH (tree) == 0)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1149 abort ();
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1150
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1151 this = under = find_interval (tree, position);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1152 if (NULL_INTERVAL_P (under)) /* Paranoia */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1153 abort ();
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1154 over = find_interval (source, 1);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1155
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1156 /* 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
1157 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
1158 then don't bother with it any more. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1159
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1160 if (position > under->position)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1161 {
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1162 INTERVAL end_unchanged
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1163 = 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
1164 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
1165 under->position = position;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1166 prev = 0;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1167 middle = 1;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1168 }
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1169 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1170 {
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1171 prev = previous_interval (under);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1172 if (prev && !END_STICKY_P (prev))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1173 prev = 0;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1174 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1175
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1176 /* Insertion is now at beginning of UNDER. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1177
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1178 /* The inserted text "sticks" to the interval `under',
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1179 which means it gets those properties. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1180 while (! NULL_INTERVAL_P (over))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1181 {
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1182 if (LENGTH (over) + 1 < LENGTH (under))
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1183 this = split_interval_left (under, LENGTH (over));
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1184 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1185 this = under;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1186 copy_properties (over, this);
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1187 /* Insertion at the end of an interval, PREV,
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1188 inherits from PREV if PREV is sticky at the end. */
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1189 if (prev && ! FRONT_STICKY_P (under)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1190 && MERGE_INSERTIONS (prev))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1191 merge_properties (prev, this);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1192 /* Maybe it inherits from the following interval
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1193 if that is sticky at the front. */
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1194 else if ((FRONT_STICKY_P (under) || middle)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1195 && MERGE_INSERTIONS (under))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1196 merge_properties (under, this);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1197 over = next_interval (over);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1198 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1199
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1200 buffer->intervals = balance_intervals (buffer->intervals);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1201 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1202 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1203
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1204 /* 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
1205 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
1206 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
1207
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1208 Lisp_Object
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1209 textget (plist, prop)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1210 Lisp_Object plist;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1211 register Lisp_Object prop;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1212 {
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1213 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
1214 fallback = Qnil;
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1215
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1216 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
1217 {
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1218 register Lisp_Object tem;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1219 tem = Fcar (tail);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1220 if (EQ (prop, tem))
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1221 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
1222 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
1223 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
1224 }
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1225
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1226 return fallback;
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1227 }
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1228
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1229 /* 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
1230 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
1231 move back to an ok place to display. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1232
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1233 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1234 set_point (position, buffer)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1235 register int position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1236 register struct buffer *buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1237 {
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1238 register INTERVAL to, from, toprev, fromprev, target;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1239 int buffer_point;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1240 register Lisp_Object obj;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1241 int backwards = (position < BUF_PT (buffer)) ? 1 : 0;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1242 int old_position = buffer->text.pt;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1243
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1244 if (position == buffer->text.pt)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1245 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1246
2779
857bb0f59668 * intervals.c (set_point): Check for point out of bounds before
Jim Blandy <jimb@redhat.com>
parents: 2090
diff changeset
1247 /* 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
1248 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
1249 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
1250 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
1251 abort ();
857bb0f59668 * intervals.c (set_point): Check for point out of bounds before
Jim Blandy <jimb@redhat.com>
parents: 2090
diff changeset
1252
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1253 if (NULL_INTERVAL_P (buffer->intervals))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1254 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1255 buffer->text.pt = position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1256 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1257 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1258
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1259 /* 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
1260 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
1261 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
1262 to = find_interval (buffer->intervals, position);
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1263 if (position == BUF_BEGV (buffer))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1264 toprev = 0;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1265 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
1266 toprev = previous_interval (to);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1267 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1268 toprev = to;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1269
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1270 buffer_point = (BUF_PT (buffer) == BUF_ZV (buffer)
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1271 ? 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
1272 : BUF_PT (buffer));
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1273
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1274 /* 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
1275 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
1276 Either one may be null. They may be equal. */
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1277 /* We could cache this and save time. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1278 from = find_interval (buffer->intervals, buffer_point);
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1279 if (from->position == BUF_BEGV (buffer))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1280 fromprev = 0;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1281 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
1282 fromprev = previous_interval (from);
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1283 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
1284 fromprev = from, from = 0;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1285 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1286 fromprev = from;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1287
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1288 /* 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
1289 if (to == from && toprev == fromprev && INTERVAL_VISIBLE_P (to))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1290 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1291 buffer->text.pt = position;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1292 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1293 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1294
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1295 /* If the new position is before an invisible character,
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1296 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
1297 while (! NULL_INTERVAL_P (to)
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1298 && ! INTERVAL_VISIBLE_P (to)
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1299 && ! DISPLAY_INVISIBLE_GLYPH (to))
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1300 {
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1301 toprev = to;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1302 to = next_interval (to);
3734
5ada670e1fd8 (set_point): When moving over invis chars,
Richard M. Stallman <rms@gnu.org>
parents: 3591
diff changeset
1303 if (NULL_INTERVAL_P (to))
5ada670e1fd8 (set_point): When moving over invis chars,
Richard M. Stallman <rms@gnu.org>
parents: 3591
diff changeset
1304 position = BUF_ZV (buffer);
5ada670e1fd8 (set_point): When moving over invis chars,
Richard M. Stallman <rms@gnu.org>
parents: 3591
diff changeset
1305 else
5ada670e1fd8 (set_point): When moving over invis chars,
Richard M. Stallman <rms@gnu.org>
parents: 3591
diff changeset
1306 position = to->position;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1307 }
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1308
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1309 buffer->text.pt = position;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1310
1288
b05982e82d93 Various comment changes.
Joseph Arceneaux <jla@gnu.org>
parents: 1211
diff changeset
1311 /* We run point-left and point-entered hooks here, iff the
b05982e82d93 Various comment changes.
Joseph Arceneaux <jla@gnu.org>
parents: 1211
diff changeset
1312 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
1313 (old_point, new_point) as arguments. */
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1314 if (! intervals_equal (from, to)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1315 || ! intervals_equal (fromprev, toprev))
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1316 {
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1317 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
1318
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1319 if (fromprev)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1320 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
1321 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1322 leave_after = Qnil;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1323 if (from)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1324 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
1325 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1326 leave_before = Qnil;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1327
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1328 if (toprev)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1329 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
1330 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1331 enter_after = Qnil;
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1332 if (to)
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1333 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
1334 else
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1335 enter_before = Qnil;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1336
1964
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1337 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
1338 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
1339 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
1340 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
1341
e6c49ff3a53c (intervals_equal): Handle one arg null and other not.
Richard M. Stallman <rms@gnu.org>
parents: 1958
diff changeset
1342 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
1343 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
1344 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
1345 call2 (enter_after, old_position, position);
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1346 }
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1347 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1348
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1349 /* Set point temporarily, without checking any text properties. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1350
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1351 INLINE void
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1352 temp_set_point (position, buffer)
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1353 int position;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1354 struct buffer *buffer;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1355 {
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1356 buffer->text.pt = position;
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1357 }
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1358
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1359 /* 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
1360 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
1361 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
1362
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1363 Lisp_Object
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1364 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
1365 register int position;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1366 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
1367 {
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1368 register INTERVAL interval;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1369 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
1370
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1371 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
1372 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
1373
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1374 /* Perhaps we should just change `position' to the limit. */
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1375 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
1376 abort ();
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1377
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1378 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
1379 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
1380 if (NILP (prop))
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1381 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
1382
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1383 /* 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
1384 tem = Fkeymapp (prop);
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1385 if (!NILP (tem))
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1386 return prop;
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1387
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1388 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
1389 }
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1390
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1391 /* 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
1392
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1393 static void
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1394 call_mod_hooks (list, start, end)
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1395 Lisp_Object list, start, end;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1396 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1397 struct gcpro gcpro1;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1398 GCPRO1 (list);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1399 while (!NILP (list))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1400 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1401 call2 (Fcar (list), start, end);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1402 list = Fcdr (list);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1403 }
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1404 UNGCPRO;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1405 }
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1406
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1407 /* 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
1408 Then check for any modification hooks in the range START up to
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1409 (but not including) TO. Create a list of all these hooks in
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1410 lexicographic order, eliminating consecutive extra copies of the
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1411 same hook. Then call those hooks in order, with START and END - 1
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1412 as arguments. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1413
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1414 void
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1415 verify_interval_modification (buf, start, end)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1416 struct buffer *buf;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1417 int start, end;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1418 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1419 register INTERVAL intervals = buf->intervals;
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1420 register INTERVAL i, prev;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1421 Lisp_Object hooks;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1422 register Lisp_Object prev_mod_hooks;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1423 Lisp_Object mod_hooks;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1424 struct gcpro gcpro1;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1425
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1426 hooks = Qnil;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1427 prev_mod_hooks = Qnil;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1428 mod_hooks = Qnil;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1429
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1430 if (NULL_INTERVAL_P (intervals))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1431 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1432
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1433 if (start > end)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1434 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1435 int temp = start;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1436 start = end;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1437 end = temp;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1438 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1439
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1440 /* 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
1441 if (start == end)
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1442 {
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1443 INTERVAL prev;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1444 Lisp_Object before, after;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1445
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1446 /* 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
1447 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
1448 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
1449 i = find_interval (intervals, start);
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1450
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1451 if (start == BUF_BEGV (buf))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1452 prev = 0;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1453 if (i->position == start)
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1454 prev = previous_interval (i);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1455 else if (i->position < start)
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1456 prev = i;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1457 if (start == BUF_ZV (buf))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1458 i = 0;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1459
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1460 if (NULL_INTERVAL_P (prev))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1461 {
3847
a58e981e2582 (verify_interval_modification): Don't just test
Richard M. Stallman <rms@gnu.org>
parents: 3736
diff changeset
1462 if (! INTERVAL_WRITABLE_P (i))
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1463 error ("Attempt to insert within read-only text");
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1464 }
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1465 else if (NULL_INTERVAL_P (i))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1466 {
3847
a58e981e2582 (verify_interval_modification): Don't just test
Richard M. Stallman <rms@gnu.org>
parents: 3736
diff changeset
1467 if (! INTERVAL_WRITABLE_P (prev))
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1468 error ("Attempt to insert within read-only text");
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1469 }
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1470 else
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1471 {
2090
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1472 before = textget (prev->plist, Qread_only);
c7e1308a7184 (set_point): Check invisibility of following character, not previous character.
Richard M. Stallman <rms@gnu.org>
parents: 2052
diff changeset
1473 after = textget (i->plist, Qread_only);
3847
a58e981e2582 (verify_interval_modification): Don't just test
Richard M. Stallman <rms@gnu.org>
parents: 3736
diff changeset
1474 if (! NILP (before) && EQ (before, after)
a58e981e2582 (verify_interval_modification): Don't just test
Richard M. Stallman <rms@gnu.org>
parents: 3736
diff changeset
1475 /* This checks Vinhibit_read_only properly
a58e981e2582 (verify_interval_modification): Don't just test
Richard M. Stallman <rms@gnu.org>
parents: 3736
diff changeset
1476 for the common value of the read-only property. */
a58e981e2582 (verify_interval_modification): Don't just test
Richard M. Stallman <rms@gnu.org>
parents: 3736
diff changeset
1477 && ! INTERVAL_WRITABLE_P (i))
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1478 error ("Attempt to insert within read-only text");
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1479 }
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1480
4066
bb9478383bde (verify_interval_modification):
Richard M. Stallman <rms@gnu.org>
parents: 4005
diff changeset
1481 /* 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
1482 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
1483 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
1484 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
1485 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
1486 GCPRO1 (mod_hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1487 if (! NILP (prev_mod_hooks))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1488 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
1489 make_number (end));
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1490 UNGCPRO;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1491 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
1492 call_mod_hooks (mod_hooks, make_number (start), make_number (end));
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1493 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1494 else
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1495 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1496 /* 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
1497 collecting their hooks. */
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1498
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1499 i = find_interval (intervals, start);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1500 do
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1501 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1502 if (! INTERVAL_WRITABLE_P (i))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1503 error ("Attempt to modify read-only text");
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1504
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1505 mod_hooks = textget (i->plist, Qmodification_hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1506 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
1507 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1508 hooks = Fcons (mod_hooks, hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1509 prev_mod_hooks = mod_hooks;
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1510 }
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1511
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1512 i = next_interval (i);
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1513 }
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1514 /* 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
1515 while (! NULL_INTERVAL_P (i) && i->position < end);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1516
2052
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1517 GCPRO1 (hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1518 hooks = Fnreverse (hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1519 while (! EQ (hooks, Qnil))
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1520 {
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1521 call_mod_hooks (Fcar (hooks), make_number (start),
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1522 make_number (end));
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1523 hooks = Fcdr (hooks);
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1524 }
48c83a34c005 (verify_interval_modification): Handle insertions
Richard M. Stallman <rms@gnu.org>
parents: 1964
diff changeset
1525 UNGCPRO;
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1526 }
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1527 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1528
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1529 /* Balance an interval node if the amount of text in its left and right
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1530 subtrees differs by more than the percentage specified by
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1531 `interval-balance-threshold'. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1532
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1533 static INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1534 balance_an_interval (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1535 INTERVAL i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1536 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1537 register int total_children_size = (LEFT_TOTAL_LENGTH (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1538 + RIGHT_TOTAL_LENGTH (i));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1539 register int threshold = (XFASTINT (interval_balance_threshold)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1540 * (total_children_size / 100));
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1541
3490
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1542 /* Balance within each side. */
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1543 balance_intervals (i->left);
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1544 balance_intervals (i->right);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1545
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1546 if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1547 && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold)
3490
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1548 {
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1549 i = rotate_right (i);
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1550 /* If that made it unbalanced the other way, take it back. */
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1551 if (RIGHT_TOTAL_LENGTH (i) > LEFT_TOTAL_LENGTH (i)
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1552 && (RIGHT_TOTAL_LENGTH (i) - LEFT_TOTAL_LENGTH (i)) > threshold)
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1553 return rotate_left (i);
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1554 return i;
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1555 }
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1556
3490
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1557 if (RIGHT_TOTAL_LENGTH (i) > LEFT_TOTAL_LENGTH (i)
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1558 && (RIGHT_TOTAL_LENGTH (i) - LEFT_TOTAL_LENGTH (i)) > threshold)
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1559 {
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1560 i = rotate_left (i);
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1561 if (LEFT_TOTAL_LENGTH (i) > RIGHT_TOTAL_LENGTH (i)
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1562 && (LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i)) > threshold)
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1563 return rotate_right (i);
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1564 return i;
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1565 }
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1566
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1567 return i;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1568 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1569
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1570 /* Balance the interval tree TREE. Balancing is by weight
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1571 (the amount of text). */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1572
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1573 INTERVAL
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1574 balance_intervals (tree)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1575 register INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1576 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1577 register INTERVAL new_tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1578
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1579 if (NULL_INTERVAL_P (tree))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1580 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1581
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1582 new_tree = tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1583 do
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1584 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1585 tree = new_tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1586 new_tree = balance_an_interval (new_tree);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1587 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1588 while (new_tree != tree);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1589
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1590 return new_tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1591 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1592
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1593 /* Produce an interval tree reflecting the intervals in
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1594 TREE from START to START + LENGTH. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1595
1316
f09c5c6563b8 * intervals.c: `copy_intervals()' no longer static.
Joseph Arceneaux <jla@gnu.org>
parents: 1307
diff changeset
1596 INTERVAL
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1597 copy_intervals (tree, start, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1598 INTERVAL tree;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1599 int start, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1600 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1601 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
1602 register int got, prevlen;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1603
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1604 if (NULL_INTERVAL_P (tree) || length <= 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1605 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1606
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1607 i = find_interval (tree, start);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1608 if (NULL_INTERVAL_P (i) || LENGTH (i) == 0)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1609 abort ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1610
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1611 /* If there is only one interval and it's the default, return nil. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1612 if ((start - i->position + 1 + length) < LENGTH (i)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1613 && DEFAULT_INTERVAL_P (i))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1614 return NULL_INTERVAL;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1615
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1616 new = make_interval ();
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1617 new->position = 1;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1618 got = (LENGTH (i) - (start - i->position));
1211
9f50cccf5963 See ChangeLog
Joseph Arceneaux <jla@gnu.org>
parents: 1189
diff changeset
1619 new->total_length = length;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1620 copy_properties (i, new);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1621
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1622 t = new;
3490
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1623 prevlen = got;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1624 while (got < length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1625 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1626 i = next_interval (i);
4135
84ea8ebc9858 * intervals.c (split_interval_left, split_interval_right): Change
Jim Blandy <jimb@redhat.com>
parents: 4080
diff changeset
1627 t = split_interval_right (t, prevlen);
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1628 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
1629 prevlen = LENGTH (i);
07b454ddc666 (copy_intervals): Don't adjust total_length at the end.
Richard M. Stallman <rms@gnu.org>
parents: 3333
diff changeset
1630 got += prevlen;
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1631 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1632
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1633 return balance_intervals (new);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1634 }
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1635
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1636 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1637
1288
b05982e82d93 Various comment changes.
Joseph Arceneaux <jla@gnu.org>
parents: 1211
diff changeset
1638 INLINE void
1157
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1639 copy_intervals_to_string (string, buffer, position, length)
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1640 Lisp_Object string, buffer;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1641 int position, length;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1642 {
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1643 INTERVAL interval_copy = copy_intervals (XBUFFER (buffer)->intervals,
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1644 position, length);
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1645 if (NULL_INTERVAL_P (interval_copy))
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1646 return;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1647
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1648 interval_copy->parent = (INTERVAL) string;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1649 XSTRING (string)->intervals = interval_copy;
a4a446feb297 Initial revision
Joseph Arceneaux <jla@gnu.org>
parents:
diff changeset
1650 }
1301
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
1651
5a27062b8b7f * intervals.c: Conditionalize all functions on
Joseph Arceneaux <jla@gnu.org>
parents: 1288
diff changeset
1652 #endif /* USE_TEXT_PROPERTIES */