#include "quantile.h"

int numk;

numlist::numlist(int i)
 {
  num=i;
  next=NULL;
 }

void printlist(numlist* list)
 {
  numlist *tmp =list;
  
  while(tmp != NULL)
   {
     printf("%d ",tmp->num);
     tmp=tmp->next;
   }
  printf("\n");
 }

numlist* randRemove(int* i,numlist* list,int m,int r)
 {
  numlist* tmp = list;
  numlist* hold = NULL;
  int x;
 
  for(x=0; x<(m/r); x++)
   {
    list=tmp;
    hold=insert(list->num,hold);
    tmp=list->next;
    delete(list);
   }
 
   list=tmp;
  tmp=list->next;
  *i = tmp->num;
  delete(list);
  while(list != NULL)
   {
    list=tmp;
    hold=insert(list->num,hold);
    tmp=list->next;
    delete(list);
   }
  return hold;
 }

numlist* insert(int i,numlist* list)
 {
  numlist* tmp = new numlist(i);

  tmp->next=list;
  return tmp;
 }

numlist* remove(numlist* list)
 {
  int i=list->num;
  numlist* tmp = list;

  list=list->next;
  delete(tmp);
  return list;
 }

void selection(int min, int max,int rank,numlist* list,int* comp,int* klist)
 {
  if ((list==NULL) | (numk==0)) return;
  int partition, pRank, test;
  pRank=min;
  numlist* lessthan=NULL;
  numlist* grtrthan=NULL;

  partition=list->num;

  list=remove(list);
  while(list != NULL)
   {
    test=list->num; 
    if(test<partition)
     {
      lessthan=insert(test,lessthan);
      pRank++;
     }
    else grtrthan=insert(test,grtrthan);
    *comp=*comp+1;
    list=remove(list);
   }

   if ((pRank%rank) == 0)
      {
       klist[(pRank/rank)-1]=partition;
       numk--;
      }
   if(pRank < rank) selection(pRank+1,max,rank,grtrthan,comp,klist);
   else {
     selection(min,pRank-1,rank,lessthan,comp,klist);
     selection(pRank+1,max,rank,grtrthan,comp,klist);
    } 
 }

main()
 {
  int x,k,num,rank;
  char* tmp= new char(16);
  numlist* list=NULL;
  int comp;
  int* klist;

  for(x=0; x<5000; x++)
   {
    printf("Enter in integer %d: ",x+1);
    gets(tmp);
    num=atoi(tmp);
    list=insert(num,list);
   }

  printf("Enter in the Quantile: ");
  gets(tmp);
  k=atoi(tmp);
  rank=5000/k;
  klist = new int[k];
  k--;
  numk=k+1;

  selection(1,5000,rank,list,&comp,klist);

  for(x=0; x<k; x++) printf(" %d\n",klist[x]);
  printf(" %d",comp);
  delete(klist);
 }