// File: Sorting/stl_purge.C
// Removing duplicates
// Programmer: E. Kaltofen (September 27, 1992)
//                         (STL sort Sep 26, 1995)
// STL items demonstrated
// generic algorithm sort with a comparator "function"
#include <iostream.h>
#include <iomanip.h>
#include <algo.h>
#include <defalloc.h>

// must overload comparison on index array indir_comp I[]: I[i]<I[j] if A[I[i]]<A[I[j]]
template <class ElType>
class indir_comp {static ElType* Aptr;
           static int comp; // counts comparisons in sorting
           // overload function call on indir_comp object
           //     (needed in third argument to STL sort function)
           public: bool operator()(const int& i, const int& j)
                                 {comp++; return Aptr[i] < Aptr[j];}
           friend int indir_sort(ElType[], int, int[]);
          };

template <class ElType>
int indir_sort(ElType A[], int n, int I[])
// set the array I[0],...,I[n-1] such that
// A[I[0]] <= A[I[1]] <= ... <= A[I[n-1]]
// note: one must have ElType& ElType::operator<(ElType&)
{int i;
 for(i=0; i<n; i++) I[i] = i;
 indir_comp<ElType>::Aptr = A;
 indir_comp<ElType>::comp = 0;
 stable_sort(I, I+n, indir_comp<ElType>());
 return indir_comp<ElType>::comp;
}

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
{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_sort(A, n, I);

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

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

 cout<<"Inverse Index Array: " << endl;
 for(i=0;i<n;i++) cout<< setw(3) << 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

#include <stdlib.h>
extern "C" long random();
extern "C" void srandom(int);
#include <stdio.h> // for sscanf
int *indir_comp<int>::Aptr; // static member must be declared
int indir_comp<int>::comp;

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 << setw(3) << array[i] << " ";
  cout<<endl;
  // print positions also
  for(i=0;i<size;i++) cout << setw(3) << i << " "; cout<<endl;

  comp = indir_sort(array, size, indexarray);
  cout << "STL-sorted array after " << comp << " comparisons" << endl;
  for(i = 0; i < size; i++) cout << setw(3) << array[indexarray[i]] << " "; cout << endl;

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