Debian Codegraph @

src/compare.c

raw
1 /*
2 * compare.c - comparison & sort
3 *
4 * Copyright (c) 2000-2024 Shiro Kawai <[email protected]>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the authors nor the names of its contributors
18 * may be used to endorse or promote products derived from this
19 * software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 */
33
34 #include <stdlib.h>
35 #define LIBGAUCHE_BODY
36 #include "gauche.h"
37 #include "gauche/priv/configP.h"
38
39 /*
40 * Comparator
41 */
42
43 /* TYPE and EQ are always a procedure.
44 COMPARE_OR_ORDER is compareFn for srfi-114, orderFn for srfi-128,
45 distinguished by SCM_COMPARATOR_SRFI_128 flag. It can be #f.
46 HASH can be #f.
47 */
48 ScmObj Scm_MakeComparator(ScmObj type, ScmObj eq,
49 ScmObj compare_or_order, ScmObj hash,
50 ScmObj name, u_long flags)
51 {
52 ScmComparator *c = SCM_NEW(ScmComparator);
53 SCM_SET_CLASS(c, &Scm_ComparatorClass);
54 c->name = name;
55 c->typeFn = type;
56 c->eqFn = eq;
57 if (flags & SCM_COMPARATOR_SRFI_128) {
58 c->compareFn = SCM_FALSE;
59 c->orderFn = compare_or_order;
60 } else {
61 c->compareFn = compare_or_order;
62 c->orderFn = SCM_FALSE;
63 }
64 c->hashFn = hash;
65 c->flags = flags;
66 return SCM_OBJ(c);
67 }
68
69 /*
70 * Generic compare.
71 */
72
73 int Scm_Compare(ScmObj x, ScmObj y)
74 {
75 /* Shortcut for typical case */
76 if (SCM_NUMBERP(x) && SCM_NUMBERP(y)) {
77 if (SCM_COMPNUMP(x) || SCM_COMPNUMP(y)) {
78 /* Scm_NumCmp can't compare complex numbers---it doesn't make
79 mathematical sense. But Scm_Compare is used just to order
80 items, it doesn't need to carry meaning. So here it goes.
81 We follow srfi-114 spec. */
82 /* TODO: If we ever introduce exact compnums, we should use
83 exact number first to compare, for Scm_GetDouble may lose
84 precision. */
85 /* TODO: Handle NaN. */
86 double xr = Scm_RealPart(x);
87 double yr = Scm_RealPart(y);
88 if (xr < yr) return -1;
89 if (xr > yr) return 1;
90 double xi = Scm_ImagPart(x);
91 double yi = Scm_ImagPart(y);
92 if (xi < yi) return -1;
93 if (xi > yi) return 1;
94 return 0;
95 } else {
96 return Scm_NumCmp(x, y);
97 }
98 }
99 if (SCM_STRINGP(x) && SCM_STRINGP(y))
100 return Scm_StringCmp(SCM_STRING(x), SCM_STRING(y));
101 if (SCM_CHARP(x) && SCM_CHARP(y))
102 return SCM_CHAR_VALUE(x) == SCM_CHAR_VALUE(y)? 0 :
103 SCM_CHAR_VALUE(x) < SCM_CHAR_VALUE(y)? -1 : 1;
104
105 /* Set cx, cy here, for we may jump to distinct_types later. */
106 ScmClass *cx = Scm_ClassOf(x);
107 ScmClass *cy = Scm_ClassOf(y);
108
109 /* srfi-114 default comparator behaviors*/
110 /* () is the smallest of all */
111 if (SCM_NULLP(x)) return (SCM_NULLP(y)? 0 : -1);
112 if (SCM_NULLP(y)) return (SCM_NULLP(x)? 0 : 1);
113 if (SCM_PAIRP(x)) {
114 if (SCM_PAIRP(y)) {
115 ScmObj px = x;
116 ScmObj py = y;
117 while (SCM_PAIRP(px) && SCM_PAIRP(py)) {
118 int r = Scm_Compare(SCM_CAR(px), SCM_CAR(py));
119 if (r != 0) return r;
120 px = SCM_CDR(px);
121 py = SCM_CDR(py);
122 }
123 return Scm_Compare(px, py);
124 }
125 goto distinct_types;
126 }
127 if (SCM_FALSEP(x)) {
128 if (SCM_FALSEP(y)) return 0;
129 if (SCM_TRUEP(y)) return -1;
130 goto distinct_types;
131 }
132 if (SCM_TRUEP(x)) {
133 if (SCM_FALSEP(y)) return 1;
134 if (SCM_TRUEP(y)) return 0;
135 goto distinct_types;
136 }
137
138 if (Scm_SubclassP(cx, cy)) {
139 if (cy->compare) return cy->compare(x, y, FALSE);
140 } else if (Scm_SubclassP(cy, cx)) {
141 if (cx->compare) return cx->compare(x, y, FALSE);
142 }
143 if (cx == cy) {
144 /* x and y are of the same type, and they can't be ordered. */
145 Scm_Error("can't compare %S and %S", x, y);
146 }
147
148 distinct_types:
149 /* x and y are of distinct types. Follow the srfi-114 rule:
150 () < pairs < booleans < chars < strings < symbols < numbers
151 < vectors < bytevectors < others
152 Note that we already eliminated NULL.
153 */
154 #define ELIMINATE(pred) \
155 do { \
156 if pred(x) return -1; \
157 if pred(y) return 1; \
158 } while (0)
159
160 ELIMINATE(SCM_PAIRP);
161 ELIMINATE(SCM_BOOLP);
162 ELIMINATE(SCM_CHARP);
163 ELIMINATE(SCM_STRINGP);
164 ELIMINATE(SCM_SYMBOLP);
165 ELIMINATE(SCM_NUMBERP);
166 ELIMINATE(SCM_VECTORP);
167
168 /* To conform srfi-114, we must order u8vector first. For the
169 consistency, we use this order:
170 u8 < s8 < u16 < s16 < u32 < s32 < u64 < s64 < f16 < f32 < f64
171 Unfortunately this doesn't match the order of ScmUVectorType,
172 so we need some tweak.
173 */
174 if (SCM_UVECTORP(x)) {
175 if (SCM_UVECTORP(y)) {
176 int tx = Scm_UVectorType(Scm_ClassOf(x));
177 int ty = Scm_UVectorType(Scm_ClassOf(y));
178 if (tx/2 < ty/2) return -1;
179 if (tx/2 > ty/2) return 1;
180 if (tx < SCM_UVECTOR_F16) {
181 /* x and y are either sNvector and uNvector with the same N.
182 The odd one is uNvector.
183 */
184 return (tx%2)? -1:1;
185 } else {
186 return (tx<ty)? -1:1;
187 }
188 }
189 return -1; /* y is other, so x comes first. */
190 } else if (SCM_UVECTORP(y)) {
191 return 1; /* x is other, so y comes first. */
192 }
193
194 /* Now we have two objects of different types, both are not the
195 types defined the order in srfi-114.
196 To achieve better stability, we first compare the name of the
197 classes and the names of their defining modules; if they are still
198 the same, we fall back to compare addresses.
199 Note: Addresses and defining modules may be changed when
200 the class is redefined.
201 */
202 ScmObj nx = cx->name;
203 ScmObj ny = cy->name;
204 int nr = Scm_Compare(nx, ny);
205 if (nr != 0) return nr;
206
207 ScmObj mx = cx->modules;
208 ScmObj my = cy->modules;
209 while (SCM_PAIRP(mx) && SCM_PAIRP(my)) {
210 SCM_ASSERT(SCM_MODULEP(SCM_CAR(mx)) && SCM_MODULEP(SCM_CAR(my)));
211 int r = Scm_Compare(SCM_MODULE(SCM_CAR(mx))->name,
212 SCM_MODULE(SCM_CAR(my))->name);
213 if (r != 0) return r;
214 mx = SCM_CDR(mx);
215 my = SCM_CDR(my);
216 }
217 if (SCM_PAIRP(mx)) return -1;
218 if (SCM_PAIRP(my)) return 1;
219
220 if (cx < cy) return -1;
221 else return 1;
222 }
223
224 /* NB: It turns out that calling back Scheme function from sort routine
225 is very inefficient and runs much slower than Scheme version, if
226 a Scheme comarison function is given.
227 So, as of 0.7.2, the C function is only used when a comparison
228 function is omitted. */
229
230 /*
231 * Basic function for sort family. An array pointed by elts will be
232 * destructively sorted. Cmpfn can be either an applicable Scheme
233 * object or #f. If it's an applicable object, two arguments x and y
234 * will be passed to it, and it must return an integer or a boolean
235 * value, such that:
236 *
237 * if (x < y), it may return a negative integer or #t.
238 * if (x == y), it may return 0 or #f.
239 * if (x > y), it may return a positive integer or #f.
240 *
241 * If cmpfn is #f, the first object's default compare method is used.
242 *
243 * Some notes:
244 * - We can't use libc's qsort, since it doesn't pass closure to cmpfn.
245 * - The naive Quicksort behaves too badly in the worst case.
246 * - The comparison operation is far more costly than exchange.
247 *
248 * The current implementation is hybrid of Quicksort and Heapsort. First
249 * the algorithm proceeds by Quicksort, but when it detects the recursion
250 * is too deep, it switches to Heapsort. See Knuth, The Art of Computer
251 * Programming Second Edition, Section 5.2.2, p.122.
252 */
253
254 /* Heap sort */
255 static inline void shift_up(ScmObj *elts, int root, int nelts,
256 int (*cmp)(ScmObj, ScmObj, ScmObj), ScmObj data)
257 {
258 int l = root+1, maxchild;
259 while (l*2 <= nelts) {
260 if (l*2 == nelts) {
261 maxchild = nelts-1;
262 } else if (cmp(elts[l*2-1], elts[l*2], data) < 0) {
263 maxchild = l*2;
264 } else {
265 maxchild = l*2-1;
266 }
267 if (cmp(elts[l-1], elts[maxchild], data) < 0) {
268 ScmObj tmp = elts[maxchild];
269 elts[maxchild] = elts[l-1];
270 elts[l-1] = tmp;
271 l = maxchild+1;
272 } else {
273 break;
274 }
275 }
276 }
277
278 static void sort_h(ScmObj *elts, int nelts,
279 int (*cmp)(ScmObj, ScmObj, ScmObj), ScmObj data)
280 {
281 for (int l=nelts/2-1; l>=0; l--) {
282 shift_up(elts, l, nelts, cmp, data);
283 }
284 for (int r=nelts-1; r>=1; r--) {
285 ScmObj tmp = elts[r];
286 elts[r] = elts[0];
287 elts[0] = tmp;
288 shift_up(elts, 0, r, cmp, data);
289 }
290 }
291
292 /* Quick sort */
293 static void sort_q(ScmObj *elts, int lo, int hi, int depth, int limit,
294 int (*cmp)(ScmObj, ScmObj, ScmObj), ScmObj data)
295 {
296 while (lo < hi) {
297 if (depth >= limit) {
298 sort_h(elts+lo, (hi-lo+1), cmp, data);
299 break;
300 } else {
301 int l = lo, r = hi;
302 ScmObj pivot = elts[lo];
303 while (l <= r) {
304 while (l <= r && cmp(elts[l], pivot, data) < 0) l++;
305 while (l <= r && cmp(pivot, elts[r], data) < 0) r--;
306 if (l > r) break;
307 ScmObj tmp = elts[l]; elts[l] = elts[r]; elts[r] = tmp;
308 l++;
309 r--;
310 }
311 if (lo < r) sort_q(elts, lo, r, depth+1, limit, cmp, data);
312 /* tail call to
313 sort_q(elts, l, hi, depth+1, limit, cmp, data); */
314 lo = l;
315 depth++;
316 }
317 }
318 }
319
320 static int cmp_scm(ScmObj x, ScmObj y, ScmObj fn)
321 {
322 ScmObj r = Scm_ApplyRec(fn, SCM_LIST2(x, y));
323 if (SCM_TRUEP(r) || (SCM_INTP(r) && SCM_INT_VALUE(r) < 0))
324 return -1;
325 else
326 return 1;
327 }
328
329 static int cmp_int(ScmObj x, ScmObj y, ScmObj dummy SCM_UNUSED)
330 {
331 return Scm_Compare(x, y);
332 }
333
334 void Scm_SortArray(ScmObj *elts, int nelts, ScmObj cmpfn SCM_UNUSED)
335 {
336 int limit, i;
337 if (nelts <= 1) return;
338 /* approximate 2*log2(nelts) */
339 for (i=nelts,limit=1; i > 0; limit++) {i>>=1;}
340 if (SCM_PROCEDUREP(cmpfn)) {
341 sort_q(elts, 0, nelts-1, 0, limit, cmp_scm, cmpfn);
342 } else {
343 sort_q(elts, 0, nelts-1, 0, limit, cmp_int, NULL);
344 }
345 }
346
347 /*
348 * higher-level fns
349 */
350
351 #define STATIC_SIZE 32
352
353 static ScmObj sort_list_int(ScmObj objs, ScmObj fn, int destructive)
354 {
355 ScmObj starray[STATIC_SIZE];
356 ScmSize len = STATIC_SIZE;
357 ScmObj *array = Scm_ListToArray(objs, &len, starray, TRUE);
358 Scm_SortArray(array, len, fn);
359 if (destructive) {
360 ScmObj cp = objs;
361 for (ScmSize i=0; i<len; i++, cp = SCM_CDR(cp)) {
362 Scm_SetCar(cp, array[i]);
363 }
364 return objs;
365 } else {
366 return Scm_ArrayToList(array, len);
367 }
368 }
369
370 ScmObj Scm_SortList(ScmObj objs, ScmObj fn)
371 {
372 return sort_list_int(objs, fn, FALSE);
373 }
374
375 ScmObj Scm_SortListX(ScmObj objs, ScmObj fn)
376 {
377 return sort_list_int(objs, fn, TRUE);
378 }
379
380 /*
381 * Initialization
382 */
383
384 void Scm__InitComparator()
385 {
386 /* code that requires initialization has been moved to
387 libcmp.scm and libomega.scm */
388 }