Show WordOrderRep.h syntax highlighted
// Copyright (C) 1994 The New York Group Theory Cooperative
// See magnus/doc/COPYRIGHT for the full notice.
// Contents: Definition of WordOrderRep and related classes.
//
// Principal Author: Sarah Rees
//
// Status: in progress
//
// Revision History:
//
#ifndef _WordOrderRep_H_
#define _WordOrderRep_H_
#include "Word.h"
#include "Vector.h"
#include "RefCounter.h"
// #include "DFSARep.h"
#include "Set.h"
#include "DiffHistoryRep.h"
typedef int State;
// @sr for now this file needs to be independent of DFSARep.
// So for now we'll typedef State to be int, but that's only temporary.
// That's because a declaration of SetOf<DiffHistory> is necessary in Set.C
// (for each of the various DiffHistory types)
// and that can't be dependent on the FSA hierarchy.
class WordOrderRep : public RefCounter {
public:
//constructors
WordOrderRep() {};
WordOrderRep(const Chars & oType ) : orderType(oType),numSyms(0), order(0),
posn(0), invposn(0) {};
WordOrderRep(const VectorOf<int> & o) : numSyms(o.length()), order(o),
posn(o.length()), invposn(o.length()) {
int i;
for (i=0;i<numSyms;i++){
posn[i]=0; invposn[i]=0;
// We MUST initialise invposn to be zero, since entries which
// remain set to zero indicate involutions
}
for (i=1;i<=numSyms;i++){
int j = order[i-1];
if (j>0) posn[j-1]=i; else invposn[-j-1]=i;
}
};
WordOrderRep(int numOfSymbols) : numSyms(numOfSymbols), order(0),
posn(0), invposn(0) {
int ngens = numOfSymbols/2;
for (int i=1;i<=ngens;i++){
order.append(i);
order.append(-i);
posn.append(2*i-1);
invposn.append(2*i);
}
}
WordOrderRep(const Chars & oType, int numOfSymbols) :
orderType(oType), numSyms(numOfSymbols), order(0), posn(0), invposn(0) {
for (int i=1;i<=numOfSymbols/2;i++){
order.append(i);
order.append(-i);
posn.append(2*i-1);
invposn.append(2*i);
}
};
WordOrderRep(const Chars & oType, const VectorOf<int> & o) :
orderType(oType), numSyms(o.length()), order(o), posn(o.length()),
invposn(o.length()) {
int i;
for (i=0;i<numSyms;i++){
posn[i]=0; invposn[i]=0;
// We MUST initialise invposn to be zero, since entries which
// remain set to zero indicate involutions
}
for (i=1;i<=numSyms;i++){
int j = order[i-1];
if (j>0) posn[j-1]=i; else invposn[-j-1]=i;
}
};
// copy constructor
WordOrderRep (const WordOrderRep & word_order) {
order=word_order.order;
orderType = word_order.orderType;
numSyms = word_order.numSyms;
posn = word_order.posn;
invposn = word_order.invposn;
};
virtual WordOrderRep *clone() const {};
//destructor
~WordOrderRep() {};
virtual int signature(const Word & w1,const Word & w2) const {return 1;};
virtual int signature(int i, int j) const {return 1;};
virtual int signature(Generator g,Generator h) const {return 1;};
virtual void balancedEquationFromRelator
(const Word & w,Word & lhs,Word & rhs) const {};
virtual int historyBound(const VectorOf<Word> & diffs) const{ return 0;}
virtual DiffHistoryRep * buildDiffHistoryRep() const {};
virtual DiffHistoryRep * buildDiffHistoryRep(State d,int g,int h) const {};
// build a difference history for the word difference g^-1h, attached
// to state d of the difference machine.
virtual DiffHistoryRep * update
(const DiffHistoryRep & dh,State d,int g,int h,const Word & wd) const {};
// Given a difference history dh associated with pairs of words w,u,
// construct the difference history associated with pairs wg,uh and the
// state d of the difference machine (which is of course the target
// of the state for dh under the pair of symbols (g,h))
virtual Bool reduction(const DiffHistoryRep & dh,int g,int h) const {};
// returns YES if the difference history contains a pair w,u of words
// such that wg=_G uh and uh < wg in the word order.
virtual Bool possibleReduction(const AheadInfoRep & ai,int g) const {};
// returns YES if it is possible (i.e. cannot yet be ruled out)
// that there is a reduction to a longer word.
virtual AheadInfoRep * update(const AheadInfoRep & ai,int g) const {};
virtual DiffHistoryVtxRep * buildDiffHistoryVtxRep() const {};
virtual DiffHistoryVtxRep
* buildDiffHistoryVtxRep(State d,int g,int h) const {};
// build a difference history Vtx for the word difference g^-1h,
// attached to state d of the difference machine.
virtual DiffHistoryVtxRep * update
(const DiffHistoryVtxRep & dh,State d, int g, int h, DiffHistoryVtx * ptr)
const {};
// Given a difference history vertex dh associated with pairs of
//words w,u,
// construct the difference history Vtx associated with
// pairs wg,uh and the
// state d of the difference machine (which is of course thetarget
// of the state for dh under the pair of symbols (g,h))
virtual Bool reduction(const DiffHistoryVtxRep & dh,int g,int h)
const {};
// returns YES if the difference history contains a pair w,uof words
// such that wg=_G uh and uh < wg in the word order.
virtual Bool possibleReductionAhead(const DiffHistoryVtxRep & dh,int g)
const {};
// returns YES if it is possible (i.e. cannot yet be ruled out)
// that there is a reduction of w to a longer word, with ug as a
// proper prefix.
Chars getOrderType() const { return orderType; }
int getNumSymbols() const { return numSyms; }
int getSymbolIndex(int i) const { return order[i-1];}
Generator getSymbol(int i) const { Generator g(order[i-1]); return g; }
int getPosition(Generator g) const {
return (ord(g)>0? posn[ord(g)-1]: invposn[-ord(g)-1]);
} // returns 0 if the generator isn't in the alphabet
Word inverse(const Word & w) const{
int len = w.length();
VectorOf<Generator> W(len);
for (int i=0; i<len;i++)
W[i]= (selfInverse(w[len-1-i])? w[len-1-i]: inv(w[len-1-i]));
return (Word)W;
}
// Returns yes if the inverse generator is not a symbol.
// It doesn't make sense to call this unless ord(g) is positive
// but this is checked to avoid crashes.
Bool selfInverse(Generator g) const {
return (ord(g)>0 && invposn[ord(g)-1]==0);
}
virtual int getWeight(int i) const { return 1;};
virtual int getWeight(Generator g) const { return 1;};
virtual int getWeight(const Word & w) const { return w.length();};
protected:
VectorOf<int> order;
VectorOf<int> posn; // posn[i] stores position in order of generator
// indexed by i, as a number in range 1..numSyms
VectorOf<int> invposn; // invposn[i] stores position in order of generator
// indexed by -i, as a number in range 1..numSyms
int numSyms;
private:
Chars orderType;
};
class ShortLexRep : public WordOrderRep {
public:
ShortLexRep() : WordOrderRep("ShortLex") {};
ShortLexRep(const VectorOf<int> & o) : WordOrderRep("ShortLex",o) { };
ShortLexRep(int numOfSymbols) : WordOrderRep("ShortLex",numOfSymbols) { };
//copy constructor
ShortLexRep( const ShortLexRep& wsl ) :
WordOrderRep(wsl) { }
WordOrderRep *clone() const { return new ShortLexRep(*this); }
int signature(const Word & w1,const Word & w2) const {
if (w1==w2) return 0;
else if (w1.length()<w2.length()) return 1;
else if (w1.length()>w2.length()) return -1;
else {
int j=0;
while (j<w1.length()){
if (getPosition(w1[j])<getPosition(w2[j])) return 1;
else if (getPosition(w1[j])>getPosition(w2[j])) return -1;
else j++;
}
}
}
int signature(int i, int j) const {
if (i==j) return 0;
else if (i<j) return 1;
else return -1;
}
int signature(Generator g,Generator h) const {
return signature(getPosition(g),getPosition(h));
}
void balancedEquationFromRelator(const Word & w,Word & lhs,Word & rhs) const {
// This code is complicated by the fact that we have to make sure that
// neither side of the equation contains the inverse symbol of an involution
// if that's not in our alphabet. We might even have got such symbols into
// the relation, because of the way magnus turns relations in input into
// relators
int len=w.length();
int i;
int len2=len - (len+1)/2;
// copy the word, replacing each g^-1 for which g is an involution by g
VectorOf<Generator> W;
for (i=0;i<len;i++)
W.append((ord(w[i])<0 && selfInverse(inv(w[i])))? inv(w[i]) : w[i]);
lhs=((Word)W).initialSegment((len+1)/2);
VectorOf<Generator> ww;
for (i=1;i<=len2;i++){
Generator g = W[len-i];
ww.append(selfInverse(g)? g : inv(g));
}
rhs=ww;
if (signature(lhs,rhs)==1){ // lhs is smaller, so switch them
rhs=lhs;
lhs=ww;
}
}
int historyBound(const VectorOf<Word> & diffs) const{ return 0;}
DiffHistoryRep * buildDiffHistoryRep() const {
SLDiffHistoryRep * dhp = new SLDiffHistoryRep();
return dhp;
}
DiffHistoryRep * buildDiffHistoryRep(State d,int g,int h) const {
if (g>0 && h>0 && g!=h){
SLDiffHistoryRep * dhp =
new SLDiffHistoryRep(d,(g>h? 1: -1),0);
return dhp;
}
else if (g>0 && h==0){
SLDiffHistoryRep * dhp = new SLDiffHistoryRep(d,0,1);
return dhp;
}
else {
std::cerr << "Parameters out of range for DiffHistoryRep constructor."<< std::endl;
SLDiffHistoryRep * dhp = new SLDiffHistoryRep;
return dhp;
}
}
DiffHistoryRep * update
(const DiffHistoryRep & dh,State d,int g,int h,const Word & wd) const {
// the parameter wd isn't actually used in the function for a ShortLex
// DiffHistory, but the generality of the code requres it to be a parameter
const SLDiffHistoryRep& ddh = (SLDiffHistoryRep&)dh;
if (g>0 && h>0 && ddh.getC0()){
SLDiffHistoryRep * dhp = new SLDiffHistoryRep
(d,ddh.getC0(),0);
return dhp;
}
else if (g>0 && h==0){
SLDiffHistoryRep * dhp = new SLDiffHistoryRep (d,0,1);
return dhp;
}
else {
std::cerr << "Parameters out of range for update."<< std::endl;
SLDiffHistoryRep * dhp = new SLDiffHistoryRep;
return dhp;
}
}
Bool reduction(const DiffHistoryRep & dh,int g,int h) const {
const SLDiffHistoryRep& ddh = (SLDiffHistoryRep&)dh;
if (g>0 && h>0 && ddh.getC0()==1){
return YES;
}
else if (g>0 && h==0) return YES;
return NO;
}
Bool possibleReduction(const AheadInfoRep & ai,int g) const {
return NO;
};
AheadInfoRep * update(const AheadInfoRep & ai,int g) const {
// this function won't actually get used, since it is not possible
// in shortlex to have w>u where w is shorter than u.
// It is necessary to have a function returning something of the right
// type to get compilation.
return new SLAheadInfoRep (); }
DiffHistoryVtxRep * buildDiffHistoryVtxRep() const {
SLDiffHistoryVtxRep * dhp = new SLDiffHistoryVtxRep();
return dhp;
}
DiffHistoryVtxRep
* buildDiffHistoryVtxRep(State d,int g,int h) const
{
if (g>0 && h>0 && g!=h){
SLDiffHistoryVtxRep * dhp =
new SLDiffHistoryVtxRep(d,h,0,1,(g>h? 1: -1));
return dhp;
}
else if (g>0 && h==0){
SLDiffHistoryVtxRep * dhp = new
SLDiffHistoryVtxRep(d,0,0,1,0);
return dhp;
}
else {
std::cerr <<
"Parameters out of range for DiffHistoryVtxRep constructor."
<< std::endl;
SLDiffHistoryVtxRep * dhp = new SLDiffHistoryVtxRep;
return dhp;
}
}
DiffHistoryVtxRep * update
(const DiffHistoryVtxRep & dh,State d,int g,int h, DiffHistoryVtx * ptr)
const {
const SLDiffHistoryVtxRep & ddh = (SLDiffHistoryVtxRep &)dh;
SLDiffHistoryVtxRep * dhp = new SLDiffHistoryVtxRep
(d,h,ptr,dh.getLength()+1,ddh.getLexComp());
return dhp;
}
Bool reduction(const DiffHistoryVtxRep & dh,int g,int h) const {
const SLDiffHistoryVtxRep& ddh = (SLDiffHistoryVtxRep&)dh;
if (g>0 && (h==0 || ddh.getLexComp()==1)) return YES;
else return NO;
}
Bool possibleReduction(const DiffHistoryVtxRep & dh,int g) const {
return NO;
};
int getWeight(int i) const { return 1;};
int getWeight(Generator g) const { return 1;};
int getWeight(const Word & w) const { return w.length();};
};
class WtShortLexRep : public WordOrderRep {
public:
WtShortLexRep() : WordOrderRep("WtShortLex"){};
WtShortLexRep(int numOfSymbols) :
WordOrderRep("WtShortLex",numOfSymbols), weight(0) {
for (int i=1;i<=numOfSymbols;i++)
weight.append(1);
};
WtShortLexRep(const VectorOf<int> & w) :
WordOrderRep("WtShortLex",w.length()), weight(w) {
};
WtShortLexRep(const VectorOf<int> & o,const VectorOf<int> & w) :
WordOrderRep("WtShortLex",o) , weight(w) {};
//copy constructor
WtShortLexRep( const WtShortLexRep& wsl ) :
WordOrderRep(wsl), weight(wsl.weight) { }
WordOrderRep *clone() const { return new WtShortLexRep(*this); }
int signature(const Word & w1,const Word & w2) const {
if (w1==w2) return 0;
else {
int len1=w1.length();
int len2=w2.length();
int wt1=0;
int wt2=0;
int j=0;
while (j<len1) wt1 += weight[getPosition(w1[j++])-1];
j=0;
while (j<len2) wt2 += weight[getPosition(w2[j++])-1];
if (wt1<wt2) return 1;
else if (wt1>wt2) return -1;
else if (w1.length()<w2.length()) return 1;
else if (w1.length()>w2.length()) return -1;
else {
j=0;
while (j<len1){
if (getPosition(w1[j])<getPosition(w2[j])) return 1;
else if (getPosition(w1[j])>getPosition(w2[j])) return -1;
else j++;
}
}
}
}
int signature(int i, int j) const {
if (i==j) return 0;
else if (weight[i-1]<weight[j-1] || (weight[i-1]==weight[j-1] && i<j))
return 1;
else return -1;
}
int signature(Generator g,Generator h) const {
return signature(getPosition(g),getPosition(h));
}
void balancedEquationFromRelator(const Word & w,Word & lhs,Word & rhs) const {
int len=w.length();
int i;
int wt1=0; int wt2=0;
// copy the word, replacing each g^-1 for which g is an involution by g
VectorOf<Generator> W;
for (i=0;i<len;i++)
W.append((ord(w[i])<0 && selfInverse(inv(w[i])))? inv(w[i]) : w[i]);
int j=0;
while (j<len) wt1 += weight[getPosition(W[j++])-1];
VectorOf<Generator> ww;
j=len;
while (--j>=0) {
Generator g=W[j];
wt1 -= weight[getPosition(g)-1];
wt2 += weight[getPosition(g)-1];
if (wt1>=wt2 ) ww.append(selfInverse(g)? g : inv(g));
else break;
}
lhs = ((Word)W).initialSegment(j+1);
rhs=ww;
if (signature(lhs,rhs)==1){ // lhs is smaller, so switch them
rhs=lhs;
lhs=ww;
}
}
int historyBound(const VectorOf<Word> & diffs) const {
int Max=0;
for (int i=0;i<diffs.length();i++){
Word w=diffs[i];
int len=w.length();
int wt=0;
for (int j=0;j<len;j++) wt += weight[getPosition(w[j])-1];
if (wt>Max) Max = wt;
}
return Max;
}
DiffHistoryRep * buildDiffHistoryRep() const {
WtSLDiffHistoryRep * dhp = new WtSLDiffHistoryRep();
return dhp;
}
DiffHistoryRep * buildDiffHistoryRep(State d,int g,int h) const {
if (g>0 && h>0 && g!=h){
WtSLDiffHistoryRep * dhp =
new WtSLDiffHistoryRep(d,(g>h? 1: -1),weight[g-1] - weight[h-1],0,0);
return dhp;
}
else if (g>0 && h==0){
WtSLDiffHistoryRep * dhp =
new WtSLDiffHistoryRep(d,0,0,1,(weight[g-1]>0?1: weight[g-1]));
return dhp;
}
else {
std::cerr << "Parameters out of range for DiffHistoryRep constructor."<< std::endl;
WtSLDiffHistoryRep * dhp = new WtSLDiffHistoryRep;
return dhp;
}
}
DiffHistoryRep * update
(const DiffHistoryRep & dh,State d,int g,int h,const Word & wd) const {
const WtSLDiffHistoryRep& ddh = (WtSLDiffHistoryRep&)dh;
if (g>0 && h>0 && ddh.getC0()){
int w0 = ddh.getW0()+weight[g-1]-weight[h-1];
int c0 = (w0>= -getWeight(wd) ? ddh.getC0() : 0);
WtSLDiffHistoryRep * dhp = new WtSLDiffHistoryRep
(d,c0,w0,0,0);
return dhp;
}
else if (g>0 && h==0){
int w1;
if (ddh.getC0() && ddh.getC1()){
w1 = (ddh.getW0()>=ddh.getW1()?
// choose the bigger weight difference in dh
// add the weight of g to it, and then set w1 to be the minimum of that and 1
(ddh.getW0()+weight[g-1]>0?1:ddh.getW0() + weight[g-1]):
(ddh.getW1()+weight[g-1]>0?1:ddh.getW1() + weight[g-1]));
}
else if (ddh.getC0())
w1 = (ddh.getW0()+weight[g-1]>0?1:ddh.getW0() + weight[g-1]);
else if (ddh.getC1())
w1 = (ddh.getW1()+weight[g-1]>0?1:ddh.getW1() + weight[g-1]);
int c1 = (w1 >= -getWeight(wd)? 1: 0);
WtSLDiffHistoryRep * dhp = new WtSLDiffHistoryRep (d,0,0,c1,w1);
return dhp;
}
else {
std::cerr << "Parameters out of range for update."<< std::endl;
WtSLDiffHistoryRep * dhp = new WtSLDiffHistoryRep;
return dhp;
}
}
Bool reduction(const DiffHistoryRep & dh,int g,int h) const {
const WtSLDiffHistoryRep& ddh = (WtSLDiffHistoryRep&)dh;
if (g>0 && h>0 && ddh.getC0()){
// For some w,u wg=_G uh where wg and uh have equal length, but wg>uh.
// Either wt(wg)>wt(uh)
// or wt(wg)=wt(uh) but uh precedes wg lexicographically.
if (ddh.getW0() + weight[g-1] - weight[h-1]>0 ||
(ddh.getW0() + weight[g-1]-weight[h-1]==0 && ddh.getC0()==1))
return YES;
}
else if (g>0 && h==0){
// For some w,u, wg=_G u, where l(wg)>l(u) and wt(wg)>=wt(u).
// Either l(w)=l(u) (getC0() returns a non-zero value), so l(wg)=l(u)+1
// or l(w)>l(u) (getC1() returns a non-zero value) and so certainly l(wg)>l(u)
if ((ddh.getC0()!=0 && ddh.getW0() + weight[g-1] >= 0)
|| (ddh.getC1()!=0 && ddh.getW1() + weight[g-1] >= 0)) return YES;
}
return NO;
}
Bool possibleReduction(const AheadInfoRep & ai,int g) const {
const WtSLAheadInfoRep & aai = (WtSLAheadInfoRep &)ai;
return (aai.getWtDiff() > weight[g-1]);};
AheadInfoRep * update(const AheadInfoRep & ai,int g) const {
const WtSLAheadInfoRep & aai = (WtSLAheadInfoRep &)ai;
WtSLAheadInfoRep * aip =
new WtSLAheadInfoRep (aai.getWtDiff()-weight[g-1]);
return aip;
}
DiffHistoryVtxRep * buildDiffHistoryVtxRep() const {
WtSLDiffHistoryVtxRep * dhp = new WtSLDiffHistoryVtxRep();
return dhp;
}
DiffHistoryVtxRep * buildDiffHistoryVtxRep(State d,int g,int h) const
{
if (g>0 && h>0 && g!=h){
WtSLDiffHistoryVtxRep * dhp =
new WtSLDiffHistoryVtxRep(d,h,0,1,(g>h? 1: -1),weight[g-1] -
weight[h-1]);
return dhp;
}
else if (g>0 && h==0){
WtSLDiffHistoryVtxRep * dhp =
new WtSLDiffHistoryVtxRep(d,0,0,1,0,weight[g-1]);
return dhp;
}
else {
std::cerr << "Parameters out of range for DiffHistoryVtxRep constructor."<< std::endl;
WtSLDiffHistoryVtxRep * dhp = new WtSLDiffHistoryVtxRep;
return dhp;
}
}
DiffHistoryVtxRep * update
(const DiffHistoryVtxRep & dh,State d,int g,int h, DiffHistoryVtx * ptr)
const {
const WtSLDiffHistoryVtxRep & ddh = (WtSLDiffHistoryVtxRep &)dh;
if (g>0 && h>0){
WtSLDiffHistoryVtxRep * dhp = new WtSLDiffHistoryVtxRep
(d,h,ptr,dh.getLength()+1,ddh.getLexComp(),
ddh.getWtDiff() + weight[g-1] - weight[h-1]);
return dhp;
}
else if (g>0 && h==0){
WtSLDiffHistoryVtxRep * dhp = new WtSLDiffHistoryVtxRep
(d,0,ptr,dh.getLength()+1,ddh.getLexComp(),
ddh.getWtDiff() + weight[g-1] );
return dhp;
}
else if (g==0 && h>0){
WtSLDiffHistoryVtxRep * dhp = new WtSLDiffHistoryVtxRep
(d,h,ptr,dh.getLength(),ddh.getLexComp(),
ddh.getWtDiff() - weight[h-1] );
return dhp;
}
else {
std::cerr << "Parameters out of range in WtLexHistoryVtxRep::update()"<<std::endl;
return new WtLexDiffHistoryVtxRep;
}
}
Bool reduction(const DiffHistoryVtxRep & dh,int g,int h) const {
const WtSLDiffHistoryVtxRep& ddh = (WtSLDiffHistoryVtxRep&)dh;
if (g>0 && h>0 ){
// dh corresponds to the difference w^-1u.
// The function returns true if wg >uh.
// if g and h are nonzero, w and u are assumed to have the same length.
// if g is nonzero, and h=0, w is at least as long as u.
// if h is nonzero, and g=0, u is at least as long as w.
// Either wt(wg)>wt(uh)
// or wt(wg)=wt(uh) but uh precedes wg lexicographically.
// or wt(w)<wt(uh)
if (ddh.getWtDiff() + weight[g-1] - weight[h-1]>0 ||
(ddh.getWtDiff() + weight[g-1]-weight[h-1]==0 &&
ddh.getLexComp()==1))
return YES;
}
else if (g>0 && h==0){
if (ddh.getWtDiff() + weight[g-1] >= 0)
return YES;
}
else if (g==0 && h>0){
if (ddh.getWtDiff() > weight[h-1] )
return YES;
}
return NO;
}
Bool possibleReductionAhead(const DiffHistoryVtxRep & dh,int g) const {
const WtSLDiffHistoryVtxRep & ddh = (WtSLDiffHistoryVtxRep &)dh;
return (ddh.getWtDiff() > weight[g-1] +1);};
// Where dh represents the difference w^-1u,
// if there's a possible reduction of w to some u' with ug a proper
// prefix of u', w must have higher weight than some ugh,
// and so weight more than one less than ug.
int getWeight(int i) const { return weight[i-1];};
int getWeight(Generator g) const { return weight[getPosition(g)-1];};
int getWeight(const Word & w) const {
int wt=0,i=0,len=w.length();
while (i<len) wt += weight[getPosition(w[i++])-1];
return wt;
};
private:
VectorOf<int> weight;
};
class WtLexRep : public WordOrderRep {
public:
WtLexRep() : WordOrderRep("WtLex"){};
WtLexRep(int numOfSymbols) :
WordOrderRep("WtLex",numOfSymbols), weight(0) {
for (int i=1;i<=numOfSymbols;i++)
weight.append(1);
};
WtLexRep(const VectorOf<int> & w) :
WordOrderRep("WtLex",w.length()), weight(w) {
};
WtLexRep(const VectorOf<int> & o,const VectorOf<int> & w) :
WordOrderRep("WtLex",o) , weight(w) {};
//copy constructor
WtLexRep( const WtLexRep& wsl ) :
WordOrderRep(wsl), weight(wsl.weight) { }
WordOrderRep *clone() const { return new WtLexRep(*this); }
int signature(const Word & w1,const Word & w2) const {
if (w1==w2) return 0;
else {
int len1=w1.length();
int len2=w2.length();
int wt1=0;
int wt2=0;
int j=0;
while (j<len1) wt1 += weight[getPosition(w1[j++])-1];
j=0;
while (j<len2) wt2 += weight[getPosition(w2[j++])-1];
if (wt1<wt2) return 1;
else if (wt1>wt2) return -1;
else {
j=0;
while (j<len1 && j<len2){
if (getPosition(w1[j])<getPosition(w2[j])) return 1;
else if (getPosition(w1[j])>getPosition(w2[j])) return -1;
else j++;
}
// at this stage, one word is simply a prefix of the other
if (len1<len2) return 1;
else return -1;
}
}
}
int signature(int i, int j) const {
if (i==j) return 0;
else if (weight[i-1]<weight[j-1] || (weight[i-1]==weight[j-1] && i<j))
return 1;
else return -1;
}
int signature(Generator g, Generator h) const {
return signature(getPosition(g),getPosition(h));
}
void balancedEquationFromRelator(const Word & w,Word & lhs,Word & rhs) const {
int len=w.length();
int wt1=0; int wt2=0;
int i;
// copy the word, replacing each g^-1 for which g is an involution by g
VectorOf<Generator> W;
for (i=0;i<len;i++)
W.append((ord(w[i])<0 && selfInverse(inv(w[i])))? inv(w[i]) : w[i]);
int j=0;
while (j<len) wt1 += weight[getPosition(W[j++])-1];
VectorOf<Generator> ww;
j=len;
while (j-->=0) {
Generator g=W[j];
wt1 -= weight[getPosition(g)-1];
wt2 += weight[getPosition(g)-1];
if (wt1>=wt2 ) ww.append(selfInverse(g)? g : inv(g));
else break;
}
lhs = ((Word)W).initialSegment(j+1);
rhs=ww;
if (signature(lhs,rhs)==1){ // lhs is smaller, so switch them
rhs=lhs;
lhs=ww;
}
}
int historyBound(const VectorOf<Word> & diffs) const {
int Max=0;
for (int i=0;i<diffs.length();i++){
Word w=diffs[i];
int len=w.length();
int wt=0;
for (int j=0;j<len;j++) wt += weight[getPosition(w[j])-1];
if (wt>Max) Max = wt;
}
return Max;
}
DiffHistoryRep * buildDiffHistoryRep() const {
WtLexDiffHistoryRep * dhp = new WtLexDiffHistoryRep();
return dhp;
}
DiffHistoryRep * buildDiffHistoryRep(State d,int g,int h) const {
if (g>0 && h>0 && g!=h){
WtLexDiffHistoryRep * dhp =
new WtLexDiffHistoryRep(d,(g>h? 1: -1),weight[g-1] - weight[h-1],0,0);
return dhp;
}
else if (g>0 && h==0){
WtLexDiffHistoryRep * dhp =
new WtLexDiffHistoryRep(d,0,0,1,(weight[g-1]>0?1: weight[g-1]));
return dhp;
}
else {
std::cerr << "Parameters out of range for DiffHistoryRep constructor."<< std::endl;
WtLexDiffHistoryRep * dhp = new WtLexDiffHistoryRep;
return dhp;
}
}
DiffHistoryRep * update
(const DiffHistoryRep & dh,State d,int g,int h,const Word & wd) const {
const WtLexDiffHistoryRep& ddh = (WtLexDiffHistoryRep&)dh;
if (g>0 && h>0 && ddh.getC0()){
int w0 = ddh.getW0()+weight[g-1]-weight[h-1];
int c0 = (w0>= -getWeight(wd) ? ddh.getC0(): 0);
WtLexDiffHistoryRep * dhp = new WtLexDiffHistoryRep
(d,c0,w0,0,0);
return dhp;
}
else if (g>0 && h==0){
int c1,w1;
if (ddh.getC0() && ddh.getC1()){
// choose the bigger weight difference in dh
// add the weight of g to it, and then set w1 to be the minimum of that and 1
// c1 is set to be ddh.getC0() if ddh.getW0()>ddh.getW1(),
// to be ddh.getC1() if ddh.getW1()>ddh.getW0(), and otherwise the
// larger of ddh.getC0() and ddh.getC1()
if (ddh.getW0()>ddh.getW1()){
w1 = (ddh.getW0()+weight[g-1]>0?1:ddh.getW0() + weight[g-1]);
c1 = ddh.getC0();
}
else if (ddh.getW1()>ddh.getW0()){
w1 = (ddh.getW1()+weight[g-1]>0?1:ddh.getW1() + weight[g-1]);
c1 = ddh.getC1();
}
else {
w1 = (ddh.getW1()+weight[g-1]>0?1:ddh.getW1() + weight[g-1]);
c1 = (ddh.getC1()>=ddh.getC0()? ddh.getC1(): ddh.getC0());
}
}
else if (ddh.getC0()){
w1 = (ddh.getW0()+weight[g-1]>0?1:ddh.getW0() + weight[g-1]);
c1 = ddh.getC0();
}
else if (ddh.getC1()){
w1 = (ddh.getW1()+weight[g-1]>0?1:ddh.getW1() + weight[g-1]);
c1 = ddh.getC1();
}
if (w1 < -getWeight(wd)) c1=0;
WtLexDiffHistoryRep * dhp = new WtLexDiffHistoryRep (d,0,0,c1,w1);
return dhp;
}
else {
std::cerr << "Parameters out of range for update."<< std::endl;
WtLexDiffHistoryRep * dhp = new WtLexDiffHistoryRep;
return dhp;
}
}
Bool reduction(const DiffHistoryRep & dh,int g,int h) const {
const WtLexDiffHistoryRep& ddh = (WtLexDiffHistoryRep&)dh;
if (g>0 && h>0 && ddh.getC0()){
// For some w,u wg=_G uh where wg and uh have equal length, but wg>uh.
// Either wt(wg)>wt(uh)
// or wt(wg)=wt(uh) but uh precedes wg lexicographically.
if (ddh.getW0() + weight[g-1] - weight[h-1]>0 ||
(ddh.getW0() + weight[g-1]-weight[h-1]==0 && ddh.getC0()==1))
return YES;
}
else if (g>0 && h==0){
// For some w,u, wg=_G u, where l(wg)>l(u),
// either wt(wg)>wt(u) or wt(wg)=wt(u) but wg>u lexicographically
// Either l(w)=l(u) (getC0() returns a non-zero value- if this is -1
// we must have wt(wg)>wt(u))
// or l(w)>l(u) (getC1() returns a non-zero value - if this is -1
// we must have wt(wg)>wt(u))
if ((ddh.getC0()==1 && ddh.getW0() + weight[g-1] >= 0)
|| (ddh.getC0()== -1 && ddh.getW0() + weight[g-1] > 0)
|| (ddh.getC1()==1 && ddh.getW1() + weight[g-1] >= 0)
|| (ddh.getC1()== -1 && ddh.getW1() + weight[g-1] > 0))
return YES;
}
return NO;
}
Bool possibleReduction(const AheadInfoRep & ai,int g) const {
const WtLexAheadInfoRep & aai = (WtLexAheadInfoRep &)ai;
return (aai.getWtDiff() > weight[g-1] ||
(aai.getWtDiff()==weight[g-1] && aai.getSign()==1 ));};
AheadInfoRep * update(const AheadInfoRep & ai,int g) const {
const WtLexAheadInfoRep & aai = (WtLexAheadInfoRep &)ai;
WtLexAheadInfoRep * aip =
new WtLexAheadInfoRep (aai.getWtDiff()-weight[g-1],aai.getSign());
return aip;
}
DiffHistoryVtxRep * buildDiffHistoryVtxRep() const {
WtLexDiffHistoryVtxRep * dhp = new WtLexDiffHistoryVtxRep();
return dhp;
}
DiffHistoryVtxRep * buildDiffHistoryVtxRep(State d,int g,int h) const {
if (g>0 && h>0 && g!=h){
WtLexDiffHistoryVtxRep * dhp =
new WtLexDiffHistoryVtxRep(d,h,0,1,(g>h? 1: -1),weight[g-1] -
weight[h-1]);
return dhp;
}
else if (g>0 && h==0){
WtLexDiffHistoryVtxRep * dhp =
new WtLexDiffHistoryVtxRep(d,0,0,1,0,weight[g-1]);
return dhp;
}
else {
std::cerr
<< "Parameters out of range for DiffHistoryVtxRep constructor."
<< std::endl;
WtLexDiffHistoryVtxRep * dhp = new WtLexDiffHistoryVtxRep;
return dhp;
}
}
DiffHistoryVtxRep * update
(const DiffHistoryVtxRep & dh,State d,int g,int h, DiffHistoryVtx * ptr) const {
const WtLexDiffHistoryVtxRep& ddh = (WtLexDiffHistoryVtxRep&)dh;
if (g>0 && h>0){
WtLexDiffHistoryVtxRep * dhp = new WtLexDiffHistoryVtxRep
(d,h,ptr,dh.getLength()+1,ddh.getLexComp(),
ddh.getWtDiff()+weight[g-1] - weight[h-1]);
return dhp;
}
else if (g>0 && h==0){
WtLexDiffHistoryVtxRep * dhp = new WtLexDiffHistoryVtxRep
(d,0,ptr,dh.getLength()+1,ddh.getLexComp(),
ddh.getWtDiff()+weight[g-1]);
return dhp;
}
else if (g==0 && h>0){
WtLexDiffHistoryVtxRep * dhp = new WtLexDiffHistoryVtxRep
(d,h,ptr,dh.getLength(),ddh.getLexComp(),
ddh.getWtDiff()-weight[h-1]);
return dhp;
}
else {
std::cerr
<< "Parameters out of range in WtLexHistoryVtxRep::update()"
<< std::endl;
return new WtLexDiffHistoryVtxRep;
}
}
Bool reduction(const DiffHistoryVtxRep & dh,int g,int h) const {
const WtLexDiffHistoryVtxRep& ddh = (WtLexDiffHistoryVtxRep&)dh;
// dh corresponds to the difference w^-1u.
// The function returns true if wg >uh.
// if g and h are nonzero, w and u are assumed to have the same length.
// if g is nonzero, and h=0, w is at least as long as u.
// if h is nonzero, and g=0, u is at least as long as w.
if (g>0 && h>0){
if (ddh.getWtDiff() + weight[g-1] - weight[h-1]>0 ||
(ddh.getWtDiff() + weight[g-1]-weight[h-1]==0 &&
ddh.getLexComp()==1))
return YES;
}
else if (g>0 && h==0){
if (ddh.getWtDiff() + weight[g-1]>0 ||
(ddh.getWtDiff() + weight[g-1]==0 &&
ddh.getLexComp()==1))
return YES;
}
else if (g==0 && h>0){
if (ddh.getWtDiff() > weight[h-1] ||
(ddh.getWtDiff() -weight[h-1]==0 &&
ddh.getLexComp()==1))
return YES;
}
return NO;
}
Bool possibleReductionAhead(const DiffHistoryVtxRep & dh,int g) const {
const WtLexDiffHistoryVtxRep & ddh = (WtLexDiffHistoryVtxRep &)dh;
return (ddh.getWtDiff() > weight[g-1] +2||
(ddh.getWtDiff()==weight[g-1]+1&& ddh.getLexComp()==1));};
// Where dh represents the difference w^-1u,
// if there's a possible reduction of w to some u' with ug a proper
// prefix of u', w must either have higher weight than some ugh,
// and so weight more than one less than ug, or the same weight
// as some ugh which it precedes lexicographically.
int getWeight(int i) const { return weight[i-1];};
int getWeight(Generator g) const { return weight[getPosition(g)-1];};
int getWeight(const Word & w) const {
int wt=0,i=0,len=w.length();
while (i<len) wt += weight[getPosition(w[i++])-1];
return wt;
};
private:
VectorOf<int> weight;
};
class InvPairWreathRep : public WordOrderRep {
public:
InvPairWreathRep() : WordOrderRep("InvPairWreath") {};
InvPairWreathRep(const VectorOf<int> & o) : WordOrderRep("InvPairWreath",o) {};
//int signature(const Word & w1,const Word & w2) const { return 1; }
// define this properly
int signature(int g, int h) const { return 1; } // temporary
};
#endif
See more files for this project here