|
4851
|
1 /* |
|
|
2 Copyright (C) 2003 David Bateman |
|
|
3 |
|
|
4 This file is part of Octave. |
|
|
5 |
|
|
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 2, or (at your option) any |
|
|
9 later version. |
|
|
10 |
|
|
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 |
|
|
14 for more details. |
|
|
15 |
|
|
16 You should have received a copy of the GNU General Public License |
|
|
17 along with Octave; see the file COPYING. If not, write to the Free |
|
5307
|
18 Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
|
|
19 02110-1301, USA. |
|
4851
|
20 |
|
|
21 Code stolen in large part from Python's, listobject.c, which itself had |
|
|
22 no license header. However, thanks to Tim Peters for the parts of the |
|
|
23 code I ripped-off. |
|
|
24 |
|
|
25 As required in the Python license the short description of the changes |
|
|
26 made are |
|
|
27 |
|
|
28 * convert the sorting code in listobject.cc into a generic class, |
|
|
29 replacing PyObject* with the type of the class T. |
|
|
30 |
|
|
31 The Python license is |
|
|
32 |
|
|
33 PSF LICENSE AGREEMENT FOR PYTHON 2.3 |
|
|
34 -------------------------------------- |
|
|
35 |
|
|
36 1. This LICENSE AGREEMENT is between the Python Software Foundation |
|
|
37 ("PSF"), and the Individual or Organization ("Licensee") accessing and |
|
|
38 otherwise using Python 2.3 software in source or binary form and its |
|
|
39 associated documentation. |
|
|
40 |
|
|
41 2. Subject to the terms and conditions of this License Agreement, PSF |
|
|
42 hereby grants Licensee a nonexclusive, royalty-free, world-wide |
|
|
43 license to reproduce, analyze, test, perform and/or display publicly, |
|
|
44 prepare derivative works, distribute, and otherwise use Python 2.3 |
|
|
45 alone or in any derivative version, provided, however, that PSF's |
|
|
46 License Agreement and PSF's notice of copyright, i.e., "Copyright (c) |
|
|
47 2001, 2002, 2003 Python Software Foundation; All Rights Reserved" are |
|
|
48 retained in Python 2.3 alone or in any derivative version prepared by |
|
|
49 Licensee. |
|
|
50 |
|
|
51 3. In the event Licensee prepares a derivative work that is based on |
|
|
52 or incorporates Python 2.3 or any part thereof, and wants to make |
|
|
53 the derivative work available to others as provided herein, then |
|
|
54 Licensee hereby agrees to include in any such work a brief summary of |
|
|
55 the changes made to Python 2.3. |
|
|
56 |
|
|
57 4. PSF is making Python 2.3 available to Licensee on an "AS IS" |
|
|
58 basis. PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR |
|
|
59 IMPLIED. BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND |
|
|
60 DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS |
|
|
61 FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON 2.3 WILL NOT |
|
|
62 INFRINGE ANY THIRD PARTY RIGHTS. |
|
|
63 |
|
|
64 5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON |
|
|
65 2.3 FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS |
|
|
66 A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON 2.3, |
|
|
67 OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF. |
|
|
68 |
|
|
69 6. This License Agreement will automatically terminate upon a material |
|
|
70 breach of its terms and conditions. |
|
|
71 |
|
|
72 7. Nothing in this License Agreement shall be deemed to create any |
|
|
73 relationship of agency, partnership, or joint venture between PSF and |
|
|
74 Licensee. This License Agreement does not grant permission to use PSF |
|
|
75 trademarks or trade name in a trademark sense to endorse or promote |
|
|
76 products or services of Licensee, or any third party. |
|
|
77 |
|
|
78 8. By copying, installing or otherwise using Python 2.3, Licensee |
|
|
79 agrees to be bound by the terms and conditions of this License |
|
|
80 Agreement. |
|
|
81 */ |
|
|
82 |
|
|
83 #if !defined (octave_sort_h) |
|
|
84 #define octave_sort_h 1 |
|
|
85 |
|
|
86 /* The maximum number of entries in a MergeState's pending-runs stack. |
|
|
87 * This is enough to sort arrays of size up to about |
|
|
88 * 32 * phi ** MAX_MERGE_PENDING |
|
|
89 * where phi ~= 1.618. 85 is ridiculously large enough, good for an array |
|
|
90 * with 2**64 elements. |
|
|
91 */ |
|
|
92 #define MAX_MERGE_PENDING 85 |
|
|
93 |
|
|
94 /* When we get into galloping mode, we stay there until both runs win less |
|
|
95 * often than MIN_GALLOP consecutive times. See listsort.txt for more info. |
|
|
96 */ |
|
|
97 #define MIN_GALLOP 7 |
|
|
98 |
|
|
99 /* Avoid malloc for small temp arrays. */ |
|
|
100 #define MERGESTATE_TEMP_SIZE 1024 |
|
|
101 |
|
|
102 template <class T> |
|
|
103 class |
|
|
104 octave_sort |
|
|
105 { |
|
4998
|
106 public: |
|
|
107 |
|
4851
|
108 octave_sort (void); |
|
|
109 |
|
|
110 octave_sort (bool (*comp) (T, T)); |
|
|
111 |
|
4998
|
112 ~octave_sort (void) { merge_freemem (); } |
|
|
113 |
|
|
114 void set_compare (bool (*comp) (T, T)) { compare = comp; } |
|
4851
|
115 |
|
|
116 void sort (T *v, int elements); |
|
|
117 |
|
4998
|
118 private: |
|
|
119 |
|
4851
|
120 /* One MergeState exists on the stack per invocation of mergesort. It's just |
|
|
121 * a convenient way to pass state around among the helper functions. |
|
|
122 * |
|
|
123 * DGB: This isn't needed with mergesort in a class, but it doesn't slow |
|
|
124 * things up, and it is likely to make my life easier for any potential |
|
|
125 * backporting of changes in the Python code. |
|
|
126 */ |
|
|
127 |
|
|
128 struct s_slice |
|
|
129 { |
|
|
130 T *base; |
|
|
131 int len; |
|
|
132 }; |
|
|
133 |
|
|
134 typedef struct s_MergeState |
|
|
135 { |
|
|
136 /* This controls when we get *into* galloping mode. It's initialized |
|
|
137 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for |
|
|
138 * random data, and lower for highly structured data. |
|
|
139 */ |
|
|
140 int min_gallop; |
|
|
141 |
|
|
142 /* 'a' is temp storage to help with merges. It contains room for |
|
|
143 * alloced entries. |
|
|
144 */ |
|
|
145 T *a; /* may point to temparray below */ |
|
|
146 int alloced; |
|
|
147 |
|
|
148 /* A stack of n pending runs yet to be merged. Run #i starts at |
|
|
149 * address base[i] and extends for len[i] elements. It's always |
|
|
150 * true (so long as the indices are in bounds) that |
|
|
151 * |
|
|
152 * pending[i].base + pending[i].len == pending[i+1].base |
|
|
153 * |
|
|
154 * so we could cut the storage for this, but it's a minor amount, |
|
|
155 * and keeping all the info explicit simplifies the code. |
|
|
156 */ |
|
|
157 int n; |
|
|
158 struct s_slice pending[MAX_MERGE_PENDING]; |
|
|
159 } MergeState; |
|
|
160 |
|
|
161 bool (*compare)(T, T); |
|
|
162 |
|
|
163 MergeState ms; |
|
|
164 |
|
|
165 void reverse_slice (T *lo, T *hi); |
|
|
166 |
|
|
167 void binarysort (T *lo, T *hi, T *start); |
|
|
168 |
|
|
169 int count_run(T *lo, T *hi, int *descending); |
|
|
170 |
|
|
171 int gallop_left(T key, T *a, int n, int hint); |
|
|
172 |
|
|
173 int gallop_right(T key, T *a, int n, int hint); |
|
|
174 |
|
|
175 void merge_init(void); |
|
|
176 |
|
|
177 void merge_freemem(void); |
|
|
178 |
|
|
179 int merge_getmem(int need); |
|
|
180 |
|
|
181 int merge_lo(T *pa, int na, T *pb, int nb); |
|
|
182 |
|
|
183 int merge_hi(T *pa, int na, T *pb, int nb); |
|
|
184 |
|
|
185 int merge_at(int i); |
|
|
186 |
|
|
187 int merge_collapse(void); |
|
|
188 |
|
|
189 int merge_force_collapse(void); |
|
|
190 |
|
|
191 int merge_compute_minrun(int n); |
|
|
192 }; |
|
|
193 |
|
|
194 #endif |
|
|
195 |
|
|
196 /* |
|
|
197 ;;; Local Variables: *** |
|
|
198 ;;; mode: C++ *** |
|
|
199 ;;; End: *** |
|
|
200 */ |
