mcs/class/Mono.CodeContracts/Mono.CodeContracts.Static.Analysis.Numerical/Monomial.cs

   1 //
   2 // Monomial.cs
   3 //
   4 // Authors:
   5 //      Alexander Chebaturkin (chebaturkin@gmail.com)
   6 //
   7 // Copyright (C) 2012 Alexander Chebaturkin
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28
  29 using System;
  30 using System.Collections.Generic;
  31 using System.Linq;
  32 using System.Text;
  33
  34 using Mono.CodeContracts.Static.DataStructures;
  35
  36 namespace Mono.CodeContracts.Static.Analysis.Numerical {
  37         struct Monomial<TVar> {
  38                 static readonly IComparer<TVar> Comparer = new ExpressionViaStringComparer<TVar> ();
  39
  40                 readonly Rational coefficient;
  41
  42                 readonly Sequence<TVar> variables;
  43
  44                 public Rational Coeff { get { return coefficient; } }
  45
  46                 public IEnumerable<TVar> Variables { get { return variables.AsEnumerable (); } }
  47
  48                 public int Degree { get; private set; }
  49
  50                 public bool IsLinear { get { return Degree <= 1; } }
  51
  52                 public bool IsConstant { get { return Degree == 0; } }
  53
  54                 Monomial (Rational coeff)
  55                         : this ()
  56                 {
  57                         coefficient = coeff;
  58                         variables = Sequence<TVar>.Empty;
  59                         Degree = 0;
  60                 }
  61
  62                 private Monomial (TVar x)
  63                         : this ()
  64                 {
  65                         coefficient = Rational.One;
  66                         variables = Sequence<TVar>.Singleton (x);
  67                         Degree = 1;
  68                 }
  69
  70                 private Monomial (Rational k, TVar x)
  71                         : this ()
  72                 {
  73                         coefficient = k;
  74                         variables = k == Rational.Zero ? Sequence<TVar>.Empty : Sequence<TVar>.Singleton (x);
  75                         Degree = variables.Length ();
  76                 }
  77
  78                 Monomial (Rational k, Sequence<TVar> vars)
  79                         : this ()
  80                 {
  81                         coefficient = k;
  82                         variables = k == Rational.Zero ? Sequence<TVar>.Empty : vars;
  83                         Degree = variables.Length ();
  84                 }
  85
  86                 public bool Contains (TVar var)
  87                 {
  88                         return variables.Any (v => v.Equals (var));
  89                 }
  90
  91                 public bool IsSingleVariable (out TVar var)
  92                 {
  93                         if (Degree == 1)
  94                                 return true.With (variables.Head, out var);
  95
  96                         return false.Without (out var);
  97                 }
  98
  99                 public Monomial<TVar> Rename (TVar x, TVar rename)
 100                 {
 101                         if (!Contains (x))
 102                                 return this;
 103
 104                         Func<TVar, TVar> renamer = v => v.Equals (x) ? rename : v;
 105
 106                         return From (Coeff, variables.Select (renamer));
 107                 }
 108
 109                 public Monomial<TVar> With (Rational coeff)
 110                 {
 111                         return new Monomial<TVar> (coeff, variables);
 112                 }
 113
 114                 public Monomial<TVar> With (Func<Rational, Rational> func)
 115                 {
 116                         return new Monomial<TVar> (func (coefficient), variables);
 117                 }
 118
 119                 public static Monomial<TVar> operator - (Monomial<TVar> m)
 120                 {
 121                         return m.With (-m.coefficient);
 122                 }
 123
 124                 public static Monomial<TVar> From (Rational coeff)
 125                 {
 126                         return new Monomial<TVar> (coeff);
 127                 }
 128
 129                 public static Monomial<TVar> From (Rational coeff, Sequence<TVar> vars)
 130                 {
 131                         return From (coeff, vars, seq => seq.AsEnumerable ());
 132                 }
 133
 134                 public static Monomial<TVar> From (Rational coeff, IEnumerable<TVar> vars)
 135                 {
 136                         return From (coeff, vars, seq => seq);
 137                 }
 138
 139                 static Monomial<TVar> From<T> (Rational coeff, T vars, Func<T, IEnumerable<TVar>> toEnumerable)
 140                 {
 141                         if (coeff == Rational.Zero)
 142                                 return new Monomial<TVar> (coeff);
 143
 144                         var list = toEnumerable (vars).ToList ();
 145                         list.Sort (Comparer);
 146
 147                         return new Monomial<TVar> (coeff, Sequence<TVar>.From (list));
 148                 }
 149
 150                 public override string ToString ()
 151                 {
 152                         return string.Format ("{0} * {1}", coefficient, VarsToString (variables));
 153                 }
 154
 155                 static string VarsToString (Sequence<TVar> seq)
 156                 {
 157                         var len = seq.Length ();
 158                         var sb = new StringBuilder ();
 159                         if (len == 0)
 160                                 sb.Append ("1");
 161                         else {
 162                                 sb.Append (seq.Head);
 163                                 seq.Tail.ForEach (v => sb.AppendFormat (" * {0}", v));
 164                         }
 165
 166                         return sb.ToString ();
 167                 }
 168
 169                 public bool IsEquivalentTo (Monomial<TVar> that)
 170                 {
 171                         if (coefficient != that.coefficient || Degree != that.Degree)
 172                                 return false;
 173
 174                         if (Degree == 1)
 175                                 return variables.Head.Equals (that.variables.Head);
 176
 177                         foreach (var var in variables.AsEnumerable ()) {
 178                                 if (!that.Contains (var))
 179                                         return false;
 180                         }
 181
 182                         return true;
 183                 }
 184
 185                 public override bool Equals (object obj)
 186                 {
 187                         if (ReferenceEquals (obj, null))
 188                                 return false;
 189
 190                         if (obj is Monomial<TVar>)
 191                                 return IsEquivalentTo ((Monomial<TVar>) obj);
 192                         return false;
 193                 }
 194
 195                 public override int GetHashCode ()
 196                 {
 197                         var res = 0;
 198                         variables.ForEach (v => res += v.GetHashCode ());
 199                         return res + coefficient.GetHashCode ();
 200                 }
 201
 202                 public bool IsIntConstant (out long constant)
 203                 {
 204                         if (IsConstant && coefficient.IsInteger)
 205                                 return true.With ((long) coefficient.NextInt64, out constant);
 206
 207                         return false.Without (out constant);
 208                 }
 209         }
 210 }