#include <cassert>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

#include <indextable.h>
#include <indextabletest.h>
#include <print.h>
#include <typedefs.h>



//
//  About: The ideas came from a public code review by
//     Herb Sutter http://www.gotw.ca/gotw/073.htm#1
//


// Client comparision function. {3k,3k+1,3k+2}
class partition3
{
public:

  bool operator()(int a, int b)
    { return ((a%3) < (b%3)); }
};

// This code is from http://www.gotw.ca/gotw/073.htm
// and was a proposed solution in the code review.
// I have formatted it so that it is better to read.
namespace Solution2
{

template< class T, class U >
struct ComparPair1stDeref
{
  bool operator()
  (
    pair<T,U> const & a,
    pair<T,U> const & b 
  ) const
    { return *a.first<*b.first; }
};

template< class IterIn, class IterOut >
void sortIndexTable
( 
  IterIn first, 
  IterIn last, 
  IterOut out
)
{
  vector<pair<IterIn,int> > s(last-first);
  for (uint i=0; i<s.size(); ++i)
    s[i]=make_pair(first+i,i);
    sort
    (
      s.begin(),
      s.end(),
      ComparPair1stDeref<IterIn,int>()
    );
  for (uint i=0; i<s.size(); ++i,++out)
    *out=s[i].second;
}

}


void indextabletest01()
{
  uintc aimax=10;
  int ai[10]={15,12,13,14,18,11,10,17,16,19};
  vector<int> aidxtbl(aimax);
  Solution2::sortIndexTable(ai,ai+aimax,aidxtbl.begin());

  cout << "######################" << endl;
  for (uint i=0; i<aimax; ++i)
    cout << SHOW(i)
         << "," << SHOW(aidxtbl[i])
         << "," << SHOW(ai[aidxtbl[i]])
         << endl;

  cout << "######################" << endl;

  sortIndexTable(aidxtbl.begin(),partition3(),ai,ai+aimax);
  for (uint i=0; i<aimax; ++i)
    cout << SHOW(i)
         << "," << SHOW(aidxtbl[i])
         << "," << SHOW(ai[aidxtbl[i]])
         << endl;

  cout << "######################" << endl;

  sortIndexTable(aidxtbl.begin(),less<int>(),ai,ai+aimax);
  for (uint i=0; i<aimax; ++i)
    cout << SHOW(i)
         << "," << SHOW(aidxtbl[i])
         << "," << SHOW(ai[aidxtbl[i]])
         << endl;

  cout << "######################" << endl;

  vector<uint> aidxtbl2;
  vector<int> ai2(ai,ai+aimax);
  sortIndexTable(aidxtbl2,greater<int>(),ai2);
  for (uint i=0; i<aimax; ++i)
    cout << SHOW(i)
         << "," << SHOW(aidxtbl2[i])
         << "," << SHOW(ai[aidxtbl2[i]])
         << endl;

}