Generated on Thu Apr 11 13:59:12 2019 for Gecode by doxygen 1.6.3

sort.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2002
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <algorithm>
00035 #include <climits>
00036 
00037 namespace Gecode { namespace Support {
00038 
00040   template<class Type, class Less>
00041   forceinline void
00042   exchange(Type &a, Type &b, Less &less) {
00043     if (less(b,a)) std::swap(a,b);
00044   }
00045 
00047   int const QuickSortCutoff = 20;
00048 
00050   template<class Type>
00051   class QuickSortStack {
00052   private:
00054     static const int maxsize = sizeof(int) * CHAR_BIT;
00056     Type** tos;
00058     Type*  stack[2*maxsize+1];
00059   public:
00061     QuickSortStack(void);
00063     bool empty(void) const;
00065     void push(Type* l, Type* r);
00067     void pop(Type*& l, Type*& r);
00068   };
00069 
00070   template<class Type>
00071   forceinline
00072   QuickSortStack<Type>::QuickSortStack(void) : tos(&stack[0]) {
00073     *(tos++) = NULL;
00074   }
00075 
00076   template<class Type>
00077   forceinline bool
00078   QuickSortStack<Type>::empty(void) const {
00079     return *(tos-1) == NULL;
00080   }
00081 
00082   template<class Type>
00083   forceinline void
00084   QuickSortStack<Type>::push(Type* l, Type* r) {
00085     *(tos++) = l; *(tos++) = r;
00086   }
00087 
00088   template<class Type>
00089   forceinline void
00090   QuickSortStack<Type>::pop(Type*& l, Type*& r) {
00091     r = *(--tos); l = *(--tos);
00092   }
00093 
00095   template<class Type, class Less>
00096   forceinline void
00097   insertion(Type* l, Type* r, Less &less) {
00098     for (Type* i = r; i > l; i--)
00099       exchange(*(i-1),*i,less);
00100     for (Type* i = l+2; i <= r; i++) {
00101       Type* j = i;
00102       Type v = *i;
00103       while (less(v,*(j-1))) {
00104         *j = *(j-1); j--;
00105       }
00106       *j = v;
00107     }
00108   }
00109 
00111   template<class Type, class Less>
00112   forceinline Type*
00113   partition(Type* l, Type* r, Less &less) {
00114     Type* i = l-1;
00115     Type* j = r;
00116     Type v = *r;
00117     while (true) {
00118       while (less(*(++i),v)) {}
00119       while (less(v,*(--j))) if (j == l) break;
00120         if (i >= j) break;
00121         std::swap(*i,*j);
00122     }
00123     std::swap(*i,*r);
00124     return i;
00125   }
00126 
00128   template<class Type, class Less>
00129   inline void
00130   quicksort(Type* l, Type* r, Less &less) {
00131     QuickSortStack<Type> s;
00132     while (true) {
00133       std::swap(*(l+((r-l) >> 1)),*(r-1));
00134       exchange(*l,*(r-1),less);
00135       exchange(*l,*r,less);
00136       exchange(*(r-1),*r,less);
00137       Type* i = partition(l+1,r-1,less);
00138       if (i-l > r-i) {
00139         if (r-i > QuickSortCutoff) {
00140           s.push(l,i-1); l=i+1; continue;
00141         }
00142         if (i-l > QuickSortCutoff) {
00143           r=i-1; continue;
00144         }
00145       } else {
00146         if (i-l > QuickSortCutoff) {
00147           s.push(i+1,r); r=i-1; continue;
00148         }
00149         if (r-i > QuickSortCutoff) {
00150           l=i+1; continue;
00151         }
00152       }
00153       if (s.empty())
00154         break;
00155       s.pop(l,r);
00156     }
00157   }
00158 
00160   template<class Type>
00161   class Less {
00162   public:
00163     bool operator ()(const Type& lhs, const Type& rhs) {
00164       return lhs < rhs;
00165     }
00166   };
00167 
00183   template<class Type, class Less>
00184   forceinline void
00185   insertion(Type* x, int n, Less &l) {
00186     if (n < 2)
00187       return;
00188     assert(!l(x[0],x[0]));
00189     insertion(x,x+n-1,l);
00190   }
00191 
00203   template<class Type>
00204   forceinline void
00205   insertion(Type* x, int n) {
00206     if (n < 2)
00207       return;
00208     Less<Type> l;
00209     assert(!l(x[0],x[0]));
00210     insertion(x,x+n-1,l);
00211   }
00212 
00228   template<class Type, class Less>
00229   forceinline void
00230   quicksort(Type* x, int n, Less &l) {
00231     if (n < 2)
00232       return;
00233     assert(!l(x[0],x[0]));
00234     if (n > QuickSortCutoff)
00235       quicksort(x,x+n-1,l);
00236     insertion(x,x+n-1,l);
00237   }
00238 
00250   template<class Type>
00251   forceinline void
00252   quicksort(Type* x, int n) {
00253     if (n < 2)
00254       return;
00255     Less<Type> l;
00256     assert(!l(x[0],x[0]));
00257     if (n > QuickSortCutoff)
00258       quicksort(x,x+n-1,l);
00259     insertion(x,x+n-1,l);
00260   }
00261 
00262 }}
00263 
00264 // STATISTICS: support-any