Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members  

/magnus/back_end/Group/include/SymmetricRelators.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: SymmetricRelators.h,v 1.2 1998/05/14 19:45:36 bormotov Exp $
00003  */
00004 
00005 // Copyright (C) 1995 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 
00008 // Contents: Implementation of SymmetricRelators class
00009 //           
00010 //
00011 //   Compact storage for symmetrised relators.
00012 //
00013 // Principal Author: Dmitry Bormotov, Dmitry Pechkin
00014 //
00015 // Status: trial implementation
00016 //
00017 // Usage:
00018 //
00019 //
00020 
00021 #ifndef _SYMMETRIC_RELATORS_H
00022 #define _SYMMETRIC_RELATORS_H
00023 
00024 #include "Set.h"
00025 #include "Word.h"
00026 #include "Vector.h"
00027 
00028 
00029 // ------------------- Some global functions -----------------------//
00030 
00031 
00032 template <class T>
00033 T arbitraryElementOf ( const SetOf<T>& S );
00034 // Returns an arbitrary element of given set.
00035 // This doesn't guaranteed to get different elements of set if it is called
00036 // repetitive. Really it may return the same element always.
00037 //
00038 //@dp May It should be defined as member of SetOf<> class?
00039 
00040 
00041 SetOf<Word>& unsymmetrise ( SetOf<Word>& S );
00042 // @dp provisional implementation, too expensive.
00043 
00044 Word minimalWord( const Word& w );
00045 // get minimal form of word W :
00046 //  minimal form M of word W is cyclic permutation of W or W^-1 such that
00047 //  if V is any cyclic permutation of W or W^-1  then V >= M
00048 
00049 SetOf<Word>& minimizeSet( SetOf<Word>& S );
00050 // rebuild set of minimal form of words.
00051 
00052 inline int rootLength( const Word& w ) { return w.length() / maximalRoot(w); }
00053 
00054 
00055 //-------------------------- class SymmetricRelators -------------------------//
00056 
00057 
00058 class SymmetricRelators {
00059 
00060 friend class SymmetricRelatorsIterator;
00061 
00062 public:
00063 
00064   ///////////////////////////////////////////////////////
00065   //                                                   //
00066   //  Constructors:                                    //
00067   //                                                   //
00068   ///////////////////////////////////////////////////////
00069 
00070   // No default constructor.
00071 
00072   // Copy constructor, operator=, and destructor supplied by compiler.
00073   
00074   SymmetricRelators ( const SetOf<Word>& relators );
00075 
00076   ~SymmetricRelators ( );
00077 
00078 
00079   ///////////////////////////////////////////////////////
00080   //                                                   //
00081   //  Accessors:                                       //
00082   //                                                   //
00083   ///////////////////////////////////////////////////////
00084 
00085   int cardinality( ) const {
00086     return symmetricRelators.length();
00087   } 
00088 
00089   const VectorOf<Word>& getRelators( ) {
00090     return symmetricRelators; 
00091   }
00092 
00093 private:
00094   
00095   ///////////////////////////////////////////////////////
00096   //                                                   //
00097   //  Data members:                                    //
00098   //                                                   //
00099   ///////////////////////////////////////////////////////
00100 
00101   VectorOf<Word> symmetricRelators;
00102   int *rootLengths;
00103   
00104 };
00105 
00106 
00107 //---------------------- class SymmetricRelatorsIterator ---------------------//
00108 
00109 
00110 class SymmetricRelatorsIterator {
00111 
00112 public:
00113 
00114 
00115   ///////////////////////////////////////////////////////
00116   //                                                   //
00117   //  Constructors:                                    //
00118   //                                                   //
00119   ///////////////////////////////////////////////////////
00120 
00121   // No default constructor.
00122 
00123   // Copy constructor, operator=, and destructor supplied by compiler.
00124 
00125   SymmetricRelatorsIterator(const SymmetricRelators& S) : 
00126       iterSet(S), relatorNumber(0), cpNum(0), invFlag(false), 
00127       iterSetLen(S.symmetricRelators.length()) {
00128     if ( !done() ) {
00129       curRelator = iterSet.symmetricRelators[relatorNumber];
00130       rootLen = iterSet.rootLengths[relatorNumber];
00131       cpNum = rootLen;
00132     }
00133   }
00134   // Constructs iterator from SymmetricRelators over which to iterate.
00135 
00136   SymmetricRelatorsIterator( const SetOf<Word>& S ); 
00137 
00138   ///////////////////////////////////////////////////////
00139   //                                                   //
00140   //  Accessors                                        //
00141   //                                                   //
00142   ///////////////////////////////////////////////////////
00143 
00144   Bool operator == ( const SymmetricRelatorsIterator& I ) const {
00145     return ( cpNum == I.cpNum  &&  invFlag == I.invFlag  &&  relatorNumber == I.relatorNumber );
00146   }
00147   // TRUE iff the iterators will look at the same elements of the (physically)
00148   // same set in the same order. Valid at any point of the iteration.
00149 
00150   Word value( ) const {
00151   #if SAFETY > 0
00152     if( done() ) error("tried to retrieve value from SymmetricRelatorsIterator "
00153                        "which is done");
00154   #endif
00155     return curRelator;
00156   }
00157   // Returns the current relator. Calling this is a fatal error if done().
00158 
00159   Bool next( ) {
00160     if( done() ) return false;
00161     bool bSuccess = true;
00162     cpNum--;
00163     if (cpNum > 0)
00164       curRelator = curRelator.cyclicallyPermute(1);
00165     else {
00166       cpNum = 0; //@db ?
00167       if( invFlag || curRelator.length() == 0 ) {
00168         bSuccess = ( ++relatorNumber < iterSetLen );
00169         if (bSuccess) {
00170           curRelator = iterSet.symmetricRelators[relatorNumber];
00171           rootLen = iterSet.rootLengths[relatorNumber];
00172           cpNum = rootLen;
00173           invFlag = false;
00174         }
00175       }
00176       else {
00177         curRelator = curRelator.inverse();
00178         // length of root of curRelator is not changed
00179           cpNum = rootLen;
00180         invFlag = !invFlag;
00181       }
00182     }
00183     return bSuccess;
00184   }
00185   // Advances this iterator.
00186   // Returns TRUE iff the iteration has not finished.
00187   // This may be called after it returns FALSE with no side effect.
00188 
00189   
00190   bool done( ) const { 
00191     return (relatorNumber >= iterSetLen); 
00192   }
00193   // Returns TRUE iff the iteration has finished. This may
00194   // be called after it returns TRUE with no side effect.
00195   
00196   void reset( ) {
00197     relatorNumber = 0;
00198     cpNum = 0;
00199     invFlag = false;
00200     if ( !done() )  {
00201       curRelator = iterSet.symmetricRelators[relatorNumber];
00202       rootLen = iterSet.rootLengths[relatorNumber];
00203       cpNum = rootLen;
00204     }
00205   }
00206   // Resets this iterator to the state it was in after construction.
00207   
00208 private:
00209 
00210   ///////////////////////////////////////////////////////
00211   //                                                   //
00212   //  Data members:                                    //
00213   //                                                   //
00214   ///////////////////////////////////////////////////////
00215 
00216   const SymmetricRelators& iterSet;
00217   int iterSetLen;
00218   int relatorNumber;
00219   int cpNum;       // number of cyclic permutation
00220   int rootLen;     // length of root of curRelator 
00221   bool invFlag;    // true, if we iterate for inverse curRelator
00222   Word curRelator; // current relator
00223 
00224 };
00225 
00226 #endif
00227 
00228 

Generated at Tue Jun 19 09:49:36 2001 for Magnus Classes by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001