1 /*
2 * mzNumberLine.c --
3 *
4 * Implements datastructure that permits division of line into intervals
5 * (end points) are integers, and given any interger, allows (quick) access to
6 * the interval containing that integer.
7 *
8 * *********************************************************************
9 * * Copyright (C) 1988, 1990 Michael H. Arnold and the Regents of the *
10 * * University of California. *
11 * * Permission to use, copy, modify, and distribute this *
12 * * software and its documentation for any purpose and without *
13 * * fee is hereby granted, provided that the above copyright *
14 * * notice appear in all copies. The University of California *
15 * * makes no representations about the suitability of this *
16 * * software for any purpose. It is provided "as is" without *
17 * * express or implied warranty. Export of this software outside *
18 * * of the United States of America may require an export license. *
19 * *********************************************************************
20 */
21
22 #ifndef lint
23 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/mzrouter/mzNumLine.c,v 1.2 2010/10/22 15:02:15 tim Exp $";
24 #endif /* not lint */
25
26 /* -- includes -- */
27
28 #include <stdio.h>
29
30 #include "utils/magic.h"
31 #include "utils/geometry.h"
32 #include "utils/geofast.h"
33 #include "tiles/tile.h"
34 #include "utils/hash.h"
35 #include "database/database.h"
36 #include "utils/signals.h"
37 #include "textio/textio.h"
38 #include "windows/windows.h"
39 #include "dbwind/dbwind.h"
40 #include "utils/malloc.h"
41 #include "utils/list.h"
42 #include "debug/debug.h"
43 #include "textio/textio.h"
44 #include "utils/heap.h"
45 #include "mzrouter/mzrouter.h"
46 #include "mzrouter/mzInternal.h"
47
48
49 /*
50 * ----------------------------------------------------------------------------
51 *
52 * mzNLInit -
53 *
54 * Initial a number line.
55 *
56 * Results:
57 * None.
58 *
59 * Side effects:
60 * Allocs entires array and sets number line to the single interval
61 * from MINFINITY to INFINITY.
62 *
63 * ----------------------------------------------------------------------------
64 */
65
66 void
mzNLInit(nL,size)67 mzNLInit(nL, size)
68 NumberLine *nL;
69 int size; /*initial size of number line */
70 {
71 int *entries;
72 size = MAX(size, 2);
73
74 nL->nl_sizeAlloced = size;
75 nL->nl_sizeUsed = 2;
76
77 entries = (int *) mallocMagic((unsigned)(sizeof(int)*size));
78 entries[0] = MINFINITY;
79 entries[1] = INFINITY;
80
81 nL->nl_entries = entries;
82
83 return;
84 }
85
86
87 /*
88 * ----------------------------------------------------------------------------
89 *
90 * mzNLInsert -
91 *
92 * Add new division point to numberline.
93 *
94 * Results:
95 * None.
96 *
97 * Side effects:
98 * Modifiy number line, allocate larger entry array if necessary.
99 *
100 * ----------------------------------------------------------------------------
101 */
102
103 void
mzNLInsert(nL,x)104 mzNLInsert(nL,x)
105 NumberLine *nL;
106 int x; /* new point */
107 {
108
109 int lowI, highI;
110
111 /* find entries bounding x */
112 {
113 lowI = 0;
114 highI = nL->nl_sizeUsed - 1;
115
116
117 while(highI-lowI > 1)
118 {
119 int newI = lowI + (highI - lowI)/2;
120 int newV = nL->nl_entries[newI];
121
122 if(newV <= x)
123 {
124 lowI = newI;
125 }
126 if(newV >= x)
127 {
128 highI = newI;
129 }
130 }
131 }
132
133 /* if x is already an entry, just return */
134 if(lowI == highI)
135 {
136 return;
137 }
138
139 /* if number line is full, allocate twice as big an entry array */
140 if(nL->nl_sizeUsed == nL->nl_sizeAlloced)
141 {
142 int *newEntries;
143 int newSize;
144
145 /* allocate new entry array */
146 newSize = nL->nl_sizeUsed*2;
147 newEntries = (int *) mallocMagic(sizeof(int) * (unsigned)(newSize));
148
149 /* copy old entries to new */
150 {
151 int *sentinel = &(nL->nl_entries[nL->nl_sizeAlloced]);
152 int *source = nL->nl_entries;
153 int *target = newEntries;
154 while(source != sentinel)
155 {
156 *(target++) = *(source++);
157 }
158 }
159
160 /* free up old array */
161 freeMagic(nL->nl_entries);
162
163 /* update numberline */
164 nL->nl_sizeAlloced = newSize;
165 nL->nl_entries = newEntries;
166 }
167
168 /* move larger entries down one to make room */
169 {
170 int * sentinel = &((nL->nl_entries)[lowI]);
171 int * target = &((nL->nl_entries)[nL->nl_sizeUsed]);
172 int * source = target-1;
173
174 while(source!=sentinel)
175 {
176 *(target--) = *(source--);
177 }
178 }
179
180 /* insert new entry */
181 (nL->nl_entries)[highI] = x;
182
183 /* update entry count */
184 (nL->nl_sizeUsed)++;
185
186 /* and return */
187 return;
188 }
189
190
191 /*
192 * ----------------------------------------------------------------------------
193 *
194 * mzNLGetContainingInterval -
195 *
196 * Find interval containing x (by binary search)
197 *
198 * Results:
199 * Pointer to array of two ints bounding x.
200 *
201 * Side effects:
202 * None.
203 *
204 * ----------------------------------------------------------------------------
205 */
206
207 int *
mzNLGetContainingInterval(nL,x)208 mzNLGetContainingInterval(nL,x)
209 NumberLine *nL;
210 int x; /* new point */
211 {
212
213 int lowI, highI;
214
215 /* find entries bounding x */
216 {
217 lowI = 0;
218 highI = nL->nl_sizeUsed - 1;
219
220 while(highI-lowI > 1)
221 {
222 int newI = lowI + (highI - lowI)/2;
223 int newV = nL->nl_entries[newI];
224
225 if(newV <= x)
226 {
227 lowI = newI;
228 }
229 if(newV >= x)
230 {
231 highI = newI;
232 }
233 }
234 }
235
236 /* return pointer to bounding entries */
237 return &((nL->nl_entries)[lowI]);
238 }
239
240
241 /*
242 * ----------------------------------------------------------------------------
243 *
244 * mzNLClear -
245 *
246 * Clears numberline to single interval from MINFINITY to INFINITY.
247 *
248 * Results:
249 * None.
250 *
251 * Side effects:
252 * See above. CURRENTLY WE LEAVE THE ALLOCATED SIZE OF THE NUMBERLINE
253 * ALONE.
254 *
255 * ----------------------------------------------------------------------------
256 */
257
258 void
mzNLClear(nL)259 mzNLClear(nL)
260 NumberLine *nL;
261 {
262
263 nL->nl_entries[0] = MINFINITY;
264 nL->nl_entries[1] = INFINITY;
265 nL->nl_sizeUsed = 2;
266
267 return;
268 }
269