permlib  0.2.9
Library for permutation computations
set_stabilize_refinement.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 SETSTABILIZEREFINEMENT_H_
34 #define SETSTABILIZEREFINEMENT_H_
35 
36 #include <permlib/predicate/pointwise_stabilizer_predicate.h>
37 
38 #include <permlib/search/partition/partition.h>
39 #include <permlib/search/partition/refinement.h>
40 
41 #include <algorithm>
42 #include <boost/dynamic_bitset.hpp>
43 #include <boost/foreach.hpp>
44 
45 namespace permlib {
46 namespace partition {
47 
49 template<class PERM>
50 class SetStabilizeRefinement : public Refinement<PERM> {
51 public:
53  template<class InputIterator>
54  SetStabilizeRefinement(unsigned long n, InputIterator begin, InputIterator end);
55 
56  virtual unsigned int apply(Partition& pi) const;
57 
58  virtual bool init(Partition& pi);
59 private:
60  std::vector<unsigned long> toStab;
61 };
62 
63 template<class PERM>
64 template<class InputIterator>
65 SetStabilizeRefinement<PERM>::SetStabilizeRefinement(unsigned long n, InputIterator begin, InputIterator end)
66  : Refinement<PERM>(n, Default), toStab(begin, end)
67 {
68  std::sort(toStab.begin(), toStab.end());
69  PERMLIB_DEBUG(print_iterable(toStab.begin(), toStab.end(), 0, "to stab");)
70 }
71 
72 template<class PERM>
74  BOOST_ASSERT( this->initialized() );
75  unsigned int ret = 0;
76  BOOST_FOREACH(unsigned int cell, Refinement<PERM>::m_cellPairs) {
77  PERMLIB_DEBUG(std::cout << "apply set stab " << cell << std::endl;)
78  if (pi.intersect(toStab.begin(), toStab.end(), cell))
79  ++ret;
80  }
81  return ret;
82 }
83 
84 template<class PERM>
86  for (unsigned int c = 0; c < pi.cells(); ++c) {
87  if (pi.intersect(toStab.begin(), toStab.end(), c))
88  Refinement<PERM>::m_cellPairs.push_back(c);
89  }
90  if (!Refinement<PERM>::m_cellPairs.empty()) {
91  typename Refinement<PERM>::RefinementPtr ref(new SetStabilizeRefinement<PERM>(*this));
93  return true;
94  }
95  return false;
96 }
97 
98 }
99 }
100 
101 #endif // -- SETSTABILIZEREFINEMENT_H_
concrete -refinements for set stabilization
Definition: set_stabilize_refinement.h:50
virtual unsigned int apply(Partition &pi) const
applies (left-)refinement to pi which is the original partition this refinement was initialized to ...
Definition: set_stabilize_refinement.h:73
base class for a -refinement which is used in an R-base and bound to an initial partition ...
Definition: refinement.h:53
virtual bool init(Partition &pi)
initializes refinement
Definition: set_stabilize_refinement.h:85
partition
Definition: partition.h:48
unsigned long cells() const
number of cells in this partition
Definition: partition.h:157
bool intersect(ForwardIterator begin, ForwardIterator end, unsigned int j)
intersects the j-th cell of this partition with a given set
Definition: partition.h:186
SetStabilizeRefinement(unsigned long n, InputIterator begin, InputIterator end)
constructor
Definition: set_stabilize_refinement.h:65
Definition: abstract_bsgs.h:49