permlib
0.2.6
Library for permutation computations
|
00001 // --------------------------------------------------------------------------- 00002 // 00003 // This file is part of PermLib. 00004 // 00005 // Copyright (c) 2009-2011 Thomas Rehn <thomas@carmen76.de> 00006 // All rights reserved. 00007 // 00008 // Redistribution and use in source and binary forms, with or without 00009 // modification, are permitted provided that the following conditions 00010 // are met: 00011 // 1. Redistributions of source code must retain the above copyright 00012 // notice, this list of conditions and the following disclaimer. 00013 // 2. Redistributions in binary form must reproduce the above copyright 00014 // notice, this list of conditions and the following disclaimer in the 00015 // documentation and/or other materials provided with the distribution. 00016 // 3. The name of the author may not be used to endorse or promote products 00017 // derived from this software without specific prior written permission. 00018 // 00019 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 00020 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 00021 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 00022 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 00023 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 00024 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 00025 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 00026 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 00027 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 00028 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00029 // 00030 // --------------------------------------------------------------------------- 00031 00032 00033 #ifndef REFINEMENT_H_ 00034 #define REFINEMENT_H_ 00035 00036 #include <vector> 00037 #include <boost/shared_ptr.hpp> 00038 00039 #include <permlib/search/partition/partition.h> 00040 00041 namespace permlib { 00042 namespace partition { 00043 00045 enum RefinementType { 00046 Default, 00047 Backtrack, 00048 Group 00049 }; 00050 00052 template<class PERM> 00053 class Refinement { 00054 public: 00056 Refinement(unsigned long n, RefinementType type); 00058 virtual ~Refinement(); 00059 00061 00064 bool initializeAndApply(Partition& pi); 00066 00071 virtual unsigned int apply(Partition& pi) const = 0; 00072 00074 00079 virtual unsigned int apply2(Partition& pi, const PERM& t) const; 00080 00082 void undo(Partition& pi, unsigned int count) const; 00083 00084 typedef typename boost::shared_ptr<Refinement<PERM> > RefinementPtr; 00085 typedef typename std::vector<RefinementPtr>::const_iterator RefinementPtrIterator; 00086 00088 RefinementType type() const; 00090 unsigned int alternatives() const; 00092 RefinementPtrIterator backtrackBegin() const { return m_backtrackRefinements.begin(); } 00094 RefinementPtrIterator backtrackEnd() const { return m_backtrackRefinements.end(); } 00095 00097 virtual bool init(Partition& pi) = 0; 00098 00100 virtual void sort(const BaseSorterByReference&, const Partition*) { } 00101 protected: 00103 unsigned long m_n; 00105 std::vector<RefinementPtr> m_backtrackRefinements; 00107 std::list<int> m_cellPairs; 00108 00110 bool initialized() const; 00111 private: 00112 bool m_initialized; 00113 RefinementType m_type; 00114 }; 00115 00116 template<class PERM> 00117 Refinement<PERM>::Refinement(unsigned long n_, RefinementType type_) 00118 : m_n(n_), m_initialized(false), m_type(type_) 00119 { } 00120 00121 template<class PERM> 00122 Refinement<PERM>::~Refinement() 00123 { } 00124 00125 template<class PERM> 00126 unsigned int Refinement<PERM>::alternatives() const { 00127 return m_backtrackRefinements.size(); 00128 } 00129 00130 template<class PERM> 00131 RefinementType Refinement<PERM>::type() const { 00132 return m_type; 00133 } 00134 00135 template<class PERM> 00136 bool Refinement<PERM>::initializeAndApply(Partition& pi) { 00137 if (!m_initialized) { 00138 m_initialized = true; 00139 return init(pi); 00140 } 00141 return false; 00142 } 00143 00144 template<class PERM> 00145 bool Refinement<PERM>::initialized() const { 00146 return m_initialized; 00147 } 00148 00149 template<class PERM> 00150 void Refinement<PERM>::undo(Partition& pi, unsigned int count) const { 00151 for (unsigned int i=0; i<count; ++i) 00152 pi.undoIntersection(); 00153 } 00154 00155 template<class PERM> 00156 unsigned int Refinement<PERM>::apply2(Partition& pi, const PERM& t) const { 00157 return this->apply(pi); 00158 } 00159 00160 } 00161 } 00162 00163 #endif // -- REFINEMENT_H_