permlib  0.2.9
Library for permutation computations
redundant_base_point_insertion_strategy.h
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 
42 template <class PERM, class TRANS>
44 public:
46 
50 
51  // virtual destructor
53 
55 
60  virtual int findInsertionPoint(dom_int beta, std::list<typename PERM::ptr> &S_i) const = 0;
61 protected:
64 };
65 
67 template <class PERM, class TRANS>
69 public:
72 
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 
88 template <class PERM, class TRANS>
90 public:
93 
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_
predicate matching points that are stabilized by given permutations
Definition: stabilizes_point_predicate.h:42
insertion position after first non-trivial transversal
Definition: redundant_base_point_insertion_strategy.h:68
TrivialRedundantBasePointInsertionStrategy(const BSGS< PERM, TRANS > &bsgs)
constructor
Definition: redundant_base_point_insertion_strategy.h:71
virtual int findInsertionPoint(dom_int beta, std::list< typename PERM::ptr > &S_i) const
finds possible insertion point for base point
Definition: redundant_base_point_insertion_strategy.h:94
predicate matching a permutation if it stabilizes a given list of points pointwise ...
Definition: pointwise_stabilizer_predicate.h:42
insertion position at first position i such that stabilizes beta
Definition: redundant_base_point_insertion_strategy.h:89
const BSGS< PERM, TRANS > & m_bsgs
BSGS to work on.
Definition: redundant_base_point_insertion_strategy.h:63
strategy for redundant base point insertion
Definition: redundant_base_point_insertion_strategy.h:43
FirstRedundantBasePointInsertionStrategy(const BSGS< PERM, TRANS > &bsgs)
constructor
Definition: redundant_base_point_insertion_strategy.h:92
RedundantBasePointInsertionStrategy(const BSGS< PERM, TRANS > &bsgs)
constructor
Definition: redundant_base_point_insertion_strategy.h:49
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:58
virtual int findInsertionPoint(dom_int beta, std::list< typename PERM::ptr > &S_i) const
finds possible insertion point for base point
Definition: redundant_base_point_insertion_strategy.h:73
virtual int findInsertionPoint(dom_int beta, std::list< typename PERM::ptr > &S_i) const =0
finds possible insertion point for base point
Definition: abstract_bsgs.h:49