// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#define Permutation_CC

#include <stdlib.h>
#include <LINK/basic/Permutation.h>

// exchange two elements of the array with indexes i and j
//#include "Permutation.h"
//#include "Error.cc"


// exchange two elements in the array
inline void
	swap ( int* array, int i, int j )
{ int tmpr;
      tmpr=array[i];
      array[i]=array[j];
      array[j]=tmpr;
} 

// function factorial n! 
inline int fctr ( int n )
{ int fact; 
  if ( n == 0 )  fact=1;
  else
  { fact=1;
    int i;
    for (i=1; i<=n; i++ ) fact*=i; 
  }
  return fact;
} 

// define next invers matrix          
inline  void
        incr( int* array, int dim )
{ int i=dim-1;
  while( (i>=0) && ( (array[i]+1)>(dim-i) ) )
       { array[i]=0; i--; }
  array[i]++;
}

// define previous invers matrix
inline void
       decr( int* array, int dim )
{  int i=dim-1;
   while( (i>=0) && ((array[i]-1)<0) )
        { array[i]=dim-i; i--; }
   array[i]--;
}

//shift to the left  all tail elements from the
// possition ="possition", "last" elements bigin 0; 
inline
void shift_left( int* curr, int possition, int last)
{
  int i;
  for (i=possition; i<last; i++ )
      curr[i]=curr[i+1];
  curr[last]=0;
}

//reconstract permutation from invers matrix
void
   reconstract_permutation( int* next, int* inv, int  size )
{  int* temp;
   int i, j;
       temp=new int[size+1]; // temp is identical permutation
    for (i=0; i<=size; i++ ) temp[i]=i+1;
    for ( i=0; i<size; i++ ) //loop for elements
    { j=inv[i];          //exept last
      next[i]=temp[j]; 
      shift_left(temp,j,size);
     }
    next[size]=temp[0]; // last element 
}

//initialization of permutation
Permutation::Permutation(int size)
{   if (size <= 0 )  
    { warning("Wrong argument, size must be >0\n");
      size=1;
     } 
    _length=size;
    _permutation = new int[_length];

    int i;
    for (i=0; i<_length; i++)  _permutation[i]=i+1; 
}


//initialization of permutation
Permutation::Permutation(const Permutation& p)
{   
    _length=p.size();
    _permutation = new int[_length];

    int i;
    for (i=0; i<_length; i++)  _permutation[i]=p[i];
}


// display permutation 
ostream&  Permutation::display(ostream& os) const
{
   os<<"{";
   int i;
   for (i=0; i<_length-1; i++ )
        os<<_permutation[i]<<",";
        os<<_permutation[_length-1]<<"}";
   os<<endl;
}

// returm the first permutation
Permutation& 
Permutation::first()
{ 
  int i;
  for (i=0; i<_length; i++) _permutation[i]=i+1;
  return *this;
}

// return the last permutation
Permutation&
Permutation::last()
{ for ( int i=0; i<_length; i++ ) _permutation[i]=_length-i;
  return *this;
}


// operator == return TRUE, if two permutations 
// are equavalnt in lexographic order.
Bool
Permutation::operator==(const Permutation& perm) const
{ if ( this != &perm )  
      {
      if ( _length != perm._length) return FALSE;
      int i;
      for (i=0; i<_length; i++ )
      if ( _permutation[i] != perm._permutation[i] ) return FALSE;
      }
  return TRUE;
}

Bool
Permutation::eq(const Permutation& perm) const
{ return operator==(perm) ;}

Bool
Permutation::operator!= (const Permutation& perm) const
{ return !operator==(perm) ;}

Bool
Permutation::neq(const Permutation& perm) const
{ return operator!=(perm) ;}

Bool
Permutation::operator > (const Permutation& perm ) const
{ if ( _length != perm._length )
       { warning(" Permutation opertor> : permutations has different size\n");
       return FALSE; }
  int i=0; 
  while ( (_permutation[i]==perm._permutation[i])
          && ( i< _length) ) i++;
   if ( i==_length ) i--; 
   if ( _permutation[i] > perm._permutation[i]) return TRUE; 
   if ( _permutation[i] < perm._permutation[i]) return FALSE; 
   return FALSE; 
}

Bool
Permutation::gt(const Permutation& perm) const
{ return operator>(perm) ;}

Bool
Permutation::operator <= (const Permutation& perm ) const
{ return !operator>(perm); }

Bool
Permutation::lte(const Permutation& perm) const
{ return operator<=(perm) ;}

