UTILIB Reference Manual Version Version 1.0

00001 /*  _________________________________________________________________________
00002  *
00003  *  UTILIB: A utility library for developing portable C++ codes.
00004  *  Copyright (c) 2001, Sandia National Laboratories.
00005  *  This software is distributed under the GNU Lesser General Public License.
00006  *  For more information, see the README file in the top UTILIB directory.
00007  *  _________________________________________________________________________
00008  */
00009 
00016 #ifndef __sort_h
00017 #define __sort_h
00018 
00019 #if defined(__cplusplus) && defined(ANSI_HDRS)
00020 #include <cstdlib>
00021 #else
00022 #include <stdlib.h>
00023 #endif
00024 
00025 #ifdef __cplusplus
00026 #include "BasicArray.h"
00027 #include "compare.h"
00028 #endif
00029 #include "utilib_dll.h"
00030 #include "_generic.h"
00031 
00032 
00058 #if defined(SUNOS)
00059 #ifdef __GNUC__
00060 #define SORT_VOID       void
00061 #define COMP_VOID       const void
00062 #define SORT_RETVAL     int
00063 #define SORT_RETURN     0
00064 #define SORT_ARGS (SORT_VOID* base, long unsigned int nel, long unsigned int width, \
00065                                 compare_fn_type compare )
00066 #else
00067 #define SORT_VOID       void
00068 #define COMP_VOID       const void
00069 #define SORT_RETVAL     void
00070 #define SORT_RETURN     
00071 #define SORT_ARGS (SORT_VOID* base, int nel, int width, \
00072                                 compare_fn_type compare )
00073 #endif
00074 #endif
00075 
00076 #if defined(SGI)
00077 #ifdef __GNUC__
00078 #define SORT_VOID       void
00079 #define COMP_VOID       const void
00080 #define SORT_RETVAL     void
00081 #define SORT_RETURN     0
00082 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00083                                 compare_fn_type compare )
00084 #else
00085 #define SORT_VOID       void
00086 #define COMP_VOID       const void
00087 #define SORT_RETVAL     void
00088 #define SORT_RETURN     
00089 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00090                                 compare_fn_type compare )
00091 #endif
00092 #endif
00093 
00094 #if defined(SOLARIS)
00095 #if defined(__GNUC__)
00096 #define SORT_VOID       void
00097 #define COMP_VOID       const void
00098 #define SORT_RETVAL     void
00099 #define SORT_RETURN     
00100 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00101                                 compare_fn_type compare )
00102 #else
00103 #define SORT_VOID       void
00104 #define COMP_VOID       const void
00105 #define SORT_RETVAL     void
00106 #define SORT_RETURN     
00107 #define SORT_ARGS (SORT_VOID* base, unsigned int nel, unsigned int width, \
00108                                 compare_fn_type compare )
00109 #endif
00110 #endif
00111 
00112 #ifdef PARAGON
00113 #define SORT_VOID       void
00114 #define COMP_VOID       const void
00115 #define SORT_RETVAL     void
00116 #define SORT_RETURN     
00117 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00118                                 compare_fn_type compare )
00119 
00120 #elif COUGAR
00121 #define SORT_VOID       void
00122 #define COMP_VOID       const void
00123 #define SORT_RETVAL     void
00124 #define SORT_RETURN     
00125 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00126                                 compare_fn_type compare )
00127 
00128 #elif OSF
00129 #define SORT_VOID       void
00130 #define COMP_VOID       const void
00131 #define SORT_RETVAL     void
00132 #define SORT_RETURN     
00133 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00134                                 compare_fn_type compare )
00135 
00136 #elif CPLANT
00137 #define SORT_VOID       void
00138 #define COMP_VOID       const void
00139 #define SORT_RETVAL     void
00140 #define SORT_RETURN     
00141 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00142                                 compare_fn_type compare )
00143 
00144 #elif HPUX
00145 #define SORT_VOID       void
00146 #define COMP_VOID       const void
00147 #define SORT_RETVAL     void
00148 #define SORT_RETURN     
00149 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00150                                 compare_fn_type compare )
00151 
00152 #elif UWIN
00153 #ifdef __GNUC__
00154 /* TODO */
00155 #else
00156 #define SORT_VOID       void
00157 #define COMP_VOID       const void
00158 #define SORT_RETVAL     void
00159 #define SORT_RETURN     
00160 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00161                                 compare_fn_type compare )
00162 #endif
00163 
00164 #elif _MSC_VER
00165 #define SORT_VOID       void
00166 #define COMP_VOID       const void
00167 #define SORT_RETVAL     void
00168 #define SORT_RETURN     
00169 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00170                                 compare_fn_type compare )
00171 
00172 #elif LINUX
00173 #define SORT_VOID       void
00174 #define COMP_VOID       __const void
00175 #define SORT_RETVAL     void
00176 #define SORT_RETURN     
00177 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00178                                 compare_fn_type compare )
00179 
00180 #elif RS6K
00181 #define SORT_VOID       void
00182 #define COMP_VOID       const void
00183 #define SORT_RETVAL     void
00184 #define SORT_RETURN     
00185 #define SORT_ARGS (SORT_VOID* base, size_t nel, size_t width, \
00186                                 compare_fn_type compare )
00187 #endif
00188 
00189 #ifdef __cplusplus
00190 extern "C" {
00191 #endif
00192 
00193 typedef int (*compare_fn_type)(COMP_VOID*,COMP_VOID*);
00194 #ifdef __cplusplus
00195 };
00196 #endif
00197 
00199 #define SORT_FORM       SORT_RETVAL (*) SORT_ARGS
00200 
00201 
00202 #ifdef __cplusplus
00203 extern "C" {
00204 #endif
00205 
00207 SORT_RETVAL   ins_sort _( SORT_ARGS );
00209 SORT_RETVAL  heap_sort _( SORT_ARGS );
00211 SORT_RETVAL quick_sort _( SORT_ARGS );
00213 SORT_RETVAL merge_sort _( SORT_ARGS );
00215 SORT_RETVAL shell_sort _( SORT_ARGS );
00216 
00217 
00219 UTILIB_API int compare_int _((COMP_VOID*, COMP_VOID*));
00221 UTILIB_API int compare_float _((COMP_VOID*, COMP_VOID*));
00223 UTILIB_API int compare_double _((COMP_VOID*, COMP_VOID*));
00224 
00225 
00226 /* 
00227  * Misc sorting utilities
00228  */
00229 
00234 UTILIB_API void orderx _((int *ndx, int n, SORT_VOID* base, int width, 
00235         compare_fn_type compar, SORT_FORM));
00240 UTILIB_API void rank _((int* ndx_vec, int* rank_vec, int n));
00244 void order_k _((SORT_VOID* base, int nel, int width, compare_fn_type compar,
00245                                 int k));
00249 void order_ki _((SORT_VOID* base, int nel, int width,
00250                                 compare_fn_type compar, int k, int* ndx));
00251 
00252 #ifdef __cplusplus
00253 };
00254 
00255                         
00257 template <class T>
00258 inline UTILIB_API void sort(BasicArray<T>& array)
00259 { qsort((SORT_VOID*)(vec.data()), array.size(), (int)sizeof(T), compare); }
00260 
00261 
00262 
00264 template <class T>
00265 inline UTILIB_API void sort(BasicArray<T>& array, compare_fn_type compare_fn)
00266 { qsort((SORT_VOID*)(array.data()), array.size(), (int)sizeof(T), compare_fn); }
00267         
00268 
00270 template <class T>
00271 inline UTILIB_API void order(BasicArray<int>& ndx, const BasicArray<T>& v,
00272                                 compare_fn_type compare_fn)
00273 { 
00274 orderx(ndx.data(), ndx.size(), (SORT_VOID*)(v.data()), (int)sizeof(T),
00275                                         compare_fn,qsort);
00276 }
00277 
00278 
00280 template <class T>
00281 inline UTILIB_API void rank(BasicArray<int>& rvec, BasicArray<T>& v,
00282                                                 compare_fn_type compare_fn)
00283 {
00284 BasicArray<int> ovec(v.size());
00285 order(ovec, v, compare_fn);
00286 rank(ovec.data(), rvec.data(), rvec.size());
00287 }
00288 
00289 
00291 inline UTILIB_API void sort(BasicArray<int>& array)
00292 { sort(array, compare_int); }
00293 
00295 inline UTILIB_API void sort(BasicArray<float>& array)
00296 { sort(array, compare_float); }
00297 
00299 inline UTILIB_API void sort(BasicArray<double>& array)
00300 { sort(array, compare_double); }
00301 
00302 
00304 inline UTILIB_API void order(BasicArray<int>& ndx, BasicArray<int>& array)
00305 { order(ndx, array, compare_int); }
00306 
00308 inline UTILIB_API void order(BasicArray<int>& ndx, BasicArray<float>& array)
00309 { order(ndx, array, compare_float); }
00310 
00312 inline UTILIB_API void order(BasicArray<int>& ndx, BasicArray<double>& array)
00313 { order(ndx, array, compare_double); }
00314 
00315 
00317 inline UTILIB_API void rank(BasicArray<int>& ndx, BasicArray<int>& array)
00318 { rank(ndx, array, compare_int); }
00319 
00321 inline UTILIB_API void rank(BasicArray<int>& ndx, BasicArray<float>& array)
00322 { rank(ndx, array, compare_float); }
00323 
00325 inline UTILIB_API void rank(BasicArray<int>& ndx, BasicArray<double>& array)
00326 { rank(ndx, array, compare_double); }
00327 
00328 #endif
00329 #endif
sort.h
