//////////////////////////////////////////////////////////////////////////////
// $Id: PermutationGroup_tmpl.h,v 1.1.1.2 2005/01/26 13:42:20 nthiery Exp $
// Name:	PermutationGroup_tmpl.cc
// Purpose:	Class PermutationGroup for groups of permutations
//		(Template implementation)
// Author:	Nicolas M. Thiéry <nthiery@mines.edu>
// Created:	2000/04
// Copyright:	LGPL
//////////////////////////////////////////////////////////////////////////////

#ifndef GLIP_PERMUTATION_GROUP_TMPL_H
#define GLIP_PERMUTATION_GROUP_TMPL_H

#include <cmath>
#include <algorithm>
#include <functional>
#include <set>
#include <list>
#include <queue>

#include <GLIP/Permutation.h>
#include <GLIP/Permutation_tmpl.h>
#include <GLIP/PermutationGroup.h>

namespace GLIP {

  using std::queue;

  ////////////////////////////////////////////////////////////////////////////
  // Private helper functions

  namespace {
    template<class L>
    L
    split_value(L l,
		typename L::value_type v1,
		typename L::value_type v2,
		BinaryList partition) {
      // Splits the values v1 of l between v1 and v2, following the given
      // partition from left to right. Eg, if partition[i] is true, the
      // ith v1 value of l is replaced by v2.
      // Example: split_value([0,2,0,2,2],2,3,[1,0,1]) yields [0,3,0,2,3]
      typename L::size_type j=0;
      for(typename L::iterator i=l.begin(); i!=l.end(); i++) {
	if (*i==v1) {
	  if (partition[j]) {
	    *i=v2;
	  }
	  j++;
	}
      }
      return(l);
    }
  }
  
  ////////////////////////////////////////////////////////////////////////////
  // Implementation of the template member functions
  
  template<class L>
  L
  PermutationGroup::canonic (const L &l) const {
    L l2;	// 
    L lmax(l);	// future canonical form
    for(const_iterator ip=begin(); ip!=end(); ip++) {
      l2=(*ip)(l);
      if (lmax<l2) {
	lmax=l2;
      }
    }
    return(lmax);
  }

  template<class L>
  bool
  PermutationGroup::is_canonic (const L &l) { 
    // Actually looks for a permutation g such that g^{-1}.l < l.
    // This is logically equivalent, but allow to use the decrease
    // method which is much faster than a plain g(l)<l.
    // If such a permutation is found, it's moved at the begining of the group

    for(iterator ip=begin(); ip!=end(); ip++) {
      if (ip->decrease(l)) {
	if (ip!=begin()) {
	  splice(begin(),(*this),ip);
	}
	return false;
      }
    }
    return true;
  }

  template<class L>
  PermutationGroup
  PermutationGroup::automorphism_group(const L &l) const {
    PermutationGroup group(n);
    for(const_iterator ip=begin(); ip!=end(); ip++) {
      if (ip->stabilize(l)) {
	group.push_back(*ip);
      }
    }
    return group;
  }

  template<class L>
  size_t
  PermutationGroup::automorphism_group_size(const L &l) const {
    // It would be better to use the std::count algorithm instead, but
    // for some reason this does not work.
    //  return count(begin(), end(),
    // 		 bind2nd(mem_fun(Permutation::stabilize<L>),l));
    size_t count=0;
    for(const_iterator ip=begin(); ip!=end(); ip++) {
      if (ip->stabilize(l)) { count++; }
    }
    return count;
  }

  template<class L>
  vector<L>
  PermutationGroup::orbit(const L &l) const {
    vector<L> v(size());
    typename vector<L>::iterator iv=v.begin();
    for(const_iterator ip=begin(); ip!=end(); ip++,iv++) {
      *iv=(*ip)(l);
    }
    // Would be nicer with an algorithm ...
    //      transform(begin(), end(), v.begin(),
    //  	      bind2nd(mem_fun_ref(&(Permutation::operator ()<L>)),l));
    return v;
  }

  template<class L>
  set<L>
  PermutationGroup::orbit_set(const L &l) const {
    vector<L> v=orbit(l);
    return set<L>(v.begin(), v.end());
  }

  template<class L>
  size_t
  PermutationGroup::orbit_size(const L &l) const {
    return size()/automorphism_group_size(l);
  }

