2
Copyright (C) 2003, 2004, 2005, 2006, 2007 David Bateman
4
This file is part of Octave.
6
Octave is free software; you can redistribute it and/or modify it
7
under the terms of the GNU General Public License as published by the
8
Free Software Foundation; either version 3 of the License, or (at your
9
option) any later version.
11
Octave is distributed in the hope that it will be useful, but WITHOUT
12
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16
You should have received a copy of the GNU General Public License
17
along with Octave; see the file COPYING. If not, see
18
<http://www.gnu.org/licenses/>.
20
Code stolen in large part from Python's, listobject.c, which itself had
21
no license header. However, thanks to Tim Peters for the parts of the
24
As required in the Python license the short description of the changes
27
* convert the sorting code in listobject.cc into a generic class,
28
replacing PyObject* with the type of the class T.
32
PSF LICENSE AGREEMENT FOR PYTHON 2.3
33
--------------------------------------
35
1. This LICENSE AGREEMENT is between the Python Software Foundation
36
("PSF"), and the Individual or Organization ("Licensee") accessing and
37
otherwise using Python 2.3 software in source or binary form and its
38
associated documentation.
40
2. Subject to the terms and conditions of this License Agreement, PSF
41
hereby grants Licensee a nonexclusive, royalty-free, world-wide
42
license to reproduce, analyze, test, perform and/or display publicly,
43
prepare derivative works, distribute, and otherwise use Python 2.3
44
alone or in any derivative version, provided, however, that PSF's
45
License Agreement and PSF's notice of copyright, i.e., "Copyright (c)
46
2001, 2002, 2003 Python Software Foundation; All Rights Reserved" are
47
retained in Python 2.3 alone or in any derivative version prepared by
50
3. In the event Licensee prepares a derivative work that is based on
51
or incorporates Python 2.3 or any part thereof, and wants to make
52
the derivative work available to others as provided herein, then
53
Licensee hereby agrees to include in any such work a brief summary of
54
the changes made to Python 2.3.
56
4. PSF is making Python 2.3 available to Licensee on an "AS IS"
57
basis. PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR
58
IMPLIED. BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND
59
DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS
60
FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON 2.3 WILL NOT
61
INFRINGE ANY THIRD PARTY RIGHTS.
63
5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON
64
2.3 FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS
65
A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON 2.3,
66
OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF.
68
6. This License Agreement will automatically terminate upon a material
69
breach of its terms and conditions.
71
7. Nothing in this License Agreement shall be deemed to create any
72
relationship of agency, partnership, or joint venture between PSF and
73
Licensee. This License Agreement does not grant permission to use PSF
74
trademarks or trade name in a trademark sense to endorse or promote
75
products or services of Licensee, or any third party.
77
8. By copying, installing or otherwise using Python 2.3, Licensee
78
agrees to be bound by the terms and conditions of this License
82
#if !defined (octave_sort_h)
83
#define octave_sort_h 1
85
// The maximum number of entries in a MergeState's pending-runs stack.
86
// This is enough to sort arrays of size up to about
87
// 32 * phi ** MAX_MERGE_PENDING
88
// where phi ~= 1.618. 85 is ridiculously large enough, good for an array
89
// with 2**64 elements.
90
#define MAX_MERGE_PENDING 85
92
// When we get into galloping mode, we stay there until both runs win less
93
// often than MIN_GALLOP consecutive times. See listsort.txt for more info.
96
// Avoid malloc for small temp arrays.
97
#define MERGESTATE_TEMP_SIZE 1024
107
octave_sort (bool (*comp) (T, T));
109
~octave_sort (void) { merge_freemem (); }
111
void set_compare (bool (*comp) (T, T)) { compare = comp; }
113
void sort (T *v, int elements);
117
// One MergeState exists on the stack per invocation of mergesort.
118
// It's just a convenient way to pass state around among the helper
121
// DGB: This isn't needed with mergesort in a class, but it doesn't
122
// slow things up, and it is likely to make my life easier for any
123
// potential backporting of changes in the Python code.
133
// This controls when we get *into* galloping mode. It's
134
// initialized to MIN_GALLOP. merge_lo and merge_hi tend to nudge
135
// it higher for random data, and lower for highly structured
139
// 'a' is temp storage to help with merges. It contains room for
141
T *a; // may point to temparray below
144
// A stack of n pending runs yet to be merged. Run #i starts at
145
// address base[i] and extends for len[i] elements. It's always
146
// true (so long as the indices are in bounds) that
148
// pending[i].base + pending[i].len == pending[i+1].base
150
// so we could cut the storage for this, but it's a minor amount,
151
// and keeping all the info explicit simplifies the code.
153
struct s_slice pending[MAX_MERGE_PENDING];
156
bool (*compare) (T, T);
160
void reverse_slice (T *lo, T *hi);
162
void binarysort (T *lo, T *hi, T *start);
164
int count_run (T *lo, T *hi, int *descending);
166
int gallop_left (T key, T *a, int n, int hint);
168
int gallop_right (T key, T *a, int n, int hint);
170
void merge_init (void);
172
void merge_freemem (void);
174
int merge_getmem (int need);
176
int merge_lo (T *pa, int na, T *pb, int nb);
178
int merge_hi (T *pa, int na, T *pb, int nb);
180
int merge_at (int i);
182
int merge_collapse (void);
184
int merge_force_collapse (void);
186
int merge_compute_minrun (int n);
192
;;; Local Variables: ***
added
removed
liboctave/oct-sort.h
