/*****************************************************************
 * author Daniel Lemire 
 * (c) NRC 
 ************************************************************
 *
 * Created March 23rd 2003 : Test some heuristics for normalization.
 *			Workd done by D. Lemire and O. Kaser.
 **/
 
 /**
 *  This program is free software; you can
 *  redistribute it and/or modify it under the terms of the GNU General Public
 *  License as published by the Free Software Foundation (version 2). This
 *  program is distributed in the hope that it will be useful, but WITHOUT ANY
 *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 *  FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 *  details. You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software Foundation,
 *  Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

#include "OwenCommon.h"
 /*
 * Next follows a multiscale normalization algorithm. We only work on rows
 * but it is only twice the work to do both rows and cols.
 */
void multiscaleNormalize( vector<vector<bool> >& x) {
  // this code assumes m = 2
  const short m = 2;// size of the smallest blocks
  const short b = 2;// work in pairs
  for(int SizeOfBlocks = m; SizeOfBlocks < x.size(); SizeOfBlocks *= b) {
    const int NumberOfPairs = x.size() / ( 2 * SizeOfBlocks );
    for (int pair = 0; pair < NumberOfPairs; ++pair) {
      // next lines are hard-coded and ugly, really ugly
      float DoNothing = holap(x,x.size()/2);//SizeOfBlocks);// this is not quite right, need true multiscale
      const int SizeOfSubBlocks = SizeOfBlocks / 2;
      exchange(x, 2 *  pair * SizeOfBlocks, 2 * pair * SizeOfBlocks + 2 * SizeOfSubBlocks, SizeOfSubBlocks);
      float SwitchFirstBlockWithThird = holap(x,x.size()/2);//SizeOfBlocks);
      unexchange(x, 2 * pair * SizeOfBlocks, 2 * pair * SizeOfBlocks + 2 * SizeOfSubBlocks, SizeOfSubBlocks);
      exchange(x, 2 * pair * SizeOfBlocks, 2 * pair * SizeOfBlocks + 3 * SizeOfSubBlocks, SizeOfSubBlocks);
      float SwitchFirstBlockWithFourth = holap(x,x.size()/2);//SizeOfBlocks);
      unexchange(x, 2 * pair * SizeOfBlocks, 2 * pair * SizeOfBlocks + 3 * SizeOfSubBlocks, SizeOfSubBlocks);
      if(SwitchFirstBlockWithThird < DoNothing)  {
        if(SwitchFirstBlockWithThird < SwitchFirstBlockWithFourth) {
          exchange(x, pair * SizeOfBlocks, pair * SizeOfBlocks + 2 * SizeOfSubBlocks, SizeOfSubBlocks);
        } else {
          exchange(x, pair * SizeOfBlocks, pair * SizeOfBlocks + 3 * SizeOfSubBlocks, SizeOfSubBlocks);
  }
      } else if (SwitchFirstBlockWithFourth < SwitchFirstBlockWithThird) {
        if(SwitchFirstBlockWithFourth < DoNothing) exchange(x, pair * SizeOfBlocks, pair * SizeOfBlocks + 3 * SizeOfSubBlocks, SizeOfSubBlocks);
        } else {
        if (SwitchFirstBlockWithThird < DoNothing) exchange(x, pair * SizeOfBlocks, pair * SizeOfBlocks + 2 * SizeOfSubBlocks, SizeOfSubBlocks);
      }
      
    }
    cout << "result with blocks of size "<<SizeOfBlocks << endl;
    print(x);
  }
}	
/*
 * What I call stupid sort is a heuristics first proposed by
 * Owen Kaser. It is not stupid in the sense that it is not a 
 * good heuristics. It is stupid in the sense that it is "simple".
 **/
void stupidSort(vector<vector<bool> > & x) {
  vector<pair<short,short> > freqrows(x.size());
  for(short k = 0; k < x.size(); ++k) freqrows[k] = pair<short,short>(0,k);
  vector<pair<short,short> > freqcols(x[0].size());
  for(short k = 0; k < x[0].size(); ++k) freqcols[k] = pair<short,short>(0,k);
  for(short row = 0; row < x.size() ; ++row) {
    for(short col = 0; col < x[0].size(); ++col) {
      if(x[row][col] == true) {
        freqrows[row].first++;
        freqcols[col].first++;
      }
    }
  }
  sort(freqrows.begin(),freqrows.end());
  sort(freqcols.begin(),freqcols.end());
  deque<short> rows(x.size());
  deque<short> cols(x[0].size());
  for(int k = 0; k < x.size(); ++k) {
    rows[freqrows[k].second] = k;
  }
  for(int k = 0; k < x[0].size(); ++k) {
    cols[freqcols[k].second] = k;
  }
  vector<vector<bool> > buffer(x);
  normalize(x,buffer,rows, cols);
  x = buffer;
}

/*
 * Do some testing here.
 **/
void testHeuristic() {
  const short N = 8;
  vector<vector<bool> > randommatrix = randomMatrix(N);
  vector<vector<bool> > matrix = randommatrix;
  
  cout << "Matrix before ( HOLAP = "<<holap(matrix,N/2) << " ) " << endl;
  print(matrix);
  multiscaleNormalize(matrix);
  cout << "Matrix after multiscaleNormalize ( HOLAP = "<<holap(matrix,N/2) << " ) " << endl;
  print(matrix);

  matrix = randommatrix;
  stupidSort(matrix);
  cout << "Matrix after stupidSort ( HOLAP = "<<holap(matrix,N/2) << " ) " << endl;
  print(matrix);

}

int main(void) {
   cout << "(C) NRC and Owen Kaser" << endl;//in case my boss looks at this
   srand( (unsigned)time( NULL ) );
   testHeuristic();
   cout << " Done."<<endl;// congratulation, you can write code that makes it to the end
   return 0;
}


