permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/test/group_type.h
00001 // ---------------------------------------------------------------------------
00002 //
00003 //  This file is part of PermLib.
00004 //
00005 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de>
00006 // All rights reserved.
00007 // 
00008 // Redistribution and use in source and binary forms, with or without
00009 // modification, are permitted provided that the following conditions
00010 // are met:
00011 // 1. Redistributions of source code must retain the above copyright
00012 //    notice, this list of conditions and the following disclaimer.
00013 // 2. Redistributions in binary form must reproduce the above copyright
00014 //    notice, this list of conditions and the following disclaimer in the
00015 //    documentation and/or other materials provided with the distribution.
00016 // 3. The name of the author may not be used to endorse or promote products
00017 //    derived from this software without specific prior written permission.
00018 // 
00019 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00020 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00021 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00022 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00023 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00024 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00028 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029 //
00030 // ---------------------------------------------------------------------------
00031 
00032 #ifndef GROUP_TYPE_H_
00033 #define GROUP_TYPE_H_
00034 
00035 #include <cstring>
00036 
00037 namespace permlib {
00038 
00040 class GroupType {
00041 public:
00043         enum Type {
00044                 None,
00045                 Trivial,
00046                 Named,
00047                 Anonymous,
00048                 WreathSymmetric,
00049                 DirectProduct
00050         };
00051         
00053         void writeToStream(std::ostream& o) const {
00054                 if (!m_naturalAction)
00055                         o << "ISO( ";
00056                 this->writeTypeToStream(o);
00057                 if (!m_naturalAction)
00058                         o << " , " << m_realDegree << " )";
00059         }
00060         
00062         unsigned int realDegree() const { return m_realDegree; }
00064 
00067         bool isNaturalAction() const { return m_naturalAction; }
00069         Type type() const { return m_type; }
00070         
00072         bool equals(const GroupType* type_) const {
00073                 if (this->m_type != type_->m_type)
00074                         return false;
00075                 if (this->m_realDegree != type_->m_realDegree)
00076                         return false;
00077                 if (this->m_naturalAction != type_->m_naturalAction)
00078                         return false;
00079                 return this->equalsType(type_);
00080         }
00081         
00083         void setNonNaturalAction(unsigned int realDegree_) {
00084                 m_realDegree = realDegree_;
00085                 m_naturalAction = false;
00086         }
00087         
00089         virtual ~GroupType() { }
00090 protected:
00092         Type m_type;
00094         unsigned int m_realDegree;
00096         bool m_naturalAction;
00097         
00099         GroupType(Type type_, unsigned int realDegree_, bool naturalAction) 
00100                 : m_type(type_), m_realDegree(realDegree_), m_naturalAction(naturalAction) { }
00101         
00103 
00107         virtual bool equalsType(const GroupType* type_) const { return false; }
00109         virtual void writeTypeToStream(std::ostream& o) const = 0;
00110 };
00111 
00112 
00114 class TrivialGroupType : public GroupType {
00115 public:
00119         TrivialGroupType(unsigned int realDegree_) : GroupType(Trivial, realDegree_, true) { }
00120         
00121         virtual void writeTypeToStream(std::ostream& o) const {
00122                 o << "Trivial(" << m_realDegree << ")";
00123         }
00124 protected:
00125         virtual bool equalsType(const GroupType* type_) const { return true; }
00126 };
00127 
00128 
00130 template<class IntegerType = boost::uint64_t>
00131 class AnonymousGroupType : public GroupType {
00132 public:
00137         AnonymousGroupType(unsigned int realDegree_, IntegerType order_ = 0)
00138                 : GroupType(Anonymous, realDegree_, true), m_order(order_) { }
00139         
00140         virtual void writeTypeToStream(std::ostream& o) const {
00141                 if (m_order)
00142                         o << "anonymous(" << m_realDegree << ", " << m_order << ")";
00143                 else
00144                         o << "anonymous(" << m_realDegree << ")";
00145         }
00146 protected:
00147         IntegerType m_order;
00148         
00149         virtual bool equalsType(const GroupType* type_) const { 
00150                 // we can never know if two anonymous groups are equal without digging deeper
00151                 return false;
00152         }
00153 };
00154 
00155 
00157 class NamedGroupType : public GroupType {
00158 public:
00159         virtual void writeTypeToStream(std::ostream& o) const {
00160                 o << m_name << "_" << m_typeDegree;
00161         }
00162         
00164         const char* name() const { return m_name; }
00166         unsigned int typeDegree() const { return m_typeDegree; }
00167 protected:
00168         const char* m_name;
00169         unsigned int m_typeDegree;
00170         
00176         NamedGroupType(const char* name_, unsigned int typeDegree_, unsigned int realDegree_)
00177                 : GroupType(Named, realDegree_, typeDegree_ == realDegree_), m_name(name_), m_typeDegree(typeDegree_) { }
00178         
00179         virtual bool equalsType(const GroupType* type_) const { 
00180                 const NamedGroupType* namedType = dynamic_cast<const NamedGroupType*>(type_);
00181                 return namedType->m_typeDegree == this->m_typeDegree && std::strcmp(namedType->m_name, this->m_name) == 0;
00182         }
00183 };
00184 
00185 
00187 class SymmetricGroupType : public NamedGroupType {
00188 public:
00193         SymmetricGroupType(unsigned int typeDegree_, unsigned int realDegree_)
00194                 : NamedGroupType("S", typeDegree_, realDegree_) { }
00195 };
00196 
00197 
00199 class AlternatingGroupType : public NamedGroupType {
00200 public:
00205         AlternatingGroupType(unsigned int typeDegree_, unsigned int realDegree_)
00206                 : NamedGroupType("A", typeDegree_, realDegree_) { }
00207 };
00208 
00209 
00211 class CyclicGroupType : public NamedGroupType {
00212 public:
00217         CyclicGroupType(unsigned int typeDegree_, unsigned int realDegree_)
00218                 : NamedGroupType("C", typeDegree_, realDegree_) { }
00219 };
00220 
00221 
00223 
00226 class WreathSymmetricGroupType : public GroupType {
00227 public:
00228         WreathSymmetricGroupType(unsigned int degreeG_, unsigned int degreeH_, unsigned int realDegree_)
00229                 : GroupType(WreathSymmetric, realDegree_, realDegree_ == degreeG_ * degreeH_), m_degreeG(degreeG_), m_degreeH(degreeH_) { }
00230         
00231         virtual void writeTypeToStream(std::ostream& o) const {
00232                 o << "S_" << m_degreeG << " wr S_" << m_degreeH;
00233         }
00234         
00235         unsigned int degreeG() const { return m_degreeG; }
00236         unsigned int degreeH() const { return m_degreeH; }
00237 protected:
00238         unsigned int m_degreeG;
00239         unsigned int m_degreeH;
00240         
00241         virtual bool equalsType(const GroupType* type_) const { 
00242                 const WreathSymmetricGroupType* wreathType = dynamic_cast<const WreathSymmetricGroupType*>(type_);
00243                 return wreathType->m_degreeG == m_degreeG && wreathType->m_degreeH == m_degreeH;
00244         }
00245 };
00246 
00248 class DirectProductGroupType : public GroupType {
00249 public:
00255         DirectProductGroupType(const GroupType* type1, const GroupType* type2, unsigned int realDegree_)
00256                 : GroupType(DirectProduct, realDegree_, realDegree_ == type1->realDegree() + type2->realDegree()), m_components(2) 
00257         { 
00258                 m_components[0] = GroupTypePtr(type1);
00259                 m_components[1] = GroupTypePtr(type2);
00260         }
00261         
00262         virtual void writeTypeToStream(std::ostream& o) const {
00263                 for (unsigned int i = 0; i < m_components.size(); ++i) {
00264                         if (i > 0)
00265                                 o << " x ";
00266                         m_components[i]->writeToStream(o);
00267                 }
00268         }
00269         
00270 protected:
00271         typedef boost::shared_ptr<const GroupType> GroupTypePtr;
00272         std::vector<GroupTypePtr> m_components;
00273         
00274         virtual bool equalsType(const GroupType* type_) const { 
00275                 const DirectProductGroupType* directType = dynamic_cast<const DirectProductGroupType*>(type_);
00276                 if (m_components.size() != directType->m_components.size())
00277                         return false;
00278                 std::vector<GroupTypePtr>::const_iterator itMe = m_components.begin();
00279                 std::vector<GroupTypePtr>::const_iterator itOther = directType->m_components.begin();
00280                 while (itMe != m_components.end()) {
00281                         if ( ! (*itMe)->equals((*itOther).get()) )
00282                                 return false;
00283                         ++itMe;
00284                         ++itOther;
00285                 }
00286                 return true;
00287         }
00288 };
00289 
00290 }
00291 
00292 #endif