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

#include "normalizationscommon.h"

// put in this class all the permutation stuff (1D)
class PermutationUtil {
public:

    //apply a normalization to a bunch of indices
    static inline vector<int> permute(const vector<int>& indices, const norm_type& Normalization) {
        vector<int> answer (indices.size(),0);
        for(uint dim = 0; dim < indices.size(); ++dim)
            answer[dim] =  Normalization[dim][indices[dim]];
        return answer;
    }

    // return the identity permutation which amounts to the identity function
    static norm_type identity( const vector<int>& shape) {
        norm_type DefaultNormalization(shape.size());
        for(uint dim = 0; dim < shape.size(); ++dim)
            DefaultNormalization[dim] = identity(shape[dim]);
        return DefaultNormalization;
    }
    

    // return an identity permutation (which is also an identity function)
    static vector<int> identity( const int nElem) {
        vector<int> answer(nElem,0);
        for(int index = 0; index < nElem ; ++index ) answer[index] = index;
        return answer;
    }

    static bool isPermutation( const vector<int> &f) {
        vector<int> temp(f);
        sort(temp.begin(),temp.end(),less<int>());
        for(uint k = 0; k < f.size() ; ++k) {
            if (temp[k] != (int) k) return false;
        }
        return true;
    }

    // return a randomly generated permutation
    static vector<int> randomPermutation( const int nElem) {
        vector<int> eggs(nElem);  // eggs will be scrambled...
        for (int i=0; i < nElem; i++) eggs[i] = i;
        random_shuffle(eggs.begin(), eggs.end() );  // scramble
        assert(isPermutation(eggs));
        return eggs;
    }

    // return a vector of random permutations consistent with a cube's shape
    static norm_type randomPermutation( const vector<int>& shape) {
        norm_type randNormalization(shape.size());
        for(uint dim = 0; dim < shape.size(); ++dim) {
            randNormalization[dim] = randomPermutation(shape[dim]);
        }
        return randNormalization;
    }


    // invert a permutation
    static vector<int> invert( vector<int> perm) {
      assert(isPermutation(perm));
      vector<int> inverse(perm.size());
      for (uint i=0; i < perm.size(); i++) inverse[ perm[i]] = i;
      assert(isPermutation(perm));
      return inverse;
    }

    static norm_type invert( norm_type perms) {
        norm_type inversions(perms.size());
        for(uint dim = 0; dim < perms.size(); ++dim) {
            inversions[dim] = invert(perms[dim]);
        }
        return inversions;
    }



};

#endif 

