// Removing duplicates
// Programmer: E. Kaltofen (September 27, 1992)
#include <iostream.h>

typedef int ElType; // for testing purposes
extern int indir_mergesort(ElType[], int, int, int[]);

int purge(ElType A[], int& n)
/* Removes duplicates in A without changing order
   returns number of duplicates removed, sets n to new size */
{int i, j, k = 0, dupl;
 int *I, *Iinv; 
 ElType *A2; // receives fresh elements;

 I = new int[n];
 Iinv = new int[n];
 A2 = new ElType[n];

 indir_mergesort(A, 0, n-1, I);

 cout<<endl<<"        Index Array: ";
 for(i=0;i<n;i++) cout<<I[i]<<" "; cout<<endl;

 for (j=0; j < n; j++) Iinv[ I[j] ] = j;

 cout<<"Inverse Index Array: ";
 for(i=0;i<n;i++) cout<<Iinv[i]<<" "; cout<<endl<<endl;

 for (j=0; j < n; j++)
     {i = Iinv[j]; // index of A[j] in sorted array
      if (i < 1) dupl = 0;
      else {dupl = (A[ I[i-1] ] == A[j]);

#ifdef DEBUG
      cout << "A[" << j << "] = " << A[j] << " is in " << i << "th place" << endl;
      cout << "A[" << I[i-1] << "] = " << A[I[i-1]] << " is before it, dupl = "
           << dupl << endl;
#endif

           };
      if (!dupl)
         {A2[k++] = A[j];

#ifdef DEBUG
          cout << "A2[" << k-1 << "] = A[" << j << "] = " << A[j] << endl;
#endif

         };
     };
  dupl = n-k; // use as counter now
  n = k;
  for(k=0; k < n; k++) A[k] = A2[k];
  delete I; delete Iinv; delete A2;
  return(dupl); }// end purge

extern "C" long random();
extern "C" void srandom(int);
#include <stdio.h> // for sscanf

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;

#ifdef MY_EXAMPLE
  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;
#else
  if (argc < 4) 
    {
      cerr << "Call as \"" << argv[0] << " <size> <mod> <seed> \"" << endl; 
      return 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;
#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;
  return 0;
}