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

/magnus/back_end/KB/include/DiffHistory.h

Go to the documentation of this file.
00001 /*
00002  *   $Id: DiffHistory.h,v 1.1 1996/08/15 18:55:35 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 DiffHistory class.
00009 //
00010 // Principal Author: Sarah Rees
00011 //
00012 // Status: in progress
00013 //
00014 // Revision History:
00015 //
00016 
00017 #ifndef _DiffHistory_H_
00018 #define _DiffHistory_H_
00019 
00020 #include "Word.h"
00021 #include "Vector.h"
00022 // #include "DFSARep.h"
00023 typedef int State; 
00024 #include "DiffHistoryRep.h"
00025 #include "WordOrder.h"
00026 // @sr for now this file needs to be independent of DFSARep.
00027 // So for now we'll typedef State to be int, but that's only temporary.
00028 // That's because a declaration of SetOf<DiffHistory> is necessary in Set.C
00029 // and that can't be dependent on the FSA hierarchy.
00030 // If that weren't necessary, this could all be in DiffMachineRep.h
00031 
00032 // A DiffHistory consists of a word difference d together with additional 
00033 // information about its origin.
00034 // A word difference  corresponds to a state of the difference
00035 // machine used for word reduction and to construct the automata for
00036 // an automatic group, and also to a word equal in the group
00037 // to some products w^-1u, for pairs of words w,u. The additional
00038 // information relates to those pairs w,u associated with d which are
00039 // relevant in the particular context in which the word difference is
00040 // being used. The whole point of carrying this information is to
00041 // find out whether for some such w,u, w is a prefix of some w' and u a prefix
00042 // of some u' where w'>u' in the word ordering.
00043 // For different word orders, different information needs to be attached
00044 // to a word difference, therefore there are different types of DiffHistories
00045 // for different word orders.
00046 
00047 class DiffHistory : public ObjectOf<DiffHistoryRep> {
00048 public:
00049 //constructor
00050   DiffHistory() : 
00051     ObjectOf< DiffHistoryRep > (new DiffHistoryRep()){};
00052   DiffHistory(const WordOrder & word_order) : 
00053   ObjectOf<DiffHistoryRep> ( word_order.buildDiffHistoryRep() ){};
00054   DiffHistory(State d,int g,int h,const WordOrder & word_order) : 
00055   ObjectOf<DiffHistoryRep> ( word_order.buildDiffHistoryRep(d,g,h) ){};
00056   DiffHistory
00057     (const DiffHistory & dh,State d,int g,int h,const Word & wd,const WordOrder & word_order) :
00058   ObjectOf<DiffHistoryRep> (word_order.update(*dh.look(),d,g,h,wd) )
00059   {};
00060 //hash function
00061   int hash() const {return look()->hash();};
00062 
00063   Bool empty() const { return look()->empty();};
00064   State getDiff() const {return look()->getDiff();};
00065   int operator == ( const DiffHistory & dh ) const {
00066          return ((look() == dh.look()) || (*look() == *dh.look()));
00067   }
00068 
00069   int operator != ( const DiffHistory & dh ) const { return !( *this == dh ); }
00070 
00071   Bool sameLengthWords() const 
00072 // return yes if the difference histroy contains a pair of words w,u
00073 // of the same length
00074   {return look()->sameLengthWords();} ;
00075 
00076 
00077   void improveBy(const DiffHistory & dh) {
00078 // add to the current difference history any information held by the DiffHistory
00079 // dh which improves it.
00080     change()->improveBy(*dh.look());
00081   };
00082 
00083   Bool reduction(int g,int h,const WordOrder & word_order) const
00084 // returns yes if for some pair of words w,u in the difference history of d,
00085 // wg reduces to uh, where uh is earlier than wg in the word order
00086     { return word_order.reduction(*look(),g,h);}
00087 
00088   Bool possibleReductionAhead() const
00089 // returns yes if it is possible (i.e. cannot be immediately ruled out) that
00090 // for some pair of words w,u in the difference history of d,
00091 // w reduces to some longer word uH, which precedes it in the word order.
00092     { return look()->possibleReductionAhead();}
00093 
00094   AheadInfoRep *  buildAheadInfoRep() const
00095     { return look()->buildAheadInfoRep();}
00096 
00097   void printOn(ostream &str = cout) const { look()->printOn(str); }
00098 
00099   inline friend ostream& operator << 
00100         ( ostream& ostr, const DiffHistory& dh ) {
00101     dh.look()->printOn(ostr);
00102     return ostr;
00103   }
00104 
00105 protected:
00106   typedef ObjectOf<DiffHistoryRep> R;
00107   DiffHistory( DiffHistoryRep *p ) : R(p) {}
00108 };
00109 
00110 // AheadInfo hierarchy is used in situations where it is necessary to
00111 // look ahead. More precisely, we use this to invesigate the possibility
00112 // that, where a given word difference d is associated with a pair of words w,u
00113 // (such that d=_G w^-1u), w is equal in the group G to a word u', of which
00114 // u is a prefix, which is longer than w, but less than it in the word ordering.
00115 
00116 class AheadInfo : public ObjectOf<AheadInfoRep> {
00117 public:
00118 //constructor
00119   AheadInfo() : 
00120     ObjectOf< AheadInfoRep > (new AheadInfoRep()){};
00121   AheadInfo(const DiffHistory & dh) : 
00122   ObjectOf<AheadInfoRep> ( dh.buildAheadInfoRep() ){};
00123   AheadInfo
00124     (const AheadInfo & ai,int g,const WordOrder & word_order) :
00125   ObjectOf<AheadInfoRep> (word_order.update(*ai.look(),g) ){};
00126   Bool possibleReduction(int g,const WordOrder & word_order) const
00127 // returns yes if it is possible (i.e. cannot be immediately ruled out) that
00128 // there is a reduction of w to the longer word got by adding g to the word currently stored.
00129     { return word_order.possibleReduction(*look(),g);}
00130 
00131 protected:
00132   typedef ObjectOf<AheadInfoRep> R;
00133   AheadInfo( AheadInfoRep *p ) : R(p) {}
00134 };
00135 
00136 class DiffHistoryVtx : public ObjectOf<DiffHistoryVtxRep> {
00137 
00138 public:
00139 //constructor
00140   DiffHistoryVtx() : 
00141     ObjectOf< DiffHistoryVtxRep > (new DiffHistoryVtxRep()){};
00142   DiffHistoryVtx(const WordOrder & word_order) : 
00143   ObjectOf<DiffHistoryVtxRep> 
00144     (word_order.buildDiffHistoryVtxRep() ){};
00145   DiffHistoryVtx(State d,int g,int h,const WordOrder & word_order)
00146     :ObjectOf<DiffHistoryVtxRep>
00147             ( word_order.buildDiffHistoryVtxRep(d,g,h)){};
00148   DiffHistoryVtx
00149     (DiffHistoryVtx * dhp,State d,int g,int h,const WordOrder & word_order) :
00150   ObjectOf<DiffHistoryVtxRep> (word_order.update(*(dhp->look()),d,g,h,dhp) )
00151   {};
00152  
00153   Bool reduction(int g,int h,const WordOrder & word_order) const
00154 // returns yes if, where this vertex corresponds to d=w^-1u,
00155 // wg reduces to uh, where uh is earlier than wg in the word order
00156     { return word_order.reduction(*look(),g,h);}
00157 
00158   Trichotomy betterThan(DiffHistoryVtx* dhp) const
00159 // Only to be called if the word differences match.
00160 // If the word differences match,
00161 // returns yes if whenever *dhp predicts a reduction, the current
00162 // DiffHistoryVtx predicts one too and there could be situations
00163 // where the current DiffHistoryVtx predicts a reduction but *dhp 
00164 // does not, no if *dhp predicts a
00165 // reduction whenever the current DiffHistoryVtx does,
00166 // dontknow if neither of the above is true (or it seems too much work 
00167 // to find out).
00168     { return look()->betterThan(*(dhp->look()));}
00169 
00170   Bool possibleReductionAhead() const
00171 // returns yes if, where this vertex corresponds to d=w^-1u,
00172 // it is possible that
00173 // w reduces to some longer word uH, which precedes it in the word order.
00174     { return look()->possibleReductionAhead();}
00175 
00176   Bool possibleReductionAhead(int g,const WordOrder & word_order) const
00177 // returns yes if, where this vertex corresponds to d=w^-1u,
00178 // and given that wg does not reduce, it is possible that
00179 // w reduces to some longer word ugH (H non-trivial), which 
00180 // precedes it in the word order.
00181     { return word_order.possibleReductionAhead(*look(),g);}
00182 
00183   void printOn(ostream &str = cout) const {
00184     look()->printOn(str); }
00185 
00186   inline friend ostream& operator << 
00187         ( ostream& ostr, const DiffHistoryVtx& dh ) {
00188     dh.look()->printOn(ostr);
00189     return ostr;
00190   }
00191   State getDiff() const {return look()->getDiff();};
00192   int getGenerator() const { return look()->getGenerator();}
00193   DiffHistoryVtx *getBackptr() const { return look()->getBackptr();}
00194   int getLength() const { return look()->getLength();}
00195 protected:
00196   typedef ObjectOf<DiffHistoryVtxRep> R;
00197   DiffHistoryVtx( DiffHistoryVtxRep *p ) : R(p) {}
00198 };
00199 
00200  #endif

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