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

/magnus/back_end/KB/include/WordOrderRep.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: WordOrderRep.h,v 1.2 2000/02/09 23:59:20 bormotov Exp $
00003  */
00004 
00005 // Copyright (C) 1994 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007 
00008 // Contents: Definition of WordOrderRep and related classes.
00009 //
00010 // Principal Author: Sarah Rees
00011 //
00012 // Status: in progress
00013 //
00014 // Revision History:
00015 //
00016 
00017 #ifndef _WordOrderRep_H_
00018 #define _WordOrderRep_H_
00019 
00020 #include "Word.h"
00021 #include "Vector.h"
00022 #include "RefCounter.h"
00023 // #include "DFSARep.h"
00024 #include "Set.h"
00025 #include "DiffHistoryRep.h"
00026 typedef int State; 
00027 // @sr for now this file needs to be independent of DFSARep.
00028 // So for now we'll typedef State to be int, but that's only temporary.
00029 // That's because a declaration of SetOf<DiffHistory> is necessary in Set.C
00030 // (for each of the various DiffHistory types)
00031 // and that can't be dependent on the FSA hierarchy.
00032 
00033 
00034 class WordOrderRep : public RefCounter {
00035 public:
00036 //constructors
00037   WordOrderRep() {};
00038   WordOrderRep(const Chars & oType ) : orderType(oType),numSyms(0), order(0),
00039     posn(0), invposn(0) {};
00040   WordOrderRep(const VectorOf<int> & o) : numSyms(o.length()), order(o),
00041     posn(o.length()), invposn(o.length()) {
00042     int i;
00043     for (i=0;i<numSyms;i++){
00044       posn[i]=0; invposn[i]=0; 
00045            // We MUST initialise invposn to be zero, since entries which
00046            // remain set to zero indicate involutions
00047     }
00048     for (i=1;i<=numSyms;i++){
00049       int j = order[i-1];
00050       if (j>0) posn[j-1]=i; else invposn[-j-1]=i;
00051     }
00052   };
00053   WordOrderRep(int numOfSymbols) : numSyms(numOfSymbols), order(0),
00054     posn(0), invposn(0) {
00055     int ngens = numOfSymbols/2;
00056     for (int i=1;i<=ngens;i++){
00057       order.append(i);
00058       order.append(-i);
00059       posn.append(2*i-1);
00060       invposn.append(2*i);
00061     }
00062   }
00063   WordOrderRep(const Chars & oType, int numOfSymbols) : 
00064     orderType(oType), numSyms(numOfSymbols), order(0), posn(0), invposn(0) {
00065     for (int i=1;i<=numOfSymbols/2;i++){
00066       order.append(i);
00067       order.append(-i);
00068       posn.append(2*i-1);
00069       invposn.append(2*i);
00070     }
00071   };
00072   WordOrderRep(const Chars & oType, const VectorOf<int> & o) : 
00073     orderType(oType), numSyms(o.length()), order(o), posn(o.length()), 
00074       invposn(o.length()) {
00075     int i;
00076     for (i=0;i<numSyms;i++){
00077       posn[i]=0; invposn[i]=0; 
00078            // We MUST initialise invposn to be zero, since entries which
00079            // remain set to zero indicate involutions
00080     }
00081     for (i=1;i<=numSyms;i++){
00082       int j = order[i-1];
00083       if (j>0) posn[j-1]=i; else invposn[-j-1]=i;
00084     }
00085   };
00086 // copy constructor
00087   WordOrderRep (const WordOrderRep & word_order) { 
00088     order=word_order.order;
00089     orderType = word_order.orderType;
00090     numSyms = word_order.numSyms;
00091     posn = word_order.posn;
00092     invposn = word_order.invposn;
00093   };
00094   virtual WordOrderRep *clone() const {};
00095 //destructor
00096   ~WordOrderRep() {};
00097   virtual int signature(const Word & w1,const Word & w2) const {return 1;};
00098   virtual int signature(int i, int j) const {return 1;};
00099   virtual int signature(Generator g,Generator h) const {return 1;};
00100   virtual void balancedEquationFromRelator
00101                       (const Word & w,Word & lhs,Word & rhs) const {};
00102   virtual int historyBound(const VectorOf<Word> & diffs) const{ return 0;}
00103   virtual DiffHistoryRep * buildDiffHistoryRep() const  {};
00104   virtual DiffHistoryRep * buildDiffHistoryRep(State d,int g,int h) const  {};
00105 // build a difference history for the word difference g^-1h, attached
00106 // to state d of the difference machine.
00107 
00108   virtual DiffHistoryRep * update 
00109      (const DiffHistoryRep & dh,State d,int g,int h,const Word & wd) const {};
00110 // Given a difference history dh associated with pairs of words w,u,
00111 // construct the difference history associated with pairs wg,uh and the
00112 // state d of the difference machine (which is of course the target
00113 // of the state for dh under the pair of symbols (g,h))
00114 
00115   virtual Bool reduction(const DiffHistoryRep & dh,int g,int h) const {};
00116 // returns YES if the difference history contains a pair w,u of words
00117 // such that wg=_G uh and uh < wg in the word order.
00118 
00119   virtual Bool possibleReduction(const AheadInfoRep & ai,int g) const {};
00120 // returns YES if it is possible (i.e. cannot yet be ruled out)
00121 // that there is a reduction to a longer word. 
00122 
00123   virtual AheadInfoRep *  update(const AheadInfoRep & ai,int g) const {};
00124 
00125   virtual DiffHistoryVtxRep * buildDiffHistoryVtxRep() const  {};
00126   virtual DiffHistoryVtxRep 
00127       * buildDiffHistoryVtxRep(State d,int g,int h) const  {}; 
00128 // build a difference history Vtx for the word difference g^-1h,
00129 // attached to state d of the difference machine.
00130 
00131   virtual DiffHistoryVtxRep * update 
00132      (const DiffHistoryVtxRep & dh,State d, int g, int h, DiffHistoryVtx * ptr)
00133              const {}; 
00134 // Given a difference history vertex dh associated with pairs of
00135 //words w,u,  
00136 // construct the difference history Vtx associated with
00137 // pairs wg,uh and the  
00138 // state d of the difference machine (which is of course thetarget  
00139 // of the state for dh under the pair of symbols (g,h))
00140 
00141   virtual Bool reduction(const DiffHistoryVtxRep & dh,int g,int h)
00142 const {};
00143 // returns YES if the difference history contains a pair w,uof words 
00144 // such that wg=_G uh and uh < wg in the word order.
00145 
00146   virtual Bool possibleReductionAhead(const DiffHistoryVtxRep & dh,int g)
00147 const {}; 
00148 
00149 // returns YES if it is possible (i.e. cannot yet be ruled out) 
00150 // that there is a reduction of w to a longer word, with ug as a 
00151 // proper prefix. 
00152 
00153   Chars getOrderType() const { return orderType; }
00154   int getNumSymbols() const { return numSyms; }
00155   int getSymbolIndex(int i) const { return order[i-1];}
00156   Generator getSymbol(int i) const { Generator g(order[i-1]); return g; }
00157   int getPosition(Generator g) const { 
00158     return (ord(g)>0? posn[ord(g)-1]: invposn[-ord(g)-1]);
00159   } // returns 0 if the generator isn't in the alphabet
00160 
00161   Word inverse(const Word & w) const{
00162     int len = w.length();
00163     VectorOf<Generator> W(len);
00164     for (int i=0; i<len;i++)
00165       W[i]= (selfInverse(w[len-1-i])? w[len-1-i]: inv(w[len-1-i]));
00166     return (Word)W;
00167   }
00168 // Returns yes if the inverse generator is not a symbol.
00169 // It doesn't make sense to call this unless ord(g) is positive
00170 // but this is checked to avoid crashes.
00171   Bool selfInverse(Generator g) const {
00172     return (ord(g)>0 && invposn[ord(g)-1]==0);
00173   }
00174   virtual int getWeight(int i) const { return 1;};
00175   virtual int getWeight(Generator g) const { return 1;};
00176   virtual int getWeight(const Word & w) const { return w.length();};
00177 protected:
00178   VectorOf<int> order;
00179   VectorOf<int> posn; // posn[i] stores position in order of generator
00180                       // indexed by i, as a number in range 1..numSyms
00181   VectorOf<int> invposn; // invposn[i] stores position in order of generator
00182                       // indexed by -i, as a number in range 1..numSyms
00183   int numSyms;
00184 private:
00185   Chars orderType;
00186 };
00187 
00188 class ShortLexRep : public WordOrderRep {
00189 public:
00190   ShortLexRep() : WordOrderRep("ShortLex") {};
00191 
00192   ShortLexRep(const VectorOf<int> &  o) : WordOrderRep("ShortLex",o) { };
00193 
00194   ShortLexRep(int numOfSymbols) : WordOrderRep("ShortLex",numOfSymbols) { };
00195 
00196 //copy constructor
00197   ShortLexRep( const ShortLexRep& wsl ) : 
00198     WordOrderRep(wsl) { }
00199 
00200   WordOrderRep *clone() const { return new ShortLexRep(*this); }
00201 
00202   int signature(const Word & w1,const Word & w2) const { 
00203     if (w1==w2) return 0;
00204     else if (w1.length()<w2.length()) return 1;
00205     else if (w1.length()>w2.length()) return -1;
00206     else {
00207       int j=0;
00208       while (j<w1.length()){
00209         if (getPosition(w1[j])<getPosition(w2[j])) return 1;
00210         else if (getPosition(w1[j])>getPosition(w2[j])) return -1;
00211         else j++;
00212       }
00213     }
00214   } 
00215 
00216   int signature(int i, int j) const {
00217     if (i==j) return 0;
00218     else if (i<j) return 1;
00219     else return -1;
00220   }
00221 
00222   int signature(Generator g,Generator h) const {
00223     return signature(getPosition(g),getPosition(h));
00224   }
00225 
00226   void balancedEquationFromRelator(const Word & w,Word & lhs,Word & rhs) const {
00227 // This code is complicated by the fact that we have to make sure that
00228 // neither side of the equation contains the inverse symbol of an involution
00229 // if that's not in our alphabet. We might even have got such symbols into
00230 // the relation, because of the way magnus turns relations in input into
00231 // relators
00232 
00233     int len=w.length();
00234     int i;
00235     int len2=len - (len+1)/2;
00236 
00237 // copy the word, replacing each g^-1 for which g is an involution by g
00238     VectorOf<Generator> W;
00239     for (i=0;i<len;i++)
00240       W.append((ord(w[i])<0 && selfInverse(inv(w[i])))? inv(w[i]) : w[i]);
00241 
00242     lhs=((Word)W).initialSegment((len+1)/2);
00243     VectorOf<Generator> ww;
00244     for (i=1;i<=len2;i++){
00245       Generator g = W[len-i];
00246       ww.append(selfInverse(g)? g : inv(g));
00247     }
00248     rhs=ww;
00249     if (signature(lhs,rhs)==1){ // lhs is smaller, so switch them
00250       rhs=lhs;
00251       lhs=ww;
00252     }
00253   }
00254 
00255   int historyBound(const VectorOf<Word> & diffs) const{ return 0;}
00256 
00257   DiffHistoryRep * buildDiffHistoryRep() const { 
00258     SLDiffHistoryRep * dhp = new SLDiffHistoryRep();
00259       return dhp;
00260   }
00261 
00262   DiffHistoryRep * buildDiffHistoryRep(State d,int g,int h) const { 
00263     if (g>0 && h>0 && g!=h){
00264       SLDiffHistoryRep * dhp = 
00265         new SLDiffHistoryRep(d,(g>h? 1: -1),0);
00266       return dhp;
00267     }
00268     else if (g>0 && h==0){
00269       SLDiffHistoryRep * dhp = new SLDiffHistoryRep(d,0,1);
00270       return dhp;
00271     }
00272     else { 
00273       cerr << "Parameters out of range for DiffHistoryRep constructor."<< endl;
00274       SLDiffHistoryRep * dhp =  new SLDiffHistoryRep;
00275       return dhp;
00276     }
00277   }
00278 
00279   DiffHistoryRep * update
00280     (const DiffHistoryRep & dh,State d,int g,int h,const Word & wd) const {
00281 // the parameter wd isn't actually used in the function for a ShortLex 
00282 // DiffHistory, but the generality of the code requres it to be a parameter
00283     const SLDiffHistoryRep& ddh = (SLDiffHistoryRep&)dh;
00284     if (g>0 && h>0 && ddh.getC0()){
00285       SLDiffHistoryRep * dhp = new SLDiffHistoryRep
00286               (d,ddh.getC0(),0);
00287       return dhp;
00288     }
00289     else if (g>0 && h==0){
00290       SLDiffHistoryRep * dhp = new SLDiffHistoryRep (d,0,1);
00291       return dhp;
00292     }
00293     else { 
00294       cerr << "Parameters out of range for update."<< endl;
00295       SLDiffHistoryRep * dhp =  new SLDiffHistoryRep;
00296       return dhp;
00297     }
00298   }
00299 
00300   Bool reduction(const DiffHistoryRep & dh,int g,int h) const {
00301     const SLDiffHistoryRep& ddh = (SLDiffHistoryRep&)dh;
00302     if (g>0 && h>0 && ddh.getC0()==1){
00303       return YES;
00304     } 
00305     else if (g>0 && h==0) return YES;
00306     return NO;
00307   }
00308 
00309   Bool possibleReduction(const AheadInfoRep & ai,int g) const { 
00310      return NO;
00311   };
00312 
00313   AheadInfoRep *  update(const AheadInfoRep & ai,int g) const {
00314 // this function won't actually get used, since it is not possible
00315 // in shortlex to have w>u where w is shorter than u.
00316 // It is necessary to have a function returning something of the right
00317 // type to get  compilation.
00318      return new SLAheadInfoRep (); }
00319 
00320   DiffHistoryVtxRep * buildDiffHistoryVtxRep() const { 
00321     SLDiffHistoryVtxRep * dhp = new SLDiffHistoryVtxRep();
00322       return dhp;
00323   }
00324 
00325   DiffHistoryVtxRep
00326     * buildDiffHistoryVtxRep(State d,int g,int h) const
00327 { 
00328     if (g>0 && h>0 && g!=h){
00329       SLDiffHistoryVtxRep * dhp = 
00330         new SLDiffHistoryVtxRep(d,h,0,1,(g>h? 1: -1));
00331       return dhp;
00332     }
00333     else if (g>0 && h==0){
00334       SLDiffHistoryVtxRep * dhp = new
00335              SLDiffHistoryVtxRep(d,0,0,1,0);
00336       return dhp;
00337     }
00338     else { 
00339       cerr <<
00340  "Parameters out of range for DiffHistoryVtxRep constructor."
00341          << endl;
00342       SLDiffHistoryVtxRep * dhp =  new SLDiffHistoryVtxRep;
00343       return dhp;
00344     }
00345   }
00346 
00347   DiffHistoryVtxRep * update
00348     (const DiffHistoryVtxRep & dh,State d,int g,int h, DiffHistoryVtx * ptr)
00349        const {
00350     const SLDiffHistoryVtxRep & ddh = (SLDiffHistoryVtxRep &)dh;
00351     SLDiffHistoryVtxRep * dhp = new SLDiffHistoryVtxRep
00352               (d,h,ptr,dh.getLength()+1,ddh.getLexComp());
00353     return dhp;
00354   }
00355    
00356 
00357   Bool reduction(const DiffHistoryVtxRep & dh,int g,int h) const {
00358     const SLDiffHistoryVtxRep& ddh = (SLDiffHistoryVtxRep&)dh;
00359     if (g>0 && (h==0 || ddh.getLexComp()==1)) return YES;
00360     else return NO;
00361   }
00362 
00363   Bool possibleReduction(const DiffHistoryVtxRep & dh,int g) const { 
00364      return NO;
00365   };
00366 
00367 
00368   int getWeight(int i) const { return 1;};
00369   int getWeight(Generator g) const { return 1;};
00370   int getWeight(const Word & w) const { return w.length();};
00371 };
00372 
00373 class WtShortLexRep : public WordOrderRep {
00374 public:
00375   WtShortLexRep() : WordOrderRep("WtShortLex"){};
00376 
00377   WtShortLexRep(int numOfSymbols) : 
00378     WordOrderRep("WtShortLex",numOfSymbols), weight(0) { 
00379     for (int i=1;i<=numOfSymbols;i++)
00380       weight.append(1);
00381   };
00382 
00383   WtShortLexRep(const VectorOf<int>  & w) : 
00384     WordOrderRep("WtShortLex",w.length()), weight(w) { 
00385   };
00386 
00387   WtShortLexRep(const VectorOf<int> & o,const VectorOf<int> & w) : 
00388     WordOrderRep("WtShortLex",o) , weight(w) {};
00389 
00390 //copy constructor
00391   WtShortLexRep( const WtShortLexRep& wsl ) : 
00392     WordOrderRep(wsl), weight(wsl.weight) { }
00393 
00394   WordOrderRep *clone() const { return new WtShortLexRep(*this); }
00395 
00396   int signature(const Word & w1,const Word & w2) const { 
00397     if (w1==w2) return 0; 
00398     else {
00399       int len1=w1.length();
00400       int len2=w2.length();
00401       int wt1=0;
00402       int wt2=0;
00403       int j=0;
00404       while (j<len1) wt1 += weight[getPosition(w1[j++])-1];
00405       j=0;
00406       while (j<len2) wt2 += weight[getPosition(w2[j++])-1];
00407       if (wt1<wt2) return 1; 
00408       else if (wt1>wt2) return -1; 
00409       else if (w1.length()<w2.length()) return 1; 
00410       else if (w1.length()>w2.length()) return -1; 
00411       else { 
00412         j=0;
00413         while (j<len1){ 
00414           if (getPosition(w1[j])<getPosition(w2[j])) return 1; 
00415           else if (getPosition(w1[j])>getPosition(w2[j])) return -1;
00416           else j++; 
00417         }
00418       }
00419     } 
00420   }
00421 
00422   int signature(int i, int j) const {
00423     if (i==j) return 0;
00424     else if (weight[i-1]<weight[j-1] || (weight[i-1]==weight[j-1] && i<j))
00425       return 1;
00426     else return -1;
00427   }
00428 
00429   int signature(Generator g,Generator h) const {
00430     return signature(getPosition(g),getPosition(h));
00431   }
00432 
00433   void balancedEquationFromRelator(const Word & w,Word & lhs,Word & rhs) const {
00434     int len=w.length();
00435     int i;
00436     int wt1=0; int wt2=0;
00437 
00438 // copy the word, replacing each g^-1 for which g is an involution by g
00439     VectorOf<Generator> W;
00440     for (i=0;i<len;i++)
00441       W.append((ord(w[i])<0 && selfInverse(inv(w[i])))? inv(w[i]) : w[i]);
00442 
00443     int j=0;
00444     while (j<len) wt1 += weight[getPosition(W[j++])-1];
00445     VectorOf<Generator> ww;
00446     j=len;
00447     while (--j>=0) {
00448       Generator g=W[j];
00449       wt1 -= weight[getPosition(g)-1];
00450       wt2 += weight[getPosition(g)-1];
00451       if  (wt1>=wt2 ) ww.append(selfInverse(g)? g : inv(g));
00452       else break;
00453     }
00454     lhs = ((Word)W).initialSegment(j+1);
00455     rhs=ww;
00456     if (signature(lhs,rhs)==1){ // lhs is smaller, so switch them
00457       rhs=lhs;
00458       lhs=ww;
00459     }
00460   }
00461 
00462   int historyBound(const VectorOf<Word> & diffs) const { 
00463     int Max=0;
00464     for (int i=0;i<diffs.length();i++){
00465       Word w=diffs[i];
00466       int len=w.length();
00467       int wt=0;
00468       for (int j=0;j<len;j++) wt += weight[getPosition(w[j])-1];
00469       if (wt>Max) Max = wt;
00470     }
00471     return Max;
00472   }
00473 
00474   DiffHistoryRep * buildDiffHistoryRep() const { 
00475     WtSLDiffHistoryRep * dhp = new WtSLDiffHistoryRep();
00476       return dhp;
00477   }
00478 
00479   DiffHistoryRep * buildDiffHistoryRep(State d,int g,int h) const { 
00480     if (g>0 && h>0 && g!=h){
00481       WtSLDiffHistoryRep * dhp = 
00482         new WtSLDiffHistoryRep(d,(g>h? 1: -1),weight[g-1] - weight[h-1],0,0);
00483       return dhp;
00484     }
00485     else if (g>0 && h==0){
00486       WtSLDiffHistoryRep * dhp = 
00487         new WtSLDiffHistoryRep(d,0,0,1,(weight[g-1]>0?1: weight[g-1]));
00488       return dhp;
00489     }
00490     else { 
00491       cerr << "Parameters out of range for DiffHistoryRep constructor."<< endl;
00492       WtSLDiffHistoryRep * dhp =  new WtSLDiffHistoryRep;
00493       return dhp;
00494     }
00495   }
00496 
00497   DiffHistoryRep * update
00498     (const DiffHistoryRep & dh,State d,int g,int h,const Word & wd) const {
00499     const WtSLDiffHistoryRep& ddh = (WtSLDiffHistoryRep&)dh;
00500     if (g>0 && h>0 && ddh.getC0()){
00501       int w0 = ddh.getW0()+weight[g-1]-weight[h-1];
00502       int c0 = (w0>= -getWeight(wd) ? ddh.getC0() : 0);
00503       WtSLDiffHistoryRep * dhp = new WtSLDiffHistoryRep
00504               (d,c0,w0,0,0);
00505       return dhp;
00506     }
00507     else if (g>0 && h==0){
00508       int w1;
00509       if (ddh.getC0() && ddh.getC1()){
00510         w1 = (ddh.getW0()>=ddh.getW1()? 
00511 // choose the bigger weight difference in dh 
00512 // add the weight of g to it, and then set w1 to be the minimum of that and 1
00513          (ddh.getW0()+weight[g-1]>0?1:ddh.getW0() + weight[g-1]):
00514          (ddh.getW1()+weight[g-1]>0?1:ddh.getW1() + weight[g-1]));
00515       }
00516       else if (ddh.getC0())
00517          w1 = (ddh.getW0()+weight[g-1]>0?1:ddh.getW0() + weight[g-1]);
00518       else if (ddh.getC1())
00519          w1 = (ddh.getW1()+weight[g-1]>0?1:ddh.getW1() + weight[g-1]);
00520 
00521       int c1 = (w1 >= -getWeight(wd)? 1: 0);
00522       WtSLDiffHistoryRep * dhp = new WtSLDiffHistoryRep (d,0,0,c1,w1); 
00523       return dhp;
00524     }
00525     else { 
00526       cerr << "Parameters out of range for update."<< endl;
00527       WtSLDiffHistoryRep * dhp =  new WtSLDiffHistoryRep;
00528       return dhp;
00529     }
00530   }
00531 
00532   Bool reduction(const DiffHistoryRep & dh,int g,int h) const {
00533     const WtSLDiffHistoryRep& ddh = (WtSLDiffHistoryRep&)dh;
00534     if (g>0 && h>0 && ddh.getC0()){
00535 
00536 // For some w,u wg=_G uh where wg and uh have equal length, but wg>uh. 
00537 // Either wt(wg)>wt(uh) 
00538 // or wt(wg)=wt(uh) but uh precedes wg lexicographically.
00539 
00540       if (ddh.getW0() + weight[g-1] - weight[h-1]>0 || 
00541         (ddh.getW0() + weight[g-1]-weight[h-1]==0 && ddh.getC0()==1)) 
00542            return YES;
00543     } 
00544 
00545     else if (g>0 && h==0){
00546 
00547 // For some w,u, wg=_G u, where l(wg)>l(u) and wt(wg)>=wt(u).
00548 // Either l(w)=l(u) (getC0() returns a non-zero value), so l(wg)=l(u)+1
00549 // or l(w)>l(u) (getC1() returns a non-zero value) and so certainly l(wg)>l(u)
00550 
00551       if ((ddh.getC0()!=0 && ddh.getW0() + weight[g-1] >= 0)
00552          || (ddh.getC1()!=0 && ddh.getW1() + weight[g-1] >= 0)) return YES;
00553     }
00554 
00555     return NO;
00556   }
00557 
00558   Bool possibleReduction(const AheadInfoRep & ai,int g) const { 
00559      const WtSLAheadInfoRep & aai = (WtSLAheadInfoRep &)ai;
00560      return (aai.getWtDiff() > weight[g-1]);};
00561 
00562   AheadInfoRep * update(const AheadInfoRep & ai,int g) const {
00563      const WtSLAheadInfoRep & aai = (WtSLAheadInfoRep &)ai;
00564      WtSLAheadInfoRep * aip = 
00565               new WtSLAheadInfoRep (aai.getWtDiff()-weight[g-1]); 
00566      return aip; 
00567   }
00568 
00569   DiffHistoryVtxRep * buildDiffHistoryVtxRep() const { 
00570     WtSLDiffHistoryVtxRep * dhp = new WtSLDiffHistoryVtxRep();
00571       return dhp;
00572   }
00573 
00574   DiffHistoryVtxRep * buildDiffHistoryVtxRep(State d,int g,int h) const
00575 { 
00576     if (g>0 && h>0 && g!=h){
00577       WtSLDiffHistoryVtxRep * dhp = 
00578         new WtSLDiffHistoryVtxRep(d,h,0,1,(g>h? 1: -1),weight[g-1] -
00579 weight[h-1]);
00580       return dhp;
00581     }
00582     else if (g>0 && h==0){
00583       WtSLDiffHistoryVtxRep * dhp = 
00584         new WtSLDiffHistoryVtxRep(d,0,0,1,0,weight[g-1]);
00585       return dhp;
00586     }
00587     else { 
00588       cerr << "Parameters out of range for DiffHistoryVtxRep
00589 constructor."<< endl;
00590       WtSLDiffHistoryVtxRep * dhp =  new WtSLDiffHistoryVtxRep;
00591       return dhp;
00592     }
00593   }
00594 
00595   DiffHistoryVtxRep * update
00596     (const DiffHistoryVtxRep & dh,State d,int g,int h, DiffHistoryVtx * ptr)
00597        const {
00598     const WtSLDiffHistoryVtxRep & ddh = (WtSLDiffHistoryVtxRep &)dh;
00599     if (g>0 && h>0){
00600        WtSLDiffHistoryVtxRep * dhp = new WtSLDiffHistoryVtxRep
00601               (d,h,ptr,dh.getLength()+1,ddh.getLexComp(),
00602                  ddh.getWtDiff() + weight[g-1] - weight[h-1]);
00603       return dhp;
00604     }
00605     else if (g>0 && h==0){
00606      WtSLDiffHistoryVtxRep * dhp = new WtSLDiffHistoryVtxRep
00607               (d,0,ptr,dh.getLength()+1,ddh.getLexComp(),
00608                  ddh.getWtDiff() + weight[g-1] );
00609       return dhp;
00610     }
00611     else if (g==0 && h>0){
00612      WtSLDiffHistoryVtxRep * dhp = new WtSLDiffHistoryVtxRep
00613               (d,h,ptr,dh.getLength(),ddh.getLexComp(),
00614                  ddh.getWtDiff() - weight[h-1] );
00615       return dhp;
00616     }
00617     else {
00618       cerr << "Parameters out of range in WtLexHistoryVtxRep::update()"<<endl;
00619       return new WtLexDiffHistoryVtxRep;
00620     }
00621   }
00622 
00623   Bool reduction(const DiffHistoryVtxRep & dh,int g,int h) const {
00624     const WtSLDiffHistoryVtxRep& ddh = (WtSLDiffHistoryVtxRep&)dh;
00625     if (g>0 && h>0 ){
00626 
00627 // dh corresponds to the difference w^-1u.
00628 // The function returns true if wg >uh.
00629 // if g and h are nonzero, w and u are assumed to have the same length.
00630 // if g is nonzero, and h=0, w is at least as long as u.
00631 // if h is nonzero, and g=0, u is at least as long as w.
00632 // Either wt(wg)>wt(uh) 
00633 // or wt(wg)=wt(uh) but uh precedes wg lexicographically.
00634 // or wt(w)<wt(uh) 
00635 
00636       if (ddh.getWtDiff() + weight[g-1] - weight[h-1]>0 || 
00637         (ddh.getWtDiff() + weight[g-1]-weight[h-1]==0 &&
00638                     ddh.getLexComp()==1)) 
00639            return YES;
00640     } 
00641 
00642     else if (g>0 && h==0){
00643 
00644       if (ddh.getWtDiff() + weight[g-1] >= 0)
00645          return YES;
00646     }
00647 
00648     else if (g==0 && h>0){
00649 
00650       if (ddh.getWtDiff() > weight[h-1] )
00651          return YES;
00652     }
00653 
00654     return NO;
00655   }
00656 
00657   Bool possibleReductionAhead(const DiffHistoryVtxRep & dh,int g) const { 
00658      const WtSLDiffHistoryVtxRep & ddh = (WtSLDiffHistoryVtxRep &)dh;
00659      return (ddh.getWtDiff() > weight[g-1] +1);};
00660 // Where dh represents the difference w^-1u,
00661 // if there's a possible reduction of w to some u' with ug a proper
00662 // prefix of u', w must have higher weight than some ugh,
00663 // and so weight more than one less than ug.
00664 
00665   int getWeight(int i) const { return weight[i-1];};
00666   int getWeight(Generator g) const { return weight[getPosition(g)-1];};
00667   int getWeight(const Word & w) const { 
00668     int wt=0,i=0,len=w.length();
00669     while (i<len) wt += weight[getPosition(w[i++])-1];
00670     return wt;
00671  };
00672 
00673 private:
00674   VectorOf<int> weight;
00675 };
00676 
00677 class WtLexRep : public WordOrderRep {
00678 public:
00679   WtLexRep() : WordOrderRep("WtLex"){};
00680 
00681   WtLexRep(int numOfSymbols) : 
00682     WordOrderRep("WtLex",numOfSymbols), weight(0) { 
00683     for (int i=1;i<=numOfSymbols;i++)
00684       weight.append(1);
00685   };
00686 
00687   WtLexRep(const VectorOf<int>  & w) : 
00688     WordOrderRep("WtLex",w.length()), weight(w) { 
00689   };
00690 
00691   WtLexRep(const VectorOf<int> & o,const VectorOf<int> & w) : 
00692     WordOrderRep("WtLex",o) , weight(w) {};
00693 
00694 //copy constructor
00695   WtLexRep( const WtLexRep& wsl ) : 
00696     WordOrderRep(wsl), weight(wsl.weight) { }
00697 
00698   WordOrderRep *clone() const { return new WtLexRep(*this); }
00699 
00700   int signature(const Word & w1,const Word & w2) const {  
00701     if (w1==w2) return 0; 
00702     else {
00703       int len1=w1.length();
00704       int len2=w2.length();
00705       int wt1=0;
00706       int wt2=0;
00707       int j=0;
00708       while (j<len1) wt1 += weight[getPosition(w1[j++])-1];
00709       j=0;
00710       while (j<len2) wt2 += weight[getPosition(w2[j++])-1];
00711       if (wt1<wt2) return 1; 
00712       else if (wt1>wt2) return -1; 
00713       else { 
00714         j=0;
00715         while (j<len1 && j<len2){ 
00716           if (getPosition(w1[j])<getPosition(w2[j])) return 1; 
00717           else if (getPosition(w1[j])>getPosition(w2[j])) return -1;
00718           else j++; 
00719         }
00720         // at this stage, one word is simply a prefix of the other
00721         if (len1<len2) return 1;
00722         else return -1; 
00723       }
00724     } 
00725   }
00726 
00727   int signature(int i, int j) const {
00728     if (i==j) return 0;
00729     else if (weight[i-1]<weight[j-1] || (weight[i-1]==weight[j-1] && i<j))
00730       return 1;
00731     else return -1;
00732   }
00733   int signature(Generator g, Generator h) const {
00734     return signature(getPosition(g),getPosition(h));
00735   }
00736 
00737   void balancedEquationFromRelator(const Word & w,Word & lhs,Word & rhs) const {
00738     int len=w.length();
00739     int wt1=0; int wt2=0;
00740     int i;
00741 // copy the word, replacing each g^-1 for which g is an involution by g
00742     VectorOf<Generator> W;
00743     for (i=0;i<len;i++)
00744       W.append((ord(w[i])<0 && selfInverse(inv(w[i])))? inv(w[i]) : w[i]);
00745 
00746     int j=0;
00747     while (j<len) wt1 += weight[getPosition(W[j++])-1];
00748     VectorOf<Generator> ww;
00749     j=len;
00750     while (j-->=0) {
00751       Generator g=W[j];
00752       wt1 -= weight[getPosition(g)-1];
00753       wt2 += weight[getPosition(g)-1];
00754       if  (wt1>=wt2 ) ww.append(selfInverse(g)? g : inv(g));
00755       else break;
00756     }
00757     lhs = ((Word)W).initialSegment(j+1);
00758     rhs=ww;
00759     if (signature(lhs,rhs)==1){ // lhs is smaller, so switch them
00760       rhs=lhs;
00761       lhs=ww;
00762     }
00763   }
00764 
00765   int historyBound(const VectorOf<Word> & diffs) const { 
00766     int Max=0;
00767     for (int i=0;i<diffs.length();i++){
00768       Word w=diffs[i];
00769       int len=w.length();
00770       int wt=0;
00771       for (int j=0;j<len;j++) wt += weight[getPosition(w[j])-1];
00772       if (wt>Max) Max = wt;
00773     }
00774     return Max;
00775   }
00776   DiffHistoryRep * buildDiffHistoryRep() const { 
00777     WtLexDiffHistoryRep * dhp = new WtLexDiffHistoryRep();
00778       return dhp;
00779   }
00780 
00781   DiffHistoryRep * buildDiffHistoryRep(State d,int g,int h) const { 
00782     if (g>0 && h>0 && g!=h){
00783       WtLexDiffHistoryRep * dhp = 
00784         new WtLexDiffHistoryRep(d,(g>h? 1: -1),weight[g-1] - weight[h-1],0,0);
00785       return dhp;
00786     }
00787     else if (g>0 && h==0){
00788       WtLexDiffHistoryRep * dhp = 
00789         new WtLexDiffHistoryRep(d,0,0,1,(weight[g-1]>0?1: weight[g-1]));
00790       return dhp;
00791     }
00792     else { 
00793       cerr << "Parameters out of range for DiffHistoryRep constructor."<< endl;
00794       WtLexDiffHistoryRep * dhp =  new WtLexDiffHistoryRep;
00795       return dhp;
00796     }
00797   }
00798 
00799   DiffHistoryRep * update
00800     (const DiffHistoryRep & dh,State d,int g,int h,const Word & wd) const {
00801     const WtLexDiffHistoryRep& ddh = (WtLexDiffHistoryRep&)dh;
00802     if (g>0 && h>0 && ddh.getC0()){
00803       int w0 = ddh.getW0()+weight[g-1]-weight[h-1];
00804       int c0 = (w0>= -getWeight(wd) ? ddh.getC0(): 0);
00805       WtLexDiffHistoryRep * dhp = new WtLexDiffHistoryRep
00806               (d,c0,w0,0,0);
00807       return dhp;
00808     }
00809     else if (g>0 && h==0){
00810       int c1,w1;
00811       if (ddh.getC0() && ddh.getC1()){
00812 // choose the bigger weight difference in dh 
00813 // add the weight of g to it, and then set w1 to be the minimum of that and 1
00814 // c1 is set to be ddh.getC0() if ddh.getW0()>ddh.getW1(),
00815 // to be ddh.getC1() if ddh.getW1()>ddh.getW0(), and otherwise the
00816 // larger of ddh.getC0() and ddh.getC1()
00817 
00818         if (ddh.getW0()>ddh.getW1()){
00819           w1 = (ddh.getW0()+weight[g-1]>0?1:ddh.getW0() + weight[g-1]);
00820           c1 = ddh.getC0();
00821         }
00822         else if (ddh.getW1()>ddh.getW0()){
00823           w1 = (ddh.getW1()+weight[g-1]>0?1:ddh.getW1() + weight[g-1]);
00824           c1 = ddh.getC1();
00825         }
00826         else {
00827           w1 = (ddh.getW1()+weight[g-1]>0?1:ddh.getW1() + weight[g-1]);
00828           c1 = (ddh.getC1()>=ddh.getC0()? ddh.getC1(): ddh.getC0());
00829         }
00830       }
00831       else if (ddh.getC0()){
00832          w1 = (ddh.getW0()+weight[g-1]>0?1:ddh.getW0() + weight[g-1]);
00833          c1 = ddh.getC0();
00834       }
00835       else if (ddh.getC1()){
00836          w1 = (ddh.getW1()+weight[g-1]>0?1:ddh.getW1() + weight[g-1]);
00837          c1 = ddh.getC1();
00838       } 
00839       if (w1 < -getWeight(wd)) c1=0;
00840       WtLexDiffHistoryRep * dhp = new WtLexDiffHistoryRep (d,0,0,c1,w1); 
00841       return dhp;
00842     }
00843     else { 
00844       cerr << "Parameters out of range for update."<< endl;
00845       WtLexDiffHistoryRep * dhp =  new WtLexDiffHistoryRep;
00846       return dhp;
00847     }
00848   }
00849 
00850   Bool reduction(const DiffHistoryRep & dh,int g,int h) const {
00851     const WtLexDiffHistoryRep& ddh = (WtLexDiffHistoryRep&)dh;
00852     if (g>0 && h>0 && ddh.getC0()){
00853 
00854 // For some w,u wg=_G uh where wg and uh have equal length, but wg>uh. 
00855 // Either wt(wg)>wt(uh) 
00856 // or wt(wg)=wt(uh) but uh precedes wg lexicographically.
00857 
00858       if (ddh.getW0() + weight[g-1] - weight[h-1]>0 || 
00859         (ddh.getW0() + weight[g-1]-weight[h-1]==0 && ddh.getC0()==1)) 
00860            return YES;
00861     } 
00862 
00863     else if (g>0 && h==0){
00864 
00865 // For some w,u, wg=_G u, where l(wg)>l(u),
00866 // either wt(wg)>wt(u) or wt(wg)=wt(u) but wg>u lexicographically
00867 // Either l(w)=l(u) (getC0() returns a non-zero value- if this is -1
00868 // we must have wt(wg)>wt(u))
00869 // or l(w)>l(u) (getC1() returns a non-zero value  - if this is -1
00870 // we must have wt(wg)>wt(u))
00871 
00872       if ((ddh.getC0()==1 && ddh.getW0() + weight[g-1] >= 0)
00873        || (ddh.getC0()== -1 && ddh.getW0() + weight[g-1] > 0)
00874        || (ddh.getC1()==1 && ddh.getW1() + weight[g-1] >= 0)
00875        || (ddh.getC1()== -1 && ddh.getW1() + weight[g-1] > 0))
00876           return YES;
00877     }
00878 
00879     return NO;
00880   }
00881 
00882   Bool possibleReduction(const AheadInfoRep & ai,int g) const { 
00883      const WtLexAheadInfoRep & aai = (WtLexAheadInfoRep &)ai;
00884      return (aai.getWtDiff() > weight[g-1] || 
00885         (aai.getWtDiff()==weight[g-1] && aai.getSign()==1 ));};
00886 
00887   AheadInfoRep * update(const AheadInfoRep & ai,int g) const {
00888      const WtLexAheadInfoRep & aai = (WtLexAheadInfoRep &)ai;
00889      WtLexAheadInfoRep * aip = 
00890        new WtLexAheadInfoRep (aai.getWtDiff()-weight[g-1],aai.getSign()); 
00891      return aip; 
00892   }
00893 
00894   DiffHistoryVtxRep * buildDiffHistoryVtxRep() const { 
00895     WtLexDiffHistoryVtxRep * dhp = new WtLexDiffHistoryVtxRep();
00896       return dhp;
00897   }
00898 
00899   DiffHistoryVtxRep * buildDiffHistoryVtxRep(State d,int g,int h) const { 
00900     if (g>0 && h>0 && g!=h){
00901       WtLexDiffHistoryVtxRep * dhp = 
00902         new WtLexDiffHistoryVtxRep(d,h,0,1,(g>h? 1: -1),weight[g-1] -
00903 weight[h-1]);
00904       return dhp;
00905     }
00906     else if (g>0 && h==0){
00907       WtLexDiffHistoryVtxRep * dhp = 
00908         new WtLexDiffHistoryVtxRep(d,0,0,1,0,weight[g-1]);
00909       return dhp;
00910     }
00911     else { 
00912       cerr << 
00913 "Parameters out of range for DiffHistoryVtxRep constructor."<< endl;
00914       WtLexDiffHistoryVtxRep * dhp =  new WtLexDiffHistoryVtxRep;
00915       return dhp;
00916     }
00917   }
00918 
00919   DiffHistoryVtxRep * update
00920     (const DiffHistoryVtxRep & dh,State d,int g,int h, DiffHistoryVtx * ptr) const {
00921     const WtLexDiffHistoryVtxRep& ddh = (WtLexDiffHistoryVtxRep&)dh;
00922     if (g>0 && h>0){
00923      WtLexDiffHistoryVtxRep * dhp = new WtLexDiffHistoryVtxRep
00924        (d,h,ptr,dh.getLength()+1,ddh.getLexComp(),
00925                ddh.getWtDiff()+weight[g-1] - weight[h-1]);
00926       return dhp;
00927     }
00928     else if (g>0 && h==0){
00929      WtLexDiffHistoryVtxRep * dhp = new WtLexDiffHistoryVtxRep
00930        (d,0,ptr,dh.getLength()+1,ddh.getLexComp(),
00931                ddh.getWtDiff()+weight[g-1]);
00932       return dhp;
00933     }
00934     else if (g==0 && h>0){ 
00935      WtLexDiffHistoryVtxRep * dhp = new WtLexDiffHistoryVtxRep
00936        (d,h,ptr,dh.getLength(),ddh.getLexComp(),
00937                ddh.getWtDiff()-weight[h-1]);
00938       return dhp;
00939     }
00940     else {
00941       cerr << "Parameters out of range in WtLexHistoryVtxRep::update()"<<endl;
00942       return new WtLexDiffHistoryVtxRep;
00943     }
00944   }
00945 
00946   Bool reduction(const DiffHistoryVtxRep & dh,int g,int h) const {
00947     const WtLexDiffHistoryVtxRep& ddh = (WtLexDiffHistoryVtxRep&)dh;
00948 // dh corresponds to the difference w^-1u.
00949 // The function returns true if wg >uh.
00950 // if g and h are nonzero, w and u are assumed to have the same length.
00951 // if g is nonzero, and h=0, w is at least as long as u.
00952 // if h is nonzero, and g=0, u is at least as long as w.
00953     if (g>0 && h>0){
00954       if (ddh.getWtDiff() + weight[g-1] - weight[h-1]>0 || 
00955         (ddh.getWtDiff() + weight[g-1]-weight[h-1]==0 &&
00956            ddh.getLexComp()==1)) 
00957            return YES;
00958     } 
00959 
00960     else if (g>0 && h==0){
00961       if (ddh.getWtDiff() + weight[g-1]>0 || 
00962         (ddh.getWtDiff() + weight[g-1]==0 &&
00963                ddh.getLexComp()==1)) 
00964           return YES;
00965     }
00966 
00967     else if (g==0 && h>0){
00968       if (ddh.getWtDiff() > weight[h-1] || 
00969         (ddh.getWtDiff() -weight[h-1]==0 &&
00970                ddh.getLexComp()==1)) 
00971           return YES;
00972     }
00973 
00974     return NO;
00975   }
00976 
00977   Bool possibleReductionAhead(const DiffHistoryVtxRep & dh,int g) const { 
00978      const WtLexDiffHistoryVtxRep & ddh = (WtLexDiffHistoryVtxRep &)dh;
00979      return (ddh.getWtDiff() > weight[g-1] +2||
00980        (ddh.getWtDiff()==weight[g-1]+1&& ddh.getLexComp()==1));};
00981 // Where dh represents the difference w^-1u,
00982 // if there's a possible reduction of w to some u' with ug a proper
00983 // prefix of u', w must either have higher weight than some ugh,
00984 // and so weight more than one less than ug, or the same weight
00985 // as some ugh which it precedes lexicographically.
00986 
00987   int getWeight(int i) const { return weight[i-1];};
00988   int getWeight(Generator g) const { return weight[getPosition(g)-1];};
00989   int getWeight(const Word & w) const { 
00990     int wt=0,i=0,len=w.length();
00991     while (i<len) wt += weight[getPosition(w[i++])-1];
00992     return wt;
00993  };
00994 
00995 private:
00996   VectorOf<int> weight;
00997 };
00998 
00999 
01000 class InvPairWreathRep : public WordOrderRep {
01001 public:
01002   InvPairWreathRep() : WordOrderRep("InvPairWreath") {};
01003 
01004   InvPairWreathRep(const VectorOf<int> & o) : WordOrderRep("InvPairWreath",o) {};
01005 
01006 
01007   //int signature(const Word & w1,const Word & w2) const { return 1; } 
01008   // define this properly
01009 
01010   int signature(int g, int h) const { return 1; } //  temporary
01011 
01012 };
01013 
01014 #endif

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