/*******************************************************************************
+
+  LEDA 3.5
+
+  _select.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_alg.h>

#ifdef SWAP
#undef SWAP
#endif

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


int SELECT(int* l, int* r, int pos)
{ 
  // compute element at position "pos" in sequence *l,...,*r
  // expected running time: O(r-l)

  register int* i;
  register int* k;
  register int s;
  register int help;

  while (l < r) 
  { i = l+(r-l)/2;
    if (*i > *r) SWAP(i,r);
    SWAP(l,i);

    i = l;
    k = r;
    s = *l;

    for(;;)
    { while (*(++i) < s);
      while (*(--k) > s);
      if (i<k) SWAP(i,k) else break;
     }
  
    SWAP(l,k);
  
    int j =  k-l+1;
    if (pos <= j) 
       r = k;
    else 
       { l = k+1;
         pos -= j;
        }
  }

  return *l;
}



double SELECT(double* l, double* r, int pos)
{ 
  register double* i;
  register double* k;
  register double s;
  register double help;

  while (l < r) 
  { i = l+(r-l)/2;
    if (*i > *r) SWAP(i,r);
    SWAP(l,i);

    i = l;
    k = r;
    s = *l;

    for(;;)
    { while (*(++i) < s);
      while (*(--k) > s);
      if (i<k) SWAP(i,k) else break;
     }
  
    SWAP(l,k);
  
    int j =  k-l+1;
    if (pos <= j) 
       r = k;
    else 
       { l = k+1;
         pos -= j;
        }
  }

  return *l;
}