Bool
Permutation::operator < (const Permutation& perm ) const
{ if ( _length != perm._length )
       { warning(" Permutation opertor< : permutations has different size\n");
       return FALSE; }
  int i=0; 
  while ( (_permutation[i]==perm._permutation[i])
          && ( i< _length) ) i++;
   if ( i==_length ) i--; 
   if ( _permutation[i] < perm._permutation[i]) return TRUE;
   if ( _permutation[i] > perm._permutation[i]) return FALSE;
   return FALSE; 
}

Bool
Permutation::lt(const Permutation& perm) const
{ return operator<(perm) ;}


Bool
Permutation::operator >= (const Permutation& perm ) const
{ return !operator<(perm); }


Bool
Permutation::gte(const Permutation& perm) const
{ return operator>=(perm) ;}

// index-th element of the permutation
int
Permutation::operator[]( int index ) const
{ if ( (index <0) || (index >=_length) )
  { warning("Permutation operator[] : index is out of range\n");
     return index;}
  return _permutation[index]; 
} 

int
Permutation::index( int index ) const
{ return operator[](index); }

//rearrange the permutation in random order
Permutation&
Permutation::random()
{ int j;
  int rnd;
  int i;
  for (i=_length-1; i>=1; i-- )
  { rnd=Link_randomLong();  
    j=rnd % (i+1);
    swap(_permutation, j,i );
  }
  return *this;
}
//operator = assing value of right permutation to left one
Permutation&
Permutation::operator = (const Permutation& perm )
{  if ( this != &perm )
   {   if ( _length != perm._length )
       {   _length=perm._length;
           delete [] _permutation;
           _permutation=new int [_length];
       } 
       int i;
       for (i=0; i<_length; i++ )
       _permutation[i]=perm._permutation[i];
   }
  return *this;
}

//Permutation&
//Permutation::copy(const Permutation& perm )
//{ return operator=(perm); }

// return the rank of the permutation in lexograghic order
int
Permutation::rank( ) const 
{ int* temp;
 
  temp=new int[_length];
  int i, j;
  for (i=0; i<_length; i++) temp[i]=_permutation[i];
  int rank=0;
  for ( i=0; i<_length; i++ )
  { rank+= ( temp[i]-1 ) * fctr( _length -i-1 );
    for (j=i+1; j<_length; j++ )
        if ( temp[j] > temp[i] ) temp[j]--;
  }
  return rank;   
}

//constract invers matrix for the permutation
void make_invers_matrix( int* inv, int* array, int dim )
{   
   int i, j;
   for (i=0; i< dim; i++ ) inv[i]=0; 
   for ( i=0; i<dim; i++ )
       for (j=i+1;  j<=dim; j++) 
           if ( array[i] > array[j] ) inv[i]++;
}


Permutation&
Permutation::next()
{ if ( (_length>1) && ( _permutation[_length-2]<_permutation[_length-1] ) )
     swap(_permutation, _length-2, _length-1);
  else
  { 
    int size=_length-1;
    _invers = new int[size];
    make_invers_matrix(_invers, _permutation, size );
    incr(_invers, size );
    reconstract_permutation( _permutation, _invers, size );
    delete [] _invers;
  }
  return *this;
}


Permutation&
Permutation::previous()
{ if ( (_length>1) && ( _permutation[_length-2]>_permutation[_length-1] ) )
     swap(_permutation, _length-2, _length-1);
  else
  { int size=_length-1;
    _invers = new int[size];
    make_invers_matrix(_invers, _permutation, size );
    decr(_invers, size );
    reconstract_permutation( _permutation, _invers, size );
    delete [] _invers;
   }
  return *this;
}

ostream&
operator<<(ostream& stream, const Permutation& perm)
{
   stream<<"{";
   for( int i=0; i<perm._length-1; i++)
        stream << perm._permutation[i] << ",";
   stream << perm._permutation[perm._length-1];
   stream << "}";
   return stream;
}

Permutation&
Permutation::unrank( int rank )
{  int* temp;
   int quot;
   if ( (rank<0) || ( rank>fctr(_length)) )
      { warning("Permutation unrank function : argument is out of range\n"); 
        rank=0;
      }
   temp=new int[_length];
   int i;
   for (i=0; i<_length; i++ ) temp[i]=i+1; 
   for ( i=_length-1; i>=0; i-- )
   { rank= rank % fctr(i+1); quot= rank / fctr(i);
     _permutation[_length-1-i]=temp[quot];
    shift_left(temp, quot, _length-1);
   } 
  return *this;
}