File: DiffHistoryRep.h

package info (click to toggle)
magnus 20060324-3
  • links: PTS
  • area: main
  • in suites: etch, etch-m68k
  • size: 19,404 kB
  • ctags: 20,466
  • sloc: cpp: 130,118; ansic: 37,076; tcl: 10,970; perl: 1,109; makefile: 963; sh: 403; yacc: 372; csh: 57; awk: 33; asm: 10
file content (807 lines) | stat: -rw-r--r-- 26,663 bytes parent folder | download | duplicates (3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
// Copyright (C) 1994 The New York Group Theory Cooperative
// See magnus/doc/COPYRIGHT for the full notice.

// Contents: Definition of DiffHistoryRep and related classes.
//
// Principal Author: Sarah Rees
//
// Status: in progress
//
// Revision History:
//

#ifndef _DiffHistoryRep_H_
#define _DiffHistoryRep_H_

#include "Word.h"
#include "Vector.h"
#include "RefCounter.h"
// #include "DFSARep.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
// and that can't be dependent on the FSA hierarchy.
// If that weren't necessary, this could all be in DiffMachineRep.h

class DiffHistoryVtx;

// First the AheadInfoRep hierarchy, one derived class for each word order.

class AheadInfoRep : public RefCounter {
public:
//constructor
  AheadInfoRep() {};
// copy constructor
  AheadInfoRep (const AheadInfoRep & ai) {}; 
  virtual AheadInfoRep *clone() const {};
//destructor
  virtual ~AheadInfoRep() {};
};

class SLAheadInfoRep : public AheadInfoRep {
public:
//constructor
  SLAheadInfoRep() {};
// copy constructor
  SLAheadInfoRep(const SLAheadInfoRep & ai) {}; 
  AheadInfoRep *clone() const { return new SLAheadInfoRep(*this); }
//destructor
  ~SLAheadInfoRep() {};
private:
};

class WtSLAheadInfoRep : public AheadInfoRep {
public:
//constructor
  WtSLAheadInfoRep() {};
  WtSLAheadInfoRep(int wd) {wtdiff=wd;};
// copy constructor
  WtSLAheadInfoRep (const WtSLAheadInfoRep & ai) {wtdiff=ai.wtdiff;}; 
  AheadInfoRep *clone() const { return new WtSLAheadInfoRep(*this); }
//destructor
  ~WtSLAheadInfoRep() {};
  int getWtDiff() const { return wtdiff;}
private:
  int wtdiff;
};

class WtLexAheadInfoRep : public AheadInfoRep {
public:
//constructor
  WtLexAheadInfoRep(): sign(0) {};
  WtLexAheadInfoRep(int wd,int sgn): wtdiff(wd), sign(sgn) {};
// copy constructor
  WtLexAheadInfoRep(const WtLexAheadInfoRep & ai) : 
     wtdiff(ai.wtdiff), sign(ai.sign){}; 
  AheadInfoRep *clone() const { return new WtLexAheadInfoRep(*this); }
//destructor
  ~WtLexAheadInfoRep() {};
  int getWtDiff() const { return wtdiff;}
  int getSign() const { return sign;}
private:
  int wtdiff; 
  int sign;
};


// Now the DiffHistoryRep hierarchy. There is one type for each word order.
// In the comments below d is always a word difference, which has arise
// as various products of the form w^-1u

class DiffHistoryRep : public RefCounter {
public:
//constructor
  DiffHistoryRep() {};
//copy constructor
  DiffHistoryRep(const DiffHistoryRep & dh) {};
  virtual DiffHistoryRep *clone() const {};
//destructor
  virtual ~DiffHistoryRep() {};

//hash function
  virtual int hash() const {};
  virtual Bool empty() const {};

  virtual State getDiff() const {};
//operators
  virtual int operator== ( const DiffHistoryRep & dh) const {
  };
  virtual DiffHistoryRep&  operator= ( const DiffHistoryRep & dh ) {};

  virtual Bool sameLengthWords() const {};
// returns YES if d has arisen as the word difference from two words
// of equal length

  virtual void improveBy(const DiffHistoryRep & dh) {};
//  add in to the current word difference history the information carried
// by the difference history dh (which is associated associated with the same
// word difference)

  virtual Bool possibleReductionAhead() const {};
// return YES if the possibility cannot be ruled out that some w is equal
// in G to a longer word u', of which u is a prefix, and such that u<w.

  virtual AheadInfoRep *  buildAheadInfoRep() const {};
// constuct and return an AheadInfoRep * for this DiffHistory 

  virtual void printOn(ostream &ostr = cout) const {};

  virtual inline ostream& operator << ( const DiffHistoryRep& dh ) {};
};

class SLDiffHistoryRep : public DiffHistoryRep {
// Together with each word difference d, integers c0,c1
// are stored, where
// c0 = 1 if d=_G w^-1u for some w, u with l(w)=l(u) and w>u
//    =  -1 if for all w,u with d=_G w^-1u and l(w)=l(u), w<u
//    = 0 if d does not arise as the word difference for 
//        words of equal length.
// c1 = 1 if d = _G w^-1u for some w,u with l(w)>l(u)
//    = 0 otherwise.
//
public:
//constructors
  SLDiffHistoryRep(): d(0),c0(0),c1(0){};
  SLDiffHistoryRep(State D,int C0,int C1):
    d(D),c0(C0),c1(C1){};
//copy constructor
  SLDiffHistoryRep(const SLDiffHistoryRep & dh) : 
    d(dh.d), c0(dh.c0), c1 (dh.c1) {};
  DiffHistoryRep *clone() const { return new SLDiffHistoryRep(*this); }
//destructor
  ~SLDiffHistoryRep() {};
//hash function
  int hash() const { return (int)d; };
  Bool empty() const { return (c0==0 && c1==0); };
//accessors
  int getDiff() const { return d;};
  int getC0() const { return c0;};
  int getC1() const { return c1;};

  //operators
  int operator== ( const DiffHistoryRep & dh) const
  {
    const SLDiffHistoryRep& ddh = (SLDiffHistoryRep&)dh;
    return (d == ddh.d && c0 == ddh.c0  && c1 == ddh.c1);
  }
 
  DiffHistoryRep&  operator= ( const DiffHistoryRep & dh )
  {
    const SLDiffHistoryRep& ddh = (SLDiffHistoryRep&)dh;
    d = ddh.d; c0 = ddh.c0; c1 = ddh.c1;
    return *this;
  }

  Bool sameLengthWords() const  { return (c0!=0);};

  void improveBy(const DiffHistoryRep & dh) 
  {
    const SLDiffHistoryRep& ddh = (SLDiffHistoryRep&)dh;
    if ((ddh.c0==0 || (c0!=0 && c0>= ddh.c0 ))
             && (ddh.c1==0 || (c1>= ddh.c1 )))
        return;
  // ddh is no better than the current SLDiffHistoryRep
    else {
      if (ddh.c0 && (c0==0 || ddh.c0 == 1)){ 
       c0 = ddh.c0;}
      if (ddh.c1 && c1==0 ) {
        c1 = ddh.c1; } 
    }
  }
  Bool possibleReductionAhead() const { return NO;}

  AheadInfoRep * buildAheadInfoRep() const { return new SLAheadInfoRep(); }

  void printOn(ostream &ostr = cout) const 
  {
    ostr << "d="<< d << " c0="<< c0 <<" c1="<<c1<<"; ";
  }
  
  inline friend ostream& operator << 
        ( ostream& ostr, const SLDiffHistoryRep& dh ) {
  		  ostr << "d="<< dh.d << " c0="<< dh.c0 <<
  			 " c1="<<dh.c1<<"; ";
    return ostr;
  }
  
  
private:
  State d;
  int c0, c1;
};

class WtSLDiffHistoryRep : public DiffHistoryRep {
// Together with each word difference d, integers c0,w0,c1,w1
// are stored, where
// w0 = max{wt(w)-wt(u):l(u)=l(w),u \neq w, d=_G w^-1u }, 
// where that set is non-empty,
// and is otherwise meaningless. c0=0 if the set above is empty, 1 if there
// is some u with wt(w)-wt(u)=w0, l(u)=l(w), d=_G w^-1u and u<w in shortlex,
// and -1 if for all such u, w<u in shortlex.
// w1 = min{1,max{wt(w)-wt(u):l(u)<l(w), d_G w^-1u }, 
// where that set is non-empty,
// and is otherwise meaningless. c1=0 if that set if empty, 1 otherwise.
//
// Given such a difference history (d,c0,w0,c1,w1)
// 
// Where g is a generator, and g^-1d=_G id,
//    if either c0 is nonzero and w0+wt(g)>=0 
//       or c1 is non-zero and w1+wt(g)>=0,
//    then for some w where d=_G w^-1u, wg is equal in G to a 
//       shorter word of no greater weight.
//
//  Where g,h are generators and g^-1dh=_G id,
//     c0 is non-zero,
//     and either w0+wt(g)-wt(h)>0
//         or w0+wt(g)-wt(h)=0 and c0=1,
//     then wg reduces to uh, of the same length as wg,
//         but preceding it in weighted shortlex
//         (in the first case it has lesser weight, in the
//          second it has the same weight but is lexicographically earlier)
//
//   Where H is a word of length >= 2 with H^-1dg=id, c0 is non-zero
//   and g^-1d(h_1h_2..h_i) is in D for all prefixes h_1h_2..h_i of H
//   and w0 + wt(g) - wt(h_1) - ... wt(h_n) > 0,
//   then wg reduces to uH which is longer, but of lower weight.
//

public:
//constructors
  WtSLDiffHistoryRep(): d(0),c0(0),w0(0),c1(0),w1(0){};
  WtSLDiffHistoryRep(State D,int C0,int W0,int C1,int W1):
    d(D),c0(C0),w0(W0),c1(C1),w1(W1){};
//copy constructor
  WtSLDiffHistoryRep(const WtSLDiffHistoryRep & dh):
    d(dh.d), c0(dh.c0), w0(dh.w0), c1(dh.c1), w1(dh.w1){};
  DiffHistoryRep *clone() const { return new WtSLDiffHistoryRep(*this); }
//destructor
  ~WtSLDiffHistoryRep() {};
//hash function
  int hash() const { return (int)d; };
  Bool empty() const { return (c0==0 && c1==0); };
//accessors
  int getDiff() const { return d;};
  int getC0() const { return c0;};
  int getW0() const { return w0;};
  int getC1() const { return c1;};
  int getW1() const { return w1;};

  //operators
  int operator== ( const DiffHistoryRep & dh) const
  {
    const WtSLDiffHistoryRep& ddh = (WtSLDiffHistoryRep&)dh;
    return (d == ddh.d && c0 == ddh.c0 && w0 == ddh.w0 
                 && c1 == ddh.c1 && w1 == ddh.w1);
  }
 
  DiffHistoryRep&  operator= ( const DiffHistoryRep & dh )
  {
    const WtSLDiffHistoryRep& ddh = (WtSLDiffHistoryRep&)dh;
    d = ddh.d; c0 = ddh.c0; w0 = ddh.w0; c1 = ddh.c1; w1 = ddh.w1;
    return *this;
  }
  Bool sameLengthWords() const  { return (c0!=0);};
  void improveBy(const DiffHistoryRep & dh) 
  {
    const WtSLDiffHistoryRep& ddh = (WtSLDiffHistoryRep&)dh;
    if (ddh.c0 && (c0==0 || w0 < ddh.w0 || (w0==ddh.w0 && ddh.c0 == 1))){ 
      c0 = ddh.c0; w0 = ddh.w0;}
    if (ddh.c1 && (c1==0 || w1 < ddh.w1)){ 
      c1 = ddh.c1; w1 = ddh.w1;}
  }
  Bool possibleReductionAhead() const { return (c0 && w0 > 1);}

  AheadInfoRep * buildAheadInfoRep() const { 
    WtSLAheadInfoRep *  aip = new WtSLAheadInfoRep(w0); return aip; }

  void printOn(ostream &ostr = cout) const 
  {
    ostr << "d="<< d << " c0="<< c0 <<" w0="<<w0<<
          " c1="<<c1<<" w1="<<w1<<"; ";
  }
  
  inline friend ostream& operator << 
        ( ostream& ostr, const WtSLDiffHistoryRep& dh ) {
  		  ostr << "d="<< dh.d << " c0="<< dh.c0 <<
  			 " w0="<<dh.w0<<" c1="<<dh.c1<<" w1="<<dh.w1<<"; ";
    return ostr;
  }
  
  
private:
  State d;
  int c0, c1;
  int w0, w1;
};

class WtLexDiffHistoryRep : public DiffHistoryRep {
// There are only very minor differences between this class and
// WtSLDifferenceRep. The same data is held, but c1 can also take the value -1.
// The function improveBy is slightly different, and the AheadInfo needs to
// carry more information. The situations in which reduction can occur are
// also slightly different.
// Much of the code is a copy of WtSLDiffHistoryRep code, but it seems safer
// to keep the 2 classes separate, because of the minor differences which could
// lead to confusion if code were shared (or, for example if one class were
// derived from another). 

// Together with each word difference d, integers c0,w0,c1,w1
// are stored, where
// w0 = max{wt(w)-wt(u):l(u)=l(w),u \neq w, d=_G w^-1u }, 
// where that set is non-empty,
// and is otherwise meaningless. c0=0 if the set above is empty, 1 if there
// is some u with wt(w)-wt(u)=w0, l(u)=l(w), d=_G w^-1u and u<w in lex,
// and -1 if for all such u, w<u in lex.
// w1 = min{1,max{wt(w)-wt(u):l(u)<l(w), d_G w^-1u }, 
// where that set is non-empty,
// and is otherwise meaningless. c1=0 if the set above is empty, 1 if there
// is some u with wt(w)-wt(u)=w0, l(u)<l(w), d=_G w^-1u and u<w in lex,
// and -1 if for all such u, w<u in lex.
//
// Given such a difference history (d,c0,w0,c1,w1)
// 
// Where g is a generator, and g^-1d=_G id,
//    if either c0 is nonzero and w0+wt(g)>0 
//       or c0=1 and w0+wt(g)=0
//       or c1 is non-zero and w1+wt(g)>0,
//       or c1=1 and w1+wt(g)=0
//    then for some w where d=_G w^-1u, wg is equal in G to a 
//       word u which is either of lesser weight, or of the same weight, 
//       but preceding it in lex.
//
//  Where g,h are generators and g^-1dh=_G id,
//     c0 is non-zero,
//     and either w0+wt(g)-wt(h)>0
//         or w0+wt(g)-wt(h)=0 and c0=1,
//     then wg reduces to uh, of the same length as wg,
//         but preceding it in weighted lex
//         (in the first case it has lesser weight, in the
//          second it has the same weight but is lexicographically earlier)
//
//   Where H is a word of length >= 2 with H^-1dg=id, c0 is non-zero
//   and g^-1d(h_1h_2..h_i) is in D for all prefixes h_1h_2..h_i of H
//   and w0 + wt(g) - wt(h_1) - ... wt(h_n) > 0,
//   or  w0+wt(g)-wt(h_1)- .. wt(h_n)=0 and c0=1
//   then wg reduces to uH which is longer, either of lower weight than wg
//   or of the same weight as wg, and preceding it lexicographically.
//

public:
//constructors
  WtLexDiffHistoryRep(): d(0),c0(0),w0(0),c1(0),w1(0){};
  WtLexDiffHistoryRep(State D,int C0,int W0,int C1,int W1):
    d(D),c0(C0),w0(W0),c1(C1),w1(W1){};
//copy constructor
  WtLexDiffHistoryRep(const WtLexDiffHistoryRep & dh):
    d(dh.d), c0(dh.c0), w0(dh.w0), c1(dh.c1), w1(dh.w1) {};
  DiffHistoryRep *clone() const { return new WtLexDiffHistoryRep(*this); }
//destructor
  ~WtLexDiffHistoryRep() {};
//hash function
  int hash() const { return (int)d; };
  Bool empty() const { return (c0==0 && c1==0); };
//accessors
  int getDiff() const { return d;};
  int getC0() const { return c0;};
  int getW0() const { return w0;};
  int getC1() const { return c1;};
  int getW1() const { return w1;};

  //operators
  int operator== ( const DiffHistoryRep & dh) const
  {
    const WtLexDiffHistoryRep& ddh = (WtLexDiffHistoryRep&)dh;
    return (d == ddh.d && c0 == ddh.c0 && w0 == ddh.w0 
                 && c1 == ddh.c1 && w1 == ddh.w1);
  }
 
  DiffHistoryRep&  operator= ( const DiffHistoryRep & dh )
  {
    const WtLexDiffHistoryRep& ddh = (WtLexDiffHistoryRep&)dh;
    d = ddh.d; c0 = ddh.c0; w0 = ddh.w0; c1 = ddh.c1; w1 = ddh.w1;
    return *this;
  }
  Bool sameLengthWords() const  { return (c0!=0);};
  void improveBy(const DiffHistoryRep & dh) 
  {
    const WtLexDiffHistoryRep& ddh = (WtLexDiffHistoryRep&)dh;
    if (ddh.c0 && (c0==0 || w0 < ddh.w0 || (w0==ddh.w0 && ddh.c0 == 1))){ 
      c0 = ddh.c0; w0 = ddh.w0;}
    if (ddh.c1 && (c1==0 || w1 < ddh.w1 || (w1==ddh.w1 && ddh.c1 == 1))){ 
      c1 = ddh.c1; w1 = ddh.w1;}
  }
  Bool possibleReductionAhead() const { 
     return ((c0 && w0 > 0) || (w0 > 1 && c0==1));}

  AheadInfoRep * buildAheadInfoRep() const { 
    WtLexAheadInfoRep *  aip = new WtLexAheadInfoRep(w0,c0); return aip; }

  void printOn(ostream &ostr = cout) const 
  {
    ostr << "d="<< d << " c0="<< c0 <<" w0="<<w0<<" c1="<<c1<<" w1="<<w1<<"; ";
  }
  
  inline friend ostream& operator << 
        ( ostream& ostr, const WtLexDiffHistoryRep& dh ) {
  		  ostr << "d="<< dh.d << " c0="<< dh.c0 <<
  			 " w0="<<dh.w0<<" c1="<<dh.c1<<" w1="<<dh.w1<<"; ";
    return ostr;
  }
  
  
private:
  State d;
  int c0, c1;
  int w0, w1;
};


// Now the DiffHistoryVtxRep hierarchy. There is one type for each word order. 
// In the comments below d is always a word difference, which has arisen
// as various products of the form w^-1u

class DiffHistoryVtxRep : public RefCounter {
public:
//constructor
  DiffHistoryVtxRep(): diff(0), gen(0), backptr(0),len(0) {};
  DiffHistoryVtxRep(State D,int G,DiffHistoryVtx * ptr,int L):
     diff(D), gen(G), backptr(ptr),len(L) {};
//copy constructor
  DiffHistoryVtxRep(const DiffHistoryVtxRep & dh) {
    diff = dh.diff; gen = dh.gen; backptr = dh.backptr; len = dh.len;
  };
  DiffHistoryVtxRep *clone() const { return new DiffHistoryVtxRep(*this);};
//destructor
  ~DiffHistoryVtxRep() {};

  State getDiff() const {return diff;};
  int getGenerator() const { return gen;}
  DiffHistoryVtx *getBackptr() const { return backptr;}
  int getLength() const { return len;}
//operators
  int operator== ( const DiffHistoryVtxRep & dh) const {
  diff == dh.diff; gen==dh.gen; backptr == dh.backptr; len==dh.len;};
  DiffHistoryVtxRep&  operator= ( const DiffHistoryVtxRep & dh ) {
    diff = dh.diff; gen = dh.gen; backptr = dh.backptr; len = dh.len;
    return *this;
  };

  virtual Trichotomy betterThan(const DiffHistoryVtxRep & dh) const {};
// Only to be called if the word differences match.
// If the word differences match,
// returns yes if whenever dh predicts a reduction, the current
// DiffHistoryVtx predicts one too and there could be situations
// where the current DiffHistoryVtx predicts a reduction but dh 
// does not, no if dh predicts a
// reduction whenever the current DiffHistoryVtx does,
// dontknow if neither of the above is true (or it seems too much work 
// to find out).

  virtual Bool possibleReductionAhead() const {};
// return YES if the possibility cannot be ruled out that some w is equal
// in G to a longer word u', of which u is a prefix, and such that u<w.


  void printOn(ostream &ostr = cout) const {
    ostr << "diff="<< diff <<", gen= "<<gen<<", backptr = "<<backptr
         <<", len="<<len<<"; ";
  };

  inline friend ostream& operator << (ostream & ostr, const DiffHistoryVtxRep& dh ) {
    ostr << "diff="<< dh.diff <<", gen= "<<dh.gen<<", backptr = "<<dh.backptr
         <<", len="<<dh.len<<"; ";
    return ostr;
  };
private:
  State diff;
  int gen;
  DiffHistoryVtx * backptr;
  int len;
};


class SLDiffHistoryVtxRep : public DiffHistoryVtxRep {

public:
//constructors
  SLDiffHistoryVtxRep(): DiffHistoryVtxRep(),lexComp(0){};
  SLDiffHistoryVtxRep(State D,int G,DiffHistoryVtx * ptr,int L,int C):
    DiffHistoryVtxRep(D,G,ptr,L),lexComp(C) {};
//copy constructor
  SLDiffHistoryVtxRep(const SLDiffHistoryVtxRep & dh) 
    : DiffHistoryVtxRep(dh), lexComp(dh.lexComp){};
  DiffHistoryVtxRep *clone() const { 
    return new SLDiffHistoryVtxRep(*this); } 
//destructor
  ~SLDiffHistoryVtxRep() {};
//accessors
  int getLexComp() const { return lexComp;};

  //operators
/*
  int operator== ( const DiffHistoryVtxRep & dh) const
  {
LOOK in FSA hierarchy
    const SLDiffHistoryVtxRep& ddh = (SLDiffHistoryVtxRep&)dh;
    return (SOMETHING && lexComp = ddh.lexComp);
  }
*/
 
  DiffHistoryVtxRep&  operator= ( const DiffHistoryVtxRep & dh )
  {
    (DiffHistoryVtxRep)*this = dh;
    const SLDiffHistoryVtxRep& ddh = (SLDiffHistoryVtxRep&)dh;
    lexComp = ddh.lexComp;
    return *this;
  }

   Trichotomy betterThan(const DiffHistoryVtxRep & dh) const {
// Only to be called if the word differences match.
// If the word differences match,
// returns yes if whenever dh predicts a reduction, the current
// DiffHistoryVtx predicts one too and there could be situations
// where the current DiffHistoryVtx predicts a reduction but dh 
// does not, no if dh predicts a
// reduction whenever the current DiffHistoryVtx does,
// dontknow if neither of the above is true (or it seems too much work 
// to find out).

    if (getDiff()!=dh.getDiff()) return dontknow;

    int g1,g2;

// If one DiffHistoryVtx corresponds to a shorter word and one to a word
// the same length as w, neither can be considered to be better than
// the other
    if (((g1=getGenerator())==0 && (g2=dh.getGenerator()))||
         g1 & g2==0) return dontknow;

// If both words are shorter than w, either DiffHistoryVtx is as
// good as the other, so we return no

    if (g1==0 && g2==0) return no;

// If both words are the same length as w, we return yes if the
// current DiffHistoryVtx corresponds to a word which precedes w
// lexicographically, but dh does not.
// Otherwise dh is just as good as the current DiffHistoryVtx, so
// we return no.
     
    const SLDiffHistoryVtxRep& ddh = (SLDiffHistoryVtxRep&)dh;
    if (lexComp==1 && ddh.lexComp== -1) return yes;
    else return no; 
  }

  Bool possibleReductionAhead() const { return no;}

  void printOn(ostream &ostr = cout) const 
  {
    DiffHistoryVtxRep::printOn(ostr);
    ostr << " lexComp="<< lexComp <<"; ";
  }
  
  inline friend ostream& operator << 
        ( ostream& ostr, const SLDiffHistoryVtxRep& dh ) {
    DiffHistoryVtxRep ddh = (DiffHistoryVtxRep)dh;
    ostr << ddh << ", lexComp="<< dh.lexComp <<"; ";
    return ostr;
  }
  
  
private:
  int lexComp; // =1 if, where d=w^-1u, w>u in lex, -1 if w<u
                      // 0 if not set
};

// at the moment the two classes below are identical.
// if they don't change we could probably manage with one!

class WtSLDiffHistoryVtxRep : public DiffHistoryVtxRep {

public:
//constructors
  WtSLDiffHistoryVtxRep(): DiffHistoryVtxRep(),lexComp(0), wtdiff(0){};
  WtSLDiffHistoryVtxRep(State D,int G,DiffHistoryVtx * ptr,int L,
                         int C, int WD):
    DiffHistoryVtxRep(D,G,ptr,L),lexComp(C), wtdiff(WD) {};
//copy constructor
  WtSLDiffHistoryVtxRep(const WtSLDiffHistoryVtxRep & dh) 
    : DiffHistoryVtxRep(dh), lexComp(dh.lexComp), wtdiff(dh.wtdiff) {};
  DiffHistoryVtxRep *clone() const { 
    return new WtSLDiffHistoryVtxRep(*this); } 
//destructor
  ~WtSLDiffHistoryVtxRep() {};
//accessors
  int getLexComp() const { return lexComp;};
  int getWtDiff() const { return wtdiff;};

  //operators
/*
  int operator== ( const DiffHistoryVtxRep & dh) const
  {
LOOK in FSA hierarchy
    const WtSLDiffHistoryVtxRep& ddh = (WtSLDiffHistoryVtxRep&)dh;
    return (SOMETHING && lexComp = ddh.lexComp && wtdiff == ddh.wtdiff);
  }
*/
 
  DiffHistoryVtxRep&  operator= ( const DiffHistoryVtxRep & dh )
  {
    (WtSLDiffHistoryVtxRep)*this = dh;
    const WtSLDiffHistoryVtxRep& ddh = (WtSLDiffHistoryVtxRep&)dh;
    lexComp = ddh.lexComp; wtdiff = ddh.wtdiff;
    return *this;
  }

   Trichotomy betterThan(const DiffHistoryVtxRep & dh) const {
// Only to be called if the word differences match.
// If the word differences match,
// returns yes if whenever dh predicts a reduction, the current
// DiffHistoryVtx predicts one too and there could be situations
// where the current DiffHistoryVtx predicts a reduction but dh 
// does not, no if dh predicts a
// reduction whenever the current DiffHistoryVtx does,
// dontknow if neither of the above is true (or it seems too much work 
// to find out).

    if (getDiff()!=dh.getDiff()) return dontknow;

    int g1,g2;

// If one DiffHistoryVtx corresponds to a shorter word and one to a word
// the same length as w, neither can be considered to be better than
// the other
    if (((g1=getGenerator())==0 && (g2=dh.getGenerator()))||
         g1 & g2==0) return dontknow;

// If both words are shorter than w, 
// the current history is better if it has a larger weight difference,
// but otherwise dh is at least as good as the other, so we return no.

    const WtSLDiffHistoryVtxRep& ddh = (WtSLDiffHistoryVtxRep&)dh;
    if (g1==0 && g2==0){
      if (wtdiff > ddh.wtdiff) return yes;
      else return no;
    }

// If both words are the same length as w, we return yes if the
// current DiffHistoryVtx has larger weight difference than dh,
// or if it has the same weight difference as dh and corresponds 
// to a word which precedes w lexicographically, but dh does not.
// Otherwise dh is just as good as the current DiffHistoryVtx, so
// we return no.
     
    if ((wtdiff>ddh.wtdiff) ||
    (wtdiff==ddh.wtdiff && lexComp==1 && ddh.lexComp== -1))
      return yes;
    else return no; 
  }

  Bool possibleReductionAhead() const { return (wtdiff > 1);}

  void printOn(ostream &ostr = cout) const 
  {
    DiffHistoryVtxRep::printOn(ostr);
    ostr << " lexComp="<< lexComp <<" wtdiff="<<wtdiff<<"; ";
  }
  
  inline friend ostream& operator << 
        ( ostream& ostr, const WtSLDiffHistoryVtxRep& dh ) {
    DiffHistoryVtxRep ddh = (DiffHistoryVtxRep)dh;
    ostr << ddh << ", lexComp="<< dh.lexComp <<" wtdiff="<<dh.wtdiff<<"; ";
    return ostr;
  }
  
  
private:
  int lexComp;
  int wtdiff;
};

class WtLexDiffHistoryVtxRep : public DiffHistoryVtxRep {
public:
//constructors
  WtLexDiffHistoryVtxRep(): DiffHistoryVtxRep(),lexComp(0), wtdiff(0){};
  WtLexDiffHistoryVtxRep(State D,int G,DiffHistoryVtx * ptr,int L,
                         int C, int WD):
    DiffHistoryVtxRep(D,G,ptr,L),lexComp(C), wtdiff(WD) {};
//copy constructor
  WtLexDiffHistoryVtxRep(const WtLexDiffHistoryVtxRep & dh) 
    : DiffHistoryVtxRep(dh), lexComp(dh.lexComp), wtdiff(dh.wtdiff) {};
  DiffHistoryVtxRep *clone() const { 
    return new WtLexDiffHistoryVtxRep(*this); } 
//destructor
  ~WtLexDiffHistoryVtxRep() {};
//accessors
  int getLexComp() const { return lexComp;};
  int getWtDiff() const { return wtdiff;};

  //operators
/*
  int operator== ( const DiffHistoryVtxRep & dh) const
  {
LOOK in FSA hierarchy
    const WtLexDiffHistoryVtxRep& ddh = (WtLexDiffHistoryVtxRep&)dh;
    return (SOMETHING && lexComp = ddh.lexComp && wtdiff == ddh.wtdiff);
  }
*/
 
  DiffHistoryVtxRep&  operator= ( const DiffHistoryVtxRep & dh )
  {
    (WtLexDiffHistoryVtxRep)*this = dh;
    const WtLexDiffHistoryVtxRep& ddh = (WtLexDiffHistoryVtxRep&)dh;
    lexComp = ddh.lexComp; wtdiff = ddh.wtdiff;
    return *this;
  }

   Trichotomy betterThan(const DiffHistoryVtxRep & dh) const {
// Only to be called if the word differences match.
// If the word differences match,
// returns yes if whenever dh predicts a reduction, the current
// DiffHistoryVtx predicts one too and there could be situations
// where the current DiffHistoryVtx predicts a reduction but dh 
// does not, no if dh predicts a
// reduction whenever the current DiffHistoryVtx does,
// dontknow if neither of the above is true (or it seems too much work 
// to find out).

    if (getDiff()!=dh.getDiff()) return dontknow;

    int g1,g2;

// If one DiffHistoryVtx corresponds to a shorter word and one to a word
// the same length as w, neither can be considered to be better than
// the other
    if (((g1=getGenerator())==0 && (g2=dh.getGenerator()))||
         g1 & g2==0) return dontknow;

// If both words are shorter than w, 
// the current history is better if it has a larger weight difference,
// but otherwise dh is at least as good as the other, so we return no.

    const WtLexDiffHistoryVtxRep& ddh = (WtLexDiffHistoryVtxRep&)dh;
    if (g1==0 && g2==0){
      if (wtdiff > ddh.wtdiff) return yes;
      else return no;
    }

// If both words are the same length as w, we return yes if the
// current DiffHistoryVtx has larger weight difference than dh,
// or if it has the same weight difference as dh and corresponds 
// to a word which precedes w lexicographically, but dh does not.
// Otherwise dh is just as good as the current DiffHistoryVtx, so
// we return no.
     
    if ((wtdiff>ddh.wtdiff) ||
    (wtdiff==ddh.wtdiff && lexComp==1 && ddh.lexComp== -1))
      return yes;
    else return no; 
  }


  Bool possibleReductionAhead() const { 
     return (wtdiff>1 ||(lexComp==1 && wtdiff > 0));}

  void printOn(ostream &ostr = cout) const 
  {
    DiffHistoryVtxRep::printOn(ostr);
    ostr << " lexComp="<< lexComp <<" wtdiff="<<wtdiff<<"; ";
  }
  
  inline friend ostream& operator << 
        ( ostream& ostr, const WtLexDiffHistoryVtxRep& dh ) {
    DiffHistoryVtxRep ddh = (DiffHistoryVtxRep)dh;
    ostr << ddh << ", lexComp="<< dh.lexComp <<
          " wtdiff="<<dh.wtdiff<<"; ";
    return ostr;
  }
  
  
private:
  int lexComp;
  int wtdiff;
};


#endif