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