/*******************************************************************************
+
+  LEDA 3.5
+
+  _sort.c
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#include <LEDA/basic.h>

#ifdef SWAP
#undef SWAP
#endif

#define SWAP(a,b) { GenPtr help = *a; *a = *b; *b = help; }

#define MIN_D 16 


void QUICKSORT(GenPtr* l, GenPtr* r, int (*cmp)(GenPtr,GenPtr))
{ 
  GenPtr* i = l+(r-l)/2; //rand_int(l,r);
  GenPtr* k;

  if (cmp(*i,*r) > 0) SWAP(i,r);
  SWAP(l,i);

  GenPtr  s = *l;

  i = l;
  k = r;

  for(;;)
  { while (cmp(*(++i),s)<0);
    while (cmp(*(--k),s)>0);
    if (i<k) SWAP(i,k) else break;
   }

  SWAP(l,k);

  if (k > l+MIN_D) QUICKSORT(l,k-1,cmp);
  if (r > k+MIN_D) QUICKSORT(k+1,r,cmp);
}



void INT_QUICKSORT(GenPtr* l, GenPtr* r)
{ 
  GenPtr* i = l+(r-l)/2; //rand_int(l,r)
  GenPtr* k;

  if (LEDA_ACCESS(int,*i) > LEDA_ACCESS(int,*r)) SWAP(i,r);
  SWAP(l,i);

  int  s = LEDA_ACCESS(int,*l);

  i = l;
  k = r;

  for(;;)
  { while (LEDA_ACCESS(int,*(++i)) < s);
    while (LEDA_ACCESS(int,*(--k)) > s);
    if (i<k) SWAP(i,k) else break;
   }

  SWAP(l,k);

  if (k > l+MIN_D) INT_QUICKSORT(l,k-1);
  if (r > k+MIN_D) INT_QUICKSORT(k+1,r);
}


void INSERTION_SORT(GenPtr* l, GenPtr* r, GenPtr* min_stop, 
                                                  int (*cmp)(GenPtr,GenPtr))
{
  GenPtr* min=l;
  GenPtr* run;
  GenPtr* p;
  GenPtr* q;

  for (run = l+1; run <= min_stop; run++)
      if (cmp(*run,*min) < 0) min = run;

  SWAP(min,l);

  if (r == l+1) return;

  for(run=l+2; run <= r; run++)
  { for (min = run-1; cmp(*run,*min) < 0; min--);
    min++;
    if (run != min) 
    { GenPtr save = *run;
      for(p=run, q = run-1; p > min; p--,q--) *p = *q;
      *min = save;
     }
   }
}



void INT_INSERTION_SORT(GenPtr* l, GenPtr* r, GenPtr* min_stop)
{
  GenPtr* min=l;
  GenPtr* run;
  GenPtr* p;
  GenPtr* q;

  for (run = l+1; run <= min_stop; run++)
      if (LEDA_ACCESS(int,*run) <  LEDA_ACCESS(int,*min)) min = run;

  SWAP(min,l);

  if (r == l+1) return;

  for(run=l+2; run <= r; run++)
  { for (min = run-1; LEDA_ACCESS(int,*run) < LEDA_ACCESS(int,*min); min--);
    min++;
    if (run != min) 
    { GenPtr save = *run;
      for(p=run, q = run-1; p > min; p--,q--) *p = *q;
      *min = save;
     }
   }
}



void SORT(GenPtr* left, GenPtr* right, int (*cmp)(GenPtr,GenPtr)) 
{
  GenPtr* min_stop = left + MIN_D;

  if (min_stop > right) min_stop = right;

  QUICKSORT(left,right,cmp);
  INSERTION_SORT(left,right,min_stop,cmp);

 }


void INT_SORT(GenPtr* left, GenPtr* right) 
{
  GenPtr* min_stop = left + MIN_D;

  if (min_stop > right) min_stop = right;

  INT_QUICKSORT(left,right);
  INT_INSERTION_SORT(left,right,min_stop);
 }



GenPtr* BINARY_SEARCH(GenPtr x, GenPtr* left, GenPtr* right, 
                                  int (*cmp)(GenPtr,GenPtr))
{ while (left < right)
  { GenPtr* m = left+(right-left)/2;
    int c = cmp(x,*m);
    if (c == 0) return m;
    if (c > 0)  left =  m+1;
    else right =  m-1;
   }

   return nil;
}



GenPtr* INT_BINARY_SEARCH(int x, GenPtr* left, GenPtr* right)
{ while (left < right)
  { GenPtr* m = left+(right-left)/2;
    int y = LEDA_ACCESS(int,*m);
    if (x == y) return m;
    if (x > y)  left =  m+1;
    else right =  m-1;
   }

   return nil;
}


