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

#include "normalizationscommon.h"

// put here everything that depends on a chunk geometry (HOLAP)
template <class DT, class LDT>
class HOLAPUtil {
public:

    // given a cube, some chunk geometry and a normalization, compute the HOLAP cost
    static uint64 cost(DataCube<DT,LDT> & DC, const vector<int>& ChunkShape, \
                       const norm_type& Normalization, const bool verbose = false);
    static uint64 cost(const vector<int>& SizeOfChunks, const vector<int>&NumberOfAllocated, const int d,
        const bool verbose=false);
    // this is used in computing the HOLAP cost for a data cube
    static int SparseCost(DataCube<DT,LDT> & DC) {
        return holapSparseCost(DC.getShape().size());
    }

    static void computeChunkDensityInfo(DataCube<DT,LDT> & DC,
                                        const vector<int>& ChunkShape,
                                        const norm_type& Normalization,
                                        vector<int>& SizeOfChunks,
                                        vector<int>& NumberOfAllocated );


    // Given indices, the shape of a data cube and some chunk shape, compute the "chunk index"
    // (which chunk does Indices belong to!)
    // (wanted it elsewhere.  Does this make sense as public? -ofk --> I think it does. DL)
    // Note that this assumes small file size (32 bits)
    static inline int getChunkIndex(const vector<int>& Indices, const vector<int>& Shape,const vector<int>& ChunkShape) {
        int index = 0, base = 1;
        for(uint i = 0; i < Shape.size(); ++i ) {
            index += (Indices[i] / ChunkShape[i])  * base;
            base *= roundup(Shape[i] , ChunkShape[i]); // this could be computed once
        }
        return index;
    }

    //
    //	this is a slightly faster version to getChunkIndex, you need to call precomputeChunkBase before
    // Note that this assumes small file size (32 bits)

    static inline int getChunkIndexFast(const vector<int>& Indices, const vector<int>& ChunkShape,\
                                        const vector<int>& ChunkBase) {
        int index = 0;
        for(uint i = 0; i < ChunkShape.size(); ++i ) index += (Indices[i] / ChunkShape[i])  * ChunkBase[i];
        return index;
    }

    // this assumes small file sizes (32 bits)
    static inline vector<int> precomputeChunkBase(const vector<int>& Shape, const vector<int> & ChunkShape) {
        vector<int> ChunkBase(ChunkShape.size(),1);
        for(uint i = 1; i < ChunkBase.size(); ++i ) {
            assert(Shape[i-1] >= ChunkShape[i-1]);
            ChunkBase[i] *=  ChunkBase[i-1] * roundup(Shape[i-1] , ChunkShape[i-1]);
        }
        return ChunkBase;
    }

    // compute the number of chunks
    static inline int computeNumberOfChunks(const DataCube<DT,LDT> & DC, const vector<int>& ChunkShape) {
        vector<int> LastIndex(DC.getShape());
        for(uint dim = 0; dim < LastIndex.size();++dim) --LastIndex[dim];
        return getChunkIndex(LastIndex, DC.getShape(), ChunkShape) + 1;
    }



private:

    // call SparseHOLAP Cost instead!!!
    static int inline holapSparseCost(const int dimension ) {
        int answer = dimension / 2;
        if(dimension % 2 > 0) answer++;
        return answer + 1;
    }

    static inline int holap(const int number, const int allocated, const int dimension) {
        return ( holapSparseCost(dimension) * allocated < number) ? holapSparseCost(dimension) * allocated : number;
    }

    static inline int roundup(const int i, const int m) {
        return (i % m == 0) ? i/m : i/m + 1;
    }

};



