Loading [MathJax]/extensions/TeX/AMSsymbols.js
LAL 7.7.0.1-5e288d3
•All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Modules Pages
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
35extern "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 */
166int 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 */
170int 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 */
174int 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 */
180int 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 */
186int 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 */
191int 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 */
194ssize_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