// Created by Igor Markov, Feb 8, 2001

/*
    The code below is a self-contained implementation of
    index-sorting using STL, i.e., sorting of indices by values, 
    rather than sorting values themselves.  This can be useful in several
    cases, e.g., when the values are too expensive to move (imagine that 
    the values are whole IRS records --- one per person --- and you are 
    sorting them by annual income) and also to visualize various sorting 
    algorithms.

    Pages 302-305 in the Sedgewick book discuss
    additional applications of index/pointer sorting.
    Make sure you read those pages.
*/

#include <iostream>
#include <algorithm>

   class CompareByValue
   {
      const double * _caps;  // CompareByCapacity does not allocate/own
                             //   this piece of memory
      public:
         CompareByValue(const double *caps): _caps(caps) {}
      bool operator()(unsigned i, unsigned j)
         { return _caps[i] < _caps[j]; }
   };

int main()
{
      // note that in a practical application
      // you will probably need to use containers with 
      // dynamically allocated memory, and rather different
      // ways to initialize them
   double   values[5]={23.5, 13.8, 18.9, 17.3, 21.7};
   unsigned k, idx_array[5] ={0,1,2,3,4}; // the "identity" permutation
                                          // i.e., 0->0, 1->1, etc.

   cout << " Values in initial order :  ";
   for(k=0; k!=5; k++) cout << values[k] << ", ";
   cout << endl;

   CompareByValue cbc(values);
   sort(idx_array, idx_array + 5, cbc);
 
   // now compute the inverse of the permutation in idx_array
   unsigned sorting_permutation[5];
   for(k=0; k!=5; k++)   sorting_permutation[ idx_array[k] ]= k;

   for(k=0; k!=5; k++)
     cout << " Item " << k << " is #" <<sorting_permutation[k] 
          << " in the sorted order " << endl;
}