Mercurial > octave
annotate liboctave/util/oct-sort.cc @ 33248:7f73e4805a1f
replace calls to assert with liboctave_panic functions liboctave
* lo-error.h (liboctave_panic_impossible, liboctave_panic_if,
liboctave_panic_unless): New macros.
Replace all calls to assert with panic_if, panic_impossible, or
panic_unless as appropriate. Include "lo-error.h" as needed. Don't
include <cassert>. Affected files: Array-base.cc, Array-util.cc,
Array.h, CSparse.cc, DiagArray2.cc, 1 DiagArray2.h, Sparse.cc,
Sparse.h, dim-vector.h, idx-vector.cc, idx-vector.h, CollocWt.cc,
Quad.cc, oct-rand.cc, qrp.cc, svd.cc, Sparse-perm-op-defs.h, and
oct-sort.cc.
author | John W. Eaton <jwe@octave.org> |
---|---|
date | Sun, 24 Mar 2024 18:12:34 -0400 |
parents | 2e484f9f1f18 |
children |
rev | line source |
---|---|
27923
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
1 //////////////////////////////////////////////////////////////////////// |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
2 // |
32632
2e484f9f1f18
maint: update Octave Project Developers copyright for the new year
John W. Eaton <jwe@octave.org>
parents:
32590
diff
changeset
|
3 // Copyright (C) 2003-2024 The Octave Project Developers |
27923
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
4 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
5 // See the file COPYRIGHT.md in the top-level directory of this |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
6 // distribution or <https://octave.org/copyright/>. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
7 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
8 // This file is part of Octave. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
9 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
10 // Octave is free software: you can redistribute it and/or modify it |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
11 // under the terms of the GNU General Public License as published by |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
12 // the Free Software Foundation, either version 3 of the License, or |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
13 // (at your option) any later version. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
14 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
15 // Octave is distributed in the hope that it will be useful, but |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
16 // WITHOUT ANY WARRANTY; without even the implied warranty of |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
18 // GNU General Public License for more details. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
19 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
20 // You should have received a copy of the GNU General Public License |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
21 // along with Octave; see the file COPYING. If not, see |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
22 // <https://www.gnu.org/licenses/>. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
23 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
24 // Code stolen in large part from Python's, listobject.c, which itself had |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
25 // no license header. However, thanks to Tim Peters for the parts of the |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
26 // code I ripped-off. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
27 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
28 // As required in the Python license the short description of the changes |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
29 // made are |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
30 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
31 // * convert the sorting code in listobject.cc into a generic class, |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
32 // replacing PyObject* with the type of the class T. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
33 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
34 // * replaced usages of malloc, free, memcpy and memmove by standard C++ |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
35 // new [], delete [] and std::copy and std::copy_backward. Note that replacing |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
36 // memmove by std::copy is possible if the destination starts before the source. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
37 // If not, std::copy_backward needs to be used. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
38 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
39 // * templatize comparison operator in most methods, provide possible dispatch |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
40 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
41 // * duplicate methods to avoid by-the-way indexed sorting |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
42 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
43 // * add methods for verifying sortedness of array |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
44 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
45 // * row sorting via breadth-first tree subsorting |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
46 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
47 // * binary lookup and sequential binary lookup optimized for dense downsampling. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
48 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
49 // * NOTE: the memory management routines rely on the fact that delete [] silently |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
50 // ignores null pointers. Don't gripe about the missing checks - they're there. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
51 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
52 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
53 // The Python license is |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
54 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
55 // PSF LICENSE AGREEMENT FOR PYTHON 2.3 |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
56 // -------------------------------------- |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
57 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
58 // 1. This LICENSE AGREEMENT is between the Python Software Foundation |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
59 // ("PSF"), and the Individual or Organization ("Licensee") accessing and |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
60 // otherwise using Python 2.3 software in source or binary form and its |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
61 // associated documentation. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
62 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
63 // 2. Subject to the terms and conditions of this License Agreement, PSF |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
64 // hereby grants Licensee a nonexclusive, royalty-free, world-wide |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
65 // license to reproduce, analyze, test, perform and/or display publicly, |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
66 // prepare derivative works, distribute, and otherwise use Python 2.3 |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
67 // alone or in any derivative version, provided, however, that PSF's |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
68 // License Agreement and PSF's notice of copyright, i.e., "Copyright (c) |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
69 // 2001, 2002, 2003 Python Software Foundation; All Rights Reserved" are |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
70 // retained in Python 2.3 alone or in any derivative version prepared by |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
71 // Licensee. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
72 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
73 // 3. In the event Licensee prepares a derivative work that is based on |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
74 // or incorporates Python 2.3 or any part thereof, and wants to make |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
75 // the derivative work available to others as provided herein, then |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
76 // Licensee hereby agrees to include in any such work a brief summary of |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
77 // the changes made to Python 2.3. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
78 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
79 // 4. PSF is making Python 2.3 available to Licensee on an "AS IS" |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
80 // basis. PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
81 // IMPLIED. BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
82 // DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
83 // FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON 2.3 WILL NOT |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
84 // INFRINGE ANY THIRD PARTY RIGHTS. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
85 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
86 // 5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
87 // 2.3 FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
88 // A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON 2.3, |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
89 // OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
90 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
91 // 6. This License Agreement will automatically terminate upon a material |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
92 // breach of its terms and conditions. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
93 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
94 // 7. Nothing in this License Agreement shall be deemed to create any |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
95 // relationship of agency, partnership, or joint venture between PSF and |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
96 // Licensee. This License Agreement does not grant permission to use PSF |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
97 // trademarks or trade name in a trademark sense to endorse or promote |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
98 // products or services of Licensee, or any third party. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
99 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
100 // 8. By copying, installing or otherwise using Python 2.3, Licensee |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
101 // agrees to be bound by the terms and conditions of this License |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
102 // Agreement. |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
103 // |
bd51beb6205e
update formatting of copyright notices
John W. Eaton <jwe@octave.org>
parents:
27919
diff
changeset
|
104 //////////////////////////////////////////////////////////////////////// |
4851 | 105 |
21690
b6a686543080
Only include config.h in files that are compiled separately.
John W. Eaton <jwe@octave.org>
parents:
21578
diff
changeset
|
106 // This file should not include config.h. It is only included in other |
b6a686543080
Only include config.h in files that are compiled separately.
John W. Eaton <jwe@octave.org>
parents:
21578
diff
changeset
|
107 // C++ source files that should have included config.h before including |
b6a686543080
Only include config.h in files that are compiled separately.
John W. Eaton <jwe@octave.org>
parents:
21578
diff
changeset
|
108 // this file. |
4851 | 109 |
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
110 #include <algorithm> |
7480 | 111 #include <cstring> |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
112 #include <stack> |
5883 | 113 |
25366
2dad85fe6b8b
avoid warning from gcc 8 (bug #53872)
John W. Eaton <jwe@octave.org>
parents:
25054
diff
changeset
|
114 #include "lo-error.h" |
4851 | 115 #include "lo-mappers.h" |
116 #include "quit.h" | |
117 #include "oct-sort.h" | |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
118 #include "oct-locbuf.h" |
4851 | 119 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
120 template <typename T> |
31771
21f9b34eb893
maint: Eliminate "(void)" in C++ function prototypes/declarations.
Rik <rik@octave.org>
parents:
31706
diff
changeset
|
121 octave_sort<T>::octave_sort () : |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
122 m_compare (ascending_compare), m_ms (nullptr) |
22417
48c00363dc74
maint: Use '{ }' for empty function bodies in C++.
Rik <rik@octave.org>
parents:
22402
diff
changeset
|
123 { } |
4851 | 124 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
125 template <typename T> |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
126 octave_sort<T>::octave_sort (const compare_fcn_type& comp) |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
127 : m_compare (comp), m_ms (nullptr) |
22417
48c00363dc74
maint: Use '{ }' for empty function bodies in C++.
Rik <rik@octave.org>
parents:
22402
diff
changeset
|
128 { } |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
129 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
130 template <typename T> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
131 octave_sort<T>::~octave_sort () |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
132 { |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
133 delete m_ms; |
4851 | 134 } |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
135 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
136 template <typename T> |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
137 void |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
138 octave_sort<T>::set_compare (sortmode mode) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
139 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
140 if (mode == ASCENDING) |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
141 m_compare = ascending_compare; |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
142 else if (mode == DESCENDING) |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
143 m_compare = descending_compare; |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
144 else |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
145 m_compare = compare_fcn_type (); |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
146 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
147 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
148 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
149 template <typename Comp> |
4851 | 150 void |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
151 octave_sort<T>::binarysort (T *data, octave_idx_type nel, |
8700 | 152 octave_idx_type start, Comp comp) |
4851 | 153 { |
8700 | 154 if (start == 0) |
4851 | 155 ++start; |
156 | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
157 for (; start < nel; ++start) |
4851 | 158 { |
159 /* set l to where *start belongs */ | |
18084
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
160 octave_idx_type l = 0; |
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
161 octave_idx_type r = start; |
8700 | 162 T pivot = data[start]; |
4851 | 163 /* Invariants: |
164 * pivot >= all in [lo, l). | |
165 * pivot < all in [r, start). | |
166 * The second is vacuously true at the start. | |
167 */ | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
168 do |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
169 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
170 octave_idx_type p = l + ((r - l) >> 1); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
171 if (comp (pivot, data[p])) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
172 r = p; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
173 else |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
174 l = p+1; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
175 } |
4851 | 176 while (l < r); |
177 /* The invariants still hold, so pivot >= all in [lo, l) and | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
178 pivot < all in [l, start), so pivot belongs at l. Note |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
179 that if there are elements equal to pivot, l points to the |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
180 first slot after them -- that's why this sort is stable. |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
181 Slide over to make room. |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
182 Caution: using memmove is much slower under MSVC 5; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
183 we're not usually moving many slots. */ |
8700 | 184 // NOTE: using swap and going upwards appears to be faster. |
185 for (octave_idx_type p = l; p < start; p++) | |
186 std::swap (pivot, data[p]); | |
187 data[start] = pivot; | |
188 } | |
189 | |
190 return; | |
191 } | |
192 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
193 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
194 template <typename Comp> |
8700 | 195 void |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
196 octave_sort<T>::binarysort (T *data, octave_idx_type *idx, octave_idx_type nel, |
8700 | 197 octave_idx_type start, Comp comp) |
198 { | |
199 if (start == 0) | |
200 ++start; | |
201 | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
202 for (; start < nel; ++start) |
8700 | 203 { |
204 /* set l to where *start belongs */ | |
18084
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
205 octave_idx_type l = 0; |
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
206 octave_idx_type r = start; |
8700 | 207 T pivot = data[start]; |
208 /* Invariants: | |
209 * pivot >= all in [lo, l). | |
210 * pivot < all in [r, start). | |
211 * The second is vacuously true at the start. | |
212 */ | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
213 do |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
214 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
215 octave_idx_type p = l + ((r - l) >> 1); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
216 if (comp (pivot, data[p])) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
217 r = p; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
218 else |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
219 l = p+1; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
220 } |
8700 | 221 while (l < r); |
222 /* The invariants still hold, so pivot >= all in [lo, l) and | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
223 pivot < all in [l, start), so pivot belongs at l. Note |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
224 that if there are elements equal to pivot, l points to the |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
225 first slot after them -- that's why this sort is stable. |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
226 Slide over to make room. |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
227 Caution: using memmove is much slower under MSVC 5; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
228 we're not usually moving many slots. */ |
8700 | 229 // NOTE: using swap and going upwards appears to be faster. |
230 for (octave_idx_type p = l; p < start; p++) | |
231 std::swap (pivot, data[p]); | |
232 data[start] = pivot; | |
233 octave_idx_type ipivot = idx[start]; | |
234 for (octave_idx_type p = l; p < start; p++) | |
235 std::swap (ipivot, idx[p]); | |
236 idx[start] = ipivot; | |
4851 | 237 } |
238 | |
239 return; | |
240 } | |
241 | |
242 /* | |
243 Return the length of the run beginning at lo, in the slice [lo, hi). lo < hi | |
244 is required on entry. "A run" is the longest ascending sequence, with | |
245 | |
246 lo[0] <= lo[1] <= lo[2] <= ... | |
247 | |
248 or the longest descending sequence, with | |
249 | |
250 lo[0] > lo[1] > lo[2] > ... | |
251 | |
7929 | 252 DESCENDING is set to false in the former case, or to true in the latter. |
4851 | 253 For its intended use in a stable mergesort, the strictness of the defn of |
254 "descending" is needed so that the caller can safely reverse a descending | |
255 sequence without violating stability (strict > ensures there are no equal | |
256 elements to get out of order). | |
257 | |
258 Returns -1 in case of error. | |
259 */ | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
260 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
261 template <typename Comp> |
7433 | 262 octave_idx_type |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
263 octave_sort<T>::count_run (T *lo, octave_idx_type nel, bool& descending, |
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
264 Comp comp) |
4851 | 265 { |
7433 | 266 octave_idx_type n; |
8700 | 267 T *hi = lo + nel; |
4851 | 268 |
7929 | 269 descending = false; |
4851 | 270 ++lo; |
271 if (lo == hi) | |
272 return 1; | |
273 | |
274 n = 2; | |
275 | |
8700 | 276 if (comp (*lo, *(lo-1))) |
4851 | 277 { |
7929 | 278 descending = true; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
279 for (lo = lo+1; lo < hi; ++lo, ++n) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
280 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
281 if (comp (*lo, *(lo-1))) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
282 ; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
283 else |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
284 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
285 } |
4851 | 286 } |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
287 else |
4851 | 288 { |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
289 for (lo = lo+1; lo < hi; ++lo, ++n) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
290 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
291 if (comp (*lo, *(lo-1))) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
292 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
293 } |
4851 | 294 } |
295 | |
296 return n; | |
297 } | |
298 | |
299 /* | |
300 Locate the proper position of key in a sorted vector; if the vector contains | |
301 an element equal to key, return the position immediately to the left of | |
302 the leftmost equal element. [gallop_right() does the same except returns | |
303 the position to the right of the rightmost equal element (if any).] | |
304 | |
305 "a" is a sorted vector with n elements, starting at a[0]. n must be > 0. | |
306 | |
307 "hint" is an index at which to begin the search, 0 <= hint < n. The closer | |
308 hint is to the final result, the faster this runs. | |
309 | |
310 The return value is the int k in 0..n such that | |
311 | |
312 a[k-1] < key <= a[k] | |
313 | |
314 pretending that *(a-1) is minus infinity and a[n] is plus infinity. IOW, | |
315 key belongs at index k; or, IOW, the first k elements of a should precede | |
316 key, and the last n-k should follow key. | |
317 | |
318 Returns -1 on error. See listsort.txt for info on the method. | |
319 */ | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
320 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
321 template <typename Comp> |
7433 | 322 octave_idx_type |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
323 octave_sort<T>::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
|
324 octave_idx_type hint, |
8700 | 325 Comp comp) |
4851 | 326 { |
7433 | 327 octave_idx_type ofs; |
328 octave_idx_type lastofs; | |
329 octave_idx_type k; | |
4851 | 330 |
331 a += hint; | |
332 lastofs = 0; | |
333 ofs = 1; | |
8700 | 334 if (comp (*a, key)) |
4851 | 335 { |
336 /* a[hint] < key -- gallop right, until | |
337 * a[hint + lastofs] < key <= a[hint + ofs] | |
338 */ | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
339 const octave_idx_type maxofs = n - hint; /* &a[n-1] is highest */ |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
340 while (ofs < maxofs) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
341 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
342 if (comp (a[ofs], key)) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
343 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
344 lastofs = ofs; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
345 ofs = (ofs << 1) + 1; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
346 if (ofs <= 0) /* int overflow */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
347 ofs = maxofs; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
348 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
349 else /* key <= a[hint + ofs] */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
350 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
351 } |
4851 | 352 if (ofs > maxofs) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
353 ofs = maxofs; |
4851 | 354 /* Translate back to offsets relative to &a[0]. */ |
355 lastofs += hint; | |
356 ofs += hint; | |
357 } | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
358 else |
4851 | 359 { |
360 /* key <= a[hint] -- gallop left, until | |
361 * a[hint - ofs] < key <= a[hint - lastofs] | |
362 */ | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
363 const octave_idx_type maxofs = hint + 1; /* &a[0] is lowest */ |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
364 while (ofs < maxofs) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
365 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
366 if (comp (*(a-ofs), key)) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
367 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
368 /* key <= a[hint - ofs] */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
369 lastofs = ofs; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
370 ofs = (ofs << 1) + 1; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
371 if (ofs <= 0) /* int overflow */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
372 ofs = maxofs; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
373 } |
4851 | 374 if (ofs > maxofs) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
375 ofs = maxofs; |
4851 | 376 /* Translate back to positive offsets relative to &a[0]. */ |
377 k = lastofs; | |
378 lastofs = hint - ofs; | |
379 ofs = hint - k; | |
380 } | |
381 a -= hint; | |
382 | |
383 /* Now a[lastofs] < key <= a[ofs], so key belongs somewhere to the | |
384 * right of lastofs but no farther right than ofs. Do a binary | |
385 * search, with invariant a[lastofs-1] < key <= a[ofs]. | |
386 */ | |
387 ++lastofs; | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
388 while (lastofs < ofs) |
4851 | 389 { |
7433 | 390 octave_idx_type m = lastofs + ((ofs - lastofs) >> 1); |
4851 | 391 |
8700 | 392 if (comp (a[m], key)) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
393 lastofs = m+1; /* a[m] < key */ |
4851 | 394 else |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
395 ofs = m; /* key <= a[m] */ |
4851 | 396 } |
7234 | 397 |
4851 | 398 return ofs; |
399 } | |
400 | |
401 /* | |
402 Exactly like gallop_left(), except that if key already exists in a[0:n], | |
403 finds the position immediately to the right of the rightmost equal value. | |
404 | |
405 The return value is the int k in 0..n such that | |
406 | |
407 a[k-1] <= key < a[k] | |
408 | |
409 or -1 if error. | |
410 | |
411 The code duplication is massive, but this is enough different given that | |
412 we're sticking to "<" comparisons that it's much harder to follow if | |
413 written as one routine with yet another "left or right?" flag. | |
414 */ | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
415 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
416 template <typename Comp> |
7433 | 417 octave_idx_type |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
418 octave_sort<T>::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
|
419 octave_idx_type hint, |
8700 | 420 Comp comp) |
4851 | 421 { |
7433 | 422 octave_idx_type ofs; |
423 octave_idx_type lastofs; | |
424 octave_idx_type k; | |
4851 | 425 |
426 a += hint; | |
427 lastofs = 0; | |
428 ofs = 1; | |
8700 | 429 if (comp (key, *a)) |
4851 | 430 { |
431 /* key < a[hint] -- gallop left, until | |
432 * a[hint - ofs] <= key < a[hint - lastofs] | |
433 */ | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
434 const octave_idx_type maxofs = hint + 1; /* &a[0] is lowest */ |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
435 while (ofs < maxofs) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
436 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
437 if (comp (key, *(a-ofs))) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
438 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
439 lastofs = ofs; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
440 ofs = (ofs << 1) + 1; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
441 if (ofs <= 0) /* int overflow */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
442 ofs = maxofs; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
443 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
444 else /* a[hint - ofs] <= key */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
445 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
446 } |
4851 | 447 if (ofs > maxofs) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
448 ofs = maxofs; |
4851 | 449 /* Translate back to positive offsets relative to &a[0]. */ |
450 k = lastofs; | |
451 lastofs = hint - ofs; | |
452 ofs = hint - k; | |
453 } | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
454 else |
4851 | 455 { |
456 /* a[hint] <= key -- gallop right, until | |
457 * a[hint + lastofs] <= key < a[hint + ofs] | |
458 */ | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
459 const octave_idx_type maxofs = n - hint; /* &a[n-1] is highest */ |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
460 while (ofs < maxofs) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
461 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
462 if (comp (key, a[ofs])) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
463 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
464 /* a[hint + ofs] <= key */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
465 lastofs = ofs; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
466 ofs = (ofs << 1) + 1; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
467 if (ofs <= 0) /* int overflow */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
468 ofs = maxofs; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
469 } |
4851 | 470 if (ofs > maxofs) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
471 ofs = maxofs; |
4851 | 472 /* Translate back to offsets relative to &a[0]. */ |
473 lastofs += hint; | |
474 ofs += hint; | |
475 } | |
476 a -= hint; | |
477 | |
478 /* Now a[lastofs] <= key < a[ofs], so key belongs somewhere to the | |
479 * right of lastofs but no farther right than ofs. Do a binary | |
480 * search, with invariant a[lastofs-1] <= key < a[ofs]. | |
481 */ | |
482 ++lastofs; | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
483 while (lastofs < ofs) |
4851 | 484 { |
7433 | 485 octave_idx_type m = lastofs + ((ofs - lastofs) >> 1); |
4851 | 486 |
8700 | 487 if (comp (key, a[m])) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
488 ofs = m; /* key < a[m] */ |
4851 | 489 else |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
490 lastofs = m+1; /* a[m] <= key */ |
4851 | 491 } |
7234 | 492 |
4851 | 493 return ofs; |
494 } | |
495 | |
7433 | 496 static inline octave_idx_type |
29654
d13d090cb03a
use std::size_t and std::ptrdiff_t in C++ code (bug #60471)
John W. Eaton <jwe@octave.org>
parents:
29358
diff
changeset
|
497 roundupsize (std::size_t n) |
4851 | 498 { |
499 unsigned int nbits = 3; | |
29654
d13d090cb03a
use std::size_t and std::ptrdiff_t in C++ code (bug #60471)
John W. Eaton <jwe@octave.org>
parents:
29358
diff
changeset
|
500 std::size_t n2 = n >> 8; |
4851 | 501 |
502 /* Round up: | |
503 * If n < 256, to a multiple of 8. | |
504 * If n < 2048, to a multiple of 64. | |
505 * If n < 16384, to a multiple of 512. | |
506 * If n < 131072, to a multiple of 4096. | |
507 * If n < 1048576, to a multiple of 32768. | |
508 * If n < 8388608, to a multiple of 262144. | |
509 * If n < 67108864, to a multiple of 2097152. | |
510 * If n < 536870912, to a multiple of 16777216. | |
511 * ... | |
512 * If n < 2**(5+3*i), to a multiple of 2**(3*i). | |
513 * | |
514 * This over-allocates proportional to the list size, making room | |
515 * for additional growth. The over-allocation is mild, but is | |
516 * enough to give linear-time amortized behavior over a long | |
517 * sequence of appends() in the presence of a poorly-performing | |
518 * system realloc() (which is a reality, e.g., across all flavors | |
519 * of Windows, with Win9x behavior being particularly bad -- and | |
520 * we've still got address space fragmentation problems on Win9x | |
521 * even with this scheme, although it requires much longer lists to | |
522 * provoke them than it used to). | |
523 */ | |
7234 | 524 while (n2) |
525 { | |
526 n2 >>= 3; | |
527 nbits += 3; | |
528 } | |
529 | |
29654
d13d090cb03a
use std::size_t and std::ptrdiff_t in C++ code (bug #60471)
John W. Eaton <jwe@octave.org>
parents:
29358
diff
changeset
|
530 std::size_t new_size = ((n >> nbits) + 1) << nbits; |
25366
2dad85fe6b8b
avoid warning from gcc 8 (bug #53872)
John W. Eaton <jwe@octave.org>
parents:
25054
diff
changeset
|
531 |
27863
546346314210
Avoid warning from gcc 9 about comparison of expressions of different signedness
Markus Mützel <markus.muetzel@gmx.de>
parents:
27379
diff
changeset
|
532 if (new_size == 0 |
546346314210
Avoid warning from gcc 9 about comparison of expressions of different signedness
Markus Mützel <markus.muetzel@gmx.de>
parents:
27379
diff
changeset
|
533 || new_size |
29654
d13d090cb03a
use std::size_t and std::ptrdiff_t in C++ code (bug #60471)
John W. Eaton <jwe@octave.org>
parents:
29358
diff
changeset
|
534 > static_cast<std::size_t> (std::numeric_limits<octave_idx_type>::max ())) |
25366
2dad85fe6b8b
avoid warning from gcc 8 (bug #53872)
John W. Eaton <jwe@octave.org>
parents:
25054
diff
changeset
|
535 (*current_liboctave_error_handler) |
2dad85fe6b8b
avoid warning from gcc 8 (bug #53872)
John W. Eaton <jwe@octave.org>
parents:
25054
diff
changeset
|
536 ("unable to allocate sufficient memory for sort"); |
2dad85fe6b8b
avoid warning from gcc 8 (bug #53872)
John W. Eaton <jwe@octave.org>
parents:
25054
diff
changeset
|
537 |
2dad85fe6b8b
avoid warning from gcc 8 (bug #53872)
John W. Eaton <jwe@octave.org>
parents:
25054
diff
changeset
|
538 return static_cast<octave_idx_type> (new_size); |
4851 | 539 } |
540 | |
541 /* Ensure enough temp memory for 'need' array slots is available. | |
542 * Returns 0 on success and -1 if the memory can't be gotten. | |
543 */ | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
544 template <typename T> |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
545 void |
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
546 octave_sort<T>::MergeState::getmem (octave_idx_type need) |
4851 | 547 { |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
548 if (need <= m_alloced) |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
549 return; |
4851 | 550 |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
551 need = roundupsize (need); |
4851 | 552 /* Don't realloc! That can cost cycles to copy the old data, but |
553 * we don't care what's in the block. | |
554 */ | |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
555 delete [] m_a; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
556 delete [] m_ia; // Must do this or fool possible next getmemi. |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
557 m_a = new T [need]; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
558 m_alloced = need; |
7234 | 559 |
4851 | 560 } |
561 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
562 template <typename T> |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
563 void |
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
564 octave_sort<T>::MergeState::getmemi (octave_idx_type need) |
8700 | 565 { |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
566 if (m_ia && need <= m_alloced) |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
567 return; |
8700 | 568 |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
569 need = roundupsize (need); |
8700 | 570 /* Don't realloc! That can cost cycles to copy the old data, but |
571 * we don't care what's in the block. | |
572 */ | |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
573 delete [] m_a; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
574 delete [] m_ia; |
8700 | 575 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
576 m_a = new T [need]; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
577 m_ia = new octave_idx_type [need]; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
578 m_alloced = need; |
8700 | 579 } |
4851 | 580 |
581 /* Merge the na elements starting at pa with the nb elements starting at pb | |
582 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. | |
583 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the | |
584 * merge, and should have na <= nb. See listsort.txt for more info. | |
585 * Return 0 if successful, -1 if error. | |
586 */ | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
587 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
588 template <typename Comp> |
4851 | 589 int |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
590 octave_sort<T>::merge_lo (T *pa, octave_idx_type na, |
8700 | 591 T *pb, octave_idx_type nb, |
592 Comp comp) | |
4851 | 593 { |
7433 | 594 octave_idx_type k; |
4851 | 595 T *dest; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
596 int result = -1; /* guilty until proved innocent */ |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
597 octave_idx_type min_gallop = m_ms->m_min_gallop; |
4851 | 598 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
599 m_ms->getmem (na); |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
600 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
601 std::copy (pa, pa + na, m_ms->m_a); |
4851 | 602 dest = pa; |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
603 pa = m_ms->m_a; |
4851 | 604 |
605 *dest++ = *pb++; | |
606 --nb; | |
607 if (nb == 0) | |
608 goto Succeed; | |
609 if (na == 1) | |
610 goto CopyB; | |
611 | |
7234 | 612 for (;;) |
613 { | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
614 octave_idx_type acount = 0; /* # of times A won in a row */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
615 octave_idx_type bcount = 0; /* # of times B won in a row */ |
7234 | 616 |
617 /* Do the straightforward thing until (if ever) one run | |
618 * appears to win consistently. | |
619 */ | |
620 for (;;) | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
621 { |
4851 | 622 |
8700 | 623 // FIXME: these loops are candidates for further optimizations. |
624 // Rather than testing everything in each cycle, it may be more | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
625 // efficient to do it in hunks. |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
626 if (comp (*pb, *pa)) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
627 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
628 *dest++ = *pb++; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
629 ++bcount; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
630 acount = 0; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
631 --nb; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
632 if (nb == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
633 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
634 if (bcount >= min_gallop) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
635 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
636 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
637 else |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
638 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
639 *dest++ = *pa++; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
640 ++acount; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
641 bcount = 0; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
642 --na; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
643 if (na == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
644 goto CopyB; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
645 if (acount >= min_gallop) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
646 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
647 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
648 } |
4851 | 649 |
7234 | 650 /* One run is winning so consistently that galloping may |
651 * be a huge win. So try that, and continue galloping until | |
652 * (if ever) neither run appears to be winning consistently | |
653 * anymore. | |
654 */ | |
655 ++min_gallop; | |
656 do | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
657 { |
26397
c4ec882ffb7c
oct-sort.cc: Fix static analyzer detected issues (bug #55347).
Rik <rik@octave.org>
parents:
26376
diff
changeset
|
658 min_gallop -= (min_gallop > 1); |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
659 m_ms->m_min_gallop = min_gallop; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
660 k = gallop_right (*pb, pa, na, 0, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
661 acount = k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
662 if (k) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
663 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
664 if (k < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
665 goto Fail; |
8700 | 666 dest = std::copy (pa, pa + k, dest); |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
667 pa += k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
668 na -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
669 if (na == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
670 goto CopyB; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
671 /* na==0 is impossible now if the comparison |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
672 * function is consistent, but we can't assume |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
673 * that it is. |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
674 */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
675 if (na == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
676 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
677 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
678 *dest++ = *pb++; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
679 --nb; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
680 if (nb == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
681 goto Succeed; |
7234 | 682 |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
683 k = gallop_left (*pa, pb, nb, 0, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
684 bcount = k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
685 if (k) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
686 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
687 if (k < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
688 goto Fail; |
8700 | 689 dest = std::copy (pb, pb + k, dest); |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
690 pb += k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
691 nb -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
692 if (nb == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
693 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
694 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
695 *dest++ = *pa++; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
696 --na; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
697 if (na == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
698 goto CopyB; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
699 } |
7234 | 700 while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
701 | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
702 ++min_gallop; /* penalize it for leaving galloping mode */ |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
703 m_ms->m_min_gallop = min_gallop; |
4851 | 704 } |
705 | |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
706 Succeed: |
4851 | 707 result = 0; |
7234 | 708 |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
709 Fail: |
4851 | 710 if (na) |
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
711 std::copy (pa, pa + na, dest); |
4851 | 712 return result; |
7234 | 713 |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
714 CopyB: |
4851 | 715 /* The last element of pa belongs at the end of the merge. */ |
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
716 std::copy (pb, pb + nb, dest); |
4851 | 717 dest[nb] = *pa; |
7234 | 718 |
4851 | 719 return 0; |
720 } | |
721 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
722 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
723 template <typename Comp> |
8700 | 724 int |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
725 octave_sort<T>::merge_lo (T *pa, octave_idx_type *ipa, octave_idx_type na, |
8700 | 726 T *pb, octave_idx_type *ipb, octave_idx_type nb, |
727 Comp comp) | |
728 { | |
729 octave_idx_type k; | |
730 T *dest; | |
731 octave_idx_type *idest; | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
732 int result = -1; /* guilty until proved innocent */ |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
733 octave_idx_type min_gallop = m_ms->m_min_gallop; |
8700 | 734 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
735 m_ms->getmemi (na); |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
736 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
737 std::copy (pa, pa + na, m_ms->m_a); |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
738 std::copy (ipa, ipa + na, m_ms->m_ia); |
8700 | 739 dest = pa; idest = ipa; |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
740 pa = m_ms->m_a; ipa = m_ms->m_ia; |
8700 | 741 |
742 *dest++ = *pb++; *idest++ = *ipb++; | |
743 --nb; | |
744 if (nb == 0) | |
745 goto Succeed; | |
746 if (na == 1) | |
747 goto CopyB; | |
748 | |
749 for (;;) | |
750 { | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
751 octave_idx_type acount = 0; /* # of times A won in a row */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
752 octave_idx_type bcount = 0; /* # of times B won in a row */ |
8700 | 753 |
754 /* Do the straightforward thing until (if ever) one run | |
755 * appears to win consistently. | |
756 */ | |
757 for (;;) | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
758 { |
8700 | 759 |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
760 if (comp (*pb, *pa)) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
761 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
762 *dest++ = *pb++; *idest++ = *ipb++; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
763 ++bcount; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
764 acount = 0; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
765 --nb; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
766 if (nb == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
767 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
768 if (bcount >= min_gallop) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
769 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
770 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
771 else |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
772 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
773 *dest++ = *pa++; *idest++ = *ipa++; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
774 ++acount; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
775 bcount = 0; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
776 --na; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
777 if (na == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
778 goto CopyB; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
779 if (acount >= min_gallop) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
780 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
781 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
782 } |
8700 | 783 |
784 /* One run is winning so consistently that galloping may | |
785 * be a huge win. So try that, and continue galloping until | |
786 * (if ever) neither run appears to be winning consistently | |
787 * anymore. | |
788 */ | |
789 ++min_gallop; | |
790 do | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
791 { |
26397
c4ec882ffb7c
oct-sort.cc: Fix static analyzer detected issues (bug #55347).
Rik <rik@octave.org>
parents:
26376
diff
changeset
|
792 min_gallop -= (min_gallop > 1); |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
793 m_ms->m_min_gallop = min_gallop; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
794 k = gallop_right (*pb, pa, na, 0, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
795 acount = k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
796 if (k) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
797 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
798 if (k < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
799 goto Fail; |
8700 | 800 dest = std::copy (pa, pa + k, dest); |
801 idest = std::copy (ipa, ipa + k, idest); | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
802 pa += k; ipa += k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
803 na -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
804 if (na == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
805 goto CopyB; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
806 /* na==0 is impossible now if the comparison |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
807 * function is consistent, but we can't assume |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
808 * that it is. |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
809 */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
810 if (na == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
811 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
812 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
813 *dest++ = *pb++; *idest++ = *ipb++; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
814 --nb; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
815 if (nb == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
816 goto Succeed; |
8700 | 817 |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
818 k = gallop_left (*pa, pb, nb, 0, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
819 bcount = k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
820 if (k) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
821 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
822 if (k < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
823 goto Fail; |
8700 | 824 dest = std::copy (pb, pb + k, dest); |
825 idest = std::copy (ipb, ipb + k, idest); | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
826 pb += k; ipb += k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
827 nb -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
828 if (nb == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
829 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
830 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
831 *dest++ = *pa++; *idest++ = *ipa++; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
832 --na; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
833 if (na == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
834 goto CopyB; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
835 } |
8700 | 836 while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
837 | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
838 ++min_gallop; /* penalize it for leaving galloping mode */ |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
839 m_ms->m_min_gallop = min_gallop; |
8700 | 840 } |
841 | |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
842 Succeed: |
8700 | 843 result = 0; |
844 | |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
845 Fail: |
8700 | 846 if (na) |
847 { | |
848 std::copy (pa, pa + na, dest); | |
849 std::copy (ipa, ipa + na, idest); | |
850 } | |
851 return result; | |
852 | |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
853 CopyB: |
8700 | 854 /* The last element of pa belongs at the end of the merge. */ |
855 std::copy (pb, pb + nb, dest); | |
856 std::copy (ipb, ipb + nb, idest); | |
857 dest[nb] = *pa; | |
858 idest[nb] = *ipa; | |
859 | |
860 return 0; | |
861 } | |
862 | |
4851 | 863 /* Merge the na elements starting at pa with the nb elements starting at pb |
864 * in a stable way, in-place. na and nb must be > 0, and pa + na == pb. | |
865 * Must also have that *pb < *pa, that pa[na-1] belongs at the end of the | |
866 * merge, and should have na >= nb. See listsort.txt for more info. | |
867 * Return 0 if successful, -1 if error. | |
868 */ | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
869 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
870 template <typename Comp> |
4851 | 871 int |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
872 octave_sort<T>::merge_hi (T *pa, octave_idx_type na, |
8700 | 873 T *pb, octave_idx_type nb, |
874 Comp comp) | |
4851 | 875 { |
7433 | 876 octave_idx_type k; |
4851 | 877 T *dest; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
878 int result = -1; /* guilty until proved innocent */ |
8700 | 879 T *basea, *baseb; |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
880 octave_idx_type min_gallop = m_ms->m_min_gallop; |
4851 | 881 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
882 m_ms->getmem (nb); |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
883 |
4851 | 884 dest = pb + nb - 1; |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
885 std::copy (pb, pb + nb, m_ms->m_a); |
4851 | 886 basea = pa; |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
887 baseb = m_ms->m_a; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
888 pb = m_ms->m_a + nb - 1; |
4851 | 889 pa += na - 1; |
890 | |
891 *dest-- = *pa--; | |
892 --na; | |
893 if (na == 0) | |
894 goto Succeed; | |
895 if (nb == 1) | |
896 goto CopyA; | |
897 | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
898 for (;;) |
4851 | 899 { |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
900 octave_idx_type acount = 0; /* # of times A won in a row */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
901 octave_idx_type bcount = 0; /* # of times B won in a row */ |
4851 | 902 |
903 /* Do the straightforward thing until (if ever) one run | |
904 * appears to win consistently. | |
905 */ | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
906 for (;;) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
907 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
908 if (comp (*pb, *pa)) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
909 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
910 *dest-- = *pa--; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
911 ++acount; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
912 bcount = 0; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
913 --na; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
914 if (na == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
915 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
916 if (acount >= min_gallop) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
917 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
918 } |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
919 else |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
920 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
921 *dest-- = *pb--; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
922 ++bcount; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
923 acount = 0; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
924 --nb; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
925 if (nb == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
926 goto CopyA; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
927 if (bcount >= min_gallop) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
928 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
929 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
930 } |
4851 | 931 |
932 /* One run is winning so consistently that galloping may | |
933 * be a huge win. So try that, and continue galloping until | |
934 * (if ever) neither run appears to be winning consistently | |
935 * anymore. | |
936 */ | |
937 ++min_gallop; | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
938 do |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
939 { |
26397
c4ec882ffb7c
oct-sort.cc: Fix static analyzer detected issues (bug #55347).
Rik <rik@octave.org>
parents:
26376
diff
changeset
|
940 min_gallop -= (min_gallop > 1); |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
941 m_ms->m_min_gallop = min_gallop; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
942 k = gallop_right (*pb, basea, na, na-1, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
943 if (k < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
944 goto Fail; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
945 k = na - k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
946 acount = k; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
947 if (k) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
948 { |
8700 | 949 dest = std::copy_backward (pa+1 - k, pa+1, dest+1) - 1; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
950 pa -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
951 na -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
952 if (na == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
953 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
954 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
955 *dest-- = *pb--; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
956 --nb; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
957 if (nb == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
958 goto CopyA; |
4851 | 959 |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
960 k = gallop_left (*pa, baseb, nb, nb-1, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
961 if (k < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
962 goto Fail; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
963 k = nb - k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
964 bcount = k; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
965 if (k) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
966 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
967 dest -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
968 pb -= k; |
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
969 std::copy (pb+1, pb+1 + k, dest+1); |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
970 nb -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
971 if (nb == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
972 goto CopyA; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
973 /* nb==0 is impossible now if the comparison |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
974 * function is consistent, but we can't assume |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
975 * that it is. |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
976 */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
977 if (nb == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
978 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
979 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
980 *dest-- = *pa--; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
981 --na; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
982 if (na == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
983 goto Succeed; |
32590
3c2c585965cc
maint: C++ style check for liboctave/ before 9.1 release.
Rik <rik@octave.org>
parents:
31771
diff
changeset
|
984 } |
3c2c585965cc
maint: C++ style check for liboctave/ before 9.1 release.
Rik <rik@octave.org>
parents:
31771
diff
changeset
|
985 while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
986 ++min_gallop; /* penalize it for leaving galloping mode */ |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
987 m_ms->m_min_gallop = min_gallop; |
4851 | 988 } |
7234 | 989 |
4851 | 990 Succeed: |
991 result = 0; | |
7234 | 992 |
4851 | 993 Fail: |
994 if (nb) | |
8206
0168d22e6bba
fix sorting of non-POD objects
Jaroslav Hajek <highegg@gmail.com>
parents:
7929
diff
changeset
|
995 std::copy (baseb, baseb + nb, dest-(nb-1)); |
4851 | 996 return result; |
7234 | 997 |
4851 | 998 CopyA: |
999 /* The first element of pb belongs at the front of the merge. */ | |
8700 | 1000 dest = std::copy_backward (pa+1 - na, pa+1, dest+1) - 1; |
4851 | 1001 pa -= na; |
1002 *dest = *pb; | |
7234 | 1003 |
4851 | 1004 return 0; |
1005 } | |
1006 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1007 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1008 template <typename Comp> |
8700 | 1009 int |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1010 octave_sort<T>::merge_hi (T *pa, octave_idx_type *ipa, octave_idx_type na, |
8700 | 1011 T *pb, octave_idx_type *ipb, octave_idx_type nb, |
1012 Comp comp) | |
1013 { | |
1014 octave_idx_type k; | |
1015 T *dest; | |
1016 octave_idx_type *idest; | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1017 int result = -1; /* guilty until proved innocent */ |
8700 | 1018 T *basea, *baseb; |
13218
01b7a60e2ff0
fix warnings for unused but set variables
John W. Eaton <jwe@octave.org>
parents:
11586
diff
changeset
|
1019 octave_idx_type *ibaseb; |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1020 octave_idx_type min_gallop = m_ms->m_min_gallop; |
8700 | 1021 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1022 m_ms->getmemi (nb); |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
1023 |
8700 | 1024 dest = pb + nb - 1; |
1025 idest = ipb + nb - 1; | |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1026 std::copy (pb, pb + nb, m_ms->m_a); |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1027 std::copy (ipb, ipb + nb, m_ms->m_ia); |
13218
01b7a60e2ff0
fix warnings for unused but set variables
John W. Eaton <jwe@octave.org>
parents:
11586
diff
changeset
|
1028 basea = pa; |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1029 baseb = m_ms->m_a; ibaseb = m_ms->m_ia; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1030 pb = m_ms->m_a + nb - 1; ipb = m_ms->m_ia + nb - 1; |
8700 | 1031 pa += na - 1; ipa += na - 1; |
1032 | |
1033 *dest-- = *pa--; *idest-- = *ipa--; | |
1034 --na; | |
1035 if (na == 0) | |
1036 goto Succeed; | |
1037 if (nb == 1) | |
1038 goto CopyA; | |
1039 | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1040 for (;;) |
8700 | 1041 { |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1042 octave_idx_type acount = 0; /* # of times A won in a row */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1043 octave_idx_type bcount = 0; /* # of times B won in a row */ |
8700 | 1044 |
1045 /* Do the straightforward thing until (if ever) one run | |
1046 * appears to win consistently. | |
1047 */ | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1048 for (;;) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1049 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1050 if (comp (*pb, *pa)) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1051 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1052 *dest-- = *pa--; *idest-- = *ipa--; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1053 ++acount; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1054 bcount = 0; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1055 --na; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1056 if (na == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1057 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1058 if (acount >= min_gallop) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1059 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1060 } |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1061 else |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1062 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1063 *dest-- = *pb--; *idest-- = *ipb--; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1064 ++bcount; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1065 acount = 0; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1066 --nb; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1067 if (nb == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1068 goto CopyA; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1069 if (bcount >= min_gallop) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1070 break; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1071 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1072 } |
8700 | 1073 |
1074 /* One run is winning so consistently that galloping may | |
1075 * be a huge win. So try that, and continue galloping until | |
1076 * (if ever) neither run appears to be winning consistently | |
1077 * anymore. | |
1078 */ | |
1079 ++min_gallop; | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1080 do |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1081 { |
26397
c4ec882ffb7c
oct-sort.cc: Fix static analyzer detected issues (bug #55347).
Rik <rik@octave.org>
parents:
26376
diff
changeset
|
1082 min_gallop -= (min_gallop > 1); |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1083 m_ms->m_min_gallop = min_gallop; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1084 k = gallop_right (*pb, basea, na, na-1, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1085 if (k < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1086 goto Fail; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1087 k = na - k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1088 acount = k; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1089 if (k) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1090 { |
8700 | 1091 dest = std::copy_backward (pa+1 - k, pa+1, dest+1) - 1; |
1092 idest = std::copy_backward (ipa+1 - k, ipa+1, idest+1) - 1; | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1093 pa -= k; ipa -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1094 na -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1095 if (na == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1096 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1097 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1098 *dest-- = *pb--; *idest-- = *ipb--; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1099 --nb; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1100 if (nb == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1101 goto CopyA; |
8700 | 1102 |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1103 k = gallop_left (*pa, baseb, nb, nb-1, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1104 if (k < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1105 goto Fail; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1106 k = nb - k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1107 bcount = k; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1108 if (k) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1109 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1110 dest -= k; idest -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1111 pb -= k; ipb -= k; |
8700 | 1112 std::copy (pb+1, pb+1 + k, dest+1); |
1113 std::copy (ipb+1, ipb+1 + k, idest+1); | |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1114 nb -= k; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1115 if (nb == 1) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1116 goto CopyA; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1117 /* nb==0 is impossible now if the comparison |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1118 * function is consistent, but we can't assume |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1119 * that it is. |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1120 */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1121 if (nb == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1122 goto Succeed; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1123 } |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1124 *dest-- = *pa--; *idest-- = *ipa--; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1125 --na; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1126 if (na == 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1127 goto Succeed; |
32590
3c2c585965cc
maint: C++ style check for liboctave/ before 9.1 release.
Rik <rik@octave.org>
parents:
31771
diff
changeset
|
1128 } |
3c2c585965cc
maint: C++ style check for liboctave/ before 9.1 release.
Rik <rik@octave.org>
parents:
31771
diff
changeset
|
1129 while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP); |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1130 ++min_gallop; /* penalize it for leaving galloping mode */ |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1131 m_ms->m_min_gallop = min_gallop; |
8700 | 1132 } |
1133 | |
1134 Succeed: | |
1135 result = 0; | |
1136 | |
1137 Fail: | |
1138 if (nb) | |
1139 { | |
1140 std::copy (baseb, baseb + nb, dest-(nb-1)); | |
1141 std::copy (ibaseb, ibaseb + nb, idest-(nb-1)); | |
1142 } | |
1143 return result; | |
1144 | |
1145 CopyA: | |
1146 /* The first element of pb belongs at the front of the merge. */ | |
1147 dest = std::copy_backward (pa+1 - na, pa+1, dest+1) - 1; | |
1148 idest = std::copy_backward (ipa+1 - na, ipa+1, idest+1) - 1; | |
1149 pa -= na; ipa -= na; | |
1150 *dest = *pb; *idest = *ipb; | |
1151 | |
1152 return 0; | |
1153 } | |
1154 | |
4851 | 1155 /* Merge the two runs at stack indices i and i+1. |
1156 * Returns 0 on success, -1 on error. | |
1157 */ | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1158 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1159 template <typename Comp> |
4851 | 1160 int |
8700 | 1161 octave_sort<T>::merge_at (octave_idx_type i, T *data, |
1162 Comp comp) | |
4851 | 1163 { |
1164 T *pa, *pb; | |
7433 | 1165 octave_idx_type na, nb; |
1166 octave_idx_type k; | |
4851 | 1167 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1168 pa = data + m_ms->m_pending[i].m_base; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1169 na = m_ms->m_pending[i].m_len; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1170 pb = data + m_ms->m_pending[i+1].m_base; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1171 nb = m_ms->m_pending[i+1].m_len; |
4851 | 1172 |
1173 /* Record the length of the combined runs; if i is the 3rd-last | |
1174 * run now, also slide over the last run (which isn't involved | |
1175 * in this merge). The current run i+1 goes away in any case. | |
1176 */ | |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1177 m_ms->m_pending[i].m_len = na + nb; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1178 if (i == m_ms->m_n - 3) |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1179 m_ms->m_pending[i+1] = m_ms->m_pending[i+2]; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1180 m_ms->m_n--; |
4851 | 1181 |
1182 /* Where does b start in a? Elements in a before that can be | |
1183 * ignored (already in place). | |
1184 */ | |
8700 | 1185 k = gallop_right (*pb, pa, na, 0, comp); |
4851 | 1186 if (k < 0) |
1187 return -1; | |
1188 pa += k; | |
1189 na -= k; | |
1190 if (na == 0) | |
1191 return 0; | |
1192 | |
1193 /* Where does a end in b? Elements in b after that can be | |
1194 * ignored (already in place). | |
1195 */ | |
8700 | 1196 nb = gallop_left (pa[na-1], pb, nb, nb-1, comp); |
4851 | 1197 if (nb <= 0) |
1198 return nb; | |
1199 | |
1200 /* Merge what remains of the runs, using a temp array with | |
15018
3d8ace26c5b4
maint: Use Octave coding conventions for cuddled parentheses in liboctave/.
Rik <rik@octave.org>
parents:
14138
diff
changeset
|
1201 * min (na, nb) elements. |
4851 | 1202 */ |
1203 if (na <= nb) | |
8700 | 1204 return merge_lo (pa, na, pb, nb, comp); |
4851 | 1205 else |
8700 | 1206 return merge_hi (pa, na, pb, nb, comp); |
1207 } | |
1208 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1209 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1210 template <typename Comp> |
8700 | 1211 int |
1212 octave_sort<T>::merge_at (octave_idx_type i, T *data, octave_idx_type *idx, | |
1213 Comp comp) | |
1214 { | |
1215 T *pa, *pb; | |
1216 octave_idx_type *ipa, *ipb; | |
1217 octave_idx_type na, nb; | |
1218 octave_idx_type k; | |
1219 | |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1220 pa = data + m_ms->m_pending[i].m_base; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1221 ipa = idx + m_ms->m_pending[i].m_base; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1222 na = m_ms->m_pending[i].m_len; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1223 pb = data + m_ms->m_pending[i+1].m_base; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1224 ipb = idx + m_ms->m_pending[i+1].m_base; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1225 nb = m_ms->m_pending[i+1].m_len; |
8700 | 1226 |
1227 /* Record the length of the combined runs; if i is the 3rd-last | |
1228 * run now, also slide over the last run (which isn't involved | |
1229 * in this merge). The current run i+1 goes away in any case. | |
1230 */ | |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1231 m_ms->m_pending[i].m_len = na + nb; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1232 if (i == m_ms->m_n - 3) |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1233 m_ms->m_pending[i+1] = m_ms->m_pending[i+2]; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1234 m_ms->m_n--; |
8700 | 1235 |
1236 /* Where does b start in a? Elements in a before that can be | |
1237 * ignored (already in place). | |
1238 */ | |
1239 k = gallop_right (*pb, pa, na, 0, comp); | |
1240 if (k < 0) | |
1241 return -1; | |
1242 pa += k; ipa += k; | |
1243 na -= k; | |
1244 if (na == 0) | |
1245 return 0; | |
1246 | |
1247 /* Where does a end in b? Elements in b after that can be | |
1248 * ignored (already in place). | |
1249 */ | |
1250 nb = gallop_left (pa[na-1], pb, nb, nb-1, comp); | |
1251 if (nb <= 0) | |
1252 return nb; | |
1253 | |
1254 /* Merge what remains of the runs, using a temp array with | |
15018
3d8ace26c5b4
maint: Use Octave coding conventions for cuddled parentheses in liboctave/.
Rik <rik@octave.org>
parents:
14138
diff
changeset
|
1255 * min (na, nb) elements. |
8700 | 1256 */ |
1257 if (na <= nb) | |
1258 return merge_lo (pa, ipa, na, pb, ipb, nb, comp); | |
1259 else | |
1260 return merge_hi (pa, ipa, na, pb, ipb, nb, comp); | |
4851 | 1261 } |
1262 | |
1263 /* Examine the stack of runs waiting to be merged, merging adjacent runs | |
1264 * until the stack invariants are re-established: | |
1265 * | |
1266 * 1. len[-3] > len[-2] + len[-1] | |
1267 * 2. len[-2] > len[-1] | |
1268 * | |
1269 * See listsort.txt for more info. | |
1270 * | |
1271 * Returns 0 on success, -1 on error. | |
1272 */ | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1273 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1274 template <typename Comp> |
4851 | 1275 int |
8700 | 1276 octave_sort<T>::merge_collapse (T *data, Comp comp) |
4851 | 1277 { |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1278 struct s_slice *p = m_ms->m_pending; |
4851 | 1279 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1280 while (m_ms->m_n > 1) |
4851 | 1281 { |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1282 octave_idx_type n = m_ms->m_n - 2; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1283 if (n > 0 && p[n-1].m_len <= p[n].m_len + p[n+1].m_len) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1284 { |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1285 if (p[n-1].m_len < p[n+1].m_len) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1286 --n; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1287 if (merge_at (n, data, comp) < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1288 return -1; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1289 } |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1290 else if (p[n].m_len <= p[n+1].m_len) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1291 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1292 if (merge_at (n, data, comp) < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1293 return -1; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1294 } |
8700 | 1295 else |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1296 break; |
8700 | 1297 } |
1298 | |
1299 return 0; | |
1300 } | |
1301 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1302 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1303 template <typename Comp> |
8700 | 1304 int |
1305 octave_sort<T>::merge_collapse (T *data, octave_idx_type *idx, Comp comp) | |
1306 { | |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1307 struct s_slice *p = m_ms->m_pending; |
8700 | 1308 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1309 while (m_ms->m_n > 1) |
8700 | 1310 { |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1311 octave_idx_type n = m_ms->m_n - 2; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1312 if (n > 0 && p[n-1].m_len <= p[n].m_len + p[n+1].m_len) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1313 { |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1314 if (p[n-1].m_len < p[n+1].m_len) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1315 --n; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1316 if (merge_at (n, data, idx, comp) < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1317 return -1; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1318 } |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1319 else if (p[n].m_len <= p[n+1].m_len) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1320 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1321 if (merge_at (n, data, idx, comp) < 0) |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1322 return -1; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1323 } |
4851 | 1324 else |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1325 break; |
4851 | 1326 } |
7234 | 1327 |
4851 | 1328 return 0; |
1329 } | |
1330 | |
1331 /* Regardless of invariants, merge all runs on the stack until only one | |
1332 * remains. This is used at the end of the mergesort. | |
1333 * | |
1334 * Returns 0 on success, -1 on error. | |
1335 */ | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1336 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1337 template <typename Comp> |
4851 | 1338 int |
8700 | 1339 octave_sort<T>::merge_force_collapse (T *data, Comp comp) |
4851 | 1340 { |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1341 struct s_slice *p = m_ms->m_pending; |
4851 | 1342 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1343 while (m_ms->m_n > 1) |
4851 | 1344 { |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1345 octave_idx_type n = m_ms->m_n - 2; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1346 if (n > 0 && p[n-1].m_len < p[n+1].m_len) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1347 --n; |
8700 | 1348 if (merge_at (n, data, comp) < 0) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1349 return -1; |
8700 | 1350 } |
1351 | |
1352 return 0; | |
1353 } | |
1354 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1355 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1356 template <typename Comp> |
8700 | 1357 int |
1358 octave_sort<T>::merge_force_collapse (T *data, octave_idx_type *idx, Comp comp) | |
1359 { | |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1360 struct s_slice *p = m_ms->m_pending; |
8700 | 1361 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1362 while (m_ms->m_n > 1) |
8700 | 1363 { |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1364 octave_idx_type n = m_ms->m_n - 2; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1365 if (n > 0 && p[n-1].m_len < p[n+1].m_len) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1366 --n; |
8700 | 1367 if (merge_at (n, data, idx, comp) < 0) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1368 return -1; |
4851 | 1369 } |
7234 | 1370 |
4851 | 1371 return 0; |
1372 } | |
1373 | |
1374 /* Compute a good value for the minimum run length; natural runs shorter | |
1375 * than this are boosted artificially via binary insertion. | |
1376 * | |
1377 * If n < 64, return n (it's too small to bother with fancy stuff). | |
1378 * Else if n is an exact power of 2, return 32. | |
1379 * Else return an int k, 32 <= k <= 64, such that n/k is close to, but | |
1380 * strictly less than, an exact power of 2. | |
1381 * | |
1382 * See listsort.txt for more info. | |
1383 */ | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1384 template <typename T> |
7433 | 1385 octave_idx_type |
1386 octave_sort<T>::merge_compute_minrun (octave_idx_type n) | |
4851 | 1387 { |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1388 octave_idx_type r = 0; /* becomes 1 if any 1 bits are shifted off */ |
4851 | 1389 |
7234 | 1390 while (n >= 64) |
1391 { | |
1392 r |= n & 1; | |
1393 n >>= 1; | |
1394 } | |
1395 | |
4851 | 1396 return n + r; |
1397 } | |
1398 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1399 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1400 template <typename Comp> |
4851 | 1401 void |
8700 | 1402 octave_sort<T>::sort (T *data, octave_idx_type nel, Comp comp) |
4851 | 1403 { |
1404 /* Re-initialize the Mergestate as this might be the second time called */ | |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1405 if (! m_ms) m_ms = new MergeState; |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
1406 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1407 m_ms->reset (); |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1408 m_ms->getmem (MERGESTATE_TEMP_SIZE); |
4851 | 1409 |
8700 | 1410 if (nel > 1) |
4851 | 1411 { |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1412 octave_idx_type nremaining = nel; |
8700 | 1413 octave_idx_type lo = 0; |
1414 | |
1415 /* March over the array once, left to right, finding natural runs, | |
1416 * and extending short natural runs to minrun elements. | |
1417 */ | |
1418 octave_idx_type minrun = merge_compute_minrun (nremaining); | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1419 do |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1420 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1421 bool descending; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1422 octave_idx_type n; |
8700 | 1423 |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1424 /* Identify next run. */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1425 n = count_run (data + lo, nremaining, descending, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1426 if (n < 0) |
21168
26f85aa072de
maint: Replace instances of goto in liboctave where convenient.
Rik <rik@octave.org>
parents:
21139
diff
changeset
|
1427 return; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1428 if (descending) |
8700 | 1429 std::reverse (data + lo, data + lo + n); |
15018
3d8ace26c5b4
maint: Use Octave coding conventions for cuddled parentheses in liboctave/.
Rik <rik@octave.org>
parents:
14138
diff
changeset
|
1430 /* If short, extend to min (minrun, nremaining). */ |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1431 if (n < minrun) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1432 { |
23450
855122b993da
maint: Wrap tertiary operator in parentheses "(COND ? x : y)".
Rik <rik@octave.org>
parents:
23449
diff
changeset
|
1433 const octave_idx_type force = (nremaining <= minrun ? nremaining |
855122b993da
maint: Wrap tertiary operator in parentheses "(COND ? x : y)".
Rik <rik@octave.org>
parents:
23449
diff
changeset
|
1434 : minrun); |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1435 binarysort (data + lo, force, n, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1436 n = force; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1437 } |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1438 /* Push run onto m_pending-runs stack, and maybe merge. */ |
33248
7f73e4805a1f
replace calls to assert with liboctave_panic functions liboctave
John W. Eaton <jwe@octave.org>
parents:
32632
diff
changeset
|
1439 liboctave_panic_unless (m_ms->m_n < MAX_MERGE_PENDING); |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1440 m_ms->m_pending[m_ms->m_n].m_base = lo; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1441 m_ms->m_pending[m_ms->m_n].m_len = n; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1442 m_ms->m_n++; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1443 if (merge_collapse (data, comp) < 0) |
21168
26f85aa072de
maint: Replace instances of goto in liboctave where convenient.
Rik <rik@octave.org>
parents:
21139
diff
changeset
|
1444 return; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1445 /* Advance to find next run. */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1446 lo += n; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1447 nremaining -= n; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1448 } |
8700 | 1449 while (nremaining); |
1450 | |
1451 merge_force_collapse (data, comp); | |
1452 } | |
1453 } | |
1454 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1455 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1456 template <typename Comp> |
8700 | 1457 void |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1458 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel, |
8700 | 1459 Comp comp) |
1460 { | |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
1461 /* Re-initialize the Mergestate as this might be the second time called */ |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1462 if (! m_ms) m_ms = new MergeState; |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
1463 |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1464 m_ms->reset (); |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1465 m_ms->getmemi (MERGESTATE_TEMP_SIZE); |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
1466 |
8700 | 1467 if (nel > 1) |
1468 { | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1469 octave_idx_type nremaining = nel; |
8700 | 1470 octave_idx_type lo = 0; |
4851 | 1471 |
1472 /* March over the array once, left to right, finding natural runs, | |
1473 * and extending short natural runs to minrun elements. | |
1474 */ | |
7433 | 1475 octave_idx_type minrun = merge_compute_minrun (nremaining); |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1476 do |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1477 { |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1478 bool descending; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1479 octave_idx_type n; |
4851 | 1480 |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1481 /* Identify next run. */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1482 n = count_run (data + lo, nremaining, descending, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1483 if (n < 0) |
21168
26f85aa072de
maint: Replace instances of goto in liboctave where convenient.
Rik <rik@octave.org>
parents:
21139
diff
changeset
|
1484 return; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1485 if (descending) |
8700 | 1486 { |
1487 std::reverse (data + lo, data + lo + n); | |
1488 std::reverse (idx + lo, idx + lo + n); | |
1489 } | |
15018
3d8ace26c5b4
maint: Use Octave coding conventions for cuddled parentheses in liboctave/.
Rik <rik@octave.org>
parents:
14138
diff
changeset
|
1490 /* If short, extend to min (minrun, nremaining). */ |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1491 if (n < minrun) |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1492 { |
23450
855122b993da
maint: Wrap tertiary operator in parentheses "(COND ? x : y)".
Rik <rik@octave.org>
parents:
23449
diff
changeset
|
1493 const octave_idx_type force = (nremaining <= minrun ? nremaining |
855122b993da
maint: Wrap tertiary operator in parentheses "(COND ? x : y)".
Rik <rik@octave.org>
parents:
23449
diff
changeset
|
1494 : minrun); |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1495 binarysort (data + lo, idx + lo, force, n, comp); |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1496 n = force; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1497 } |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1498 /* Push run onto m_pending-runs stack, and maybe merge. */ |
33248
7f73e4805a1f
replace calls to assert with liboctave_panic functions liboctave
John W. Eaton <jwe@octave.org>
parents:
32632
diff
changeset
|
1499 liboctave_panic_unless (m_ms->m_n < MAX_MERGE_PENDING); |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1500 m_ms->m_pending[m_ms->m_n].m_base = lo; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1501 m_ms->m_pending[m_ms->m_n].m_len = n; |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1502 m_ms->m_n++; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1503 if (merge_collapse (data, idx, comp) < 0) |
21168
26f85aa072de
maint: Replace instances of goto in liboctave where convenient.
Rik <rik@octave.org>
parents:
21139
diff
changeset
|
1504 return; |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1505 /* Advance to find next run. */ |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1506 lo += n; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1507 nremaining -= n; |
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1508 } |
7234 | 1509 while (nremaining); |
4851 | 1510 |
8700 | 1511 merge_force_collapse (data, idx, comp); |
4851 | 1512 } |
1513 } | |
1514 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1515 template <typename T> |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1516 using compare_fcn_ptr = bool (*) (typename ref_param<T>::type, |
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1517 typename ref_param<T>::type); |
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1518 |
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1519 template <typename T> |
8700 | 1520 void |
1521 octave_sort<T>::sort (T *data, octave_idx_type nel) | |
1522 { | |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1523 #if defined (INLINE_ASCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1524 if (*m_compare.template target<compare_fcn_ptr<T>> () == ascending_compare) |
8700 | 1525 sort (data, nel, std::less<T> ()); |
1526 else | |
1527 #endif | |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1528 #if defined (INLINE_DESCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1529 if (*m_compare.template target<compare_fcn_ptr<T>> () == descending_compare) |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1530 sort (data, nel, std::greater<T> ()); |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
1531 else |
8700 | 1532 #endif |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1533 if (m_compare) |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1534 sort (data, nel, m_compare); |
8700 | 1535 } |
1536 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1537 template <typename T> |
8700 | 1538 void |
1539 octave_sort<T>::sort (T *data, octave_idx_type *idx, octave_idx_type nel) | |
1540 { | |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1541 #if defined (INLINE_ASCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1542 if (*m_compare.template target<compare_fcn_ptr<T>> () == ascending_compare) |
8700 | 1543 sort (data, idx, nel, std::less<T> ()); |
1544 else | |
1545 #endif | |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1546 #if defined (INLINE_DESCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1547 if (*m_compare.template target<compare_fcn_ptr<T>> () == descending_compare) |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1548 sort (data, idx, nel, std::greater<T> ()); |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
1549 else |
8700 | 1550 #endif |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1551 if (m_compare) |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1552 sort (data, idx, nel, m_compare); |
8700 | 1553 } |
1554 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1555 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1556 template <typename Comp> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1557 bool |
23588
0549061d35b9
maint: Deprecate is_sorted and replace with issorted.
Rik <rik@octave.org>
parents:
23450
diff
changeset
|
1558 octave_sort<T>::issorted (const T *data, octave_idx_type nel, Comp comp) |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1559 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1560 const T *end = data + nel; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1561 if (data != end) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1562 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1563 const T *next = data; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1564 while (++next != end) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1565 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1566 if (comp (*next, *data)) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1567 break; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1568 data = next; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1569 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1570 data = next; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1571 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1572 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1573 return data == end; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1574 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1575 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1576 template <typename T> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1577 bool |
23588
0549061d35b9
maint: Deprecate is_sorted and replace with issorted.
Rik <rik@octave.org>
parents:
23450
diff
changeset
|
1578 octave_sort<T>::issorted (const T *data, octave_idx_type nel) |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1579 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1580 bool retval = false; |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1581 #if defined (INLINE_ASCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1582 if (*m_compare.template target<compare_fcn_ptr<T>> () == ascending_compare) |
23588
0549061d35b9
maint: Deprecate is_sorted and replace with issorted.
Rik <rik@octave.org>
parents:
23450
diff
changeset
|
1583 retval = issorted (data, nel, std::less<T> ()); |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1584 else |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1585 #endif |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1586 #if defined (INLINE_DESCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1587 if (*m_compare.template target<compare_fcn_ptr<T>> () == descending_compare) |
23588
0549061d35b9
maint: Deprecate is_sorted and replace with issorted.
Rik <rik@octave.org>
parents:
23450
diff
changeset
|
1588 retval = issorted (data, nel, std::greater<T> ()); |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
1589 else |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1590 #endif |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1591 if (m_compare) |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1592 retval = issorted (data, nel, m_compare); |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1593 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1594 return retval; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1595 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1596 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1597 struct sortrows_run_t |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1598 { |
30155
14b098a6ba46
maint: Use public: qualifier in structs that are really classes.
Rik <rik@octave.org>
parents:
29655
diff
changeset
|
1599 public: |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1600 sortrows_run_t (octave_idx_type c, octave_idx_type o, octave_idx_type n) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1601 : col (c), ofs (o), nel (n) { } |
30155
14b098a6ba46
maint: Use public: qualifier in structs that are really classes.
Rik <rik@octave.org>
parents:
29655
diff
changeset
|
1602 //-------- |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1603 octave_idx_type col, ofs, nel; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1604 }; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1605 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1606 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1607 template <typename Comp> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1608 void |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1609 octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx, |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1610 octave_idx_type rows, octave_idx_type cols, |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1611 Comp comp) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1612 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1613 OCTAVE_LOCAL_BUFFER (T, buf, rows); |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1614 for (octave_idx_type i = 0; i < rows; i++) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1615 idx[i] = i; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1616 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1617 if (cols == 0 || rows <= 1) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1618 return; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1619 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1620 // This is a breadth-first traversal. |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1621 typedef sortrows_run_t run_t; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1622 std::stack<run_t> runs; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1623 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1624 runs.push (run_t (0, 0, rows)); |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1625 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1626 while (! runs.empty ()) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1627 { |
15018
3d8ace26c5b4
maint: Use Octave coding conventions for cuddled parentheses in liboctave/.
Rik <rik@octave.org>
parents:
14138
diff
changeset
|
1628 octave_idx_type col = runs.top ().col; |
3d8ace26c5b4
maint: Use Octave coding conventions for cuddled parentheses in liboctave/.
Rik <rik@octave.org>
parents:
14138
diff
changeset
|
1629 octave_idx_type ofs = runs.top ().ofs; |
3d8ace26c5b4
maint: Use Octave coding conventions for cuddled parentheses in liboctave/.
Rik <rik@octave.org>
parents:
14138
diff
changeset
|
1630 octave_idx_type nel = runs.top ().nel; |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1631 runs.pop (); |
33248
7f73e4805a1f
replace calls to assert with liboctave_panic functions liboctave
John W. Eaton <jwe@octave.org>
parents:
32632
diff
changeset
|
1632 liboctave_panic_unless (nel > 1); |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1633 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1634 T *lbuf = buf + ofs; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1635 const T *ldata = data + rows*col; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1636 octave_idx_type *lidx = idx + ofs; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1637 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1638 // Gather. |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1639 for (octave_idx_type i = 0; i < nel; i++) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1640 lbuf[i] = ldata[lidx[i]]; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1641 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1642 // Sort. |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1643 sort (lbuf, lidx, nel, comp); |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1644 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1645 // Identify constant runs and schedule subsorts. |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1646 if (col < cols-1) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1647 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1648 octave_idx_type lst = 0; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1649 for (octave_idx_type i = 0; i < nel; i++) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1650 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1651 if (comp (lbuf[lst], lbuf[i])) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1652 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1653 if (i > lst + 1) |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
1654 runs.push (run_t (col+1, ofs + lst, i - lst)); |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1655 lst = i; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1656 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1657 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1658 if (nel > lst + 1) |
8820
89b95972e178
fix previously introduced problem in octave_sort, improve design
Jaroslav Hajek <highegg@gmail.com>
parents:
8816
diff
changeset
|
1659 runs.push (run_t (col+1, ofs + lst, nel - lst)); |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1660 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1661 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1662 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1663 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1664 template <typename T> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1665 void |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1666 octave_sort<T>::sort_rows (const T *data, octave_idx_type *idx, |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1667 octave_idx_type rows, octave_idx_type cols) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1668 { |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1669 #if defined (INLINE_ASCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1670 if (*m_compare.template target<compare_fcn_ptr<T>> () == ascending_compare) |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1671 sort_rows (data, idx, rows, cols, std::less<T> ()); |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1672 else |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1673 #endif |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1674 #if defined (INLINE_DESCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1675 if (*m_compare.template target<compare_fcn_ptr<T>> () == descending_compare) |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1676 sort_rows (data, idx, rows, cols, std::greater<T> ()); |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
1677 else |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1678 #endif |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1679 if (m_compare) |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1680 sort_rows (data, idx, rows, cols, m_compare); |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1681 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1682 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1683 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1684 template <typename Comp> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1685 bool |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1686 octave_sort<T>::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
|
1687 octave_idx_type cols, Comp comp) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1688 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1689 if (rows <= 1 || cols == 0) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1690 return true; |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1691 |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1692 // This is a breadth-first traversal. |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1693 const T *lastrow = data + rows*(cols - 1); |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1694 typedef std::pair<const T *, octave_idx_type> run_t; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1695 std::stack<run_t> runs; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1696 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1697 bool sorted = true; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1698 runs.push (run_t (data, rows)); |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1699 while (sorted && ! runs.empty ()) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1700 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1701 const T *lo = runs.top ().first; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1702 octave_idx_type n = runs.top ().second; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1703 runs.pop (); |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1704 if (lo < lastrow) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1705 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1706 // Not the final column. |
33248
7f73e4805a1f
replace calls to assert with liboctave_panic functions liboctave
John W. Eaton <jwe@octave.org>
parents:
32632
diff
changeset
|
1707 liboctave_panic_unless (n > 1); |
18084
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
1708 const T *hi = lo + n; |
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
1709 const T *lst = lo; |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1710 for (lo++; lo < hi; lo++) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1711 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1712 if (comp (*lst, *lo)) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1713 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1714 if (lo > lst + 1) |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
1715 runs.push (run_t (lst + rows, lo - lst)); |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1716 lst = lo; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1717 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1718 else if (comp (*lo, *lst)) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1719 break; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1720 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1721 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1722 if (lo == hi) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1723 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1724 if (lo > lst + 1) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1725 runs.push (run_t (lst + rows, lo - lst)); |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1726 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1727 else |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1728 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1729 sorted = false; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1730 break; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1731 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1732 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1733 else |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1734 // The final column - use fast code. |
23588
0549061d35b9
maint: Deprecate is_sorted and replace with issorted.
Rik <rik@octave.org>
parents:
23450
diff
changeset
|
1735 sorted = issorted (lo, n, comp); |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1736 } |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1737 |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1738 return sorted; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1739 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1740 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1741 template <typename T> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1742 bool |
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1743 octave_sort<T>::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
|
1744 octave_idx_type cols) |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1745 { |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1746 bool retval = false; |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1747 #if defined (INLINE_ASCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1748 if (*m_compare.template target<compare_fcn_ptr<T>> () == ascending_compare) |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1749 retval = is_sorted_rows (data, rows, cols, std::less<T> ()); |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1750 else |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1751 #endif |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1752 #if defined (INLINE_DESCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1753 if (*m_compare.template target<compare_fcn_ptr<T>> () == descending_compare) |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1754 retval = is_sorted_rows (data, rows, cols, std::greater<T> ()); |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
1755 else |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1756 #endif |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1757 if (m_compare) |
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1758 retval = is_sorted_rows (data, rows, cols, m_compare); |
8721
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1759 |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1760 return retval; |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1761 } |
e9cb742df9eb
imported patch sort3.diff
Jaroslav Hajek <highegg@gmail.com>
parents:
8700
diff
changeset
|
1762 |
9407
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1763 // The simple binary lookup. |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1764 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1765 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1766 template <typename Comp> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1767 octave_idx_type |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1768 octave_sort<T>::lookup (const T *data, octave_idx_type nel, |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1769 const T& value, Comp comp) |
9362
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1770 { |
18084
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
1771 octave_idx_type lo = 0; |
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
1772 octave_idx_type hi = nel; |
9407
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1773 |
9362
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1774 while (lo < hi) |
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1775 { |
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1776 octave_idx_type mid = lo + ((hi-lo) >> 1); |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1777 if (comp (value, data[mid])) |
9362
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1778 hi = mid; |
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1779 else |
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1780 lo = mid + 1; |
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1781 } |
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1782 |
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1783 return lo; |
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1784 } |
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1785 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1786 template <typename T> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1787 octave_idx_type |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1788 octave_sort<T>::lookup (const T *data, octave_idx_type nel, |
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1789 const T& value) |
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1790 { |
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1791 octave_idx_type retval = 0; |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1792 #if defined (INLINE_ASCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1793 if (*m_compare.template target<compare_fcn_ptr<T>> () == ascending_compare) |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1794 retval = lookup (data, nel, value, std::less<T> ()); |
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1795 else |
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1796 #endif |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1797 #if defined (INLINE_DESCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1798 if (*m_compare.template target<compare_fcn_ptr<T>> () == descending_compare) |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1799 retval = lookup (data, nel, value, std::greater<T> ()); |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
1800 else |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1801 #endif |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1802 if (m_compare) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1803 retval = lookup (data, nel, value, m_compare); |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1804 |
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1805 return retval; |
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1806 } |
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1807 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1808 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1809 template <typename Comp> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1810 void |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1811 octave_sort<T>::lookup (const T *data, octave_idx_type nel, |
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1812 const T *values, octave_idx_type nvalues, |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1813 octave_idx_type *idx, Comp comp) |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1814 { |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1815 // Use a sequence of binary lookups. |
21578
683a1beee538
maint: Use "FIXME:" for all code blocks needing further attention.
Rik <rik@octave.org>
parents:
21301
diff
changeset
|
1816 // FIXME: Can this be sped up generally? The sorted merge case is dealt with |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1817 // elsewhere. |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1818 for (octave_idx_type j = 0; j < nvalues; j++) |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1819 idx[j] = lookup (data, nel, values[j], comp); |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1820 } |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1821 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1822 template <typename T> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1823 void |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1824 octave_sort<T>::lookup (const T *data, octave_idx_type nel, |
23449
c763214a8260
maint: Use convention 'int *x' for naming pointers.
Rik <rik@octave.org>
parents:
23220
diff
changeset
|
1825 const T *values, octave_idx_type nvalues, |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1826 octave_idx_type *idx) |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1827 { |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1828 #if defined (INLINE_ASCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1829 if (*m_compare.template target<compare_fcn_ptr<T>> () == ascending_compare) |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1830 lookup (data, nel, values, nvalues, idx, std::less<T> ()); |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1831 else |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1832 #endif |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1833 #if defined (INLINE_DESCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1834 if (*m_compare.template target<compare_fcn_ptr<T>> () == descending_compare) |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1835 lookup (data, nel, values, nvalues, idx, std::greater<T> ()); |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
1836 else |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1837 #endif |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1838 if (m_compare) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1839 lookup (data, nel, values, nvalues, idx, m_compare); |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1840 } |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1841 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1842 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1843 template <typename Comp> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1844 void |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1845 octave_sort<T>::lookup_sorted (const T *data, octave_idx_type nel, |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1846 const T *values, octave_idx_type nvalues, |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1847 octave_idx_type *idx, bool rev, Comp comp) |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1848 { |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1849 if (rev) |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1850 { |
18084
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
1851 octave_idx_type i = 0; |
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
1852 octave_idx_type j = nvalues - 1; |
9407
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1853 |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1854 if (nvalues > 0 && nel > 0) |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1855 { |
9407
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1856 while (true) |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1857 { |
9407
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1858 if (comp (values[j], data[i])) |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1859 { |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1860 idx[j] = i; |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1861 if (--j < 0) |
9407
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1862 break; |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1863 } |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1864 else if (++i == nel) |
9362
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1865 break; |
8814
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1866 } |
de16ebeef93d
improve lookup, provide Array<T>::lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
8725
diff
changeset
|
1867 } |
9362
2ebf3ca62add
use a smarter algorithm for default lookup
Jaroslav Hajek <highegg@gmail.com>
parents:
9341
diff
changeset
|
1868 |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1869 for (; j >= 0; j--) |
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1870 idx[j] = i; |
9407
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1871 } |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1872 else |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1873 { |
18084
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
1874 octave_idx_type i = 0; |
8e056300994b
Follow coding convention of defining and initializing only 1 variable per line in liboctave.
Rik <rik@octave.org>
parents:
17769
diff
changeset
|
1875 octave_idx_type j = 0; |
9407
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1876 |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1877 if (nvalues > 0 && nel > 0) |
9407
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1878 { |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1879 while (true) |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1880 { |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1881 if (comp (values[j], data[i])) |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1882 { |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1883 idx[j] = i; |
9407
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1884 if (++j == nvalues) |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1885 break; |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1886 } |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1887 else if (++i == nel) |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1888 break; |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1889 } |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1890 } |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1891 |
0951174cbb03
remove experimental stuff from lookup, simplify
Jaroslav Hajek <highegg@gmail.com>
parents:
9400
diff
changeset
|
1892 for (; j != nvalues; j++) |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1893 idx[j] = i; |
9341
9fd5c56ce57a
extend lookup capabilities
Jaroslav Hajek <highegg@gmail.com>
parents:
8820
diff
changeset
|
1894 } |
9fd5c56ce57a
extend lookup capabilities
Jaroslav Hajek <highegg@gmail.com>
parents:
8820
diff
changeset
|
1895 } |
9fd5c56ce57a
extend lookup capabilities
Jaroslav Hajek <highegg@gmail.com>
parents:
8820
diff
changeset
|
1896 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1897 template <typename T> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1898 void |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1899 octave_sort<T>::lookup_sorted (const T *data, octave_idx_type nel, |
23449
c763214a8260
maint: Use convention 'int *x' for naming pointers.
Rik <rik@octave.org>
parents:
23220
diff
changeset
|
1900 const T *values, octave_idx_type nvalues, |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1901 octave_idx_type *idx, bool rev) |
9341
9fd5c56ce57a
extend lookup capabilities
Jaroslav Hajek <highegg@gmail.com>
parents:
8820
diff
changeset
|
1902 { |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1903 #if defined (INLINE_ASCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1904 if (*m_compare.template target<compare_fcn_ptr<T>> () == ascending_compare) |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1905 lookup_sorted (data, nel, values, nvalues, idx, rev, std::less<T> ()); |
9341
9fd5c56ce57a
extend lookup capabilities
Jaroslav Hajek <highegg@gmail.com>
parents:
8820
diff
changeset
|
1906 else |
9fd5c56ce57a
extend lookup capabilities
Jaroslav Hajek <highegg@gmail.com>
parents:
8820
diff
changeset
|
1907 #endif |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1908 #if defined (INLINE_DESCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1909 if (*m_compare.template target<compare_fcn_ptr<T>> () == descending_compare) |
9921
7c8392a034e6
fix & improve lookup API
Jaroslav Hajek <highegg@gmail.com>
parents:
9725
diff
changeset
|
1910 lookup_sorted (data, nel, values, nvalues, idx, rev, std::greater<T> ()); |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
1911 else |
9341
9fd5c56ce57a
extend lookup capabilities
Jaroslav Hajek <highegg@gmail.com>
parents:
8820
diff
changeset
|
1912 #endif |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1913 if (m_compare) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1914 lookup_sorted (data, nel, values, nvalues, idx, rev, m_compare); |
9341
9fd5c56ce57a
extend lookup capabilities
Jaroslav Hajek <highegg@gmail.com>
parents:
8820
diff
changeset
|
1915 } |
9fd5c56ce57a
extend lookup capabilities
Jaroslav Hajek <highegg@gmail.com>
parents:
8820
diff
changeset
|
1916 |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1917 template <typename T> |
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1918 template <typename Comp> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1919 void |
9725 | 1920 octave_sort<T>::nth_element (T *data, octave_idx_type nel, |
1921 octave_idx_type lo, octave_idx_type up, | |
1922 Comp comp) | |
1923 { | |
1924 // Simply wrap the STL algorithms. | |
1925 // FIXME: this will fail if we attempt to inline <,> for Complex. | |
1926 if (up == lo+1) | |
1927 std::nth_element (data, data + lo, data + nel, comp); | |
1928 else if (lo == 0) | |
1929 std::partial_sort (data, data + up, data + nel, comp); | |
1930 else | |
1931 { | |
1932 std::nth_element (data, data + lo, data + nel, comp); | |
1933 if (up == lo + 2) | |
1934 { | |
1935 // Finding two subsequent elements. | |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1936 std::swap (data[lo+1], |
9725 | 1937 *std::min_element (data + lo + 1, data + nel, comp)); |
1938 } | |
1939 else | |
1940 std::partial_sort (data + lo + 1, data + up, data + nel, comp); | |
1941 } | |
1942 } | |
1943 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1944 template <typename T> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1945 void |
9725 | 1946 octave_sort<T>::nth_element (T *data, octave_idx_type nel, |
1947 octave_idx_type lo, octave_idx_type up) | |
1948 { | |
1949 if (up < 0) | |
1950 up = lo + 1; | |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1951 |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1952 #if defined (INLINE_ASCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1953 if (*m_compare.template target<compare_fcn_ptr<T>> () == ascending_compare) |
9725 | 1954 nth_element (data, nel, lo, up, std::less<T> ()); |
1955 else | |
1956 #endif | |
21724
aba2e6293dd8
use "#if ..." consistently instead of "#ifdef" and "#ifndef"
John W. Eaton <jwe@octave.org>
parents:
21690
diff
changeset
|
1957 #if defined (INLINE_DESCENDING_SORT) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1958 if (*m_compare.template target<compare_fcn_ptr<T>> () == descending_compare) |
9725 | 1959 nth_element (data, nel, lo, up, std::greater<T> ()); |
17769
49a5a4be04a1
maint: Use GNU style coding conventions for code in liboctave/
Rik <rik@octave.org>
parents:
17744
diff
changeset
|
1960 else |
9725 | 1961 #endif |
27379
3db033e86376
use m_ prefix for data members in most liboctave/util classes
John W. Eaton <jwe@octave.org>
parents:
26397
diff
changeset
|
1962 if (m_compare) |
29280
448bbc1f99a1
oct-sort.h: Use std::function for passing compare function.
Markus Mützel <markus.muetzel@gmx.de>
parents:
27923
diff
changeset
|
1963 nth_element (data, nel, lo, up, m_compare); |
9725 | 1964 } |
1965 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1966 template <typename T> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1967 bool |
8725 | 1968 octave_sort<T>::ascending_compare (typename ref_param<T>::type x, |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1969 typename ref_param<T>::type y) |
8700 | 1970 { |
1971 return x < y; | |
1972 } | |
1973 | |
21139
538b57866b90
consistently use "typename" intead of "class" in template declarations
John W. Eaton <jwe@octave.org>
parents:
19697
diff
changeset
|
1974 template <typename T> |
11586
12df7854fa7c
strip trailing whitespace from source files
John W. Eaton <jwe@octave.org>
parents:
11523
diff
changeset
|
1975 bool |
8725 | 1976 octave_sort<T>::descending_compare (typename ref_param<T>::type x, |
10314
07ebe522dac2
untabify liboctave C++ sources
John W. Eaton <jwe@octave.org>
parents:
10158
diff
changeset
|
1977 typename ref_param<T>::type y) |
8700 | 1978 { |
1979 return x > y; | |
1980 } |