annotate src/intervals.c @ 1211:9f50cccf5963

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