GNU Octave  4.2.1
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-2017 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 "octave-config.h"
87 
88 #include "lo-traits.h"
89 
90 // The maximum number of entries in a MergeState's pending-runs stack.
91 // This is enough to sort arrays of size up to about
92 // 32 * phi ** MAX_MERGE_PENDING
93 // where phi ~= 1.618. 85 is ridiculously large enough, good for an array
94 // with 2**64 elements.
95 #define MAX_MERGE_PENDING 85
96 
97 // When we get into galloping mode, we stay there until both runs win less
98 // often than MIN_GALLOP consecutive times. See listsort.txt for more info.
99 #define MIN_GALLOP 7
100 
101 // Avoid malloc for small temp arrays.
102 #define MERGESTATE_TEMP_SIZE 1024
103 
104 // Enum for type of sort function
106 
107 template <typename T>
108 class
110 {
111 public:
112 
113  typedef bool (*compare_fcn_type) (typename ref_param<T>::type,
114  typename ref_param<T>::type);
115 
116  octave_sort (void);
117 
118  octave_sort (compare_fcn_type);
119 
120  ~octave_sort (void);
121 
122  void set_compare (compare_fcn_type comp) { compare = comp; }
123 
124  void set_compare (sortmode mode);
125 
126  // Sort an array in-place.
127  void sort (T *data, octave_idx_type nel);
128 
129  // Ditto, but also permute the passed indices (may not be valid indices).
130  void sort (T *data, octave_idx_type *idx, octave_idx_type nel);
131 
132  // Check whether an array is sorted.
133  bool is_sorted (const T *data, octave_idx_type nel);
134 
135  // Sort a matrix by rows, return a permutation
136  // vector.
137  void sort_rows (const T *data, octave_idx_type *idx,
138  octave_idx_type rows, octave_idx_type cols);
139 
140  // Determine whether a matrix (as a contiguous block) is sorted by rows.
141  bool is_sorted_rows (const T *data,
142  octave_idx_type rows, octave_idx_type cols);
143 
144  // Do a binary lookup in a sorted array.
145  octave_idx_type lookup (const T *data, octave_idx_type nel,
146  const T& value);
147 
148  // Ditto, but for an array.
149  void lookup (const T *data, octave_idx_type nel,
150  const T* values, octave_idx_type nvalues,
151  octave_idx_type *idx);
152 
153  // A linear merge of two sorted tables. rev indicates the second table is
154  // in reverse order.
155  void lookup_sorted (const T *data, octave_idx_type nel,
156  const T* values, octave_idx_type nvalues,
157  octave_idx_type *idx, bool rev = false);
158 
159  // Rearranges the array so that the elements with indices
160  // lo..up-1 are in their correct place.
161  void nth_element (T *data, octave_idx_type nel,
162  octave_idx_type lo, octave_idx_type up = -1);
163 
164  static bool ascending_compare (typename ref_param<T>::type,
165  typename ref_param<T>::type);
166 
167  static bool descending_compare (typename ref_param<T>::type,
168  typename ref_param<T>::type);
169 
170 private:
171 
172  // One MergeState exists on the stack per invocation of mergesort.
173  // It's just a convenient way to pass state around among the helper
174  // functions.
175  //
176  // DGB: This isn't needed with mergesort in a class, but it doesn't
177  // slow things up, and it is likely to make my life easier for any
178  // potential backporting of changes in the Python code.
179 
180  struct s_slice
181  {
183  };
184 
185  struct MergeState
186  {
187  MergeState (void)
188  : min_gallop (), a (0), ia (0), alloced (0), n (0)
189  { reset (); }
190 
191  ~MergeState (void)
192  { delete [] a; delete [] ia; }
193 
194  void reset (void)
195  { min_gallop = MIN_GALLOP; n = 0; }
196 
197  void getmem (octave_idx_type need);
198 
199  void getmemi (octave_idx_type need);
200 
201  // This controls when we get *into* galloping mode. It's
202  // initialized to MIN_GALLOP. merge_lo and merge_hi tend to nudge
203  // it higher for random data, and lower for highly structured
204  // data.
206 
207  // 'a' is temp storage to help with merges. It contains room for
208  // alloced entries.
209  T *a; // may point to temparray below
212 
213  // A stack of n pending runs yet to be merged. Run #i starts at
214  // address base[i] and extends for len[i] elements. It's always
215  // true (so long as the indices are in bounds) that
216  //
217  // pending[i].base + pending[i].len == pending[i+1].base
218  //
219  // so we could cut the storage for this, but it's a minor amount,
220  // and keeping all the info explicit simplifies the code.
222  struct s_slice pending[MAX_MERGE_PENDING];
223 
224  // No copying!
225 
226  MergeState (const MergeState&);
227 
228  MergeState& operator = (const MergeState&);
229  };
230 
231  compare_fcn_type compare;
232 
234 
235  template <typename Comp>
236  void binarysort (T *data, octave_idx_type nel,
237  octave_idx_type start, Comp comp);
238 
239  template <typename Comp>
240  void binarysort (T *data, octave_idx_type *idx, octave_idx_type nel,
241  octave_idx_type start, Comp comp);
242 
243  template <typename Comp>
244  octave_idx_type count_run (T *lo, octave_idx_type n, bool& descending,
245  Comp comp);
246 
247  template <typename Comp>
248  octave_idx_type gallop_left (T key, T *a, octave_idx_type n,
249  octave_idx_type hint, Comp comp);
250 
251  template <typename Comp>
252  octave_idx_type gallop_right (T key, T *a, octave_idx_type n,
253  octave_idx_type hint, Comp comp);
254 
255  template <typename Comp>
256  int merge_lo (T *pa, octave_idx_type na,
257  T *pb, octave_idx_type nb,
258  Comp comp);
259 
260  template <typename Comp>
261  int merge_lo (T *pa, octave_idx_type *ipa, octave_idx_type na,
262  T *pb, octave_idx_type *ipb, octave_idx_type nb,
263  Comp comp);
264 
265  template <typename Comp>
266  int merge_hi (T *pa, octave_idx_type na,
267  T *pb, octave_idx_type nb,
268  Comp comp);
269 
270  template <typename Comp>
271  int merge_hi (T *pa, octave_idx_type *ipa, octave_idx_type na,
272  T *pb, octave_idx_type *ipb, octave_idx_type nb,
273  Comp comp);
274 
275  template <typename Comp>
276  int merge_at (octave_idx_type i, T *data, Comp comp);
277 
278  template <typename Comp>
279  int merge_at (octave_idx_type i, T *data, octave_idx_type *idx, Comp comp);
280 
281  template <typename Comp>
282  int merge_collapse (T *data, Comp comp);
283 
284  template <typename Comp>
285  int merge_collapse (T *data, octave_idx_type *idx, Comp comp);
286 
287  template <typename Comp>
288  int merge_force_collapse (T *data, Comp comp);
289 
290  template <typename Comp>
291  int merge_force_collapse (T *data, octave_idx_type *idx, Comp comp);
292 
293  octave_idx_type merge_compute_minrun (octave_idx_type n);
294 
295  template <typename Comp>
296  void sort (T *data, octave_idx_type nel, Comp comp);
297 
298  template <typename Comp>
299  void sort (T *data, octave_idx_type *idx, octave_idx_type nel, Comp comp);
300 
301  template <typename Comp>
302  bool is_sorted (const T *data, octave_idx_type nel, Comp comp);
303 
304  template <typename Comp>
305  void sort_rows (const T *data, octave_idx_type *idx,
306  octave_idx_type rows, octave_idx_type cols,
307  Comp comp);
308 
309  template <typename Comp>
310  bool is_sorted_rows (const T *data, octave_idx_type rows,
311  octave_idx_type cols, Comp comp);
312 
313  template <typename Comp>
314  octave_idx_type lookup (const T *data, octave_idx_type nel,
315  const T& value, Comp comp);
316 
317  template <typename Comp>
318  void lookup (const T *data, octave_idx_type nel,
319  const T* values, octave_idx_type nvalues,
320  octave_idx_type *idx, Comp comp);
321 
322  template <typename Comp>
323  void lookup_sorted (const T *data, octave_idx_type nel,
324  const T* values, octave_idx_type nvalues,
325  octave_idx_type *idx, bool rev, Comp comp);
326 
327  template <typename Comp>
328  void nth_element (T *data, octave_idx_type nel,
330  Comp comp);
331 
332  // No copying!
333 
334  octave_sort (const octave_sort&);
335 
336  octave_sort& operator = (const octave_sort&);
337 };
338 
339 template <typename T>
340 class
341 vec_index
342 {
343 public:
344  T vec;
346 };
347 #endif
MergeState * ms
Definition: oct-sort.h:233
octave_idx_type len
Definition: oct-sort.h:182
octave_idx_type * ia
Definition: oct-sort.h:210
sortmode
Definition: oct-sort.h:105
Return the CPU time used by your Octave session The first output is the total time spent executing your process and is equal to the sum of second and third which are the number of CPU seconds spent executing in user mode and the number of CPU seconds spent executing in system mode
Definition: data.cc:6386
void set_compare(compare_fcn_type comp)
Definition: oct-sort.h:122
octave_idx_type lookup(const T *x, octave_idx_type n, T y)
octave_idx_type alloced
Definition: oct-sort.h:211
octave_idx_type indx
Definition: oct-sort.h:345
cell array If invoked with two or more scalar integer or a vector of integer values
Definition: ov-cell.cc:1205
calling an anonymous function involves an overhead quite comparable to the overhead of an m file function Passing a handle to a built in function is because the interpreter is not involved in the internal loop For a
Definition: cellfun.cc:398
compare_fcn_type compare
Definition: oct-sort.h:231
#define MAX_MERGE_PENDING
Definition: oct-sort.h:95
if_then_else< is_class_type< T >::no, T, T const & >::result type
Definition: lo-traits.h:118
octave::sys::time start
Definition: graphics.cc:11731
=val(i)}if ode{val(i)}occurs in table i
Definition: lookup.cc:239
OCTAVE_EXPORT octave_value_list or N dimensional array whose elements are all equal to the IEEE symbol zero divided by nd tex zero divided by nd ifnottex and any operation involving another NaN value(5+NaN).Note that NaN always compares not equal to NaN(NaN!
#define MIN_GALLOP
Definition: oct-sort.h:99
octave_idx_type n
Definition: oct-sort.h:221
octave_idx_type min_gallop
Definition: oct-sort.h:205