// File: Sorting/slow_purge.C
// Removing duplicates
#include <iostream.h>

template <class ElType>
int purge(ElType A[], int& n)
// Removes duplicates in A without changing order
// returns number of duplicates removed, sets n to new size
// runs in Theta(n^2) steps
{int i, j, k, dupl = 0;
 for(i=0; i < n-1; i++)
    for(j=i+1; j < n; j++)
       if(A[i] == A[j])
         {// shift rest of array left by 1
          dupl++;
          for(k=j+1; k < n; k++)
             A[k-1] = A[k]; // at most O(n^2) many times ex
          n--;
          j--; // look at shifted element next
         }
 return(dupl);
}// end purge

extern "C" long random();
extern "C" void srandom(int);
#include <stdio.h> // for sscanf
extern int indir_mergesort(int[], int, int, int[]);

main(int argc, char** argv)
// run as "a.out 100 25 11", where 100 is the size to be tested,
// and 25 is the range of entries;
// 11 is the seed for the random number generator;
{
  int *array, *indexarray; int comp, i, size, mod, seed;

#ifndef MY_EXAMPLE
  if (argc < 4) 
    {
      cerr << "Call as \"" << argv[0] << " <size> <mod> <seed> \"" << endl; 
      exit(1);
    };

  sscanf(argv[1], "%d", &size); sscanf(argv[2], "%d", &mod);
  array = new int[size];
  indexarray = new int[size];

  sscanf(argv[3], "%d",&seed);
  srandom(seed);
  for(i = 0; i < size; i++) 
    array[i] = random() % mod;
  cout << endl;
#else
  size = 10;
  array = new int[size];
  indexarray = new int[size];
  /* initialize the array with : 77 61 (61) 83 (61) 35 (61) (77) (83) 47 */
  /* elements shown in parantheses are duplicates */
  array[0]=77;array[1]=61;array[2]=61;array[3]=83;array[4]=47;
  array[5]=61;array[6]=35;array[7]=61;array[8]=83;array[9]=77;
#endif

  cout << "Input array" << endl;
  for(i=0;i<size;i++)
    cout << array[i] << " ";
  cout<<endl;

  comp = indir_mergesort(array, 0, size-1, indexarray);
  cout << "mergesorted array after " << comp << " comparisons" << endl;
  for(i = 0; i < size; i++) cout << array[indexarray[i]] << " "; cout << endl;

  comp = purge(array, size);
  cout << "Purged array after " << comp << " removals" << endl;
  for(i = 0; i < size; i++) cout << array[i] << " "; cout << endl;
}