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

// Specifications:
//  - Structure for group of permutations of {0,...,n-1}
//  - The canonical form of a list l is the largest element in the orbit of l

#ifndef GLIP_PERMUTATION_GROUP_H
#define GLIP_PERMUTATION_GROUP_H

#include <list>
#include <vector>
#include <set>
#include <GLIP/Permutation.h>

namespace GLIP {

  using std::vector;
  using std::list;
  using std::set;
  using std::logical_not;
  using std::min;
  using std::back_inserter;
  using std::transform;

  typedef SmallList<bool> BinaryList;

  // Classes for different caching strategies

  class MemoryCache {
    // Save in the memory all canonic binary lists with less ones than
    // zeroes, and use complement to reconstruct the others
    
  private:
    size_t n;
    vector<list<BinaryList> > cache;
  public:
    MemoryCache(size_t nn);
    bool have(size_t k);
    // test if something is in the cache
    list<BinaryList> get(size_t k);
    // Fetch something from the cache.
    // It's the responsability of the user to ensure it's there !
    void set(size_t k, list<BinaryList> l);
    // Set something in the cache
  };

  class PermutationGroup: public list<Permutation> {

  private:
    typedef Permutation::size_type psize_type;
    // type for the elements of {0,...,n-1}
    const size_t n;
    mutable MemoryCache cache;	// Caching strategy

  public:

    // Constructors

    template<class In>
    PermutationGroup(In first, In last) :
      list<Permutation>(first, last), n(first->size()), cache(n) {
    }
    PermutationGroup(size_t nn) : list<Permutation>(), n(nn), cache(nn) {
    }

    // Accessors

    size_t card() const { return n; };
    // returns n such that this is a group of permutations of {0,...,n-1}

    // Action of the group on lists
  
    template<class L>
    L canonic (const L &l) const;
    // returns the canonical form of a list versus the group

    template<class L>
    bool is_canonic (const L &l);
    // Returns true if there exists g in the group such that g.l < l.
    // This is not a const function, because the internal ordering
    // of the elements of the group maybe changed to automatically
    // adapt to the kind of lists encountered.

    template<class L>
    PermutationGroup automorphism_group(const L &l) const;
    // The automorphism group of l is the subset of the current
    // permutation group which stabilizes l.
  
    template<class L>
    size_t automorphism_group_size(const L &l) const;
    // Equivalent to G.automorphism_group(l).size(), but more efficient.

    template<class L>
    vector<L> orbit(const L &l) const;
    // Return the orbit, without removing duplicates

    template<class L>
    set<L>
    orbit_set(const L &l) const;
    // Return the orbit, without duplicates

    template<class L>
    size_t orbit_size(const L &l) const;
    // Equivalent to G.orbit_set(l).size(), but more efficient

    template<class L>
    PermutationGroup weight_automorphism_group(const L &l,
					       typename L::value_type v) const;
    // The automorphism group of l is the subset of the current
    // permutation group which stabilizes l.
    // Given a weight v, this group acts by permutation on the set
    // of positions with weight v in l.
    // weight_automorphism_group generates the permutation group
    // corresponding to this action, after renumbering the positions
    // from left to right starting at 0

    template<class L>
    list<L> split_value_canonics(const L &l,
				 typename L::value_type v1,
				 typename L::value_type v2) const;
    // Generate all canonical lists obtained by splitting the
    // values v1 of l into v1 and v2
  
    template<class L>
    list<L> augment (const L &l,
		     typename L::value_type v1,
		     typename L::value_type v2);
    // Generate all canonical lists obtained by augmenting l, i.e.
    // by replacing one of the trailing values v1 by v2.

    // generates all canonic binary lists with k ones and n-k zeroes
    list<BinaryList> canonics (size_t k);

    // generates all canonic binary lists
    list<BinaryList> canonics ();

    list<SmallList<> > canonic_compositions (size_t d);
    // generates a transversal set of the compositions of d
    // (i.e. lists of non-negative integers of total sum d)
    
    template <class L>
    list<L> canonics_shape(L l);
    // generates all canonic lists having same shape as l
    // L must be a container type allowing random access
    // and whose value_type's are totaly ordered

    template <class L>
    list<L> canonics_shape_rec(L shape);
    // idem, but with "recursive" algorithm
  };

  ////////////////////////////////////////////////////////////////////////////
  // Helper functions
  
  template <class In>
  PermutationGroup closure(In first, In last);
  // Preconditions: [first:last[ is a range of permutations
  //		    all permutations have same size
  //		    [first:last[ is not empty
  // This last condition is necessary, in order to know the sizes
  // of the permutations in the group. If there is no generator,
  // are we speaking of the identity on {1..3}, or {1..19} ?

}
#endif	/* GLIP_PERMUTATION_GROUP_H */

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