// Ring, Complex, Polynomial
// This program requires .NET version 2.0
// Peter Sestoft (sestoft@itu.dk) * 2001-12-12

// Using an abstract class as constraint, recursive constraints
// involving the class itself, a class as a constraint on a struct,
// etc.

// Alas, operators are static, and therefore cannot be specified in
// interfaces or abstract classes.

using System;

interface Ring<E> 
  where E : Ring<E> {
  E Zero();	// Lack of constructor or static specification
  E Plus(E e);
  E Times(E e);
  E Negate();
  E Minus(E e);
}

// A Ring adapter that saves us from defining Minus in subclasses

abstract class RingC<E> : Ring<E> 
  where E : Ring<E> {
  public abstract E Zero();
  public abstract E Plus(E e);
  public abstract E Times(E e);
  public abstract E Negate();
  public E Minus(E e) {
    return this.Plus(e.Negate());
  }
}

// The complex numbers

struct Complex : Ring<Complex> { 
  private double re, im;

  public Complex(double re, double im) {
    this.re = re; this.im = im;
  }

  public Complex Zero() {
    return new Complex(0.0, 0.0);
  }

  public Complex Plus(Complex that) {
    return new Complex(re + that.re, im + that.im);
  }

  public Complex Negate() {
    return new Complex(-re, -im);
  }

  public Complex Minus(Complex that) {
    return new Complex(re - that.re, im - that.im);
  }

  public Complex Conjugate() {
    return new Complex(re, -im);
  }

  public Complex Times(Complex that) {
    return new Complex(re * that.re - im * that.im, 
		       im * that.re + re * that.im); 
  }

  public static Complex operator +(Complex z1, Complex z2) {
    return z1.Plus(z2);
  }

  public static Complex operator *(Complex z1, Complex z2) {
    return z1.Times(z2);
  }

  public static Complex operator *(Complex z, double r) {
    return new Complex(z.re * r, z.im * r);
  }

  public static Complex operator *(double r, Complex z) {
    return new Complex(z.re * r, z.im * r);
  }

  public static Complex operator -(Complex z1) {
    return z1.Negate();
  }

  public static Complex operator ~(Complex z1) {
    return z1.Conjugate();
  }
}

// The ring of polynomials

class Polynomial<E> : RingC< Polynomial<E>> 
  where E : Ring<E> { 
  // Coefficients of x^0, x^1, ...; absent coefficients are zero.
  // Invariant: cs != null && cs.Length >= 1, so cs[0].Zero() is a zero for E.
  private readonly E[] cs;  
  
  public Polynomial(E[] cs) {	
    this.cs = cs;
  }

  public Polynomial(E s) : this(new E[] { s }) { }	// Constant s

  public override Polynomial<E> Zero() {
    return new Polynomial<E>(cs[0].Zero());
  }

  public override Polynomial<E> Plus(Polynomial<E> that) {
    int newlen = Math.Max(this.cs.Length, that.cs.Length);
    int minlen = Math.Min(this.cs.Length, that.cs.Length);
    E[] newcs = new E[newlen];
    if (this.cs.Length <= that.cs.Length) {
      for (int i=0; i<minlen; i++)
	newcs[i] = this.cs[i].Plus(that.cs[i]);
      for (int i=minlen; i<newlen; i++)
	newcs[i] = that.cs[i];
    } else {
      for (int i=0; i<minlen; i++)
	newcs[i] = this.cs[i].Plus(that.cs[i]);
      for (int i=minlen; i<newlen; i++)
	newcs[i] = this.cs[i];
    }
    return new Polynomial<E>(newcs);
  }

  public override Polynomial<E> Times(Polynomial<E> that) {
    int newlen = Math.Max(1, this.cs.Length + that.cs.Length - 1);
    E[] newcs = new E[newlen];
    E zero = cs[0].Zero();
    for (int i=0; i<newlen; i++) {
      E sum = zero.Zero();
      int start = Math.Max(0, i-that.cs.Length+1);
      int stop  = Math.Min(i, this.cs.Length-1);
      for (int j=start; j<=stop; j++) {
	// assert 0<=j && j<this.cs.Length && 0<=i-j && i-j<that.cs.Length;
	sum = sum.Plus(this.cs[j].Times(that.cs[i-j]));
      }
      newcs[i] = sum;
    }
    return new Polynomial<E>(newcs);
  }

  public override Polynomial<E> Negate() {
    int newlen = cs.Length;
    E[] newcs = new E[newlen];
    for (int i=0; i<newlen; i++)
      newcs[i] = cs[i].Negate();
    return new Polynomial<E>(newcs);
  }

  public static Polynomial<E> operator + (Polynomial<E> p1, 
					  Polynomial<E> p2) {
    return p1.Plus(p2);
  }

  public static Polynomial<E> operator + (Polynomial<E> p1, E s) {
    return p1 + new Polynomial<E>(s);
  }

  public static Polynomial<E> operator * (Polynomial<E> p1, 
					  Polynomial<E> p2) {
    return p1.Times(p2);
  }

  public static Polynomial<E> operator * (Polynomial<E> p1, E s) {
    return p1.Times(new Polynomial<E>(s));
  }

  public static Polynomial<E> operator * (E s, Polynomial<E> p1) {
    return new Polynomial<E>(s).Times(p1);
  }

  public static Polynomial<E> operator - (Polynomial<E> p1) {
    return p1.Negate();
  }

  public E Evaluate(E x) {
    E res = x.Zero();
    for (int i=cs.Length-1; i>=0; i--)
      res = res.Times(x).Plus(cs[i]);
    return res;
  }

  public E this[E e] {
    get { return Evaluate(e); }
  }
}

// Trying it

class TestRing { 
  static void Main(string[] args) {
    Complex one = new Complex(1.0, 0.0);
    Complex i = new Complex(0.0, 1.0);
    Polynomial<Complex> p1 = 
      new Polynomial<Complex>(new Complex[] { one, i * 2.0, i });
    Polynomial<Complex> p2, p3;
    p2 = p1 * new Complex(7.0, 0.0) + p1 * p1;
    p3 = new Polynomial<Complex>(new Complex(0, 0));
    p3 += p2;
    p3 += new Complex(6.0, 0.0) * p2;
  }
}