// 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 MATCHING_H
#define MATCHING_H

#include "normalizations.h"
// #include "graph.h"


/***********************************************************************
 * To do: explain why this should be optimal for volume=2 chunking.
 *
 * As a heuristic (I guess) I apply it to each dimension in turn, and
 * get a result that hopefully works well for 2x2x..x2 chunking.
 *
 *  Bug report: weather, groupbits 6680 -fast -roundup_even
 *   the ALL option ends up NOT BEING OPTIMAL 2x1x1..x1: cost 207432
 *   versus 206604 for frequency sort.  Where is the bug?  In this
 *   code or frequency sort or in cost calculation?
 *
 */

template <class _DT, class _LDT>
class MatchingNorm : public Normalization<_DT,_LDT> {
public:
    enum{ ALL_DIMS = -1};
    MatchingNorm(int d): dimToProcess(d) {}
    virtual MatchingNorm* clone() const { return new MatchingNorm(*this); }
    virtual ~MatchingNorm() {}
    virtual const string getTextName(void) const {
      ostringstream ost;
      if (dimToProcess == ALL_DIMS) 
  ost << "Weighted Matching iterated BETTER over all dimensions";
      else
  ost << "Weighted Matching BROKEN? [dim " << dimToProcess << "]";
      return ost.str();}
    virtual norm_type computeNormalFrom(DataCube<_DT,_LDT>& DC, 
        const norm_type & initial);
 private:
    const int dimToProcess;
};


//
// Implementations follow...
///////////////////////////////

template <class _DT, class _LDT>
  norm_type MatchingNorm<_DT,_LDT>::computeNormalFrom(DataCube<_DT,_LDT>& DC,  const norm_type & initial) {

  // ignores initial completely for the dimensions it assigns.  
  norm_type answer(initial);

  // DANGER: BROKEN FOR INITIAL != IDENTITY
  // we now do the normalization but do not later compose :(

  const vector<int> shape = DC.getShape();

  assert (dimToProcess == ALL_DIMS); // new changes are suspect otherwise...

  int startDim = (dimToProcess == ALL_DIMS) ? 0 : dimToProcess;
  int stopDim  = (dimToProcess == ALL_DIMS) ? shape.size() - 1 : dimToProcess;


  for (int dim = startDim; dim <= stopDim; ++dim) {
    int chunkSize = (0x1 << dim);  // working on 2x2x..x2x1x1..1 size
    const int vectorLen = DC.getVolume() / (shape[dim] * chunkSize);
    GraphForMatching g;
    
    for (int val = 0; val < shape[dim]; ++val) {
      vector<double> occupancy(vectorLen,0);  
      // hacked from Pearson...
      vector<int> start(shape.size(),0);
      start[dim] = val;
      vector<int> indices(start);
      vector<int> bounds = shape;
      bounds[dim] = val + 1;
      int count = 0;   
      do {
  assert(count/chunkSize < vectorLen);
  const bool allocated1 = (DC.get(PermutationUtil::permute(indices,answer)) != 0);  
  occupancy[count/chunkSize] += double(allocated1);   // rely on increment's right-to-left behaviour
  //	assert( dim != 0 || occupancy[count/chunkSize] < 1.5);
  ++count;
      } while(MathUtil::increment( indices, start, bounds) );
      
      assert(count/chunkSize == vectorLen);
      g.addVtx(occupancy);  
    }
    
    answer[dim] = // g.implicitMaxMatching( BitOrWeight() );
                  // g.implicitMaxMatching( ChunkingWeight() );  // same as BitOrWeight
      g.implicitMaxMatching( ChunkingWeight(dim,HOLAPUtil<_DT,_LDT>::SparseCost(DC)) );
    assert(PermutationUtil::isPermutation(answer[dim]));
  }

  return answer;
}


#endif
