LAL  7.5.0.1-ec27e42
Sort.h
Go to the documentation of this file.
1 /*
2 * Copyright (C) 2007 Jolien Creighton
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with with program; see the file COPYING. If not, write to the
16 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
17 * MA 02110-1301 USA
18 */
19 
20 /*-----------------------------------------------------------------------
21  *
22  * File Name: Sort.h
23  *
24  * Author: Creighton, T. D.
25  *
26  *
27  *-----------------------------------------------------------------------*/
28 
29 #ifndef _SORT_H
30 #define _SORT_H
31 
32 #include <lal/LALStdlib.h>
33 
34 #ifdef __cplusplus
35 extern "C" {
36 #endif
37 
38 
39 /**
40  * \defgroup Sort_h Header Sort.h
41  * \ingroup lal_utilities
42  *
43  * \brief Provides routines for sorting, indexing, and ranking real vector elements.
44  *
45  * ### Synopsis ###
46  *
47  * \code
48  * #include <lal/Sort.h>
49  * \endcode
50  *
51  * ### Description ###
52  *
53  * ## Heap Sort ##
54  *
55  * These routines sort a vector <tt>*data</tt> (of type \c REAL4Vector
56  * or \c REAL8Vector) into ascending order using the in-place
57  * heapsort algorithm, or construct an index vector <tt>*index</tt> that
58  * indexes <tt>*data</tt> in increasing order (leaving <tt>*data</tt>
59  * unchanged), or construct a rank vector <tt>*rank</tt> that gives the
60  * rank order of the corresponding <tt>*data</tt> element.
61  *
62  * The relationship between sorting, indexing, and ranking can be a bit
63  * confusing. One way of looking at it is that the original array is
64  * ordered by index, while the sorted array is ordered by rank. The
65  * index array gives the index as a function of rank; i.e.\ if you're
66  * looking for a given rank (say the 0th, or smallest element), the index
67  * array tells you where to look it up in the unsorted array:
68  * \code
69  * unsorted_array[index[i]] = sorted_array[i]
70  * \endcode
71  * The rank array gives the rank as a function of index; i.e.\ it tells
72  * you where a given element in the unsorted array will appear in the
73  * sorted array:
74  * \code
75  * unsorted_array[j] = sorted_array[rank[j]]
76  * \endcode
77  * Clearly these imply the following relationships, which can be used to
78  * construct the index array from the rank array or vice-versa:
79  * \code
80  * index[rank[j]] = j
81  * rank[index[i]] = i
82  * \endcode
83  *
84  * The XLAL versions of these routines, \c XLALHeapSort(), \c XLALHeapIndex(),
85  * and \c XLALHeapRank(), perform the same operations but on arrays of
86  * \c nobj generic objects of size \c size pointed to by \c base and
87  * using the comparison function \c compar. The function \c compar() has
88  * the prototype
89  * \code
90  * int compar( void *p, const void *x, const void *y )
91  * \endcode
92  * and returns \f$-1\f$ if \f${\mathtt{x}}<{\mathtt{y}}\f$,
93  * \f$0\f$ if \f${\mathtt{x}}={\mathtt{y}}\f$,
94  * and \f$+1\f$ if \f${\mathtt{x}}>{\mathtt{y}}\f$. Here \c p (which may be NULL)
95  * is a pointer to additional data that may be used in the comparison function.
96  * This pointer is passed to the comparison function unchanged from the argument
97  * \c params of \c XLALHeapSort(), \c XLALHeapIndex(), and
98  * \c XLALHeapRank().
99  *
100  * ## Insertion Sort ##
101  *
102  * This is provided so the frame file cache handling code could have access
103  * to a sort algorithm that has the property that the original element
104  * order is preserved in the case of ties, a feature it relies on for
105  * proper treatment of cache files containing redundant fail-over copies.
106  * The C library's \c qsort() does not guarantee that order is preserved.
107  * This function is not fast, it just is what it is.
108  *
109  * ## Merge Sort ##
110  *
111  * This is also a stable sort algorithm, faster than insertion sort, but
112  * requires more temporary memory.
113  *
114  * ## Search Sorted ##
115  *
116  * The routine \c XLALIsSorted() returns \f$1\f$ if the array is sorted (in
117  * ascending order) or \f$0\f$ otherwise. To determine if an array is sorted
118  * in descending order, reverse the arguments in the \c compar routine.
119  *
120  * The routine \c XLALSearchSorted() returns the index in which the element
121  * given by \c key should be inserted in order to maintain the sort order.
122  *
123  * If \f${\mathtt{side}} < 0\f$ then the index to insert is on the left:
124  * \code
125  * a[i-1] < v <= a[i]
126  * \endcode
127  * If \f${\mathtt{side}} > 0\f$ then the index to insert is on the right:
128  * \code
129  * a[i-1] <= v < a[i]
130  * \endcode
131  * If \f${\mathtt{side}} = 0\f$ then the index is that of a matching element:
132  * \code
133  * a[i] == v
134  * \endcode
135  * or \f$-1\f$ is returned if there is no matching element.
136  *
137  * ### Algorithm ###
138  *
139  * ## Heap Sort ##
140  *
141  * These routines use the standard heap sort algorithm described in
142  * Sec. 8.3 of Ref. \cite ptvf1992 .
143  *
144  * The <tt>LALSHeapSort()</tt> and <tt>LALDHeapSort()</tt> routines are entirely
145  * in-place, with no auxiliary storage vector. The <tt>LALSHeapIndex()</tt>
146  * and <tt>LALDHeapIndex()</tt> routines are also technically in-place, but
147  * they require two input vectors (the data vector and the index vector),
148  * and leave the data vector unchanged. The <tt>LALSHeapRank()</tt> and
149  * <tt>LALDHeapRank()</tt> routines require two input vectors (the data and
150  * rank vectors), and also allocate a temporary index vector internally;
151  * these routines are therefore the most memory-intensive. All of these
152  * algorithms are \f$N\log_2(N)\f$ algorithms, regardless of the ordering of
153  * the initial dataset.
154  *
155  *
156  * Note: if you can use \c qsort(), you should.
157  *
158  */
159 /** @{ */
160 
161 /* Function prototypes. */
162 
163 /* ----- HeapSort.c ----- */
164 
165 /** \see See \ref Sort_h for documentation */
166 int XLALHeapSort( void *base, UINT4 nobj, UINT4 size, void *params,
167  int (*compar)(void *, const void *, const void *) );
168 
169 /** \see See \ref Sort_h for documentation */
170 int XLALHeapIndex( INT4 *indx, void *base, UINT4 nobj, UINT4 size, void *params,
171  int (*compar)(void *, const void *, const void *) );
172 
173 /** \see See \ref Sort_h for documentation */
174 int XLALHeapRank( INT4 *rank, void *base, UINT4 nobj, UINT4 size, void *params,
175  int (*compar)(void *, const void *, const void *) );
176 
177 /* ----- InsertionSort.c ----- */
178 
179 /** \see See \ref Sort_h for documentation */
180 int XLALInsertionSort( void *base, size_t nobj, size_t size, void *params,
181  int (*compar)(void *, const void *, const void *) );
182 
183 /* ----- MergeSort.c ----- */
184 
185 /** \see See \ref Sort_h for documentation */
186 int XLALMergeSort(void *base, size_t nobj, size_t size, void *params, int (*compar)(void *, const void *, const void *));
187 
188 /* ----- SearchSorted.c ----- */
189 
190 /** \see See \ref Sort_h for documentation */
191 int XLALIsSorted(void *base, size_t nobj, size_t size, void *params, int (*compar)(void *, const void *, const void *));
192 
193 /** \see See \ref Sort_h for documentation */
194 ssize_t XLALSearchSorted(const void *key, const void *base, size_t nobj, size_t size, void *params, int (*compar)(void *, const void *, const void *), int side);
195 
196 /** @} */
197 
198 #ifdef __cplusplus
199 }
200 #endif
201 
202 #endif /* _SORT_H */
UINT4
uint32_t UINT4
Four-byte unsigned integer.
Definition: LALAtomicDatatypes.h:59
INT4
int32_t INT4
Four-byte signed integer.
Definition: LALAtomicDatatypes.h:57
XLALHeapSort
int XLALHeapSort(void *base, UINT4 nobj, UINT4 size, void *params, int(*compar)(void *, const void *, const void *))
Definition: HeapSort.c:44
XLALMergeSort
int XLALMergeSort(void *base, size_t nobj, size_t size, void *params, int(*compar)(void *, const void *, const void *))
Definition: MergeSort.c:36
XLALIsSorted
int XLALIsSorted(void *base, size_t nobj, size_t size, void *params, int(*compar)(void *, const void *, const void *))
Definition: SearchSorted.c:17
XLALHeapRank
int XLALHeapRank(INT4 *rank, void *base, UINT4 nobj, UINT4 size, void *params, int(*compar)(void *, const void *, const void *))
Definition: HeapSort.c:152
XLALSearchSorted
ssize_t XLALSearchSorted(const void *key, const void *base, size_t nobj, size_t size, void *params, int(*compar)(void *, const void *, const void *), int side)
Definition: SearchSorted.c:31
XLALInsertionSort
int XLALInsertionSort(void *base, size_t nobj, size_t size, void *params, int(*compar)(void *, const void *, const void *))
Definition: InsertionSort.c:37
XLALHeapIndex
int XLALHeapIndex(INT4 *indx, void *base, UINT4 nobj, UINT4 size, void *params, int(*compar)(void *, const void *, const void *))
Definition: HeapSort.c:98