permlib  0.2.6
Library for permutation computations
 All Classes Functions Variables Typedefs Enumerations Friends
include/permlib/permutationword.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 PERMUTATIONWORD_H_
00034 #define PERMUTATIONWORD_H_
00035 
00036 #include <permlib/permutation.h>
00037 #include <vector>
00038 
00039 #include <boost/shared_ptr.hpp>
00040 #include <boost/foreach.hpp>
00041 
00042 namespace permlib {
00043 
00044 typedef boost::shared_ptr<Permutation> PermutationPtr;
00045 
00047 
00050 class PermutationWord {
00051 public:
00053         typedef Permutation::perm perm;
00054         
00056         typedef boost::shared_ptr<PermutationWord> ptr;
00057         
00059         explicit PermutationWord(unsigned int n);
00061         PermutationWord(unsigned int n, const std::string &cycles);
00063         explicit PermutationWord(const perm &p);
00065         PermutationWord(const PermutationWord &p);
00066 
00068     PermutationWord operator*(const PermutationWord &p) const;
00070 
00073     PermutationWord& operator*=(const PermutationWord &p);
00075 
00078     PermutationWord& operator^=(const PermutationWord &p);
00080     PermutationWord operator~() const;
00082     PermutationWord& invertInplace();
00084     bool operator==(const PermutationWord &p2) const;
00085 
00087         inline unsigned long operator/(unsigned long val) const { return at(val); }
00089         unsigned long at(unsigned long val) const;
00091         unsigned long operator%(unsigned long val) const;
00092 
00094         friend std::ostream &operator<< (std::ostream &out, const PermutationWord &p);
00095 
00097 
00101         bool isIdentity(bool flush = false) const;
00102     
00104         //TODO: it must be the other way round: isIdentity should call flush
00105         inline void flush() { isIdentity(true); }
00107         inline unsigned int size() const { return m_n; }
00108         
00110         static unsigned long elementsNumber() { return ms_elements.size(); }
00111         
00113         static void clearStorage();
00114 private:
00115         static std::vector<PermutationPtr> ms_elements;
00116         static std::vector<PermutationPtr> ms_elementsInverse;
00117         static void addElement(const perm &p);
00118         static void addElement(const perm &p, const perm &pInv);
00119         static void addElement(PermutationPtr p);
00120 
00121         mutable std::vector<int> m_word;
00122         unsigned int m_n;
00123 };
00124 
00125 std::vector<PermutationPtr> PermutationWord::ms_elements(1);
00126 std::vector<PermutationPtr> PermutationWord::ms_elementsInverse(1);
00127 
00128 inline PermutationWord::PermutationWord(unsigned int n) 
00129         : m_n(n) 
00130 { }
00131 
00132 inline PermutationWord::PermutationWord(unsigned int n, const std::string &cycles) 
00133         : m_n(n) 
00134 {
00135         Permutation *pp = new Permutation(n, cycles);
00136         ms_elements.push_back(PermutationPtr(pp));
00137         ms_elementsInverse.push_back(PermutationPtr(new Permutation(~*pp)));
00138         m_word.reserve(2);
00139         m_word.push_back(ms_elements.size()-1);
00140 }
00141 
00142 inline PermutationWord::PermutationWord(const PermutationWord &p) 
00143         : m_word(p.m_word), m_n(p.m_n) 
00144 { }
00145 
00146 inline PermutationWord::PermutationWord(const perm &p) 
00147         : m_n(p.size()) 
00148 {
00149         addElement(p);
00150         m_word.reserve(2);
00151         m_word.push_back(ms_elements.size()-1);
00152 }
00153 
00154 inline void PermutationWord::addElement(const perm &p) {
00155         PermutationPtr gen(new Permutation(p));
00156         ms_elements.push_back(gen);
00157         PermutationPtr genInv(new Permutation(~*gen));
00158         ms_elementsInverse.push_back(genInv);
00159 }
00160 inline void PermutationWord::addElement(PermutationPtr p) {
00161         ms_elements.push_back(p);
00162         PermutationPtr genInv(new Permutation(~*p));
00163         ms_elementsInverse.push_back(genInv);
00164 }
00165 
00166 inline void PermutationWord::addElement(const perm &p, const perm &pInv) {
00167         PermutationPtr gen(new Permutation(p));
00168         ms_elements.push_back(gen);
00169         PermutationPtr genInv(new Permutation(pInv));
00170         ms_elementsInverse.push_back(genInv);
00171 }
00172 
00173 
00174 inline PermutationWord PermutationWord::operator*(const PermutationWord &p) const {
00175         PermutationWord res(*this);
00176         res *= p;
00177         return res;
00178 }
00179 
00180 inline PermutationWord& PermutationWord::operator*=(const PermutationWord &p) {
00181         if (m_word.empty()) {
00182                 m_word.insert(m_word.end(), p.m_word.begin(), p.m_word.end());
00183                 return *this;
00184         } else if (p.m_word.empty())
00185                 return *this;
00186 
00187         m_word.insert(m_word.end(), p.m_word.begin(), p.m_word.end());
00188         return *this;
00189 }
00190 
00191 inline PermutationWord& PermutationWord::operator^=(const PermutationWord &p) {
00192         if (m_word.empty()) {
00193                 m_word.insert(m_word.end(), p.m_word.begin(), p.m_word.end());
00194                 return *this;
00195         } else if (p.m_word.empty())
00196                 return *this;
00197         
00198         m_word.insert(m_word.begin(), p.m_word.begin(), p.m_word.end());
00199         return *this;
00200 }
00201 
00202 
00203 inline PermutationWord& PermutationWord::invertInplace() {
00204         std::vector<int> oldWord(m_word);
00205         for (unsigned int i=0; i<oldWord.size(); ++i) {
00206                 m_word[i] = -oldWord[oldWord.size() - 1 - i];
00207         }
00208         return *this;
00209 }
00210 
00211 inline PermutationWord PermutationWord::operator~() const {
00212         PermutationWord inv(*this);
00213         for (unsigned int i=0; i<m_word.size(); ++i) {
00214                 inv.m_word[i] = -m_word[m_word.size() - 1 - i];
00215         }
00216         return inv;
00217 }
00218 
00219 inline unsigned long PermutationWord::at(unsigned long val) const {
00220         unsigned long ret = val;
00221         BOOST_FOREACH(int e, m_word) {
00222                 if (e > 0)
00223                         ret = *(ms_elements[e]) / ret;
00224                 else
00225                         ret = *(ms_elementsInverse[-e]) / ret;
00226         }
00227         return ret;
00228 }
00229 
00230 inline unsigned long PermutationWord::operator%(unsigned long val) const {
00231         unsigned long ret = val;
00232         for (std::vector<int>::reverse_iterator lit = m_word.rbegin(); lit != m_word.rend(); ++lit) {
00233                 int e = *lit;
00234                 if (e < 0)
00235                         ret = *(ms_elements[-e]) / ret;
00236                 else
00237                         ret = *(ms_elementsInverse[e]) / ret;
00238         }
00239         return ret;
00240 }
00241 
00242 inline bool PermutationWord::isIdentity(bool flush_) const {
00243         if (m_word.empty()) {
00244                 return true;
00245         }
00246         if (m_word.size() == 1) {
00247                 if (flush_)
00248                         return true;
00249                 int e = m_word.front();
00250                 if (e>0)
00251                         return ms_elements[e]->isIdentity();
00252                 else
00253                         return ms_elementsInverse[-e]->isIdentity();
00254         }
00255 
00256         perm mult(m_n);
00257         perm multInv(m_n);
00258 
00259         PermutationPtr resMult(new Permutation(m_n));
00260         BOOST_FOREACH(int e, m_word) {
00261                 *resMult *= (e > 0)
00262                                 ? *ms_elements[e].get()
00263                                 : *ms_elementsInverse[-e].get();
00264         }
00265 
00266         const bool permIsIdentity = resMult->isIdentity();
00267 
00268         if (!permIsIdentity) {
00269                 addElement(resMult);
00270                 m_word.clear();
00271                 m_word.reserve(2);
00272                 m_word.push_back(ms_elements.size()-1);
00273         }
00274 
00275 
00276         return permIsIdentity;
00277 }
00278 
00279 inline std::ostream &operator<< (std::ostream &out, const PermutationWord &p) {
00280     out << "W[";
00281     BOOST_FOREACH(int g, p.m_word) {
00282         out << g << ",";
00283     }
00284     out << "]";
00285     return out;
00286 }
00287 
00288 inline bool PermutationWord::operator==(const PermutationWord &p2) const {
00289         if (m_n != p2.m_n)
00290                 return false;
00291 
00292         //TODO: is this correct or do we need the old code (below) or keep references to all perm instances?
00293     //note: this is not correct: compare result of \inv{g} * g and g * \inv{g}, but this can be fixed by   .... -x x ...... stripping when multiplying
00294     // in other cases it might have a good chance to work as intended
00295         //
00296         // NOTE: old code deleted from below during clean-up
00297         return m_word == p2.m_word;
00298 }
00299 
00300 inline void PermutationWord::clearStorage() {
00301         ms_elements.clear();
00302         ms_elements.resize(1);
00303         ms_elementsInverse.clear();
00304         ms_elementsInverse.resize(1);
00305 }
00306 
00307 }
00308 
00309 #endif // -- PERMUTATIONWORD_H_