template <class DT, class LDT>
void HOLAPUtil<DT,LDT>::
computeChunkDensityInfo(DataCube<DT,LDT> & DC,
                        const vector<int>& ChunkShape,
                        const norm_type& Normalization,
                        vector<int>& SizeOfChunks, // output
                        vector<int>& NumberOfAllocated // output
                       ) {
    // to do this, we first have to figure how many chunks there are and then be
    // able to find the index of each chunks, then I can just visit each cell or
    // component once and be done with it.
    vector<int> Shape = DC.getShape();
    for(uint dim = 0; dim < Shape.size() ; ++dim) assert(Shape[dim] >= ChunkShape[dim]);// sanity check
    //
    const int NumberOfChunks = computeNumberOfChunks(DC,ChunkShape);
    NumberOfAllocated.resize(NumberOfChunks,0);
    SizeOfChunks.resize(NumberOfChunks,0);
    vector<int> Indices(Shape.size(), 0);
    vector<int> Start(Indices);
    vector<int> ChunkBase = precomputeChunkBase(Shape,ChunkShape);
    //
    do {
        int ChunkIndex = getChunkIndexFast(Indices, ChunkShape, ChunkBase);
        ++SizeOfChunks[ChunkIndex];
        vector<int> NewValue = PermutationUtil::permute(Indices,Normalization);
        if(DC.get(NewValue) != 0) ++NumberOfAllocated[ChunkIndex];
    }
    while(MathUtil::increment( Indices, Start, Shape));
}


template <class _DT, class _LDT>
uint64 HOLAPUtil<_DT,_LDT>::
cost(DataCube<_DT, _LDT> & DC,
     const vector<int>& ChunkShape,
     const norm_type& Normalization, const bool verbose) {

    // to do this, we first have to figure how many chunks there are and then be
    // able to find the index of each chunks, then I can just visit each cell or
    // component once and be done with it.
    vector<int> Shape = DC.getShape();
    for(uint dim = 0; dim < Shape.size() ; ++dim) assert(Shape[dim] >= ChunkShape[dim]);// sanity check  
    //
    vector<int> SizeOfChunks;
    vector<int> NumberOfAllocated;

    computeChunkDensityInfo(DC,ChunkShape,Normalization,SizeOfChunks,NumberOfAllocated);
    return cost(SizeOfChunks,NumberOfAllocated,Shape.size(),verbose);
}

template <class _DT, class _LDT>
uint64 HOLAPUtil<_DT,_LDT>::
cost(const vector<int>& SizeOfChunks, const vector<int>&NumberOfAllocated, const int d, const bool verbose) {
    const int NumberOfChunks = SizeOfChunks.size();

    //
    // Ok, now, we have the geometry figured out!
    uint64 HOLAP = 0;
    uint64 TotalAllocated = 0, TotalInFull = 0, Total = 0, Empty = 0, Full = 0,
                            PartialDense = 0, PartialSparse = 0;
    for(int index = 0; index < NumberOfChunks; ++index) {
        TotalAllocated += NumberOfAllocated[index];
        Total += SizeOfChunks[index];
        uint64  HOLAPThisChunk = holap(SizeOfChunks[index], NumberOfAllocated[index], d);
        HOLAP += HOLAPThisChunk;
        if(NumberOfAllocated[index] == 0) ++Empty;
        else if(NumberOfAllocated[index] == SizeOfChunks[index]) {
            ++Full; TotalInFull += SizeOfChunks[index];
        }
        else if(HOLAPThisChunk < (uint) SizeOfChunks[index])
            ++PartialSparse;
        else ++PartialDense;
    }
    if(verbose) {
        // chunk-wise
        cout << "\tchunks="<< NumberOfChunks << "\tempty="<< Empty << "\tfull="<<\
        Full << "\tDense=" << PartialDense << "\tsparse=" << PartialSparse << endl;
        // cells-wise
        cout << "\ttotal cells allocated="<<TotalAllocated<<" total cells="<< Total \
        << " total cells in full chunks="<< TotalInFull <<endl;
        // averages
        cout <<	"\taverage size of full chunks="
        << (TotalInFull/(float)Full) << " average size of chunks=" <<
        (Total/(float)NumberOfChunks)<< endl;
    }
    return HOLAP;
}


#endif
