/*****************************************************************
 * author Daniel Lemire 
 * (c) NRC
 ************************************************************
 *
 * Created March 23rd 2003: Can we find a matrix of some class that is
 *			incompressible in an HOLAP sense under normalization. The problem
 *			with this code is that the "matrix of some class" remains undefined.
 *			I have some intuition about this, but not enough to be useful, I fear.
 *
 */

 /**
 *  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"
/*
 * This is a bit more useful. What we want to do is generate matrices randomly
 * until we find matrices with the worse possible efficiency (max holap). The
 * max efficiency is reached when holap = 1/density or 2 if the density is 1/2.
 * what we'd like is to find such a matrix that we cannot compress using 
 * renormalization.
 */

void seekIncompressible() {
  const short N = 4, m = 2;
  deque<deque<short> > PermutationSet;
  deque<short> StartPermut;
  // this next line takes about a second or less with N=8.
  cout << "Precomputing permutations..."<<endl;
  permutations(N,StartPermut,PermutationSet);
  cout << "Done. I found "<<PermutationSet.size() << " permutations. "<<endl;
  //
  float LargestMinHOLAP = 0.0f;
  vector<vector<bool> > buffer(N, vector<bool>(N,false));
  bool Found = false;
  for(int test = 0; test < 1000000; ++test) {
    cout << "Beginning test # "<< (test + 1) <<endl;
    vector<vector<bool> > matrix = randomMatrix(N); 
    while(holap(matrix,m) < 2.0f){
      matrix = randomMatrix(N);
    }
    cout << "Found a matrix..." << endl;
    float CurrentHOLAP = holap(matrix,m);
    print(matrix);	
    //
    const int Size = PermutationSet.size();
    for(deque<deque<short> >::iterator rows = PermutationSet.begin(); rows != PermutationSet.end(); rows++) {
     for(deque<deque<short> >::iterator cols = PermutationSet.begin(); cols != PermutationSet.end(); cols++) {
       normalize(matrix,buffer,*rows,*cols);// normalize the buffer      
       CurrentHOLAP = holap(buffer,m);
       if(CurrentHOLAP < 2.0f)  {
         cout << "The matrix is compressible to "<<CurrentHOLAP<<endl;
         print(buffer);
         break;
       }
     }
     if(CurrentHOLAP < 2.0f) break;
    }
    if(CurrentHOLAP == 2.0f) {
      Found = true;
      break;
    }
    //
  }
  //
  if(Found) {
    cout <<" The following matrix in incompressible. "<< endl;
    print(buffer);
  }
  
}

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


