mcs/tests/gtest-118.cs

   1 //-- ex-gen-class-polynomial
   2
   3 using System;
   4
   5 // A type implements AddMul<A,R> if one can add an A to it, giving an R:
   6
   7 interface AddMul<A,R> {
   8   R Add(A e);                   // Addition with A, giving R
   9   R Mul(A e);                   // Multiplication with A, giving R
  10 }
  11
  12 // Polynomials over E, Polynomial<E>:
  13
  14 // The base type E of the polynomial must support addition,
  15 // multiplication and zero (via the nullary constructor).  That's what
  16 // the type parameter constraint on E says.
  17
  18 // In return, one can add an E or a polynomial over E to a polynomial
  19 // over E.  Similarly, a polynomial over E can be multiplied by an E
  20 // or by a polynomial over E.  That's what the interface clauses say.
  21
  22 class Polynomial<E> : AddMul<E,Polynomial<E>>,
  23                       AddMul<Polynomial<E>,Polynomial<E>>
  24   where E : AddMul<E,E>, new() {
  25   // cs contains coefficients of x^0, x^1, ...; absent coefficients are zero.
  26   // Invariant: cs != null && cs.Length >= 0; cs.Length==0 represents zero.
  27   private readonly E[] cs;
  28
  29   public Polynomial() {
  30     this.cs = new E[0];
  31   }
  32
  33   public Polynomial(E[] cs) {
  34     this.cs = cs;
  35   }
  36
  37   public Polynomial<E> Add(Polynomial<E> that) {
  38     int newlen = Math.Max(this.cs.Length, that.cs.Length);
  39     int minlen = Math.Min(this.cs.Length, that.cs.Length);
  40     E[] newcs = new E[newlen];
  41     if (this.cs.Length <= that.cs.Length) {
  42       for (int i=0; i<minlen; i++)
  43         newcs[i] = this.cs[i].Add(that.cs[i]);
  44       for (int i=minlen; i<newlen; i++)
  45         newcs[i] = that.cs[i];
  46     } else {
  47       for (int i=0; i<minlen; i++)
  48         newcs[i] = this.cs[i].Add(that.cs[i]);
  49       for (int i=minlen; i<newlen; i++)
  50         newcs[i] = this.cs[i];
  51     }
  52     return new Polynomial<E>(newcs);
  53   }
  54
  55   public Polynomial<E> Add(E that) {
  56     return this.Add(new Polynomial<E>(new E[] { that }));
  57   }
  58
  59   public Polynomial<E> Mul(E that) {
  60     E[] newcs = new E[cs.Length];
  61     for (int i=0; i<cs.Length; i++)
  62       newcs[i] = that.Mul(cs[i]);
  63     return new Polynomial<E>(newcs);
  64   }
  65
  66   public Polynomial<E> Mul(Polynomial<E> that) {
  67     int newlen = Math.Max(1, this.cs.Length + that.cs.Length - 1);
  68     E[] newcs = new E[newlen];
  69     for (int i=0; i<newlen; i++) {
  70       E sum = new E();                     // Permitted by constraint E : new()
  71       int start = Math.Max(0, i-that.cs.Length+1);
  72       int stop  = Math.Min(i, this.cs.Length-1);
  73       for (int j=start; j<=stop; j++) {
  74         // assert 0<=j && j<this.cs.Length && 0<=i-j && i-j<that.cs.Length;
  75         sum = sum.Add(this.cs[j].Mul(that.cs[i-j]));
  76       }
  77       newcs[i] = sum;
  78     }
  79     return new Polynomial<E>(newcs);
  80   }
  81
  82   public E Eval(E x) {
  83     E res = new E();                       // Permitted by constraint E : new()
  84     for (int j=cs.Length-1; j>=0; j--)
  85       res = res.Mul(x).Add(cs[j]);
  86     return res;
  87   }
  88 }
  89
  90 struct Int : AddMul<Int,Int> {
  91   private readonly int i;
  92   public Int(int i) {
  93     this.i = i;
  94   }
  95   public Int Add(Int that) {
  96     return new Int(this.i + that.i);
  97   }
  98   public Int Mul(Int that) {
  99     return new Int(this.i * that.i);
 100   }
 101   public override String ToString() {
 102     return i.ToString();
 103   }
 104 }
 105
 106 class TestPolynomial {
 107   public static void Main(String[] args) {
 108     // The integer polynomial 2 + 5x + x^2
 109     Polynomial<Int> ip =
 110       new Polynomial<Int>(new Int[] { new Int(2), new Int(5), new Int(1) });
 111     Console.WriteLine(ip.Eval(new Int(10)));            // 152
 112     Console.WriteLine(ip.Add(ip).Eval(new Int(10)));    // 304 = 152 + 152
 113     Console.WriteLine(ip.Mul(ip).Eval(new Int(10)));    // 23104 = 152 * 152
 114   }
 115 }
 116