00001 /* 00002 Copyright (C) 2003 David Bateman 00003 00004 This file is part of Octave. 00005 00006 Octave is free software; you can redistribute it and/or modify it 00007 under the terms of the GNU General Public License as published by the 00008 Free Software Foundation; either version 2, or (at your option) any 00009 later version. 00010 00011 Octave is distributed in the hope that it will be useful, but WITHOUT 00012 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 00013 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 00014 for more details. 00015 00016 You should have received a copy of the GNU General Public License 00017 along with Octave; see the file COPYING. If not, write to the Free 00018 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 00019 00020 Code stolen in large part from Python's, listobject.c, which itself had 00021 no license header. However, thanks to Tim Peters for the parts of the 00022 code I ripped-off. 00023 00024 As required in the Python license the short description of the changes 00025 made are 00026 00027 * convert the sorting code in listobject.cc into a generic class, 00028 replacing PyObject* with the type of the class T. 00029 00030 The Python license is 00031 00032 PSF LICENSE AGREEMENT FOR PYTHON 2.3 00033 -------------------------------------- 00034 00035 1. This LICENSE AGREEMENT is between the Python Software Foundation 00036 ("PSF"), and the Individual or Organization ("Licensee") accessing and 00037 otherwise using Python 2.3 software in source or binary form and its 00038 associated documentation. 00039 00040 2. Subject to the terms and conditions of this License Agreement, PSF 00041 hereby grants Licensee a nonexclusive, royalty-free, world-wide 00042 license to reproduce, analyze, test, perform and/or display publicly, 00043 prepare derivative works, distribute, and otherwise use Python 2.3 00044 alone or in any derivative version, provided, however, that PSF's 00045 License Agreement and PSF's notice of copyright, i.e., "Copyright (c) 00046 2001, 2002, 2003 Python Software Foundation; All Rights Reserved" are 00047 retained in Python 2.3 alone or in any derivative version prepared by 00048 Licensee. 00049 00050 3. In the event Licensee prepares a derivative work that is based on 00051 or incorporates Python 2.3 or any part thereof, and wants to make 00052 the derivative work available to others as provided herein, then 00053 Licensee hereby agrees to include in any such work a brief summary of 00054 the changes made to Python 2.3. 00055 00056 4. PSF is making Python 2.3 available to Licensee on an "AS IS" 00057 basis. PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR 00058 IMPLIED. BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND 00059 DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS 00060 FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON 2.3 WILL NOT 00061 INFRINGE ANY THIRD PARTY RIGHTS. 00062 00063 5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON 00064 2.3 FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS 00065 A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON 2.3, 00066 OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF. 00067 00068 6. This License Agreement will automatically terminate upon a material 00069 breach of its terms and conditions. 00070 00071 7. Nothing in this License Agreement shall be deemed to create any 00072 relationship of agency, partnership, or joint venture between PSF and 00073 Licensee. This License Agreement does not grant permission to use PSF 00074 trademarks or trade name in a trademark sense to endorse or promote 00075 products or services of Licensee, or any third party. 00076 00077 8. By copying, installing or otherwise using Python 2.3, Licensee 00078 agrees to be bound by the terms and conditions of this License 00079 Agreement. 00080 */ 00081 00082 #if !defined (octave_sort_h) 00083 #define octave_sort_h 1 00084 00085 #ifdef HAVE_CONFIG_H 00086 #include <config.h> 00087 #endif 00088 00089 #include "lo-mappers.h" 00090 #include "quit.h" 00091 00092 /* The maximum number of entries in a MergeState's pending-runs stack. 00093 * This is enough to sort arrays of size up to about 00094 * 32 * phi ** MAX_MERGE_PENDING 00095 * where phi ~= 1.618. 85 is ridiculously large enough, good for an array 00096 * with 2**64 elements. 00097 */ 00098 #define MAX_MERGE_PENDING 85 00099 00100 /* When we get into galloping mode, we stay there until both runs win less 00101 * often than MIN_GALLOP consecutive times. See listsort.txt for more info. 00102 */ 00103 #define MIN_GALLOP 7 00104 00105 /* Avoid malloc for small temp arrays. */ 00106 #define MERGESTATE_TEMP_SIZE 1024 00107 00108 template <class T> 00109 class 00110 octave_sort 00111 { 00112 public: 00113 00114 octave_sort (void); 00115 00116 octave_sort (bool (*comp) (T, T)); 00117 00118 ~octave_sort (void) { merge_freemem (); } 00119 00120 void set_compare (bool (*comp) (T, T)) { compare = comp; } 00121 00122 void sort (T *v, int elements); 00123 00124 private: 00125 00126 /* One MergeState exists on the stack per invocation of mergesort. It's just 00127 * a convenient way to pass state around among the helper functions. 00128 * 00129 * DGB: This isn't needed with mergesort in a class, but it doesn't slow 00130 * things up, and it is likely to make my life easier for any potential 00131 * backporting of changes in the Python code. 00132 */ 00133 00134 struct s_slice 00135 { 00136 T *base; 00137 int len; 00138 }; 00139 00140 typedef struct s_MergeState 00141 { 00142 /* This controls when we get *into* galloping mode. It's initialized 00143 * to MIN_GALLOP. merge_lo and merge_hi tend to nudge it higher for 00144 * random data, and lower for highly structured data. 00145 */ 00146 int min_gallop; 00147 00148 /* 'a' is temp storage to help with merges. It contains room for 00149 * alloced entries. 00150 */ 00151 T *a; /* may point to temparray below */ 00152 int alloced; 00153 00154 /* A stack of n pending runs yet to be merged. Run #i starts at 00155 * address base[i] and extends for len[i] elements. It's always 00156 * true (so long as the indices are in bounds) that 00157 * 00158 * pending[i].base + pending[i].len == pending[i+1].base 00159 * 00160 * so we could cut the storage for this, but it's a minor amount, 00161 * and keeping all the info explicit simplifies the code. 00162 */ 00163 int n; 00164 struct s_slice pending[MAX_MERGE_PENDING]; 00165 } MergeState; 00166 00167 bool (*compare)(T, T); 00168 00169 MergeState ms; 00170 00171 void reverse_slice (T *lo, T *hi); 00172 00173 void binarysort (T *lo, T *hi, T *start); 00174 00175 int count_run(T *lo, T *hi, int *descending); 00176 00177 int gallop_left(T key, T *a, int n, int hint); 00178 00179 int gallop_right(T key, T *a, int n, int hint); 00180 00181 void merge_init(void); 00182 00183 void merge_freemem(void); 00184 00185 int merge_getmem(int need); 00186 00187 int merge_lo(T *pa, int na, T *pb, int nb); 00188 00189 int merge_hi(T *pa, int na, T *pb, int nb); 00190 00191 int merge_at(int i); 00192 00193 int merge_collapse(void); 00194 00195 int merge_force_collapse(void); 00196 00197 int merge_compute_minrun(int n); 00198 }; 00199 00200 #endif 00201 00202 /* 00203 ;;; Local Variables: *** 00204 ;;; mode: C++ *** 00205 ;;; End: *** 00206 */
SEO | [PR] 爆速!無料ブログ 無料ホームページ開設 無料ライブ放送 | ||