// Jens Kristian Jensen, dat2A 2002/2003

#include <iostream.h>
#include <stdlib.h>
#include <LEDA/graph.h>
#include <LEDA/array.h>
#include <LEDA/edge_array.h>
#include <LEDA/random_source.h>

const int SIZE = 10;

int randSelRange(int k1, int k2, array<edge>& E, int first, int last,
		     edge_array<double>& W) {
  // select an element whose order is in the range [k1, k2] from
  // E[first,..,last] by returning the index of the element in E

  if (k1 > k2) {
    cerr << "Select: k1 > k2" << endl;
    exit(0);
  }

  if (first == last)
    return first;

  // Randomized Partition
  // ====================
  random_source S(first, last);
  int median = S(); 

  int smaller = first - 1;
  edge temp = E[last];
  E[last] = E[median];
  E[median] = temp;
  for (int j=first; j<last; j++) {
    if (W[E[j]] <= W[E[last]]) {
      smaller++;
      temp = E[j];
      E[j] = E[smaller];
      E[smaller] = temp;
    }
  }
  smaller++;
  temp = E[last];
  E[last] = E[smaller];
  E[smaller] = temp;

  median = smaller;  // index of median has now changed


  // Call randSelRange recursively until the median is in the
  // appropriate range, ie. k1 <= M <= k2

  int M = median-first+1; // M is the medians number within [first..last]
  if (k1 <= M && M <= k2) {// An element has been found
    return median;
  }
  if (k2 < M) { // continue with lower part
    return randSelRange(k1, k2, E, first, median-1, W);
  }
  else { // continue with upper part
    return randSelRange(k1-M, k2-M, E, median+1, last, W);
  }
}