oct-sort.h

Go to the documentation of this file.
00001 /*
00002 Copyright (C) 2003-2012 David Bateman
00003 Copyright (C) 2009-2010 VZLU Prague
00004 
00005 This file is part of Octave.
00006 
00007 Octave is free software; you can redistribute it and/or modify it
00008 under the terms of the GNU General Public License as published by the
00009 Free Software Foundation; either version 3 of the License, or (at your
00010 option) any later version.
00011 
00012 Octave is distributed in the hope that it will be useful, but WITHOUT
00013 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00014 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
00015 for more details.
00016 
00017 You should have received a copy of the GNU General Public License
00018 along with Octave; see the file COPYING.  If not, see
00019 <http://www.gnu.org/licenses/>.
00020 
00021 Code stolen in large part from Python's, listobject.c, which itself had
00022 no license header. However, thanks to Tim Peters for the parts of the
00023 code I ripped-off.
00024 
00025 As required in the Python license the short description of the changes
00026 made are
00027 
00028 * convert the sorting code in listobject.cc into a generic class,
00029   replacing PyObject* with the type of the class T.
00030 
00031 The Python license is
00032 
00033   PSF LICENSE AGREEMENT FOR PYTHON 2.3
00034   --------------------------------------
00035 
00036   1. This LICENSE AGREEMENT is between the Python Software Foundation
00037   ("PSF"), and the Individual or Organization ("Licensee") accessing and
00038   otherwise using Python 2.3 software in source or binary form and its
00039   associated documentation.
00040 
00041   2. Subject to the terms and conditions of this License Agreement, PSF
00042   hereby grants Licensee a nonexclusive, royalty-free, world-wide
00043   license to reproduce, analyze, test, perform and/or display publicly,
00044   prepare derivative works, distribute, and otherwise use Python 2.3
00045   alone or in any derivative version, provided, however, that PSF's
00046   License Agreement and PSF's notice of copyright, i.e., "Copyright (c)
00047   2001, 2002, 2003 Python Software Foundation; All Rights Reserved" are
00048   retained in Python 2.3 alone or in any derivative version prepared by
00049   Licensee.
00050 
00051   3. In the event Licensee prepares a derivative work that is based on
00052   or incorporates Python 2.3 or any part thereof, and wants to make
00053   the derivative work available to others as provided herein, then
00054   Licensee hereby agrees to include in any such work a brief summary of
00055   the changes made to Python 2.3.
00056 
00057   4. PSF is making Python 2.3 available to Licensee on an "AS IS"
00058   basis.  PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR
00059   IMPLIED.  BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND
00060   DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS
00061   FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON 2.3 WILL NOT
00062   INFRINGE ANY THIRD PARTY RIGHTS.
00063 
00064   5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON
00065   2.3 FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS
00066   A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON 2.3,
00067   OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF.
00068 
00069   6. This License Agreement will automatically terminate upon a material
00070   breach of its terms and conditions.
00071 
00072   7. Nothing in this License Agreement shall be deemed to create any
00073   relationship of agency, partnership, or joint venture between PSF and
00074   Licensee.  This License Agreement does not grant permission to use PSF
00075   trademarks or trade name in a trademark sense to endorse or promote
00076   products or services of Licensee, or any third party.
00077 
00078   8. By copying, installing or otherwise using Python 2.3, Licensee
00079   agrees to be bound by the terms and conditions of this License
00080   Agreement.
00081 */
00082 
00083 #if !defined (octave_sort_h)
00084 #define octave_sort_h 1
00085 
00086 #include "lo-traits.h"
00087 
00088 // The maximum number of entries in a MergeState's pending-runs stack.
00089 // This is enough to sort arrays of size up to about
00090 //     32 * phi ** MAX_MERGE_PENDING
00091 // where phi ~= 1.618.  85 is ridiculously large enough, good for an array
00092 // with 2**64 elements.
00093 #define MAX_MERGE_PENDING 85
00094 
00095 // When we get into galloping mode, we stay there until both runs win less
00096 // often than MIN_GALLOP consecutive times.  See listsort.txt for more info.
00097 #define MIN_GALLOP 7
00098 
00099 // Avoid malloc for small temp arrays.
00100 #define MERGESTATE_TEMP_SIZE 1024
00101 
00102 // Enum for type of sort function
00103 enum sortmode { UNSORTED = 0, ASCENDING, DESCENDING };
00104 
00105 template <class T>
00106 class
00107 octave_sort
00108 {
00109 public:
00110 
00111   typedef bool (*compare_fcn_type) (typename ref_param<T>::type,
00112                                     typename ref_param<T>::type);
00113 
00114   octave_sort (void);
00115 
00116   octave_sort (compare_fcn_type);
00117 
00118   ~octave_sort (void);
00119 
00120   void set_compare (compare_fcn_type comp) { compare = comp; }
00121 
00122   void set_compare (sortmode mode);
00123 
00124   // Sort an array in-place.
00125   void sort (T *data, octave_idx_type nel);
00126 
00127   // Ditto, but also permute the passed indices (may not be valid indices).
00128   void sort (T *data, octave_idx_type *idx, octave_idx_type nel);
00129 
00130   // Check whether an array is sorted.
00131   bool is_sorted (const T *data, octave_idx_type nel);
00132 
00133   // Sort a matrix by rows, return a permutation
00134   // vector.
00135   void sort_rows (const T *data, octave_idx_type *idx,
00136                   octave_idx_type rows, octave_idx_type cols);
00137 
00138   // Determine whether a matrix (as a contiguous block) is sorted by rows.
00139   bool is_sorted_rows (const T *data,
00140                        octave_idx_type rows, octave_idx_type cols);
00141 
00142   // Do a binary lookup in a sorted array.
00143   octave_idx_type lookup (const T *data, octave_idx_type nel,
00144                           const T& value);
00145 
00146   // Ditto, but for an array.
00147   void lookup (const T *data, octave_idx_type nel,
00148                const T* values, octave_idx_type nvalues,
00149                octave_idx_type *idx);
00150 
00151   // A linear merge of two sorted tables. rev indicates the second table is
00152   // in reverse order.
00153   void lookup_sorted (const T *data, octave_idx_type nel,
00154                       const T* values, octave_idx_type nvalues,
00155                       octave_idx_type *idx, bool rev = false);
00156 
00157   // Rearranges the array so that the elements with indices
00158   // lo..up-1 are in their correct place.
00159   void nth_element (T *data, octave_idx_type nel,
00160                     octave_idx_type lo, octave_idx_type up = -1);
00161 
00162   static bool ascending_compare (typename ref_param<T>::type,
00163                                  typename ref_param<T>::type);
00164 
00165   static bool descending_compare (typename ref_param<T>::type,
00166                                   typename ref_param<T>::type);
00167 
00168 private:
00169 
00170   // One MergeState exists on the stack per invocation of mergesort.
00171   // It's just a convenient way to pass state around among the helper
00172   // functions.
00173   //
00174   // DGB: This isn't needed with mergesort in a class, but it doesn't
00175   // slow things up, and it is likely to make my life easier for any
00176   // potential backporting of changes in the Python code.
00177 
00178   struct s_slice
00179   {
00180     octave_idx_type base, len;
00181   };
00182 
00183   struct MergeState
00184   {
00185     MergeState (void)
00186       : min_gallop (), a (0), ia (0), alloced (0), n (0)
00187       { reset (); }
00188 
00189     ~MergeState (void)
00190       { delete [] a; delete [] ia; }
00191 
00192     void reset (void)
00193       { min_gallop = MIN_GALLOP; n = 0; }
00194 
00195     void getmem (octave_idx_type need);
00196 
00197     void getmemi (octave_idx_type need);
00198 
00199     // This controls when we get *into* galloping mode.  It's
00200     // initialized to MIN_GALLOP.  merge_lo and merge_hi tend to nudge
00201     // it higher for random data, and lower for highly structured
00202     // data.
00203     octave_idx_type min_gallop;
00204 
00205     // 'a' is temp storage to help with merges.  It contains room for
00206     // alloced entries.
00207     T *a;               // may point to temparray below
00208     octave_idx_type *ia;
00209     octave_idx_type alloced;
00210 
00211     // A stack of n pending runs yet to be merged.  Run #i starts at
00212     // address base[i] and extends for len[i] elements.  It's always
00213     // true (so long as the indices are in bounds) that
00214     //
00215     //   pending[i].base + pending[i].len == pending[i+1].base
00216     //
00217     // so we could cut the storage for this, but it's a minor amount,
00218     // and keeping all the info explicit simplifies the code.
00219     octave_idx_type n;
00220     struct s_slice pending[MAX_MERGE_PENDING];
00221 
00222     // No copying!
00223 
00224     MergeState (const MergeState&);
00225 
00226     MergeState& operator = (const MergeState&);
00227   };
00228 
00229   compare_fcn_type compare;
00230 
00231   MergeState *ms;
00232 
00233 
00234   template <class Comp>
00235   void binarysort (T *data, octave_idx_type nel,
00236               octave_idx_type start, Comp comp);
00237 
00238   template <class Comp>
00239   void binarysort (T *data, octave_idx_type *idx, octave_idx_type nel,
00240               octave_idx_type start, Comp comp);
00241 
00242   template <class Comp>
00243   octave_idx_type count_run (T *lo, octave_idx_type n, bool& descending, Comp comp);
00244 
00245   template <class Comp>
00246   octave_idx_type gallop_left (T key, T *a, octave_idx_type n, octave_idx_type hint,
00247                                Comp comp);
00248 
00249   template <class Comp>
00250   octave_idx_type gallop_right (T key, T *a, octave_idx_type n, octave_idx_type hint,
00251                                 Comp comp);
00252 
00253   template <class Comp>
00254   int merge_lo (T *pa, octave_idx_type na,
00255                 T *pb, octave_idx_type nb,
00256                 Comp comp);
00257 
00258   template <class Comp>
00259   int merge_lo (T *pa, octave_idx_type *ipa, octave_idx_type na,
00260                 T *pb, octave_idx_type *ipb, octave_idx_type nb,
00261                 Comp comp);
00262 
00263   template <class Comp>
00264   int merge_hi (T *pa, octave_idx_type na,
00265                 T *pb, octave_idx_type nb,
00266                 Comp comp);
00267 
00268   template <class Comp>
00269   int merge_hi (T *pa, octave_idx_type *ipa, octave_idx_type na,
00270                 T *pb, octave_idx_type *ipb, octave_idx_type nb,
00271                 Comp comp);
00272 
00273   template <class Comp>
00274   int merge_at (octave_idx_type i, T *data,
00275                 Comp comp);
00276 
00277   template <class Comp>
00278   int merge_at (octave_idx_type i, T *data, octave_idx_type *idx,
00279                 Comp comp);
00280 
00281   template <class Comp>
00282   int merge_collapse (T *data, Comp comp);
00283 
00284   template <class Comp>
00285   int merge_collapse (T *data, octave_idx_type *idx, Comp comp);
00286 
00287   template <class Comp>
00288   int merge_force_collapse (T *data, Comp comp);
00289 
00290   template <class Comp>
00291   int merge_force_collapse (T *data, octave_idx_type *idx, Comp comp);
00292 
00293   octave_idx_type merge_compute_minrun (octave_idx_type n);
00294 
00295   template <class Comp>
00296   void sort (T *data, octave_idx_type nel, Comp comp);
00297 
00298   template <class Comp>
00299   void sort (T *data, octave_idx_type *idx, octave_idx_type nel, Comp comp);
00300 
00301   template <class Comp>
00302   bool is_sorted (const T *data, octave_idx_type nel, Comp comp);
00303 
00304   template <class Comp>
00305   void sort_rows (const T *data, octave_idx_type *idx,
00306                   octave_idx_type rows, octave_idx_type cols,
00307                   Comp comp);
00308 
00309   template <class Comp>
00310   bool is_sorted_rows (const T *data, octave_idx_type rows,
00311                        octave_idx_type cols, Comp comp);
00312 
00313   template <class Comp>
00314   octave_idx_type lookup (const T *data, octave_idx_type nel,
00315                           const T& value, Comp comp);
00316 
00317   template <class Comp>
00318   void lookup (const T *data, octave_idx_type nel,
00319                const T* values, octave_idx_type nvalues,
00320                octave_idx_type *idx, Comp comp);
00321 
00322   template <class Comp>
00323   void lookup_sorted (const T *data, octave_idx_type nel,
00324                       const T* values, octave_idx_type nvalues,
00325                       octave_idx_type *idx, bool rev, Comp comp);
00326 
00327   template <class Comp>
00328   void nth_element (T *data, octave_idx_type nel,
00329                     octave_idx_type lo, octave_idx_type up,
00330                     Comp comp);
00331 
00332   // No copying!
00333 
00334   octave_sort (const octave_sort&);
00335 
00336   octave_sort& operator = (const octave_sort&);
00337 };
00338 
00339 template <class T>
00340 class
00341 vec_index
00342 {
00343 public:
00344   T vec;
00345   octave_idx_type indx;
00346 };
00347 #endif
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Defines