//////////////////////////////////////////////////////////////////////////////
// $Id: Permutation.h,v 1.1.1.1 2003/09/15 16:37:52 nthiery Exp $
// Name:	Permutation.h
// Purpose:	Class Permutation for efficient small permutations
//		(User interface)
// Author:	Nicolas M. Thiéry <nthiery@mines.edu>
// Created:	2000/04
// Copyright:	LGPL
//////////////////////////////////////////////////////////////////////////////

// Specifications:
//  - Data structure for permutations of the set {0,..,n}, with n small (<100)
//  - as compact and efficient as possible
//  - reference counted
//  - no consistency tests to ensure that an object is indeed a permutation
//    this is the responsibility of the user!

#ifndef GLIP_PERMUTATION_H
#define GLIP_PERMUTATION_H

#include <GLIP/SmallList.h>
#include <GLIP/SmallList_tmpl.h>

namespace GLIP {

class Permutation : public SmallList<> {
 public:

  // Constructors (just wrappers around the constructors of SmallList)

  Permutation() : SmallList<> () { };
  Permutation(size_type len) : SmallList<> (len) { };
  template <class InputIterator>
    Permutation(InputIterator first,
		InputIterator last,
		size_type len) :
    SmallList<value_type> (first,last,len) {
  }
  template <class InputIterator>
    Permutation(InputIterator first,
		InputIterator last) :
    SmallList<value_type> (first,last) {
  }
  Permutation(string s) : SmallList<> (s) {};
  ~Permutation() {};
  
  // In MuPAD, the convention is to consider permutations of [1,...,n]
  // In C/C++, the convention is to consider permutations of [0,...,n-1]
  // Those two methods do the corresponding conversions
  
  Permutation& MuPAD_to_C ();
  Permutation& C_to_MuPAD ();
  
  // Permutation seen as a function acting on lists

  template<class L>
    L operator () (const L &l) const;
  // Precondition:
  //  l is a random access container, with elements indexed by 0..size-1
  //  the permutation and l have the same size
  //  an object l2 of type L and size 5 can be initialized with L(5)
  // Postcondition:
  //  returns the result of the natural action of the permutation on l
  //  i.e. if l is seen as a function i->l[i], returns i->l[s^-1(i)]

  template<class L>
    bool stabilize (const L &l) const;
  // Precondition:
  //  l is a random access container, with elements indexed by 0..size-1
  //  the permutation and l have the same size
  //  an object l2 of type L, size 5 and with elements indexed by 0..size-1
  //  can be initialized with L(5)
  // Postcondition:
  //  returns true if l is stabilized by the permutation
  
  template<class L>
    bool decrease (const L &l) const;
  // Precondition:
  //  l is a random access container, with elements indexed by 0..size-1
  //  the permutation and l have the same size
  //  an object l2 of type L, size 5 and with elements indexed by 0..size-1
  //  can be initialized with L(5)
  // Postcondition:
  //  returns true if l transformed by the inverse of the permutation
  //  is lexicographicaly strictly bigger than l.

  template<class T>
    bool decrease (const SmallList<T> &l) const;
  // Specialization of decrease for SmallLists
  // Subscripting is manually inlined by direct access to the internal
  // data structure.
  // Is it worth it ? It only saves 10% with g++ -O9.
  // It would be better to help the compiler do the optimisation himself.

  // Some static functions defining classical permutations

  static Permutation id(size_type);
  // The identity permutation

  // Composition of permutations

  friend Permutation operator *(const Permutation &p1, const Permutation &p2);
};

}	// namespace GLIP

#endif	/* GLIP_PERMUTATION_H */

// Local Variables: 
// mode: c++
// End:
