permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/transversal/transversal.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 TRANSVERSAL_H_
00034 #define TRANSVERSAL_H_
00035 
00036 #include <permlib/sorter/base_sorter.h>
00037 #include <permlib/transversal/orbit.h>
00038 
00039 #include <map>
00040 #include <list>
00041 #include <vector>
00042 
00043 #include <boost/foreach.hpp>
00044 #include <boost/shared_ptr.hpp>
00045 
00046 namespace permlib {
00047 
00048 template <class PERM>
00049 class Transversal;
00050 
00051 template <class PERM>
00052 std::ostream &operator<< (std::ostream &out, const Transversal<PERM> &t) {
00053         out << "{";
00054         BOOST_FOREACH (boost::shared_ptr<PERM> p, t.m_transversal) {
00055                 if (p)
00056                         out << *p << ", ";
00057                 else
00058                         out << "O, ";
00059         }
00060         out << "}";
00061         return out;
00062 }
00063 
00065 template <class PERM>
00066 class Transversal : public Orbit<PERM,unsigned long> {
00067 public:
00069 
00072         Transversal(unsigned int n);
00074     virtual ~Transversal() {}
00075         
00077     virtual PERM* at(unsigned long val) const = 0;
00078     
00080         virtual bool trivialByDefinition(const PERM& x, unsigned long to) const = 0;
00081         
00083         virtual bool contains(const unsigned long& val) const;
00084 
00086         std::list<unsigned long>::const_iterator begin() const { return this->m_orbit.begin(); };
00088         std::list<unsigned long>::const_iterator end() const { return this->m_orbit.end(); };
00090         std::pair<std::list<unsigned long>::const_iterator,std::list<unsigned long>::const_iterator> pairIt() const {
00091                 return std::make_pair(begin(), end());
00092         }
00093 
00095     unsigned int size() const { return this->m_orbit.size(); }
00096         
00098     inline unsigned int n() const { return m_n; }
00099 
00101 
00105     template <class InputIterator>
00106     void sort(InputIterator Bbegin, InputIterator Bend);
00107     
00109         inline bool sorted() const { return m_sorted; }
00110         
00112         struct TrivialAction {
00114                 unsigned long operator()(const PERM &p, unsigned long v) const {
00115                         return p / v;
00116                 }
00117         };
00118         
00120 
00124         virtual void orbit(unsigned long alpha, const std::list<typename PERM::ptr> &generators);
00126 
00131         virtual void orbitUpdate(unsigned long alpha, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g);
00132         
00134 
00138         virtual void permute(const PERM& g, const PERM& gInv);
00140 
00143         virtual void updateGenerators(const std::map<PERM*,typename PERM::ptr>& generatorChange) {}
00144     
00145     virtual const unsigned long& element() const;
00146         
00148     friend std::ostream &operator<< <> (std::ostream &out, const Transversal<PERM> &p);
00149 protected:
00151     unsigned int m_n;
00152         
00154         std::vector<boost::shared_ptr<PERM> > m_transversal;
00155         
00157     std::list<unsigned long> m_orbit;
00158         
00160     bool m_sorted;
00161     
00163     virtual void registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p);
00164         
00165         virtual bool foundOrbitElement(const unsigned long& alpha, const unsigned long& alpha_p, const typename PERM::ptr& p);
00166 };
00167 
00168 //
00169 //     ----       IMPLEMENTATION
00170 //
00171 
00172 template <class PERM>
00173 Transversal<PERM>::Transversal(unsigned int n_) 
00174         : m_n(n_), m_transversal(n_), m_sorted(false) 
00175 { }
00176 
00177 template <class PERM>
00178 void Transversal<PERM>::orbit(unsigned long beta, const std::list<typename PERM::ptr> &generators) {
00179         Orbit<PERM,unsigned long>::orbit(beta, generators, TrivialAction(), m_orbit);
00180 }
00181 
00182 template <class PERM>
00183 void Transversal<PERM>::orbitUpdate(unsigned long beta, const std::list<typename PERM::ptr> &generators, const typename PERM::ptr &g) {
00184   Orbit<PERM,unsigned long>::orbitUpdate(beta, generators, g, TrivialAction(), m_orbit);
00185 }
00186 
00187 template <class PERM>
00188 bool Transversal<PERM>::foundOrbitElement(const unsigned long& alpha, const unsigned long& alpha_p, const typename PERM::ptr& p) {
00189         BOOST_ASSERT( alpha_p < m_transversal.size() );
00190         if (!m_transversal[alpha_p]) {
00191                 if (!p) {
00192                         typename PERM::ptr identity(new PERM(m_n));
00193                         registerMove(alpha, alpha_p, identity);
00194                 } else {
00195                         registerMove(alpha, alpha_p, p);
00196                 }
00197                 return true;
00198         }
00199         return false;
00200 }
00201 
00202 template <class PERM>
00203 bool Transversal<PERM>::contains(const unsigned long& val) const { 
00204         return m_transversal[val] != 0; 
00205 }
00206 
00207 template <class PERM>
00208 void Transversal<PERM>::registerMove(unsigned long from, unsigned long to, const typename PERM::ptr &p) {
00209         m_sorted = false; 
00210 }
00211 
00212 
00213 template <class PERM>
00214 template <class InputIterator>
00215 void Transversal<PERM>::sort(InputIterator Bbegin, InputIterator Bend) {
00216         this->m_orbit.sort(BaseSorter(m_n, Bbegin, Bend));
00217         m_sorted = true;
00218 }
00219 
00220 template <class PERM>
00221 void Transversal<PERM>::permute(const PERM& g, const PERM& gInv) {
00222         std::vector<boost::shared_ptr<PERM> > temp(m_n);
00223         for (unsigned long i=0; i<m_n; ++i) {
00224                 const unsigned long j = g / i;
00225                 temp[j] = m_transversal[i];
00226         }
00227         std::copy(temp.begin(), temp.end(), m_transversal.begin());
00228         BOOST_FOREACH(unsigned long& alpha, this->m_orbit) {
00229                 alpha = g / alpha;
00230         }
00231         m_sorted = false;
00232 }
00233     
00234 template <class PERM>
00235 inline const unsigned long& Transversal<PERM>::element() const {
00236     return m_orbit.front();
00237 }
00238 
00239 }
00240 
00241 #endif // -- TRANSVERSAL_H_