Debian Codegraph @

src/gauche/compare.h

raw
1 /*
2 * compare.h - comparison & sort
3 *
4 * Copyright (c) 2014-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 #ifndef GAUCHE_COMPARE_H
35 #define GAUCHE_COMPARE_H
36
37
38 SCM_DECL_BEGIN
39
40 /* srfi-114/srfi-128 comparator */
41 struct ScmComparatorRec {
42 SCM_HEADER;
43 ScmObj name; /* debugging aid */
44 ScmObj typeFn; /* proc */
45 ScmObj eqFn; /* proc */
46 ScmObj compareFn; /* proc */
47 ScmObj hashFn; /* proc */
48 ScmObj orderFn; /* proc */
49 u_long flags;
50 };
51
52 /* Difference between srfi-114 and srfi-128:
53 srfi-114 uses (compare a b) => -1 (a<b), 0 (a=b) or 1 (a>b)
54 srfi-128 uses (order a b) => #t (a<b) or #f (a>=b)
55 We can emulate one by the other, but emulation has some overhead.
56 So we allow both, and try to use whichever provided to the
57 constructor. (We do emulate if comparator-comparison-procedure
58 is called on srfi-128-constructed comparator, etc.)
59
60 Flags:
61
62 SCM_COMPARATOR_NO_ORDER - The comparator can't order.
63 (neither compare fn nor order fn is given to the constructor;
64 note that compareFn and orderFn members have dummy procedure
65 in that case).
66
67 SCM_COMPARATOR_NO_HASH - The comparator can't hash.
68 (hash fn is not given to the constructor; note that hashFn member
69 has dummy procedure)
70
71 SCM_COMPARATOR_ANY_TYPE - The comparator can accept any Scheme object.
72 A small optimization to skip type tests.
73
74 SCM_COMPARATOR_USE_COMPARISON - Records the fact that #t is passed
75 to the equality-test in srfi-114 style constructor. We use compareFn
76 for the equality check.
77
78 SCM_COMPARATOR_SRFI_128 - Indicates this is srfi-128-style comparator,
79 so using orderFn is preferred to compareFn.
80 */
81 enum ScmComparatorFlags {
82 SCM_COMPARATOR_NO_ORDER = (1L<<0), /* 'compare' proc unavailable */
83 SCM_COMPARATOR_NO_HASH = (1L<<1), /* 'hash' proc unavailable */
84 SCM_COMPARATOR_ANY_TYPE = (1L<<2), /* type-test always returns #t */
85 SCM_COMPARATOR_USE_COMPARISON = (1L<<3), /* equality use comarison */
86 SCM_COMPARATOR_SRFI_128 = (1L<<4) /* srfi-128 style comparator */
87 };
88
89 SCM_CLASS_DECL(Scm_ComparatorClass);
90 #define SCM_CLASS_COMPARATOR (&Scm_ComparatorClass)
91 #define SCM_COMPARATOR(obj) ((ScmComparator*)(obj))
92 #define SCM_COMPARATORP(obj) SCM_XTYPEP(obj, SCM_CLASS_COMPARATOR)
93
94 SCM_EXTERN ScmObj Scm_MakeComparator(ScmObj type, ScmObj eq,
95 ScmObj compare_or_order, ScmObj hash,
96 ScmObj name, u_long flags);
97 SCM_EXTERN ScmObj Scm_ComparatorComparisonProcedure(ScmComparator *);
98 SCM_EXTERN ScmObj Scm_ComparatorOrderingPredicate(ScmComparator *);
99 SCM_EXTERN ScmObj Scm_ComparatorHashFunction(ScmComparator *);
100
101 /* Other genreic utilities */
102 SCM_EXTERN int Scm_Compare(ScmObj x, ScmObj y);
103 SCM_EXTERN void Scm_SortArray(ScmObj *elts, int nelts, ScmObj cmpfn);
104 SCM_EXTERN ScmObj Scm_SortList(ScmObj objs, ScmObj fn);
105 SCM_EXTERN ScmObj Scm_SortListX(ScmObj objs, ScmObj fn);
106
107
108 SCM_DECL_END
109
110 #endif /*GAUCHE_COMPARE_H*/