///////////////////////////////////////////////////////////////
// Check Priority Queue.   By Charles Galambos
// $Id: TPriQH.cc,v 1.2 1998/09/07 15:25:58 ees1cg Exp $

#include "amma/PriQueue.hh"
#include <stdio.h>
#include <stdlib.h>

BooleanT SeqTest(void);
BooleanT InterTest(void);

#ifndef __sgi__
template class RCWrapBodyC<SDArray1dC<Tuple2C<int, int> > >;
#endif

int main() {
  printf("Starting test. \n");
  SeqTest();
  InterTest();
  return 0;
}

BooleanT SeqTest(void) {
  PriQueueC<int,int> Queue(10000);
  int i;
  for(i = 2;i < 10000;i++) {
    Queue.Insert(rand(),i+1);
    //Queue.Dump();
  }
  int Last = Queue.TopKey();
  BooleanT ok(TRUE);
  while(Queue.IsElm()) {
    Tuple2C<int,int> KP =Queue.GetTopPair();
    //Queue.Check();
    const int Val = KP.Data2();
    const int Key = KP.Data1();
    if(Key < Last) {
      printf("\n ERROR !!! %d %d (Last: %d) \n",Key,Val,Last);
      ok = FALSE;
      break;
    }
    Last = Key;
    //printf("(%d %d) ",KP.Data1(),Val);
  }
  if(ok)
    printf("Sequence test passed. \n");
  else
    printf("Sequence test failed. \n");
  return ok;
}  

BooleanT InterTest(void) {
  PriQueueC<int,int> Queue(10000);
  int i,Last;
  BooleanT ok = TRUE;
  for(i = 1;i < 10000;i++) {
    Queue.Insert(rand(),i+1);
  }
  printf("Starting Interleave. \n");
  for(int k = 0;k < 1000;k++) {
    // Remove
    Last = Queue.TopKey();
    for(i = 1;i < 10;i++) {
      Tuple2C<int,int> KP =Queue.GetTopPair();
      const int Val = KP.Data2();
      const int Key = KP.Data1();
      if(Key < Last) {
	printf("\n ERROR !!! %d %d \n",KP.Data1(),Val);
	ok = FALSE;
	break;
      }
      Last = Key;
    }
    // Insert.
    for(i = 1;i < 10;i++) {
      Queue.Insert(rand(),i+1);
    }
  }
  printf("Checking remaining queue. \n");
  Last = Queue.TopKey();
  while(Queue.IsElm()) {
    Tuple2C<int,int> KP =Queue.GetTopPair();
    const int Val = KP.Data2();
    const int Key = KP.Data1();
    if(Key < Last) {
      printf("\n ERROR !!! %d %d \n",KP.Data1(),Val);
      ok = FALSE;
      break;
    }
    Last = Key;
  }
  
  printf("Interleave test passed. \n");
  return ok;
}