|
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 |
|
|
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
|
|
19 |
|
|
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 |
|
|
22 code I ripped-off. |
|
|
23 |
|
|
24 As required in the Python license the short description of the changes |
|
|
25 made are |
|
|
26 |
|
|
27 * convert the sorting code in listobject.cc into a generic class, |
|
|
28 replacing PyObject* with the type of the class T. |
|
|
29 |
|
|
30 The Python license is |
|
|
31 |
|
|
32 PSF LICENSE AGREEMENT FOR PYTHON 2.3 |
|
|
33 -------------------------------------- |
|
|
34 |
|
|
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. |
|
|
39 |
|
|
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 |
|
|
48 Licensee. |
|
|
49 |
|
|
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. |
|
|
55 |
|
|
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. |
|
|
62 |
|
|
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. |
|
|
67 |
|
|
68 6. This License Agreement will automatically terminate upon a material |
|
|
69 breach of its terms and conditions. |
|
|
70 |
|
|
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. |
|
|
76 |
|
|
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 |
|
|
79 Agreement. |
|
|
80 */ |
|
|
81 |
|
|
82 #if !defined (octave_sort_h) |
|
|
83 #define octave_sort_h 1 |
|
|
84 |
|
|
85 #ifdef HAVE_CONFIG_H |
|
|
86 #include <config.h> |
|
|
87 #endif |
|
|
88 |
|
|
89 #include "lo-mappers.h" |
|
|
90 #include "quit.h" |
|
|
91 |
|
|
92 /* The maximum number of entries in a MergeState's pending-runs stack. |
|
|
93 * This is enough to sort arrays of size up to about |
|
|
94 * 32 * phi ** MAX_MERGE_PENDING |
|
|
95 * where phi ~= 1.618. 85 is ridiculously large enough, good for an array |
|
|
96 * with 2**64 elements. |
|
|
97 */ |
|
|
98 #define MAX_MERGE_PENDING 85 |
|
|
99 |
|
|
100 /* When we get into galloping mode, we stay there until both runs win less |
|
|
101 * often than MIN_GALLOP consecutive times. See listsort.txt for more info. |
|
|
102 */ |
|
|
103 #define MIN_GALLOP 7 |
|
|
104 |
|
|
105 /* Avoid malloc for small temp arrays. */ |
|
|
106 #define MERGESTATE_TEMP_SIZE 1024 |
|
|
107 |
|
|
108 template <class T> |
|
|
109 class |
|
|
110 octave_sort |
|
|
111 { |
|
4998
|
112 public: |
|
|
113 |
|
4851
|
114 octave_sort (void); |
|
|
115 |
|
|
116 octave_sort (bool (*comp) (T, T)); |
|
|
117 |
|
4998
|
118 ~octave_sort (void) { merge_freemem (); } |
|
|
119 |
|
|
120 void set_compare (bool (*comp) (T, T)) { compare = comp; } |
|
4851
|
121 |
|
|
122 void sort (T *v, int elements); |
|
|
123 |
|
4998
|
124 private: |
|
|
125 |
|
4851
|
126 /* One MergeState exists on the stack per invocation of mergesort. It's just |
|
|
127 * a convenient way to pass state around among the helper functions. |
|
|
128 * |
|
|
129 * DGB: This isn't needed with mergesort in a class, but it doesn't slow |
|
|
130 * things up, and it is likely to make my life easier for any potential |
|
|
131 * backporting of changes in the Python code. |
|
|
132 */ |
|
|
133 |
|
|
134 struct s_slice |
|
|
135 { |
|
|
136 T *base; |
|
|
137 int len; |
|
|
138 }; |
|
|
139 |
|
|
140 typedef struct s_MergeState |
|
|
141 { |
|
|
142 /* This controls when we get *into* galloping mode. It's initialized |
|
|
143 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for |
|
|
144 * random data, and lower for highly structured data. |
|
|
145 */ |
|
|
146 int min_gallop; |
|
|
147 |
|
|
148 /* 'a' is temp storage to help with merges. It contains room for |
|
|
149 * alloced entries. |
|
|
150 */ |
|
|
151 T *a; /* may point to temparray below */ |
|
|
152 int alloced; |
|
|
153 |
|
|
154 /* A stack of n pending runs yet to be merged. Run #i starts at |
|
|
155 * address base[i] and extends for len[i] elements. It's always |
|
|
156 * true (so long as the indices are in bounds) that |
|
|
157 * |
|
|
158 * pending[i].base + pending[i].len == pending[i+1].base |
|
|
159 * |
|
|
160 * so we could cut the storage for this, but it's a minor amount, |
|
|
161 * and keeping all the info explicit simplifies the code. |
|
|
162 */ |
|
|
163 int n; |
|
|
164 struct s_slice pending[MAX_MERGE_PENDING]; |
|
|
165 } MergeState; |
|
|
166 |
|
|
167 bool (*compare)(T, T); |
|
|
168 |
|
|
169 MergeState ms; |
|
|
170 |
|
|
171 void reverse_slice (T *lo, T *hi); |
|
|
172 |
|
|
173 void binarysort (T *lo, T *hi, T *start); |
|
|
174 |
|
|
175 int count_run(T *lo, T *hi, int *descending); |
|
|
176 |
|
|
177 int gallop_left(T key, T *a, int n, int hint); |
|
|
178 |
|
|
179 int gallop_right(T key, T *a, int n, int hint); |
|
|
180 |
|
|
181 void merge_init(void); |
|
|
182 |
|
|
183 void merge_freemem(void); |
|
|
184 |
|
|
185 int merge_getmem(int need); |
|
|
186 |
|
|
187 int merge_lo(T *pa, int na, T *pb, int nb); |
|
|
188 |
|
|
189 int merge_hi(T *pa, int na, T *pb, int nb); |
|
|
190 |
|
|
191 int merge_at(int i); |
|
|
192 |
|
|
193 int merge_collapse(void); |
|
|
194 |
|
|
195 int merge_force_collapse(void); |
|
|
196 |
|
|
197 int merge_compute_minrun(int n); |
|
|
198 }; |
|
|
199 |
|
|
200 #endif |
|
|
201 |
|
|
202 /* |
|
|
203 ;;; Local Variables: *** |
|
|
204 ;;; mode: C++ *** |
|
|
205 ;;; End: *** |
|
|
206 */ |
