1 // --------------------------------------------------------------------------- 2 // 3 // This file is part of PermLib. 4 // 5 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de> 6 // All rights reserved. 7 // 8 // Redistribution and use in source and binary forms, with or without 9 // modification, are permitted provided that the following conditions 10 // are met: 11 // 1. Redistributions of source code must retain the above copyright 12 // notice, this list of conditions and the following disclaimer. 13 // 2. Redistributions in binary form must reproduce the above copyright 14 // notice, this list of conditions and the following disclaimer in the 15 // documentation and/or other materials provided with the distribution. 16 // 3. The name of the author may not be used to endorse or promote products 17 // derived from this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 21 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 22 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 23 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 24 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 28 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 // 30 // --------------------------------------------------------------------------- 31 32 33 #ifndef REDUNDANT_BASE_POINT_INSERTION_STRATEGY_H_ 34 #define REDUNDANT_BASE_POINT_INSERTION_STRATEGY_H_ 35 36 namespace permlib { 37 38 template <class PERM, class TRANS> 39 struct BSGS; 40 41 /// strategy for redundant base point insertion 42 template <class PERM, class TRANS> 43 class RedundantBasePointInsertionStrategy { 44 public: 45 /// constructor 46 /** 47 * @param bsgs BSGS to work on 48 */ RedundantBasePointInsertionStrategy(const BSGS<PERM,TRANS> & bsgs)49 RedundantBasePointInsertionStrategy(const BSGS<PERM,TRANS> &bsgs) : m_bsgs(bsgs) {} 50 51 // virtual destructor ~RedundantBasePointInsertionStrategy()52 virtual ~RedundantBasePointInsertionStrategy() {} 53 54 /// finds possible insertion point for base point 55 /** 56 * @param beta base point to be inserted 57 * @param S_i generators for i-th fundamental orbit where i is the insert position found 58 * @return insert position; if negative then beta is already base point at position -$retVal-1 59 */ 60 virtual int findInsertionPoint(dom_int beta, std::list<typename PERM::ptr> &S_i) const = 0; 61 protected: 62 /// BSGS to work on 63 const BSGS<PERM,TRANS> &m_bsgs; 64 }; 65 66 /// insertion position after first non-trivial transversal 67 template <class PERM, class TRANS> 68 class TrivialRedundantBasePointInsertionStrategy : public RedundantBasePointInsertionStrategy<PERM,TRANS> { 69 public: 70 /// constructor TrivialRedundantBasePointInsertionStrategy(const BSGS<PERM,TRANS> & bsgs)71 TrivialRedundantBasePointInsertionStrategy(const BSGS<PERM,TRANS> &bsgs) : RedundantBasePointInsertionStrategy<PERM,TRANS>(bsgs) {} 72 findInsertionPoint(dom_int beta,std::list<typename PERM::ptr> & S_i)73 virtual int findInsertionPoint(dom_int beta, std::list<typename PERM::ptr> &S_i) const { 74 const std::vector<dom_int> &B = RedundantBasePointInsertionStrategy<PERM,TRANS>::m_bsgs.B; 75 const std::vector<TRANS> &U = RedundantBasePointInsertionStrategy<PERM,TRANS>::m_bsgs.U; 76 for (unsigned int i=0; i<B.size(); ++i) { 77 if (beta == B[i]) 78 return -i-1; 79 } 80 int pos = B.size(); 81 while (pos > 0 && U[pos-1].size() == 1) 82 --pos; 83 return pos; 84 } 85 }; 86 87 /// insertion position at first position i such that \f$G^{[i]}\f$ stabilizes beta 88 template <class PERM, class TRANS> 89 class FirstRedundantBasePointInsertionStrategy : public RedundantBasePointInsertionStrategy<PERM,TRANS> { 90 public: 91 /// constructor FirstRedundantBasePointInsertionStrategy(const BSGS<PERM,TRANS> & bsgs)92 FirstRedundantBasePointInsertionStrategy(const BSGS<PERM,TRANS> &bsgs) : RedundantBasePointInsertionStrategy<PERM,TRANS>(bsgs) {} 93 findInsertionPoint(dom_int beta,std::list<typename PERM::ptr> & S_i)94 virtual int findInsertionPoint(dom_int beta, std::list<typename PERM::ptr> &S_i) const { 95 const std::vector<dom_int> &B = RedundantBasePointInsertionStrategy<PERM,TRANS>::m_bsgs.B; 96 const std::list<typename PERM::ptr> &S = RedundantBasePointInsertionStrategy<PERM,TRANS>::m_bsgs.S; 97 typename std::vector<dom_int>::const_iterator bIt = B.begin(); 98 int pos = B.size(); 99 for (unsigned int i=0; i<B.size(); ++i) { 100 if (beta == B[i]) 101 return -i-1; 102 103 ++bIt; 104 const PointwiseStabilizerPredicate<PERM> stab_i(B.begin(), bIt); 105 S_i.clear(); 106 107 //TODO: don't create temporary copy 108 // place directly into predicate 109 std::copy_if(S.begin(), S.end(), std::back_inserter(S_i), stab_i); 110 111 StabilizesPointPredicate<PERM> stab_beta(S_i.begin(), S_i.end()); 112 if (stab_beta(beta)) { 113 pos = i+1; 114 break; 115 } 116 } 117 return pos; 118 } 119 }; 120 121 } 122 123 #endif // -- REDUNDANT_BASE_POINT_INSERTION_STRATEGY_H_ 124