// D. Brugger, december 2006// $Id: util.h 8 2006-12-16 16:47:20Z beeblbrox $//// Copyright (C) 2006 Dominik Brugger//// This program is free software; you can redistribute it and/or modify// it under the terms of the GNU General Public License as published by// the Free Software Foundation; either version 2 of the License, or// (at your option) any later version.// // This program is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the// GNU General Public License for more details.//// You should have received a copy of the GNU General Public License along// with this program; if not, write to the Free Software Foundation, Inc.,// 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.#ifndef __UTIL__H__#define __UTIL__H__#include <stdlib.h>#include <string.h>#ifndef mintemplate <class T> inline T min(T x,T y) { return (x<y)?x:y; }#endif#ifndef maxtemplate <class T> inline T max(T x,T y) { return (x>y)?x:y; }#endiftemplate <class T> inline void swap(T& x, T& y) { T t=x; x=y; y=t; }template <class S, class T> inline void clone(T*& dst, S* src, int n){  dst = new T[n];  memcpy((void *)dst,(void *)src,sizeof(T)*n);}template <class T>inline int partition(T a[], int idxs[], int p, int r){  double x = a[r];  int i = p-1;  for(int j=p; j<r; ++j)    {      if(a[j] < x){	++i;	swap(a[i],a[j]);	swap(idxs[i],idxs[j]);      }    }  ++i;  swap(a[i],a[r]);  swap(idxs[i],idxs[r]);  return i;}template <class T>void quicksort(T a[], int idxs[], int l, int r){  if(l < r)    {      int q = partition(a,idxs,l,r);      quicksort(a,idxs,l,q-1);      quicksort(a,idxs,q+1,r);    }}template <class T>void quick_sort(T a[], int idxs[], int l_, int r_){  int     i, j, s, d, l, iw, ps[20], pd[20];  T  x, w;  l     = 0;  ps[0] = l_;  pd[0] = r_;  do  {      s = ps[l];      d = pd[l];      l--;      do      {          i = s;          j = d;          x = a[(s+d)/2];          do          {              while (a[i] < x) i++;              while (a[j] > x) j--;              if (i <= j)              {                  iw    = idxs[i];                  w     = a[i];                  idxs[i] = idxs[j];                  a[i]  = a[j];                  i++;                  idxs[j] = iw;                  a[j]  = w;                  j--;              }          } while (i <= j);          if (j-s > d-i)          {              l++;              ps[l] = s;              pd[l] = j;              s     = i;          }          else          {              if (i < d)              {                  l++;                  ps[l] = i;                  pd[l] = d;              }              d = j;          }      } while (s < d);  } while(l>=0);}#endif