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
45namespace permlib {
46namespace partition {
47
49template<class PERM>
50class SetStabilizeRefinement : public Refinement<PERM> {
51public:
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);
59private:
60 std::vector<unsigned long> toStab;
61};
62
63template<class PERM>
64template<class InputIterator>
65SetStabilizeRefinement<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
72template<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
84template<class PERM>
86 for (unsigned int c = 0; c < pi.cells(); ++c) {
87 if (pi.intersect(toStab.begin(), toStab.end(), 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_
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
concrete -refinements for set stabilization
Definition: set_stabilize_refinement.h:50
virtual bool init(Partition &pi)
initializes refinement
Definition: set_stabilize_refinement.h:85
SetStabilizeRefinement(unsigned long n, InputIterator begin, InputIterator end)
constructor
Definition: set_stabilize_refinement.h:65
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