octave-nkf: liboctave/util/oct-sort.cc annotate

annotate liboctave/util/oct-sort.cc @ 20330:2db2db2df55b

Automatically convert arrays of java primitives into Octave types (bug #44882) * libinterp/octave-value/ov-java.cc (box): when the result of a java method is a java primitive type, these are converted to octave types automatically. We seem to be handling this correctly for scalars but not for arrays yet. This fixes it on the java -> octave direction.

author	Carnë Draug <carandraug@octave.org>
date	Mon, 20 Apr 2015 15:01:27 +0100
parents	4197fc428c7d
children

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

Mercurial > hg > octave-nkf

annotate liboctave/util/oct-sort.cc @ 20330:2db2db2df55b