permlib  0.2.9
Library for permutation computations
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 
40 namespace permlib {
41 namespace helpers {
42 
45 public:
47  virtual ~SupportRestriction() { }
48 
52  virtual bool canBeIgnored() const = 0;
56  virtual const std::vector<dom_int>* set() const = 0;
57 };
58 
61 public:
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; }
77 protected:
78  const boost::shared_ptr<std::set<dom_int> > m_support;
79  const std::vector<dom_int>& m_originalSet;
80 };
81 
84 public:
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 
103 public:
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  }
132 private:
133  std::vector<dom_int>* m_reducedSet;
134 };
135 
136 } // end NS permlib::helpers
137 } // end NS permlib
138 
139 #endif
virtual bool canBeIgnored() const
Definition: abstract_bsgs_helpers.h:72
bool canBeIgnored() const
Definition: abstract_bsgs_helpers.h:122
virtual bool canBeIgnored() const =0
ReducedSupportRestriction(const boost::shared_ptr< std::set< dom_int > > &support, const std::vector< dom_int > &s)
Definition: abstract_bsgs_helpers.h:89
This class never imposes a restriction on any set.
Definition: abstract_bsgs_helpers.h:60
virtual bool canBeIgnored() const
Definition: abstract_bsgs_helpers.h:95
This class implements canBeIgnored() but has a trivial set()
Definition: abstract_bsgs_helpers.h:83
This class implements both canBeIgnored() and set()
Definition: abstract_bsgs_helpers.h:102
BaseSupportRestriction(const boost::shared_ptr< std::set< dom_int > > &support, const std::vector< dom_int > &s)
Definition: abstract_bsgs_helpers.h:66
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
FullSupportRestriction(const boost::shared_ptr< std::set< dom_int > > &support, const std::vector< dom_int > &s)
Definition: abstract_bsgs_helpers.h:108
Definition: abstract_bsgs.h:49
virtual ~SupportRestriction()
destructor
Definition: abstract_bsgs_helpers.h:47