permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/search/partition/set_image_search.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_SET_IMAGE_SEARCH_H_
00034 #define PARTITION_SET_IMAGE_SEARCH_H_
00035 
00036 #include <permlib/search/partition/r_base.h>
00037 #include <permlib/predicate/set_image_predicate.h>
00038 
00039 namespace permlib {
00040 namespace partition {
00041 
00043 
00046 template<class BSGSIN,class TRANSRET>
00047 class SetImageSearch : public RBase<BSGSIN,TRANSRET> {
00048 public:
00049         typedef typename RBase<BSGSIN,TRANSRET>::PERM PERM;
00050         
00052 
00056         SetImageSearch(const BSGSIN& bsgs, unsigned int pruningLevelDCM);
00057         
00059 
00065         template<class InputIterator>
00066         void construct(InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg);
00067 protected:
00068         virtual unsigned int processNewFixPoints(const Partition& pi, unsigned int backtrackCount);
00069 private:
00070         std::vector<unsigned long> toStab;
00071 };
00072 
00073 template<class BSGSIN,class TRANSRET>
00074 SetImageSearch<BSGSIN,TRANSRET>::SetImageSearch(const BSGSIN& bsgs, unsigned int pruningLevelDCM) 
00075         : RBase<BSGSIN,TRANSRET>(bsgs, pruningLevelDCM, true)
00076 { }
00077 
00078 template<class BSGSIN,class TRANSRET>
00079 template<class InputIterator>
00080 void SetImageSearch<BSGSIN,TRANSRET>::construct(InputIterator begin, InputIterator end, InputIterator beginImg, InputIterator endImg) {
00081         SetImagePredicate<PERM>* stabPred = new SetImagePredicate<PERM>(begin, end, beginImg, endImg);
00082         toStab.insert(toStab.begin(), begin, end);
00083         
00084         SetImageRefinement<PERM> sir(RBase<BSGSIN,TRANSRET>::m_bsgs.n, begin, end, beginImg, endImg);
00085         sir.initializeAndApply(RBase<BSGSIN,TRANSRET>::m_partition);
00086         PERM empty(RBase<BSGSIN,TRANSRET>::m_bsgs.n);
00087         sir.apply2(RBase<BSGSIN,TRANSRET>::m_partition2, empty);
00088         
00089         RBase<BSGSIN,TRANSRET>::construct(stabPred, 0);
00090 }
00091 
00092 template<class BSGSIN,class TRANSRET>
00093 unsigned int SetImageSearch<BSGSIN,TRANSRET>::processNewFixPoints(const Partition& pi, unsigned int level) {
00094         const unsigned int basePos = RBase<BSGSIN,TRANSRET>::processNewFixPoints(pi, level);
00095         if (!this->m_limitInitialized) {
00096                 bool allFound = true;
00097                 BOOST_FOREACH(unsigned long alpha, toStab) {
00098                         if (std::find(pi.fixPointsBegin(), pi.fixPointsEnd(), alpha) == pi.fixPointsEnd()) {
00099                                 allFound = false;
00100                                 break;
00101                         }
00102                 }
00103                 if (allFound) {
00104                         this->m_limitLevel = level;
00105                         this->m_limitBase = basePos;
00106                         this->m_limitInitialized = true;
00107                 }
00108         }
00109         return basePos;
00110 }
00111 
00112 }
00113 }
00114 
00115 #endif // -- PARTITION_SET_IMAGE_SEARCH_H_