permlib 0.2.9
Library for permutation computations
set_image_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 SETIMAGEREFINEMENT_H_
34#define SETIMAGEREFINEMENT_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
45namespace permlib {
46namespace partition {
47
50template<class PERM>
51class SetImageRefinement : public Refinement<PERM> {
52public:
54
61 template<class InputIterator>
62 SetImageRefinement(unsigned long n, InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg);
63
64 virtual unsigned int apply(Partition& pi) const;
65 virtual unsigned int apply2(Partition& pi, const PERM& t) const;
66
67 virtual bool init(Partition& pi);
68private:
69 std::vector<unsigned long> delta;
70 std::vector<unsigned long> gamma;
71};
72
73template<class PERM>
74template<class InputIterator>
75SetImageRefinement<PERM>::SetImageRefinement(unsigned long n, InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg)
76 : Refinement<PERM>(n, Default), delta(begin, end), gamma(beginImg, endImg)
77{
78 std::sort(delta.begin(), delta.end());
79 std::sort(gamma.begin(), gamma.end());
80}
81
82template<class PERM>
84 BOOST_ASSERT( this->initialized() );
85 unsigned int ret = 0;
86 BOOST_FOREACH(unsigned int cell, Refinement<PERM>::m_cellPairs) {
87 PERMLIB_DEBUG(std::cout << "apply set image1 " << cell << std::endl;)
88 if (pi.intersect(delta.begin(), delta.end(), cell))
89 ++ret;
90 }
91 return ret;
92}
93
94template<class PERM>
95unsigned int SetImageRefinement<PERM>::apply2(Partition& pi, const PERM& t) const {
96 BOOST_ASSERT( this->initialized() );
97 unsigned int ret = 0;
98 BOOST_FOREACH(unsigned int cell, Refinement<PERM>::m_cellPairs) {
99 PERMLIB_DEBUG(std::cout << "apply set image2 " << cell << std::endl;)
100 if (pi.intersect(gamma.begin(), gamma.end(), cell))
101 ++ret;
102 }
103 return ret;
104}
105
106template<class PERM>
108 for (unsigned int c = 0; c < pi.cells(); ++c) {
109 if (pi.intersect(delta.begin(), delta.end(), c))
111 }
112 if (!Refinement<PERM>::m_cellPairs.empty()) {
113 typename Refinement<PERM>::RefinementPtr ref(new SetImageRefinement<PERM>(*this));
115 return true;
116 }
117 return false;
118}
119
120}
121}
122
123#endif // -- SETIMAGEREFINEMENT_H_
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
base class for a -refinement which is used in an R-base and bound to an initial partition
Definition: refinement.h:53
Definition: set_image_refinement.h:51
virtual bool init(Partition &pi)
initializes refinement
Definition: set_image_refinement.h:107
SetImageRefinement(unsigned long n, InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg)
constructor
Definition: set_image_refinement.h:75
virtual unsigned int apply2(Partition &pi, const PERM &t) const
applies (right-)refinement to pi which is the image of the original partition this refinement was ini...
Definition: set_image_refinement.h:95
virtual unsigned int apply(Partition &pi) const
applies (left-)refinement to pi which is the original partition this refinement was initialized to
Definition: set_image_refinement.h:83