permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/search/partition/backtrack_refinement.h
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 BACKTRACKREFINEMENT_H_
00034 #define BACKTRACKREFINEMENT_H_
00035 
00036 #include <permlib/search/partition/refinement.h>
00037 
00038 #include <list>
00039 
00040 namespace permlib {
00041 namespace partition {
00042         
00044 template<class PERM>
00045 class BacktrackRefinement : public Refinement<PERM> {
00046 public:
00048         explicit BacktrackRefinement(unsigned long n);
00050 
00054         BacktrackRefinement(unsigned long n, unsigned long alpha);
00055         
00056         virtual unsigned int apply(Partition& pi) const;
00057         
00059         unsigned long alpha() const;
00060         virtual void sort(const BaseSorterByReference& sorter, const Partition* pi);
00061 protected:
00062         virtual bool init(Partition& pi);
00063 private:
00064         unsigned long m_alpha;
00065         unsigned int m_cellElementIndex;
00066         unsigned int m_cellIndex;
00067         
00068         typedef typename Refinement<PERM>::RefinementPtr RefinementPtr;
00069         
00070         struct RefinementSorter : public std::binary_function<RefinementPtr, RefinementPtr, bool> {
00071                 RefinementSorter(const BaseSorterByReference& sorter, const Partition* pi) : m_sorter(sorter), m_pi(pi) {}
00072                 
00073                 bool operator()(RefinementPtr a, RefinementPtr b) const {
00074                         BacktrackRefinement<PERM>* backtrackA = static_cast<BacktrackRefinement<PERM>*>(a.get());
00075                         BacktrackRefinement<PERM>* backtrackB = static_cast<BacktrackRefinement<PERM>*>(b.get());
00076                         if (m_pi) {
00077                                 return m_sorter(m_pi->partition[backtrackA->m_cellElementIndex], m_pi->partition[backtrackB->m_cellElementIndex]);
00078                         }
00079                         return m_sorter(backtrackA->m_alpha, backtrackB->m_alpha);
00080                 }
00081         private:
00082                 const BaseSorterByReference& m_sorter;
00083                 const Partition* m_pi;
00084         };
00085         
00086         static const unsigned int overrideAlphaChoiceCellSizeRatio = 8;
00087 };
00088 
00089 template<class PERM>
00090 BacktrackRefinement<PERM>::BacktrackRefinement(unsigned long n) 
00091         : Refinement<PERM>(n, Backtrack), m_alpha(-1), m_cellElementIndex(-1), m_cellIndex(-1)
00092 { }
00093 
00094 template<class PERM>
00095 BacktrackRefinement<PERM>::BacktrackRefinement(unsigned long n, unsigned long alpha_) 
00096         : Refinement<PERM>(n, Backtrack), m_alpha(alpha_), m_cellElementIndex(-1), m_cellIndex(-1)
00097 { }
00098 
00099 template<class PERM>
00100 unsigned int BacktrackRefinement<PERM>::apply(Partition& pi) const {
00101         unsigned long singleCell[1];
00102         singleCell[0] = pi.partition[m_cellElementIndex];  
00103         //singleCell[0] = t / m_alpha;
00104         //print_iterable(pi.partition.begin(), pi.partition.end(), 0, " partition pi");
00105         PERMLIB_DEBUG(std::cout << " apply bt ref   alpha =" << m_alpha << ", single cell = " << singleCell[0] << " @ " << m_cellIndex << "," << m_cellElementIndex << std::endl;)
00106         return pi.intersect(singleCell, singleCell+1, m_cellIndex);
00107 }
00108 
00109 template<class PERM>
00110 unsigned long BacktrackRefinement<PERM>::alpha() const {
00111         return m_alpha;
00112 }
00113 
00114 template<class PERM>
00115 void BacktrackRefinement<PERM>::sort(const BaseSorterByReference& sorter, const Partition* pi) {
00116         std::sort(Refinement<PERM>::m_backtrackRefinements.begin(), Refinement<PERM>::m_backtrackRefinements.end(), RefinementSorter(sorter, pi));
00117 }
00118 
00119 template<class PERM>
00120 bool BacktrackRefinement<PERM>::init(Partition& pi) {
00121         unsigned int minCellSize = pi.partition.size();
00122         unsigned int minCell = 0;
00123         //std::cout << "m_alpha " << m_alpha << std::endl;
00124         
00125         std::vector<unsigned int>::const_iterator length = pi.partitionCellLength.begin();
00126         for (unsigned int j = 0; j < pi.cellCounter; ++j) {
00127                 if (1 < *length && *length < minCellSize) {
00128                         minCellSize = *length;
00129                         minCell = j;
00130                 }
00131                 ++length;
00132         }
00133         if (m_alpha == static_cast<unsigned long>(-1)) {
00134                 this->m_cellElementIndex = pi.partitionCellBorder[minCell];
00135                 this->m_alpha = pi.partition[pi.partitionCellBorder[minCell]];
00136         } else {
00137                 const unsigned int givenMinCell = pi.partitionCellOf[m_alpha];
00138                 const unsigned int givenMinCellSize = pi.partitionCellLength[givenMinCell];
00139                 if (1 < givenMinCellSize && givenMinCellSize <= overrideAlphaChoiceCellSizeRatio * minCellSize) {
00140                         minCell = givenMinCell;
00141                         minCellSize = givenMinCellSize;
00142                         for (unsigned int j = pi.partitionCellBorder[minCell]; j < pi.partitionCellBorder[minCell] + pi.partitionCellLength[minCell]; ++j) {
00143                                 if (pi.partition[j] == m_alpha) {
00144                                         this->m_cellElementIndex = j;
00145                                         break;
00146                                 }
00147                         }
00148                 } else {
00149                         this->m_cellElementIndex = pi.partitionCellBorder[minCell];
00150                         this->m_alpha = pi.partition[pi.partitionCellBorder[minCell]];
00151                 }
00152         }
00153         PERMLIB_DEBUG(std::cout << "minCellSize = " << minCellSize << std::endl;)
00154 
00155         this->m_cellIndex = minCell;
00156                 
00157         Refinement<PERM>::m_backtrackRefinements.reserve(minCellSize);
00158         for (unsigned int i = pi.partitionCellBorder[minCell]; i < pi.partitionCellBorder[minCell] + minCellSize; ++i) {
00159                 BacktrackRefinement<PERM>* br = new BacktrackRefinement<PERM>(Refinement<PERM>::m_n);
00160                 br->m_cellElementIndex = i;
00161                 br->m_cellIndex = minCell;
00162                 br->m_alpha = pi.partition[i];
00163                 //print_iterable(pi.partition.begin(), pi.partition.end(), 0, " partition pi");
00164                 PERMLIB_DEBUG(std::cout << "PREP bt alpha " << br->m_alpha << " @ " << br->m_cellIndex << " // " << br->m_cellElementIndex << std::endl;)
00165                 typename Refinement<PERM>::RefinementPtr ref(br);
00166                 Refinement<PERM>::m_backtrackRefinements.push_back(ref);
00167         }
00168         
00169         unsigned long singleCell[1];
00170         singleCell[0] = this->m_alpha;
00171         //TODO: write special case function to handle singleCell intersection
00172         const bool inter __attribute__((unused)) = pi.intersect(singleCell, singleCell+1, m_cellIndex);
00173         BOOST_ASSERT(inter);
00174         
00175         return true;
00176 }
00177 
00178 }
00179 }
00180 
00181 #endif // -- BACKTRACKREFINEMENT_H_