Mercurial > hg > octave-nkf
annotate liboctave/oct-sort.h @ 8725:d5af326a3ede
[mq]: sort-traits
| author | John W. Eaton <jwe@octave.org> |
|---|---|
| date | Thu, 12 Feb 2009 02:49:14 -0500 |
| parents | e9cb742df9eb |
| children | de16ebeef93d |
| rev | line source |
|---|---|
| 4851 | 1 /* |
| 7017 | 2 Copyright (C) 2003, 2004, 2005, 2006, 2007 David Bateman |
| 4851 | 3 |
| 4 This file is part of Octave. | |
| 5 | |
| 6 Octave is free software; you can redistribute it and/or modify it | |
| 7 under the terms of the GNU General Public License as published by the | |
| 7016 | 8 Free Software Foundation; either version 3 of the License, or (at your |
| 9 option) any later version. | |
| 4851 | 10 |
| 11 Octave is distributed in the hope that it will be useful, but WITHOUT | |
| 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 14 for more details. | |
| 15 | |
| 16 You should have received a copy of the GNU General Public License | |
| 7016 | 17 along with Octave; see the file COPYING. If not, see |
| 18 <http://www.gnu.org/licenses/>. | |
| 4851 | 19 |
| 20 Code stolen in large part from Python's, listobject.c, which itself had | |
| 21 no license header. However, thanks to Tim Peters for the parts of the | |
| 22 code I ripped-off. | |
| 23 | |
| 24 As required in the Python license the short description of the changes | |
| 25 made are | |
| 26 | |
| 27 * convert the sorting code in listobject.cc into a generic class, | |
| 28 replacing PyObject* with the type of the class T. | |
| 29 | |
| 30 The Python license is | |
| 31 | |
| 32 PSF LICENSE AGREEMENT FOR PYTHON 2.3 | |
| 33 -------------------------------------- | |
| 34 | |
| 35 1. This LICENSE AGREEMENT is between the Python Software Foundation | |
| 36 ("PSF"), and the Individual or Organization ("Licensee") accessing and | |
| 37 otherwise using Python 2.3 software in source or binary form and its | |
| 38 associated documentation. | |
| 39 | |
| 40 2. Subject to the terms and conditions of this License Agreement, PSF | |
| 41 hereby grants Licensee a nonexclusive, royalty-free, world-wide | |
| 42 license to reproduce, analyze, test, perform and/or display publicly, | |
| 43 prepare derivative works, distribute, and otherwise use Python 2.3 | |
| 44 alone or in any derivative version, provided, however, that PSF's | |
| 45 License Agreement and PSF's notice of copyright, i.e., "Copyright (c) | |
| 46 2001, 2002, 2003 Python Software Foundation; All Rights Reserved" are | |
| 47 retained in Python 2.3 alone or in any derivative version prepared by | |
| 48 Licensee. | |
| 49 | |
| 50 3. In the event Licensee prepares a derivative work that is based on | |
| 51 or incorporates Python 2.3 or any part thereof, and wants to make | |
| 52 the derivative work available to others as provided herein, then | |
| 53 Licensee hereby agrees to include in any such work a brief summary of | |
| 54 the changes made to Python 2.3. | |
| 55 | |
| 56 4. PSF is making Python 2.3 available to Licensee on an "AS IS" | |
| 57 basis. PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR | |
| 58 IMPLIED. BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND | |
| 59 DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS | |
| 60 FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON 2.3 WILL NOT | |
| 61 INFRINGE ANY THIRD PARTY RIGHTS. | |
| 62 | |
| 63 5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON | |
| 64 2.3 FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS | |
| 65 A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON 2.3, | |
| 66 OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF. | |
| 67 | |
| 68 6. This License Agreement will automatically terminate upon a material | |
| 69 breach of its terms and conditions. | |
| 70 | |
| 71 7. Nothing in this License Agreement shall be deemed to create any | |
| 72 relationship of agency, partnership, or joint venture between PSF and | |
| 73 Licensee. This License Agreement does not grant permission to use PSF | |
| 74 trademarks or trade name in a trademark sense to endorse or promote | |
| 75 products or services of Licensee, or any third party. | |
| 76 | |
| 77 8. By copying, installing or otherwise using Python 2.3, Licensee | |
| 78 agrees to be bound by the terms and conditions of this License | |
| 79 Agreement. | |
| 80 */ | |
| 81 | |
| 82 #if !defined (octave_sort_h) | |
| 83 #define octave_sort_h 1 | |
| 84 | |
| 8725 | 85 #include "lo-traits.h" |
| 86 | |
| 7234 | 87 // The maximum number of entries in a MergeState's pending-runs stack. |
| 88 // This is enough to sort arrays of size up to about | |
| 89 // 32 * phi ** MAX_MERGE_PENDING | |
| 90 // where phi ~= 1.618. 85 is ridiculously large enough, good for an array | |
| 91 // with 2**64 elements. | |
| 4851 | 92 #define MAX_MERGE_PENDING 85 |
| 93 | |
| 7234 | 94 // When we get into galloping mode, we stay there until both runs win less |
| 95 // often than MIN_GALLOP consecutive times. See listsort.txt for more info. | |
| 4851 | 96 #define MIN_GALLOP 7 |
| 97 | |
| 7234 | 98 // Avoid malloc for small temp arrays. |
| 4851 | 99 #define MERGESTATE_TEMP_SIZE 1024 |
| 100 | |
| 7433 | 101 // Enum for type of sort function |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
102 enum sortmode { UNSORTED = 0, ASCENDING, DESCENDING }; |
| 7433 | 103 |
| 4851 | 104 template <class T> |
| 105 class | |
| 106 octave_sort | |
| 107 { | |
| 4998 | 108 public: |
| 109 | |
| 8725 | 110 typedef bool (*compare_fcn_type) (typename ref_param<T>::type, |
| 111 typename ref_param<T>::type); | |
| 112 | |
| 4851 | 113 octave_sort (void); |
| 114 | |
| 8725 | 115 octave_sort (compare_fcn_type); |
| 4851 | 116 |
| 4998 | 117 ~octave_sort (void) { merge_freemem (); } |
| 118 | |
| 8725 | 119 void set_compare (compare_fcn_type comp) { compare = comp; } |
| 4851 | 120 |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
121 void set_compare (sortmode mode); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
122 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
123 // Sort an array in-place. |
| 8700 | 124 void sort (T *data, octave_idx_type nel); |
| 125 | |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
126 // Ditto, but also permute the passed indices (may not be valid indices). |
| 8700 | 127 void sort (T *data, octave_idx_type *idx, octave_idx_type nel); |
| 128 | |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
129 // Check whether an array is sorted. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
130 bool is_sorted (const T *data, octave_idx_type nel); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
131 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
132 // Sort a matrix by rows, return a permutation |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
133 // vector. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
134 void sort_rows (const T *data, octave_idx_type *idx, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
135 octave_idx_type rows, octave_idx_type cols); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
136 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
137 // Determine whether a matrix (as a contiguous block) is sorted by rows. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
138 bool is_sorted_rows (const T *data, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
139 octave_idx_type rows, octave_idx_type cols); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
140 |
| 8725 | 141 static bool ascending_compare (typename ref_param<T>::type, |
| 142 typename ref_param<T>::type); | |
| 143 | |
| 144 static bool descending_compare (typename ref_param<T>::type, | |
| 145 typename ref_param<T>::type); | |
| 4851 | 146 |
| 4998 | 147 private: |
| 148 | |
| 7234 | 149 // One MergeState exists on the stack per invocation of mergesort. |
| 150 // It's just a convenient way to pass state around among the helper | |
| 151 // functions. | |
| 152 // | |
| 153 // DGB: This isn't needed with mergesort in a class, but it doesn't | |
| 154 // slow things up, and it is likely to make my life easier for any | |
| 155 // potential backporting of changes in the Python code. | |
| 4851 | 156 |
| 157 struct s_slice | |
| 158 { | |
| 8700 | 159 octave_idx_type base, len; |
| 4851 | 160 }; |
| 161 | |
| 7234 | 162 struct MergeState |
| 4851 | 163 { |
| 7234 | 164 // This controls when we get *into* galloping mode. It's |
| 165 // initialized to MIN_GALLOP. merge_lo and merge_hi tend to nudge | |
| 166 // it higher for random data, and lower for highly structured | |
| 167 // data. | |
| 7433 | 168 octave_idx_type min_gallop; |
| 4851 | 169 |
| 7234 | 170 // 'a' is temp storage to help with merges. It contains room for |
| 171 // alloced entries. | |
| 172 T *a; // may point to temparray below | |
| 8700 | 173 octave_idx_type *ia; |
| 7433 | 174 octave_idx_type alloced; |
| 4851 | 175 |
| 7234 | 176 // A stack of n pending runs yet to be merged. Run #i starts at |
| 177 // address base[i] and extends for len[i] elements. It's always | |
| 178 // true (so long as the indices are in bounds) that | |
| 179 // | |
| 180 // pending[i].base + pending[i].len == pending[i+1].base | |
| 181 // | |
| 182 // so we could cut the storage for this, but it's a minor amount, | |
| 183 // and keeping all the info explicit simplifies the code. | |
| 7433 | 184 octave_idx_type n; |
| 4851 | 185 struct s_slice pending[MAX_MERGE_PENDING]; |
| 7234 | 186 }; |
| 4851 | 187 |
| 8725 | 188 compare_fcn_type compare; |
| 4851 | 189 |
| 190 MergeState ms; | |
| 191 | |
| 8700 | 192 |
| 193 template <class Comp> | |
| 194 void binarysort (T *data, octave_idx_type nel, | |
| 195 octave_idx_type start, Comp comp); | |
| 196 | |
| 197 template <class Comp> | |
| 198 void binarysort (T *data, octave_idx_type *idx, octave_idx_type nel, | |
| 199 octave_idx_type start, Comp comp); | |
| 4851 | 200 |
| 8700 | 201 template <class Comp> |
| 202 octave_idx_type count_run (T *lo, octave_idx_type n, bool& descending, Comp comp); | |
| 4851 | 203 |
| 8700 | 204 template <class Comp> |
| 205 octave_idx_type gallop_left (T key, T *a, octave_idx_type n, octave_idx_type hint, | |
| 206 Comp comp); | |
| 4851 | 207 |
| 8700 | 208 template <class Comp> |
| 209 octave_idx_type gallop_right (T key, T *a, octave_idx_type n, octave_idx_type hint, | |
| 210 Comp comp); | |
| 4851 | 211 |
| 7234 | 212 void merge_init (void); |
| 4851 | 213 |
| 7234 | 214 void merge_freemem (void); |
| 4851 | 215 |
| 7433 | 216 int merge_getmem (octave_idx_type need); |
| 4851 | 217 |
| 8700 | 218 int merge_getmemi (octave_idx_type need); |
| 219 | |
| 220 template <class Comp> | |
| 221 int merge_lo (T *pa, octave_idx_type na, | |
| 222 T *pb, octave_idx_type nb, | |
| 223 Comp comp); | |
| 4851 | 224 |
| 8700 | 225 template <class Comp> |
| 226 int merge_lo (T *pa, octave_idx_type *ipa, octave_idx_type na, | |
| 227 T *pb, octave_idx_type *ipb, octave_idx_type nb, | |
| 228 Comp comp); | |
| 229 | |
| 230 template <class Comp> | |
| 231 int merge_hi (T *pa, octave_idx_type na, | |
| 232 T *pb, octave_idx_type nb, | |
| 233 Comp comp); | |
| 4851 | 234 |
| 8700 | 235 template <class Comp> |
| 236 int merge_hi (T *pa, octave_idx_type *ipa, octave_idx_type na, | |
| 237 T *pb, octave_idx_type *ipb, octave_idx_type nb, | |
| 238 Comp comp); | |
| 239 | |
| 240 template <class Comp> | |
| 241 int merge_at (octave_idx_type i, T *data, | |
| 242 Comp comp); | |
| 4851 | 243 |
| 8700 | 244 template <class Comp> |
| 245 int merge_at (octave_idx_type i, T *data, octave_idx_type *idx, | |
| 246 Comp comp); | |
| 247 | |
| 248 template <class Comp> | |
| 249 int merge_collapse (T *data, Comp comp); | |
| 4851 | 250 |
| 8700 | 251 template <class Comp> |
| 252 int merge_collapse (T *data, octave_idx_type *idx, Comp comp); | |
| 253 | |
| 254 template <class Comp> | |
| 255 int merge_force_collapse (T *data, Comp comp); | |
| 256 | |
| 257 template <class Comp> | |
| 258 int merge_force_collapse (T *data, octave_idx_type *idx, Comp comp); | |
| 4851 | 259 |
| 7433 | 260 octave_idx_type merge_compute_minrun (octave_idx_type n); |
| 8700 | 261 |
| 262 template <class Comp> | |
| 263 void sort (T *data, octave_idx_type nel, Comp comp); | |
| 264 | |
| 265 template <class Comp> | |
| 266 void sort (T *data, octave_idx_type *idx, octave_idx_type nel, Comp comp); | |
| 267 | |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
268 template <class Comp> |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
269 bool is_sorted (const T *data, octave_idx_type nel, Comp comp); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
270 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
271 template <class Comp> |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
272 void sort_rows (const T *data, octave_idx_type *idx, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
273 octave_idx_type rows, octave_idx_type cols, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
274 Comp comp); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
275 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
276 template <class Comp> |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
277 bool is_sorted_rows (const T *data, octave_idx_type rows, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
278 octave_idx_type cols, Comp comp); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
279 |
| 4851 | 280 }; |
| 281 | |
| 7433 | 282 template <class T> |
| 283 class | |
| 284 vec_index | |
| 285 { | |
| 286 public: | |
| 287 T vec; | |
| 288 octave_idx_type indx; | |
| 289 }; | |
| 4851 | 290 #endif |
| 291 | |
| 292 /* | |
| 293 ;;; Local Variables: *** | |
| 294 ;;; mode: C++ *** | |
| 295 ;;; End: *** | |
| 296 */ |