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
36namespace permlib {
37
38template <class PERM, class TRANS>
39struct BSGS;
40
42template <class PERM, class TRANS>
44public:
46
50
51 // virtual destructor
53
55
60 virtual int findInsertionPoint(dom_int beta, std::list<typename PERM::ptr> &S_i) const = 0;
61protected:
64};
65
67template <class PERM, class TRANS>
69public:
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
88template <class PERM, class TRANS>
90public:
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_
insertion position at first position i such that stabilizes beta
Definition: redundant_base_point_insertion_strategy.h:89
FirstRedundantBasePointInsertionStrategy(const BSGS< PERM, TRANS > &bsgs)
constructor
Definition: redundant_base_point_insertion_strategy.h:92
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
strategy for redundant base point insertion
Definition: redundant_base_point_insertion_strategy.h:43
virtual int findInsertionPoint(dom_int beta, std::list< typename PERM::ptr > &S_i) const =0
finds possible insertion point for base point
RedundantBasePointInsertionStrategy(const BSGS< PERM, TRANS > &bsgs)
constructor
Definition: redundant_base_point_insertion_strategy.h:49
const BSGS< PERM, TRANS > & m_bsgs
BSGS to work on.
Definition: redundant_base_point_insertion_strategy.h:63
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:73
OutputIterator copy_if(InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p)
copies elements of (begin to end) to destBegin if they match the given predicate
Definition: common.h:49
Represents a base and strong generating set (BSGS)
Definition: bsgs.h:89