permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/generator/schreier_generator.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 SCHREIERGENERATOR_H_
00034 #define SCHREIERGENERATOR_H_
00035 
00036 #include <permlib/common.h>
00037 #include <permlib/generator/generator.h>
00038 
00039 #include <stack>
00040 #include <boost/scoped_ptr.hpp>
00041 #include <boost/tuple/tuple.hpp>
00042 
00043 namespace permlib {
00044 
00046 
00053 template <class PERM, class TRANS>
00054 class SchreierGenerator : public Generator<PERM> {
00055 public:
00057         typedef typename std::list<typename PERM::ptr>::const_iterator PERMlistIt;
00059         typedef typename std::list<unsigned long>::const_iterator TRANSlistIt;
00060         
00062 
00067         SchreierGenerator(const TRANS *U, PERMlistIt S_begin, PERMlistIt S_end);
00068         virtual ~SchreierGenerator();
00069 
00070         PERM next();
00071         bool hasNext();
00072         
00074 
00079         void update(TRANS *U, PERMlistIt S_begin, PERMlistIt S_end);
00080         
00082 
00087         void update(unsigned int j);
00088 private:
00089         PERMlistIt m_Sbegin;
00090         PERMlistIt m_Scurrent;
00091         PERMlistIt m_Send;
00092         const TRANS *m_U;
00093         TRANSlistIt m_Ubegin;
00094         TRANSlistIt m_Ucurrent;
00095         TRANSlistIt m_Uend;
00096         unsigned int m_posS;
00097         unsigned int m_posSlimit;
00098         unsigned int m_posU;
00099         unsigned int m_posUlimit;
00100 
00101         PERM* m_u_beta;
00102         unsigned long m_beta;
00103 
00104         std::stack<boost::tuple<unsigned int, unsigned int, unsigned int, unsigned int> > m_stackTodo;
00105 
00107         bool advance();
00109         void init();
00111         void reset();
00112 };
00113 
00114 //
00115 //     ----       IMPLEMENTATION
00116 //
00117 
00118 template <class PERM, class TRANS>
00119 SchreierGenerator<PERM, TRANS>::SchreierGenerator(const TRANS *U, PERMlistIt S_begin, PERMlistIt S_end)
00120                 : m_Sbegin(S_begin), m_Scurrent(S_begin), m_Send(S_end),
00121                   m_U(U), m_Ubegin(m_U->begin()), m_Ucurrent(m_U->begin()), m_Uend(m_U->end()),
00122                   m_posS(0), m_posSlimit(0), m_posU(0), m_posUlimit(0), m_u_beta(0)
00123 {
00124         init();
00125 }
00126 
00127 template <class PERM, class TRANS>
00128 SchreierGenerator<PERM, TRANS>::~SchreierGenerator() {
00129         delete m_u_beta;
00130 }
00131 
00132 template <class PERM, class TRANS>
00133 void SchreierGenerator<PERM, TRANS>::init() {
00134         m_beta = *m_Ucurrent;
00135         delete m_u_beta;
00136         m_u_beta = m_U->at(m_beta);
00137 }
00138 
00139 
00140 template <class PERM, class TRANS>
00141 bool SchreierGenerator<PERM, TRANS>::hasNext() {
00142         if (m_Send != m_Scurrent && m_Uend != m_Ucurrent && (!m_posUlimit || m_posU < m_posUlimit)) {
00143                 const PERM &x = **m_Scurrent;
00144                 if (m_U->trivialByDefinition(x, x / m_beta)) {
00145                         advance();
00146                         return hasNext();
00147                 }
00148                 return true;
00149         }
00150 
00151         if (!m_stackTodo.empty()) {
00152                 boost::tuple<unsigned int, unsigned int, unsigned int, unsigned int> lastTuple = m_stackTodo.top();
00153                 m_stackTodo.pop();
00154 
00155                 m_posS = boost::get<0>(lastTuple);
00156                 m_posSlimit = boost::get<1>(lastTuple);
00157                 m_posU = boost::get<2>(lastTuple);
00158                 m_posUlimit = boost::get<3>(lastTuple);
00159                 reset();
00160 
00161                 return hasNext();
00162         }
00163         return false;
00164 }
00165 
00166 template <class PERM, class TRANS>
00167 bool SchreierGenerator<PERM, TRANS>::advance() {
00168         ++m_Scurrent;
00169         ++m_posS;
00170         if (m_Scurrent == m_Send) {
00171                 m_Scurrent = boost::next(m_Sbegin, m_posSlimit);
00172                 m_posS = m_posSlimit;
00173                 ++m_Ucurrent;
00174                 ++m_posU;
00175                 if (m_Ucurrent != m_Uend)
00176                         init();
00177                 else
00178                         return false;
00179         }
00180         return true;
00181 }
00182 
00183 template <class PERM, class TRANS>
00184 PERM SchreierGenerator<PERM, TRANS>::next() {
00185         BOOST_ASSERT(m_Scurrent != m_Send);
00186         BOOST_ASSERT(m_Ucurrent != m_Uend);
00187 
00188         PERMLIB_DEBUG(std::cout << "s = " << m_posS << "; u = " << m_posU << std::endl;)
00189         const PERM &x = **m_Scurrent;
00190 
00191         PERM g = *m_u_beta * x;
00192         boost::scoped_ptr<PERM> u_beta_ptr2(m_U->at(x / m_beta));
00193         u_beta_ptr2->invertInplace();
00194         g *= *u_beta_ptr2;
00195 
00196         advance();
00197 
00198         return g;
00199 }
00200 
00201 template <class PERM, class TRANS>
00202 void SchreierGenerator<PERM, TRANS>::reset() {
00203         m_Scurrent = m_Sbegin;
00204         m_Ucurrent = m_Ubegin;
00205         int i = m_posS;
00206         while (--i>=0) ++m_Scurrent;
00207         i = m_posU;
00208         while (--i>=0) ++m_Ucurrent;
00209 
00210         if (m_Ucurrent != m_Uend)
00211                 init();
00212 }
00213 
00214 template <class PERM, class TRANS>
00215 void SchreierGenerator<PERM, TRANS>:: update(TRANS *U, PERMlistIt S_begin, PERMlistIt S_end) {
00216         if (U == m_U && S_begin == m_Sbegin && S_end == m_Send)
00217                 return;
00218         m_U = U;
00219         m_Sbegin = S_begin;
00220         m_Send = S_end;
00221         m_Ubegin = U->begin();
00222         m_Uend = U->end();
00223         reset();
00224 }
00225 
00226 template <class PERM, class TRANS>
00227 void SchreierGenerator<PERM, TRANS>:: update(unsigned int j) {
00228         m_stackTodo.push(boost::make_tuple(m_posS, m_posSlimit, m_posU, m_posUlimit));
00229         m_posUlimit = m_posU;
00230         m_posS = j;
00231         m_posSlimit = j;
00232         m_posU = 0;
00233         reset();
00234 }
00235 
00236 }
00237 
00238 #endif // -- SCHREIERGENERATOR_H_