// Lemur OLAP library (c) 2003 National Research Council of Canada by Daniel Lemire, and Owen 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.
 */
#ifndef PERFECTNORMALIZATION_H
#define PERFECTNORMALIZATION_H

#include "normalizations.h"

template <class _DT, class _LDT>
class PerfectNormalization : public Normalization<_DT,_LDT> {
public:
    PerfectNormalization(vector<int> ChunkShape): mChunkShape(ChunkShape) {}
    virtual PerfectNormalization* clone() const { return new PerfectNormalization(*this); }
    virtual ~PerfectNormalization() {}
    virtual const string getTextName(void) const { return "Perfect";}
    virtual norm_type computeNormalFrom(DataCube<_DT,_LDT>& DC, 
        const norm_type & initial);
    enum {verbose = false};
protected:
    static void permutations(const int maximum, vector<int>& CurrentPermutation,
        norm_type & PermutationSet);
    vector<int> mChunkShape;
};

/* 
* For high performance purposes where memory is not an issue, it is better to compute the permutations
* once and for all, store the object and reuse it at will.
* Now, I should really discard some of these permutations based on the fact that I use block encoded
* data cubes, but then, this call would depend on m and I'm afraid it would bring added complexity
*/
template <class _DT, class _LDT>
void PerfectNormalization<_DT,_LDT>::permutations(const int maximum, 
  vector<int> & CurrentPermutation, norm_type & PermutationSet) {
  assert(maximum > 0);
  for(short i = 0 ; i < maximum ; ++i) 
    if( find(CurrentPermutation.begin(),CurrentPermutation.end(),i) == CurrentPermutation.end() ) {
      vector<int> NewPermutation(CurrentPermutation);
      NewPermutation.push_back(i);
      if(NewPermutation.size() == (uint) maximum) 
        PermutationSet.push_back(NewPermutation);
      else
        permutations(maximum, NewPermutation, PermutationSet);      
    }
}


template <class _DT, class _LDT>
norm_type PerfectNormalization<_DT,_LDT>::computeNormalFrom(DataCube<_DT,_LDT>& DC, 
        const norm_type & initial) {// will ignore initial
  if(DC.getVolume() > 64) cout << "[Warning] This will probably run forever. Better abort now. " <<endl;
  const vector<int> shape = DC.getShape();
  const uint d = shape.size();
  map<int, norm_type >  AllPermutations;
  uint Number = 1; 
  for(uint dim = 0; dim < d; ++dim)  {
    if(AllPermutations.find(shape[dim]) == AllPermutations.end()) {
      vector<int> starter; 
      permutations(shape[dim],starter, AllPermutations[shape[dim]]);
    }
    Number *= AllPermutations[shape[dim]].size(); 
  }
  if(verbose) cout << "I'll need to test " << Number << " normalizations to find the best one." << endl;
  double lowestcost = -1;
  norm_type best;
  assert(Number > 0);
  for(uint k = 0; k < Number ; ++k ) {
    norm_type current(d);
    uint base = 1;
    for(uint dim = 0; dim < d; ++dim) {
      const int index = (k / base) % AllPermutations[shape[dim]].size();
      base *= AllPermutations[shape[dim]].size();
      current[dim] = AllPermutations[shape[dim]][index];
    }
    const float cost = HOLAPUtil<int,int64>::cost(DC,mChunkShape,current); 
    if ((lowestcost < 0) || (cost < lowestcost) ) {
      lowestcost = cost;
      best = current;
    }
  }
  return best;
  
}





#endif

