permlib
0.2.6
Library for permutation computations
|
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