permlib 0.2.9
Library for permutation computations
Loading...
Searching...
No Matches
abstract_bsgs_helpers.h
1// ---------------------------------------------------------------------------
2//
3// This file is part of PermLib.
4//
5// Copyright (c) 2009-2012 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#include <boost/scoped_ptr.hpp>
33#include <algorithm>
34#include <vector>
35#include <set>
36
37#ifndef ABSTRACT_BSGS_HELPERS_H_
38#define ABSTRACT_BSGS_HELPERS_H_
39
40namespace permlib {
41namespace helpers {
42
45public:
47 virtual ~SupportRestriction() { }
48
52 virtual bool canBeIgnored() const = 0;
56 virtual const std::vector<dom_int>* set() const = 0;
57};
58
61public:
66 BaseSupportRestriction(const boost::shared_ptr<std::set<dom_int> >& support, const std::vector<dom_int>& s)
67 : m_support(support), m_originalSet(s) {}
68
72 virtual bool canBeIgnored() const { return false; }
76 virtual const std::vector<dom_int>* set() const { return &m_originalSet; }
77protected:
78 const boost::shared_ptr<std::set<dom_int> > m_support;
79 const std::vector<dom_int>& m_originalSet;
80};
81
84public:
89 ReducedSupportRestriction(const boost::shared_ptr<std::set<dom_int> >& support, const std::vector<dom_int>& s)
90 : BaseSupportRestriction(support, s) {}
91
95 virtual bool canBeIgnored() const {
96 BOOST_ASSERT( m_support );
97 return std::find_first_of(m_support->begin(), m_support->end(), m_originalSet.begin(), m_originalSet.end()) == m_support->end();
98 }
99};
100
103public:
108 FullSupportRestriction(const boost::shared_ptr<std::set<dom_int> >& support, const std::vector<dom_int>& s)
109 : BaseSupportRestriction(support, s), m_reducedSet(0)
110 {
111 m_reducedSet = new std::vector<dom_int>();
112 m_reducedSet->reserve(s.size());
113 std::vector<dom_int> sorted(s);
114 std::sort(sorted.begin(), sorted.end());
115 std::set_intersection(m_support->begin(), m_support->end(), sorted.begin(), sorted.end(), std::back_inserter(*m_reducedSet));
116 }
117 virtual ~FullSupportRestriction() { delete m_reducedSet; }
118
122 bool canBeIgnored() const {
123 BOOST_ASSERT( m_reducedSet );
124 return m_reducedSet->empty();
125 }
129 const std::vector<dom_int>* set() const {
130 return m_reducedSet;
131 }
132private:
133 std::vector<dom_int>* m_reducedSet;
134};
135
136} // end NS permlib::helpers
137} // end NS permlib
138
139#endif
This class never imposes a restriction on any set.
Definition abstract_bsgs_helpers.h:60
BaseSupportRestriction(const boost::shared_ptr< std::set< dom_int > > &support, const std::vector< dom_int > &s)
Definition abstract_bsgs_helpers.h:66
virtual const std::vector< dom_int > * set() const
Definition abstract_bsgs_helpers.h:76
virtual bool canBeIgnored() const
Definition abstract_bsgs_helpers.h:72
This class implements both canBeIgnored() and set()
Definition abstract_bsgs_helpers.h:102
const std::vector< dom_int > * set() const
Definition abstract_bsgs_helpers.h:129
bool canBeIgnored() const
Definition abstract_bsgs_helpers.h:122
FullSupportRestriction(const boost::shared_ptr< std::set< dom_int > > &support, const std::vector< dom_int > &s)
Definition abstract_bsgs_helpers.h:108
This class implements canBeIgnored() but has a trivial set()
Definition abstract_bsgs_helpers.h:83
virtual bool canBeIgnored() const
Definition abstract_bsgs_helpers.h:95
ReducedSupportRestriction(const boost::shared_ptr< std::set< dom_int > > &support, const std::vector< dom_int > &s)
Definition abstract_bsgs_helpers.h:89
helper class to decide when an permutation action on a set is trivial or can be reduced to a subset
Definition abstract_bsgs_helpers.h:44
virtual bool canBeIgnored() const =0
virtual const std::vector< dom_int > * set() const =0
virtual ~SupportRestriction()
destructor
Definition abstract_bsgs_helpers.h:47