permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/search/partition/partition.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 PARTITION_H_
00034 #define PARTITION_H_
00035 
00036 #include <algorithm>
00037 #include <list>
00038 #include <boost/foreach.hpp>
00039 #include <boost/dynamic_bitset.hpp>
00040 
00041 namespace permlib {
00042 namespace partition {
00043         
00044 template<class T>
00045 class BacktrackRefinement;
00046 
00048 class Partition {
00049 public:
00051         explicit Partition(unsigned long n);
00052         
00054 
00061         template<class ForwardIterator>
00062         bool intersect(ForwardIterator begin, ForwardIterator end, unsigned int j);
00064         bool undoIntersection();
00065 
00068         template<class ForwardIterator>
00069         bool intersects(ForwardIterator begin, ForwardIterator end, unsigned int j) const;
00070         
00071         typedef std::vector<unsigned int> vector_t;
00073         unsigned int fixPointsSize() const;
00075         vector_t::const_iterator fixPointsBegin() const;
00077         vector_t::const_iterator fixPointsEnd() const;
00079         unsigned long cells() const;
00081         unsigned long cellSize(unsigned int c) const;
00082         
00083         typedef vector_t::const_iterator CellIt;
00084         
00085         CellIt cellBegin(unsigned long cell) const { 
00086                 BOOST_ASSERT(cell < cells());
00087                 return partition.begin() + partitionCellBorder[cell];
00088         }
00089         
00090         CellIt cellEnd(unsigned long cell) const { 
00091                 BOOST_ASSERT(cell < cells());
00092                 return partition.begin() + partitionCellBorder[cell] + partitionCellLength[cell];
00093         }
00094 private:
00095         explicit Partition(unsigned long n, bool);
00096         
00097         vector_t partition;
00098         vector_t partitionCellBorder;
00099         vector_t partitionCellLength;
00100         vector_t partitionCellOf;
00102         vector_t m_newCell;
00103         
00105         unsigned int cellCounter;
00106         
00109         vector_t fix;
00111         unsigned int fixCounter;
00112         
00113         friend std::ostream& operator<<(std::ostream& out, const Partition& p);
00114         
00115         template<class T>
00116         friend class BacktrackRefinement;
00117 };
00118 
00119 inline std::ostream& operator<<(std::ostream& out, const Partition& p) {
00120         out << "[";
00121         Partition::vector_t::const_iterator border = p.partitionCellBorder.begin();
00122         Partition::vector_t::const_iterator length = p.partitionCellLength.begin();
00123         for (unsigned int j = 0; j < p.cellCounter; ++j) {
00124                 for (unsigned int i = *border; i < *border + *length; ++i) {
00125                         out << (p.partition[i] + 1) << " ";
00126                 }
00127                 out << "| ";
00128                 ++border;
00129                 ++length;
00130         }       
00131         out << "]|(";
00132         int countFix = p.fixCounter;
00133         BOOST_FOREACH(unsigned long alpha, p.fix) {
00134                 if (--countFix < 0)
00135                         break;
00136                 out << (alpha+1) << ",";
00137         }
00138         out << ")";
00139         return out;
00140 }
00141 
00142 inline Partition::Partition(unsigned long n) 
00143         : partition(n), partitionCellBorder(n), partitionCellLength(n), partitionCellOf(n), m_newCell(n), cellCounter(1), fix(n), fixCounter(0)
00144 {
00145         for (unsigned int i=0; i<n; ++i) {
00146                 partition[i] = i;
00147                 // partitionCellOf is already zero
00148         }
00149         partitionCellBorder[0] = 0;
00150         partitionCellLength[0] = n;
00151 }
00152 
00153 inline Partition::Partition(unsigned long n, bool) 
00154         : partition(n), partitionCellBorder(n), partitionCellLength(n), partitionCellOf(n), m_newCell(n), cellCounter(0), fix(n), fixCounter(0)
00155 { }
00156 
00157 inline unsigned long Partition::cells() const {
00158         return cellCounter;
00159 }
00160 
00161 inline unsigned int Partition::fixPointsSize() const {
00162         return fixCounter;
00163 }
00164 inline Partition::vector_t::const_iterator Partition::fixPointsBegin() const {
00165         return fix.begin();
00166 }
00167 inline Partition::vector_t::const_iterator Partition::fixPointsEnd() const {
00168         return fix.begin() + fixCounter;
00169 }
00170 inline unsigned long Partition::cellSize(unsigned int c) const {
00171         return partitionCellLength[c]; 
00172 }
00173 
00174 template<class ForwardIterator>
00175 inline bool Partition::intersects(ForwardIterator begin, ForwardIterator end, unsigned int j) const {
00176         while (begin != end) {
00177                 //std::cout << " B " << *begin << " < " << partitionCellOf[*begin] << " < " << j << std::endl;
00178                 if (partitionCellOf[*begin++] == j)
00179                         return true;
00180         }
00181         return false;
00182 }
00183 
00185 template<class ForwardIterator>
00186 inline bool Partition::intersect(ForwardIterator otherCellBegin, ForwardIterator otherCellEnd, unsigned int j) {
00187         if (!intersects(otherCellBegin, otherCellEnd, j))
00188                 return false;
00189         
00190         vector_t& newCell = m_newCell;
00191         
00192         ForwardIterator otherCellIt = otherCellBegin;
00193         vector_t::iterator cellIt;
00194         vector_t::reverse_iterator newCellIt;
00195         vector_t::reverse_iterator newCellBeginIt;
00196         vector_t::iterator newCell2It;
00197         vector_t::iterator borderIt;
00198         bool createdNewCell = false;
00199         const unsigned int partitionCellSize = partitionCellLength[j];
00200         if (j >= cellCounter)
00201                 return false;
00202         if (partitionCellSize <= 1)
00203                 return false;
00204         vector_t::iterator cellBeginIt = partition.begin() + partitionCellBorder[j];
00205         vector_t::iterator cellEndIt   = partition.begin() + (partitionCellBorder[j] + partitionCellLength[j]);
00206         //print_iterable(cellBeginIt, cellEndIt, 1, " ^ cell");
00207         newCellBeginIt  = newCell.rbegin() + (partition.size() - partitionCellSize);
00208         newCellIt       = newCellBeginIt;
00209         newCell2It      = newCell.begin();
00210         unsigned int newCellCounter = 0;
00211         
00212         for (cellIt = cellBeginIt; cellIt != cellEndIt; ++cellIt) {
00213                 while (otherCellIt != otherCellEnd && *otherCellIt < *cellIt) {
00214                         ++otherCellIt;
00215                 }
00216                 if (otherCellIt != otherCellEnd && *cellIt == *otherCellIt) {
00217                         *newCell2It = *cellIt;
00218                         ++newCell2It;
00219                         if (newCellCounter == 0) {
00220                                 /*std::cout << "copy into new cell ";
00221                                 print_iterable(partition.begin() + borderLo, cellIt, 1);
00222                                 std::cout << std::endl;*/
00223                                 newCellIt = std::copy(cellBeginIt, cellIt, newCellIt);
00224                         }
00225                         ++newCellCounter;
00226                 } else if (newCellCounter) {
00227                         *newCellIt = *cellIt;
00228                         ++newCellIt;
00229                 }
00230         }
00231         
00232         if (newCellCounter > 0 && newCellCounter < partitionCellSize) {
00233                 std::reverse(newCellBeginIt, newCellIt);
00234                 std::copy(newCell.begin(), newCell.begin() + partitionCellSize, cellBeginIt);
00235                 /*std::cout << "new cell[" << partitionCellSize << "] = ";
00236                 print_iterable(newCell.begin(), newCell.begin() + partitionCellSize, 1);
00237                 std::cout << std::endl;*/
00238                 vector_t::iterator fixIt = fix.begin() + fixCounter;
00239                 
00240                 if (newCellCounter == 1) {
00241                         *fixIt = newCell[0];
00242                         ++fixIt;
00243                         ++fixCounter;
00244                 }
00245                 if (newCellCounter == partitionCellSize - 1) {
00246                         *fixIt = newCell[partitionCellSize - 1];
00247                         ++fixIt;
00248                         ++fixCounter;
00249                 }
00250                 
00251                 /*
00252                 for (unsigned int i = partitionCellBorder[j]; i < partitionCellBorder[j] + partitionCellLength[j]; ++i) {
00253                         std::cout << partition[i]+1 << " ";
00254                 }
00255                 std::cout << std::endl;
00256                 std::cout << "new cell counter " << newCellCounter << std::endl;
00257                 */
00258                 
00259                 partitionCellLength[j] = newCellCounter;
00260                 
00261                 //std::cout << "cellCounter " << cellCounter << std::endl;
00262                 partitionCellBorder[cellCounter] = partitionCellBorder[j] + newCellCounter;
00263                 partitionCellLength[cellCounter] = partitionCellSize - newCellCounter;
00264                 for (unsigned int i = partitionCellBorder[cellCounter]; i < partitionCellBorder[j] + partitionCellSize; ++i) {
00265                         BOOST_ASSERT( i < partition.size() );
00266                         BOOST_ASSERT( partition[i] < partitionCellOf.size() );
00267                         partitionCellOf[partition[i]] = cellCounter;
00268                 }
00269                 ++cellCounter;
00270                 
00271                 createdNewCell = true;
00272         }
00273                 
00274         return createdNewCell;
00275 }
00276 
00277 inline bool Partition::undoIntersection() {
00278         if (partitionCellBorder[cellCounter-1] < 1)
00279                 return false;
00280         --cellCounter;
00281         unsigned int splitFromCellNumber = partitionCellOf[ partition[partitionCellBorder[cellCounter] - 1] ];
00282         
00283         BOOST_ASSERT(partitionCellBorder[splitFromCellNumber] < partitionCellBorder[cellCounter]);
00284         BOOST_ASSERT(partitionCellLength[cellCounter] > 0 );
00285         //std::cout << "split from " << splitFromCellNumber << std::endl;
00286         //std::cout << "merge " << partitionCellBorder[splitFromCellNumber] << " " << partitionCellBorder[cellCounter] << " " << (partitionCellBorder[cellCounter] + partitionCellLength[cellCounter]) << std::endl;
00287         
00288         for (unsigned int i=partitionCellBorder[cellCounter]; i<partitionCellBorder[cellCounter] + partitionCellLength[cellCounter]; ++i) {
00289                 partitionCellOf[partition[i]] = splitFromCellNumber;
00290         }
00291         std::inplace_merge(partition.begin() + partitionCellBorder[splitFromCellNumber],
00292                                            partition.begin() + partitionCellBorder[cellCounter],
00293                                            partition.begin() + (partitionCellBorder[cellCounter] + partitionCellLength[cellCounter]));
00294         
00295         
00296         if (partitionCellLength[cellCounter] == 1) {
00297                 --fixCounter;
00298                 fix[fixCounter] = 0;
00299         }
00300         if (partitionCellLength[splitFromCellNumber] == 1) {
00301                 --fixCounter;
00302                 fix[fixCounter] = 0;
00303         }
00304         
00305         partitionCellLength[splitFromCellNumber] += partitionCellLength[cellCounter];
00306         
00307         partitionCellLength[cellCounter] = 0;
00308         partitionCellBorder[cellCounter] = 0;
00309         
00310         return true;
00311 }
00312 
00313 }
00314 }
00315 
00316 #endif // -- PARTITION_H_