  template<class L>
  PermutationGroup
  PermutationGroup::weight_automorphism_group(const L &l,
					      typename L::value_type v) const {
    typedef typename L::size_type Lsize_type;
    // Compute the renumbering
    SmallList<Lsize_type, Lsize_type> renum(l.size());
    Lsize_type k=0;			// Number of values v in l

    for (Lsize_type i=0; i!=l.size(); i++) {
      renum[i]=k;
      if(l[i]==v) {
	k++;
      }
    }

    set<Permutation> group;		// used to eliminate duplicates
    PermutationGroup pgroup(k);
    for(const_iterator ip=begin(); ip!=end(); ip++) {
      if (ip->stabilize(l)) {
	Permutation p(k);
	for(Lsize_type i=0; i!=l.size(); i++) {
	  if (l[i]==v) {
	    p[renum[i]]=renum[(*ip)[i]];
	  }
	}
	if (group.find(p)==group.end()) {
	  group. insert(p);
	  pgroup.push_back(p);
	}
      }
    }
    return pgroup;
  }

  template<class L>
  list<L>
  PermutationGroup::split_value_canonics(const L &l,
					 typename L::value_type v1,
					 typename L::value_type v2) const {
    PermutationGroup group=weight_automorphism_group(l, v1);
    list<BinaryList> partitions=group.canonics();
    list <L> result;
    for(list<BinaryList>::const_iterator ip=partitions.begin();
	ip!=partitions.end(); ip++) {
      result.push_back(split_value(l,v1,v2,*ip));
    }
    return(result);
  }
  
  template<class L>
  list<L>
  PermutationGroup::augment (const L &l,
			     typename L::value_type v1,
			     typename L::value_type v2
			     ) {
    list<L> augmentations;
    for(int i=l.size()-1;i>=0;i--) {
      if (l[i]==v2) break;
      if (l[i]==v1) {
	L l2=l;
	l2[i]=v2;
	if (is_canonic(l2)) {
	  augmentations.push_back(l2);
	}
      }
    }
    return augmentations;
  }

  template <class L>
  list<L> PermutationGroup::canonics_shape(L l) {
    list<L> result;
    std::sort(l.begin(), l.end());
    do {
      if (is_canonic(l)) {
	result.push_back(l);
      }
    } while(std::next_permutation(l.begin(), l.end()));
    return result;
  }

  template <class L>
  list<L> PermutationGroup::canonics_shape_rec(L shape) {
    
    typedef typename L::value_type Lvalue_type;
    typedef typename L::size_type  Lsize_type;

    list<L> result;

    if (shape.empty()) {
      result.push_back(shape);
      return result;
    }
  
    std::sort(shape.begin(), shape.end());

    // Look up which value is the most present in l (linear complexity)

    // We initialize value just to quiet the compiler; unless the
    // shape is empty (in which case we don't care about the content
    // of value), value will be set at least once in the loop below
    Lvalue_type value=0;
    Lsize_type k=0;			// number of occurences
    {
      typename L::const_iterator i=shape.begin();
      while(i!=shape.end()) {
	Lvalue_type v=*i;
	Lsize_type  j=1;
	while((++i!=shape.end()) && (*i==v)) { j++; }
	if (j>k) {
	  k=j;
	  value=v;
	}
      }
    }

    // Build the subshape

    L subshape(shape.size()-k);
    std::remove_copy(shape.begin(),shape.end(),
		     subshape.begin(),
		     value);

    // For each binary canonic list, build the canonics lists
    // obtained by replacing the false by value, and the trues
    // by the values of the subshape
    list<BinaryList> bcls=canonics(shape.size()-k);
    for(list<BinaryList>::const_iterator ibcls=bcls.begin();
	ibcls!=bcls.end();
	ibcls++) {
      BinaryList bcl(*ibcls);
      PermutationGroup g=weight_automorphism_group(bcl,true);
      list<L> subcanonics=g.canonics_shape(subshape);
      for(typename list<L>::const_iterator j=subcanonics.begin();
	  j !=subcanonics.end(); j++) {
	L l2(shape.size());
	L sublist(*j);
	typename L::const_iterator isublist=sublist.begin();
	for(Lsize_type i=0; i<shape.size(); i++) {
	  if (bcl[i]) {
	    l2[i]=*isublist;
	    isublist++;
	  } else {
	    l2[i]=value;
	  }
	}
	result.push_back(l2);
      }
    }
    return result;	
  }

  template <class In>
  PermutationGroup closure(In first, In last) {

    assert(first!=last);

    queue<Permutation> todo;
    set  <Permutation> group;
    PermutationGroup   pgroup(first->size());

    Permutation id=Permutation::id(first->size());
    todo . push     (id);
    group. insert   (id);
    pgroup.push_back(id);

    while(!todo.empty()) {
      for(In ig=first; ig!=last; ig++) {
	Permutation p2=todo.front()*(*ig);
	if (group.find(p2)==group.end()) {
	  group. insert(p2);
	  pgroup.push_back(p2);
	  todo.  push  (p2);
	}
      }
      todo.pop();
    }
    return pgroup;
  }
}	// End of namespace PermutationGroup

#endif	/* GLIP_PERMUTATION_GROUP_TMPL_H */

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