Mercurial > octave
annotate liboctave/util/oct-sort.h @ 21139:538b57866b90
consistently use "typename" intead of "class" in template declarations
* Object.h, QtHandlesUtils.cc, QtHandlesUtils.h, ToolBarButton.cc,
ToolBarButton.h, Cell.h, __lin_interpn__.cc, bitfcns.cc, bsxfun.cc,
cellfun.cc, data.cc, filter.cc, gcd.cc, graphics.cc, help.cc, kron.cc,
lookup.cc, ls-mat5.cc, ls-oct-text.h, lu.cc, max.cc, mgorth.cc,
oct-map.cc, oct-map.h, oct-stream.cc, oct-stream.h, octave-link.h,
pr-output.cc, profiler.h, schur.cc, sparse-xdiv.cc, sparse-xpow.cc,
sqrtm.cc, symtab.h, tril.cc, typecast.cc, variables.cc, xdiv.cc,
zfstream.h, __init_fltk__.cc, __magick_read__.cc, chol.cc, qr.cc,
ov-base-diag.cc, ov-base-diag.h, ov-base-int.cc, ov-base-int.h,
ov-base-mat.cc, ov-base-mat.h, ov-base-scalar.cc, ov-base-scalar.h,
ov-base-sparse.cc, ov-base-sparse.h, ov-base.h, ov-classdef.cc,
ov-int-traits.h, ov-java.h, ov-usr-fcn.h, ov.cc, ov.h,
op-dms-template.cc, oct-parse.in.yy, parse.h, pt-mat.cc, Array-b.cc,
Array.cc, Array.h, CDiagMatrix.h, CMatrix.h, CNDArray.h,
DiagArray2.cc, DiagArray2.h, MArray.cc, MArray.h, MDiagArray2.cc,
MDiagArray2.h, MSparse.cc, MSparse.h, MatrixType.cc, Sparse.cc,
Sparse.h, dDiagMatrix.h, dMatrix.h, dNDArray.h, fCDiagMatrix.h,
fCMatrix.h, fCNDArray.h, fDiagMatrix.h, fMatrix.h, fNDArray.h,
idx-vector.cc, idx-vector.h, intNDArray.cc, intNDArray.h, DET.h,
base-aepbal.h, base-lu.cc, base-lu.h, base-qr.cc, base-qr.h,
bsxfun-defs.cc, eigs-base.cc, lo-mappers.h, lo-specfun.cc,
lo-specfun.h, oct-convn.cc, oct-fftw.cc, oct-norm.cc,
sparse-base-chol.cc, sparse-base-chol.h, sparse-base-lu.cc,
sparse-base-lu.h, sparse-dmsolve.cc, mx-inlines.cc,
action-container.h, base-list.h, lo-traits.h, lo-utils.h,
oct-base64.h, oct-binmap.h, oct-cmplx.h, oct-inttypes.cc,
oct-inttypes.h, oct-locbuf.h, oct-refcount.h, oct-sort.cc, oct-sort.h:
Use "typename" instead of "class" in template declarations.
| author | John W. Eaton <jwe@octave.org> |
|---|---|
| date | Sun, 24 Jan 2016 13:50:04 -0500 |
| parents | f7084eae3318 |
| children | 1473547f50f5 |
| rev | line source |
|---|---|
| 4851 | 1 /* |
|
19697
4197fc428c7d
maint: Update copyright notices for 2015.
John W. Eaton <jwe@octave.org>
parents:
17822
diff
changeset
|
2 Copyright (C) 2003-2015 David Bateman |
| 11523 | 3 Copyright (C) 2009-2010 VZLU Prague |
| 4851 | 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 | |
| 7016 | 9 Free Software Foundation; either version 3 of the License, or (at your |
| 10 option) any later version. | |
| 4851 | 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 | |
| 7016 | 18 along with Octave; see the file COPYING. If not, see |
| 19 <http://www.gnu.org/licenses/>. | |
| 4851 | 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 | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
28 * convert the sorting code in listobject.cc into a generic class, |
| 4851 | 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 | |
|
20791
f7084eae3318
maint: Use Octave coding conventions for #if statements.
Rik <rik@octave.org>
parents:
19697
diff
changeset
|
83 #if ! defined (octave_oct_sort_h) |
|
17822
ebb3ef964372
maint: Use common #define syntax "octave_filename_h" in h_files.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
84 #define octave_oct_sort_h 1 |
| 4851 | 85 |
| 8725 | 86 #include "lo-traits.h" |
| 87 | |
| 7234 | 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. | |
| 4851 | 93 #define MAX_MERGE_PENDING 85 |
| 94 | |
| 7234 | 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. | |
| 4851 | 97 #define MIN_GALLOP 7 |
| 98 | |
| 7234 | 99 // Avoid malloc for small temp arrays. |
| 4851 | 100 #define MERGESTATE_TEMP_SIZE 1024 |
| 101 | |
| 7433 | 102 // Enum for type of sort function |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
103 enum sortmode { UNSORTED = 0, ASCENDING, DESCENDING }; |
| 7433 | 104 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
105 template <typename T> |
| 4851 | 106 class |
| 107 octave_sort | |
| 108 { | |
| 4998 | 109 public: |
| 110 | |
| 8725 | 111 typedef bool (*compare_fcn_type) (typename ref_param<T>::type, |
|
10312
cbc402e64d83
untabify liboctave header files
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
112 typename ref_param<T>::type); |
| 8725 | 113 |
| 4851 | 114 octave_sort (void); |
| 115 | |
| 8725 | 116 octave_sort (compare_fcn_type); |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
117 |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
118 ~octave_sort (void); |
| 4998 | 119 |
| 8725 | 120 void set_compare (compare_fcn_type comp) { compare = comp; } |
| 4851 | 121 |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
122 void set_compare (sortmode mode); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
123 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
124 // Sort an array in-place. |
| 8700 | 125 void sort (T *data, octave_idx_type nel); |
| 126 | |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
127 // Ditto, but also permute the passed indices (may not be valid indices). |
| 8700 | 128 void sort (T *data, octave_idx_type *idx, octave_idx_type nel); |
| 129 | |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
130 // Check whether an array is sorted. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
131 bool is_sorted (const T *data, octave_idx_type nel); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
132 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
133 // Sort a matrix by rows, return a permutation |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
134 // vector. |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
135 void sort_rows (const T *data, octave_idx_type *idx, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
136 octave_idx_type rows, octave_idx_type cols); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
137 |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
138 // Determine whether a matrix (as a contiguous block) is sorted by rows. |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
139 bool is_sorted_rows (const T *data, |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
140 octave_idx_type rows, octave_idx_type cols); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
141 |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
142 // Do a binary lookup in a sorted array. |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
143 octave_idx_type lookup (const T *data, octave_idx_type nel, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
144 const T& value); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
145 |
|
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
146 // Ditto, but for an array. |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
147 void lookup (const T *data, octave_idx_type nel, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
148 const T* values, octave_idx_type nvalues, |
|
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
149 octave_idx_type *idx); |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
150 |
|
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
151 // A linear merge of two sorted tables. rev indicates the second table is |
|
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
152 // in reverse order. |
|
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
153 void lookup_sorted (const T *data, octave_idx_type nel, |
|
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
154 const T* values, octave_idx_type nvalues, |
|
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
155 octave_idx_type *idx, bool rev = false); |
|
9341
9fd5c56ce57a
extend lookup capabilities
Jaroslav Hajek <highegg@gmail.com>
parents:
8920
diff
changeset
|
156 |
| 9725 | 157 // Rearranges the array so that the elements with indices |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
158 // lo..up-1 are in their correct place. |
| 9725 | 159 void nth_element (T *data, octave_idx_type nel, |
| 160 octave_idx_type lo, octave_idx_type up = -1); | |
| 161 | |
| 8725 | 162 static bool ascending_compare (typename ref_param<T>::type, |
|
10312
cbc402e64d83
untabify liboctave header files
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
163 typename ref_param<T>::type); |
| 8725 | 164 |
| 165 static bool descending_compare (typename ref_param<T>::type, | |
|
10312
cbc402e64d83
untabify liboctave header files
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
166 typename ref_param<T>::type); |
| 4851 | 167 |
| 4998 | 168 private: |
| 169 | |
| 7234 | 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. | |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
177 |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
178 struct s_slice |
| 4851 | 179 { |
| 8700 | 180 octave_idx_type base, len; |
| 4851 | 181 }; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
182 |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
183 struct MergeState |
| 4851 | 184 { |
|
11501
331fcc41ca23
data member initialization fixes
John W. Eaton <jwe@octave.org>
parents:
10521
diff
changeset
|
185 MergeState (void) |
|
331fcc41ca23
data member initialization fixes
John W. Eaton <jwe@octave.org>
parents:
10521
diff
changeset
|
186 : min_gallop (), a (0), ia (0), alloced (0), n (0) |
|
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
187 { reset (); } |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
188 |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
189 ~MergeState (void) |
|
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
190 { delete [] a; delete [] ia; } |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
191 |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
192 void reset (void) |
|
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
193 { min_gallop = MIN_GALLOP; n = 0; } |
|
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
194 |
|
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
195 void getmem (octave_idx_type need); |
|
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
196 |
|
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
197 void getmemi (octave_idx_type need); |
|
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8814
diff
changeset
|
198 |
| 7234 | 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. | |
| 7433 | 203 octave_idx_type min_gallop; |
| 4851 | 204 |
| 7234 | 205 // 'a' is temp storage to help with merges. It contains room for |
| 206 // alloced entries. | |
| 207 T *a; // may point to temparray below | |
| 8700 | 208 octave_idx_type *ia; |
| 7433 | 209 octave_idx_type alloced; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
210 |
| 7234 | 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. | |
| 7433 | 219 octave_idx_type n; |
| 4851 | 220 struct s_slice pending[MAX_MERGE_PENDING]; |
|
12122
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
221 |
|
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
222 // No copying! |
|
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
223 |
|
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
224 MergeState (const MergeState&); |
|
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
225 |
|
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
226 MergeState& operator = (const MergeState&); |
| 7234 | 227 }; |
| 4851 | 228 |
| 8725 | 229 compare_fcn_type compare; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
230 |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
231 MergeState *ms; |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
232 |
|
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
233 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
234 template <typename Comp> |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
235 void binarysort (T *data, octave_idx_type nel, |
|
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
236 octave_idx_type start, Comp comp); |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
237 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
238 template <typename Comp> |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
239 void binarysort (T *data, octave_idx_type *idx, octave_idx_type nel, |
|
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
240 octave_idx_type start, Comp comp); |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
241 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
242 template <typename Comp> |
|
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
243 octave_idx_type count_run (T *lo, octave_idx_type n, bool& descending, |
|
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
244 Comp comp); |
| 4851 | 245 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
246 template <typename Comp> |
|
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
247 octave_idx_type gallop_left (T key, T *a, octave_idx_type n, |
|
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
248 octave_idx_type hint, Comp comp); |
| 4851 | 249 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
250 template <typename Comp> |
|
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
251 octave_idx_type gallop_right (T key, T *a, octave_idx_type n, |
|
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
252 octave_idx_type hint, Comp comp); |
| 4851 | 253 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
254 template <typename Comp> |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
255 int merge_lo (T *pa, octave_idx_type na, |
| 8700 | 256 T *pb, octave_idx_type nb, |
| 257 Comp comp); | |
| 4851 | 258 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
259 template <typename Comp> |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
260 int merge_lo (T *pa, octave_idx_type *ipa, octave_idx_type na, |
| 8700 | 261 T *pb, octave_idx_type *ipb, octave_idx_type nb, |
| 262 Comp comp); | |
| 263 | |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
264 template <typename Comp> |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
265 int merge_hi (T *pa, octave_idx_type na, |
| 8700 | 266 T *pb, octave_idx_type nb, |
| 267 Comp comp); | |
| 4851 | 268 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
269 template <typename Comp> |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
270 int merge_hi (T *pa, octave_idx_type *ipa, octave_idx_type na, |
| 8700 | 271 T *pb, octave_idx_type *ipb, octave_idx_type nb, |
| 272 Comp comp); | |
| 273 | |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
274 template <typename Comp> |
|
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
275 int merge_at (octave_idx_type i, T *data, Comp comp); |
| 4851 | 276 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
277 template <typename Comp> |
|
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
278 int merge_at (octave_idx_type i, T *data, octave_idx_type *idx, Comp comp); |
| 8700 | 279 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
280 template <typename Comp> |
| 8700 | 281 int merge_collapse (T *data, Comp comp); |
| 4851 | 282 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
283 template <typename Comp> |
| 8700 | 284 int merge_collapse (T *data, octave_idx_type *idx, Comp comp); |
| 285 | |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
286 template <typename Comp> |
| 8700 | 287 int merge_force_collapse (T *data, Comp comp); |
| 288 | |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
289 template <typename Comp> |
| 8700 | 290 int merge_force_collapse (T *data, octave_idx_type *idx, Comp comp); |
| 4851 | 291 |
| 7433 | 292 octave_idx_type merge_compute_minrun (octave_idx_type n); |
| 8700 | 293 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
294 template <typename Comp> |
| 8700 | 295 void sort (T *data, octave_idx_type nel, Comp comp); |
| 296 | |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
297 template <typename Comp> |
| 8700 | 298 void sort (T *data, octave_idx_type *idx, octave_idx_type nel, Comp comp); |
| 299 | |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
300 template <typename Comp> |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
301 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
|
302 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
303 template <typename Comp> |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
304 void sort_rows (const T *data, octave_idx_type *idx, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
305 octave_idx_type rows, octave_idx_type cols, |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
306 Comp comp); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
307 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
308 template <typename Comp> |
|
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
309 bool is_sorted_rows (const T *data, octave_idx_type rows, |
|
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
310 octave_idx_type cols, Comp comp); |
|
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
311 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
312 template <typename Comp> |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
313 octave_idx_type lookup (const T *data, octave_idx_type nel, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
314 const T& value, Comp comp); |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
315 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
316 template <typename Comp> |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
317 void lookup (const T *data, octave_idx_type nel, |
|
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
318 const T* values, octave_idx_type nvalues, |
|
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
319 octave_idx_type *idx, Comp comp); |
|
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
320 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
321 template <typename Comp> |
|
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
322 void lookup_sorted (const T *data, octave_idx_type nel, |
|
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
323 const T* values, octave_idx_type nvalues, |
|
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
324 octave_idx_type *idx, bool rev, Comp comp); |
| 9725 | 325 |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
326 template <typename Comp> |
| 9725 | 327 void nth_element (T *data, octave_idx_type nel, |
| 328 octave_idx_type lo, octave_idx_type up, | |
| 329 Comp comp); | |
|
12122
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
330 |
|
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
331 // No copying! |
|
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
332 |
|
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
333 octave_sort (const octave_sort&); |
|
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
334 |
|
f4689107dd8c
Explicitly disallow copying in some classes.
Pascal Dupuis <Pascal.Dupuis@uclouvain.be>
parents:
11586
diff
changeset
|
335 octave_sort& operator = (const octave_sort&); |
| 4851 | 336 }; |
| 337 | |
|
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
20791
diff
changeset
|
338 template <typename T> |
| 7433 | 339 class |
| 340 vec_index | |
| 341 { | |
| 342 public: | |
| 343 T vec; | |
| 344 octave_idx_type indx; | |
| 345 }; | |
| 4851 | 346 #endif |