group.h

#pragma once

#include <iostream>
#include <vector>
#include <memory>
#include <set>
#include <deque>

class _Group;
class Subgroup;
typedef std::shared_ptr<const _Group> Group;

#include "permutation.h"
#include "coset.h"
#include "fhl.h"

class _Group: public std::enable_shared_from_this<const _Group> {
public:
	// checks whether the group contains the given permutation
	virtual bool contains( const Permutation& ) const = 0;

	// computes the degree of the group
	virtual int degree() const = 0;

	// computes the order of the group
	virtual __int128_t order() const = 0;

	// returns a copy of a list of generators for the group
	virtual std::vector<Permutation> generators() const = 0;

	// returns the group generated by this group and the generators
	virtual Group join( std::deque<Permutation>&& ) const = 0;

	// checks whether the group is the complete alternating or symmetric group
	virtual bool isGiant() const = 0;

	// returns a shared pointer to this group
	Group share() const;

	// returns the trivial permutation in this group
	Permutation one() const;

	// returns the point-wise stabiliser of x 
	Group stabilizer( int x ) const;

	// checks whether the group has H as subgroup
	bool hasSubgroup( Group H ) const;

	// checks whether the group is equal to H
	bool equals( Group H ) const;

	// returns a vector containing {0,...,degree()-1}
	std::vector<int> domain() const;

	// destructor
	virtual ~_Group() = 0;

	// returns a vector of all left cosets of the quotient of this group with G
	std::vector<Coset> allCosets( Group G ) const;
};

class Subgroup: public _Group {
	Group _supergroup;
	std::vector<Permutation> _generators;
	mutable FHL<Permutation> _fhl;
public:
	// returns a shared reference to the group this group is a subgroup of
	Group supergroup() const;

	virtual bool contains( const Permutation& ) const;
	virtual int degree() const;
	virtual __int128_t order() const;
	virtual std::vector<Permutation> generators() const;
	virtual Group join( std::deque<Permutation>&& ) const;
	virtual bool isGiant() const;

	// construct a subgroup generated by permutations S of G
	Subgroup( Group G, std::vector<Permutation> S );

	// construct a subgroup containing all permutations of G for which f returns true
	// WARNING: it is undefined behaviour when f does not describe a group
	Subgroup( Group G, std::function<bool(Permutation)> f );

	virtual ~Subgroup();
};

class SymmetricGroup: public _Group {
	int _degree;
public:
	virtual bool contains( const Permutation& ) const;
	virtual int degree() const;
	virtual __int128_t order() const;
	virtual std::vector<Permutation> generators() const;
	virtual Group join( std::deque<Permutation>&& ) const;
	virtual bool isGiant() const;

	// construct a symmetric group on the elements {0,...,n-1}
	SymmetricGroup( int n );
	
	virtual ~SymmetricGroup();
};