Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Analysis.AlgorithmBehavior/liblrs/Testliblrs/FractionClass.cs @ 10355

Last change on this file since 10355 was 10198, checked in by ascheibe, 11 years ago

#1886

  • added liblrs and c# wrapper for vertex enumeration/volume calculation
  • use MIConvexHull for triangulation and volume calculation
  • fixed vertex conversion code for MIConvexHull lib
  • added a unit test for measuring performance of convex hull/volume calculation
File size: 45.3 KB
Line 
1  /*
2  * Author: Syed Mehroz Alam
3  * Email: smehrozalam@yahoo.com
4  * URL: Programming Home "http://www.geocities.com/smehrozalam/"
5  *
6  */
7
8  using System;
9  using System.Runtime.InteropServices;
10  using System.Globalization;
11
12  namespace Mehroz
13  {
14    /// <summary>
15    /// Classes Contained:
16    ///     Fraction
17    ///     FractionException
18    /// </summary>
19     
20    /// Class name: Fraction
21    /// Developed by: Syed Mehroz Alam
22    /// Email: mailto:smehrozalam@yahoo.com
23    /// URL: http://www.geocities.com/smehrozalam/
24    /// Changes: Marc C. Brooks  mailto:IDisposable@gmail.com
25    ///          Jeffery Sax    http://www.extremeoptimization.com
26    /// Version: 2.2
27    ///
28    /// What's new in version 2.0:
29    ///     *   Changed Numerator and Denominator from Int32(integer) to Int64(long) for increased range
30    ///     *   renamed ConvertToString() to (overloaded) ToString()
31    ///     *   added the capability of detecting/raising overflow exceptions
32    ///     *   Fixed the bug that very small numbers e.g. 0.00000001 could not be converted to fraction
33    ///     *   Other minor bugs fixed
34    ///
35    /// What's new in version 2.1
36    ///     *   overloaded user-defined conversions to/from Fractions
37    ///
38    /// What's new in version 2.2 - Marc C. Brooks   mailto:IDisposable@gmail.com
39    ///     *   less overflows by finding the GCD for Add [Jeffery Sax] and Multiply [Marc C. Brooks]
40    ///     *   understands and handles NaN, PositiveInfinity, NegativeInfinity just like double [Marc C. Brooks]
41    ///     *   fixed several uses of int where long was correct [Marc C. Brooks]
42    ///     *   made value-type (struct) [Jeffery Sax]
43    ///     *   added ToInt32(), ToInt64() which throw for invalid (NaN, PositiveInfinity, NegativeInfinity) [Marc C. Brooks]
44    ///     *   removed redundant Value property [Jeffery Sax]
45    ///     *   added explicit conversion to Int32 and Int64 [Marc C. Brooks]
46    ///     *   better handling of exceptions [Marc C. Brooks]
47    ///     *   reorganize code, add XML doc and regions [Marc C. Brooks]
48    ///     *   proper implementations of Equals [Marc C. Brooks, Jeffery Sax]
49    ///     *   uses Math.Log(xx,2) and Math.Pow(xx,2) to get the best accuracy possible when converting doubles [Marc C. Brooks, Jeffery Sax]
50    ///
51    /// What's new in version 2.3 - Marc C. Brooks   mailto:IDisposable@gmail.com   01/10/2005
52    ///     *   fixed double-to-fraction logic to use continued fraction rules to get best possible precistion [bug fix for Syed Mehroz Alam, idea from  Jeffery Sax]
53    ///     * added static readonly values for NaN, PositiveInfinity, NegativeInfinity [idea from Jeffery Sax]
54    ///     * moved comparisons into an implementation of IComparer [idea from Jeffery Sax]
55    ///     * no longer throws for NaN(s) involved in Add, Subtract, Multiply, Divide operations [idea from Jeffery Sax]
56    ///     *   added static readonly values for Zero, MinValue, MaxValue, Epsilon to better mirror double
57    ///     *   added IsInfinity to better mirror double.
58    ///     *   added Modulus and % operators
59    ///
60    /// Properties:
61    ///     Numerator: Set/Get value for Numerator
62    ///     Denominator:  Set/Get value for Numerator
63    ///     [Note: If you Set either Property, the Fraction should be passed to ReduceFraction at some point.]
64    ///
65    /// Constructors:
66    ///     no arguments:   initializes fraction as 0/0 = NaN, so don't do that!
67    ///     (Numerator, Denominator): initializes fraction with the given numerator and denominator
68    ///                               values and reduces
69    ///     (long): initializes fraction with the given long value
70    ///     (double):   initializes fraction with the given double value
71    ///     (string):   initializes fraction with the given string value
72    ///                 the string can be an in the form of and integer, double or fraction.
73    ///                 e.g it can be like "123" or "123.321" or "123/456"
74    ///
75    /// Public Methods (Description is given with respective methods' definitions)
76    ///     Fraction ToFraction(long)
77    ///     Fraction ToFraction(double)
78    ///     Fraction ToFraction(string)
79    ///     Int32 ToInt32()
80    ///     Int64 ToInt64()
81    ///     double ToDouble()
82    ///     (override) string ToString()
83    ///     Fraction Inverse()
84    ///     Fraction Inverted(long)
85    ///     Fraction Inverted(double)
86    ///     ReduceFraction(ref Fraction)
87    ///     CrossReducePair(ref Fraction, ref Fraction)
88    ///     (override) Equals(object)
89    ///     (override) GetHashCode()
90    ///
91    /// Overloaded Operators (overloaded for Fractions, long and double)
92    ///     Unary: -
93    ///     Binary: +,-,*,/
94    ///     Relational and Logical Operators: ==,!=,<,>,<=,>= (only == and != for long and doubles)
95    ///
96    /// Overloaded user-defined conversions
97    ///     Implicit:   From long/double/string to Fraction
98    ///     Explicit:   From Fraction to long/double/string
99    /// </summary>
100    [Serializable, StructLayout(LayoutKind.Sequential)]
101    public struct Fraction : IComparable, IFormattable
102    {
103      #region Constructors
104      /// <summary>
105      /// Construct a Fraction from an integral value
106      /// </summary>
107      /// <param name="wholeNumber">The value (eventual numerator)</param>
108      /// <remarks>The denominator will be 1</remarks>
109      public Fraction(long wholeNumber)
110      {
111        if (wholeNumber == long.MinValue)
112          wholeNumber++;  // prevent serious issues later..
113
114        m_Numerator = wholeNumber;
115        m_Denominator = 1;
116        // no reducing required, we're a whole number
117      }
118     
119      /// <summary>
120      /// Construct a Fraction from a floating-point value
121      /// </summary>
122      /// <param name="floatingPointNumber">The value</param>
123      public Fraction(double floatingPointNumber)
124      {
125        this = ToFraction(floatingPointNumber);
126      }
127         
128      /// <summary>
129      /// Construct a Fraction from a string in any legal format
130      /// </summary>
131      /// <param name="inValue">A string with a legal fraction input format</param>
132      /// <remarks>Will reduce the fraction to smallest possible denominator</remarks>
133      /// <see>ToFraction(string strValue)</see>
134      public Fraction(string inValue)
135      {
136        this = ToFraction(inValue);
137      }
138         
139      /// <summary>
140      /// Construct a Fraction from a numerator, denominator pair
141      /// </summary>
142      /// <param name="numerator">The numerator (top number)</param>
143      /// <param name="denominator">The denominator (bottom number)</param>
144      /// <remarks>Will reduce the fraction to smallest possible denominator</remarks>
145      public Fraction(long numerator, long denominator)
146      {
147        if (numerator == long.MinValue)
148          numerator++;  // prevent serious issues later..
149
150        if (denominator == long.MinValue)
151          denominator++;  // prevent serious issues later..
152
153        m_Numerator = numerator;
154        m_Denominator = denominator;
155        ReduceFraction(ref this);
156      }
157
158      /// <summary>
159      /// Private constructor to synthesize a Fraction for indeterminates (NaN and infinites)
160      /// </summary>
161      /// <param name="type">Kind of inderterminate</param>
162      private Fraction(Indeterminates type)
163      {
164        m_Numerator = (long)type;
165        m_Denominator = 0;
166        // do NOT reduce, we're clean as can be!
167      }
168      #endregion
169
170      #region Properties
171      /// <summary>
172      /// The 'top' part of the fraction
173      /// </summary>
174      /// <example>For 3/4ths, this is the 3</example>
175      public long Numerator
176      {
177        get
178        {
179          return m_Numerator;
180        }
181        set
182        {
183          m_Numerator = value;
184        }
185      }
186
187      /// <summary>
188      /// The 'bottom' part of the fraction
189      /// </summary>
190      /// <example>For 3/4ths, this is the 4</example>
191      public long Denominator
192      {
193        get
194        {
195          return m_Denominator;
196        }
197        set
198        {
199          m_Denominator = value;
200        }
201      }
202      #endregion
203
204      #region Expose constants
205      public static readonly Fraction NaN = new Fraction(Indeterminates.NaN);
206      public static readonly Fraction PositiveInfinity = new Fraction(Indeterminates.PositiveInfinity);
207      public static readonly Fraction NegativeInfinity = new Fraction(Indeterminates.NegativeInfinity);
208      public static readonly Fraction Zero = new Fraction(0,1);
209      public static readonly Fraction Epsilon = new Fraction(1, Int64.MaxValue);
210      private static readonly double EpsilonDouble = 1.0 / Int64.MaxValue;
211      public static readonly Fraction MaxValue = new Fraction(Int64.MaxValue, 1);
212      public static readonly Fraction MinValue = new Fraction(Int64.MinValue, 1);
213      #endregion
214
215      #region Explicit conversions
216      #region To primitives
217      /// <summary>
218      /// Get the integral value of the Fraction object as int/Int32
219      /// </summary>
220      /// <returns>The (approximate) integer value</returns>
221      /// <remarks>If the value is not a true integer, the fractional part is discarded
222      /// (truncated toward zero). If the valid exceeds the range of an Int32 and exception is thrown.</remarks>
223      /// <exception cref="FractionException">Will throw a FractionException for NaN, PositiveInfinity
224      /// or NegativeInfinity with the InnerException set to a System.NotFiniteNumberException.</exception>
225      /// <exception cref="OverflowException" Will throw a System.OverflowException if the value is too
226      /// large or small to be represented as an Int32.</exception>
227      public Int32 ToInt32()
228      {
229        if (this.m_Denominator == 0)
230        {
231          throw new FractionException(string.Format("Cannot convert {0} to Int32", IndeterminateTypeName(this.m_Numerator)), new System.NotFiniteNumberException());
232        }
233
234        long bestGuess = this.m_Numerator / this.m_Denominator;
235
236        if (bestGuess > Int32.MaxValue || bestGuess < Int32.MinValue)
237        {
238          throw new FractionException("Cannot convert to Int32", new System.OverflowException());
239        }
240
241        return (Int32)bestGuess;
242      }
243
244      /// <summary>
245      /// Get the integral value of the Fraction object as long/Int64
246      /// </summary>
247      /// <returns>The (approximate) integer value</returns>
248      /// <remarks>If the value is not a true integer, the fractional part is discarded
249      /// (truncated toward zero). If the valid exceeds the range of an Int32, no special
250      /// handling is guaranteed.</remarks>
251      /// <exception cref="FractionException">Will throw a FractionException for NaN, PositiveInfinity
252      /// or NegativeInfinity with the InnerException set to a System.NotFiniteNumberException.</exception>
253      public Int64 ToInt64()
254      {
255        if (this.m_Denominator == 0)
256        {
257          throw new FractionException(string.Format("Cannot convert {0} to Int64", IndeterminateTypeName(this.m_Numerator)), new System.NotFiniteNumberException());
258        }
259
260        return this.m_Numerator / this.m_Denominator;
261      }
262
263      /// <summary>
264      /// Get the value of the Fraction object as double with full support for NaNs and infinities
265      /// </summary>
266      /// <returns>The decimal representation of the Fraction, or double.NaN, double.NegativeInfinity
267      /// or double.PositiveInfinity</returns>
268      public double ToDouble()
269      {
270        if (this.m_Denominator == 1)
271          return this.m_Numerator;
272        else if (this.m_Denominator == 0)
273        {
274          switch (NormalizeIndeterminate(this.m_Numerator))
275          {
276            case Indeterminates.NegativeInfinity:
277              return double.NegativeInfinity;
278
279            case Indeterminates.PositiveInfinity:
280              return double.PositiveInfinity;
281
282            case Indeterminates.NaN:
283            default:    // this can't happen
284              return double.NaN;
285          }
286        }
287        else
288        {
289          return (double)this.m_Numerator / (double)this.m_Denominator;
290        }
291      }
292
293      /// <summary>
294      /// Get the value of the Fraction as a string, with proper representation for NaNs and infinites
295      /// </summary>
296      /// <returns>The string representation of the Fraction, or the culture-specific representations of
297      /// NaN, PositiveInfinity or NegativeInfinity.</returns>
298      /// <remarks>The current culture determines the textual representation the Indeterminates</remarks>
299      public override string ToString()
300      {
301        if (this.m_Denominator == 1)
302        {
303          return this.m_Numerator.ToString();
304        }
305        else if (this.m_Denominator == 0)
306        {
307          return IndeterminateTypeName(this.m_Numerator);
308        }
309        else
310        {
311          return this.m_Numerator.ToString() + "/" + this.m_Denominator.ToString();
312        }
313      }
314      #endregion
315
316      #region From primitives
317      /// <summary>
318      /// Converts a long value to the exact Fraction
319      /// </summary>
320      /// <param name="inValue">The long to convert</param>
321      /// <returns>An exact representation of the value</returns>
322      public static Fraction ToFraction(long inValue)
323      {
324        return new Fraction(inValue);
325      }
326
327      /// <summary>
328      /// Converts a double value to the approximate Fraction
329      /// </summary>
330      /// <param name="inValue">The double to convert</param>
331      /// <returns>A best-fit representation of the value</returns>
332      /// <remarks>Supports double.NaN, double.PositiveInfinity and double.NegativeInfinity</remarks>
333      public static Fraction ToFraction(double inValue)
334      {
335        // it's one of the indeterminates... which?
336        if (double.IsNaN(inValue))
337          return NaN;
338        else if (double.IsNegativeInfinity(inValue))
339          return NegativeInfinity;
340        else if (double.IsPositiveInfinity(inValue))
341          return PositiveInfinity;
342        else if (inValue == 0.0d)
343          return Zero;
344
345        if (inValue > Int64.MaxValue)
346          throw new OverflowException(string.Format("Double {0} too large", inValue));
347
348        if (inValue < -Int64.MaxValue)
349          throw new OverflowException(string.Format("Double {0} too small", inValue));
350
351        if (-EpsilonDouble < inValue && inValue < EpsilonDouble)
352          throw new ArithmeticException(string.Format("Double {0} cannot be represented", inValue));
353
354        int sign = Math.Sign(inValue);
355        inValue = Math.Abs(inValue);
356
357        return ConvertPositiveDouble(sign, inValue);
358      }
359
360      /// <summary>
361      /// Converts a string to the corresponding reduced fraction
362      /// </summary>
363      /// <param name="inValue">The string representation of a fractional value</param>
364      /// <returns>The Fraction that represents the string</returns>
365      /// <remarks>Four forms are supported, as a plain integer, as a double, or as Numerator/Denominator
366      /// and the representations for NaN and the infinites</remarks>
367      /// <example>"123" = 123/1 and "1.25" = 5/4 and "10/36" = 5/13 and NaN = 0/0 and
368      /// PositiveInfinity = 1/0 and NegativeInfinity = -1/0</example>
369      public static Fraction ToFraction(string inValue)
370      {
371        if (inValue == null || inValue == string.Empty)
372          throw new ArgumentNullException("inValue");
373
374        // could also be NumberFormatInfo.InvariantInfo
375        NumberFormatInfo info = NumberFormatInfo.CurrentInfo;
376
377        // Is it one of the special symbols for NaN and such...
378        string trimmedValue = inValue.Trim();
379
380        if (trimmedValue == info.NaNSymbol)
381          return NaN;
382        else if (trimmedValue == info.PositiveInfinitySymbol)
383          return PositiveInfinity;
384        else if (trimmedValue == info.NegativeInfinitySymbol)
385          return NegativeInfinity;
386        else
387        {
388          // Not special, is it a Fraction?
389          int slashPos = inValue.IndexOf('/');
390
391          if (slashPos > -1)
392          {
393            // string is in the form of Numerator/Denominator
394            long numerator = Convert.ToInt64(inValue.Substring(0, slashPos));
395            long denominator = Convert.ToInt64(inValue.Substring(slashPos + 1));
396
397            return new Fraction(numerator, denominator);
398          }
399          else
400          {
401            // the string is not in the form of a fraction
402            // hopefully it is double or integer, do we see a decimal point?
403            int decimalPos = inValue.IndexOf(info.CurrencyDecimalSeparator);
404
405            if (decimalPos > -1)
406              return new Fraction(Convert.ToDouble(inValue));
407            else
408              return new Fraction(Convert.ToInt64(inValue));
409          }
410        }
411      }
412      #endregion
413      #endregion
414
415      #region Indeterminate classifications
416      /// <summary>
417      /// Determines if a Fraction represents a Not-a-Number
418      /// </summary>
419      /// <returns>True if the Fraction is a NaN</returns>
420      public bool IsNaN()
421      {
422        if (this.m_Denominator == 0
423          && NormalizeIndeterminate(this.m_Numerator) == Indeterminates.NaN)
424          return true;
425        else
426          return false;
427      }
428
429      /// <summary>
430      /// Determines if a Fraction represents Any Infinity
431      /// </summary>
432      /// <returns>True if the Fraction is Positive Infinity or Negative Infinity</returns>
433      public bool IsInfinity()
434      {
435        if (this.m_Denominator == 0
436          && NormalizeIndeterminate(this.m_Numerator) != Indeterminates.NaN)
437          return true;
438        else
439          return false;
440      }
441
442      /// <summary>
443      /// Determines if a Fraction represents Positive Infinity
444      /// </summary>
445      /// <returns>True if the Fraction is Positive Infinity</returns>
446      public bool IsPositiveInfinity()
447      {
448        if (this.m_Denominator == 0
449          && NormalizeIndeterminate(this.m_Numerator) == Indeterminates.PositiveInfinity)
450          return true;
451        else
452          return false;
453      }
454
455      /// <summary>
456      /// Determines if a Fraction represents Negative Infinity
457      /// </summary>
458      /// <returns>True if the Fraction is Negative Infinity</returns>
459      public bool IsNegativeInfinity()
460      {
461        if (this.m_Denominator == 0
462          && NormalizeIndeterminate(this.m_Numerator) == Indeterminates.NegativeInfinity)
463          return true;
464        else
465          return false;
466      }
467      #endregion
468
469      #region Inversion
470      /// <summary>
471      /// Inverts a Fraction
472      /// </summary>
473      /// <returns>The inverted Fraction (with Denominator over Numerator)</returns>
474      /// <remarks>Does NOT throw for zero Numerators as later use of the fraction will catch the error.</remarks>
475      public Fraction Inverse()
476      {
477        // don't use the obvious constructor because we do not want it normalized at this time
478        Fraction frac = new Fraction();
479
480        frac.m_Numerator = this.m_Denominator;
481        frac.m_Denominator = this.m_Numerator;
482        return frac;
483      }
484
485      /// <summary>
486      /// Creates an inverted Fraction
487      /// </summary>
488      /// <returns>The inverted Fraction (with Denominator over Numerator)</returns>
489      /// <remarks>Does NOT throw for zero Numerators as later use of the fraction will catch the error.</remarks>
490      public static Fraction Inverted(long value)
491      {
492        Fraction frac = new Fraction(value);
493        return frac.Inverse();
494      }
495
496      /// <summary>
497      /// Creates an inverted Fraction
498      /// </summary>
499      /// <returns>The inverted Fraction (with Denominator over Numerator)</returns>
500      /// <remarks>Does NOT throw for zero Numerators as later use of the fraction will catch the error.</remarks>
501      public static Fraction Inverted(double value)
502      {
503        Fraction frac = new Fraction(value);
504        return frac.Inverse();
505      }
506      #endregion
507
508      #region Operators
509      #region Unary Negation operator
510      /// <summary>
511      /// Negates the Fraction
512      /// </summary>
513      /// <param name="left">The Fraction to negate</param>
514      /// <returns>The negative version of the Fraction</returns>
515      public static Fraction operator -(Fraction left)
516      {
517        return Negate(left);
518      }
519      #endregion
520
521      #region Addition operators
522      public static Fraction operator +(Fraction left, Fraction right)
523      {
524        return Add(left, right);
525      }
526     
527      public static Fraction operator +(long left, Fraction right)
528      {
529        return Add(new Fraction(left), right);
530      }
531     
532      public static Fraction operator +(Fraction left, long right)
533      {
534        return Add(left, new Fraction(right));
535      }
536
537      public static Fraction operator +(double left, Fraction right)
538      {
539        return Add(ToFraction(left), right);
540      }
541     
542      public static Fraction operator +(Fraction left, double right)
543      {
544        return Add(left, ToFraction(right));
545      }
546      #endregion
547
548      #region Subtraction operators
549      public static Fraction operator -(Fraction left, Fraction right)
550      {
551        return Add(left, - right);
552      }
553     
554      public static Fraction operator -(long left, Fraction right)
555      {
556        return Add(new Fraction(left), - right);
557      }
558     
559      public static Fraction operator -(Fraction left, long right)
560      {
561        return Add(left, new Fraction(- right));
562      }
563
564      public static Fraction operator -(double left, Fraction right)
565      {
566        return Add(ToFraction(left), - right);
567      }
568     
569      public static Fraction operator -(Fraction left, double right)
570      {
571        return Add(left, ToFraction(- right));
572      }
573      #endregion
574
575      #region Multiplication operators
576      public static Fraction operator *(Fraction left, Fraction right)
577      {
578        return Multiply(left, right);
579      }
580     
581      public static Fraction operator *(long left, Fraction right)
582      {
583        return Multiply(new Fraction(left), right);
584      }
585     
586      public static Fraction operator *(Fraction left, long right)
587      {
588        return Multiply(left, new Fraction(right));
589      }
590     
591      public static Fraction operator *(double left, Fraction right)
592      {
593        return Multiply(ToFraction(left), right);
594      }
595     
596      public static Fraction operator *(Fraction left, double right)
597      {
598        return Multiply(left, ToFraction(right));
599      }
600      #endregion
601
602      #region Division operators
603      public static Fraction operator /(Fraction left, Fraction right)
604      {
605        return Multiply(left, right.Inverse());
606      }
607     
608      public static Fraction operator /(long left, Fraction right)
609      {
610        return Multiply(new Fraction(left), right.Inverse());
611      }
612     
613      public static Fraction operator /(Fraction left, long right)
614      {
615        return Multiply(left, Inverted(right));
616      }
617     
618      public static Fraction operator /(double left, Fraction right)
619      {
620        return Multiply(ToFraction(left), right.Inverse());
621      }
622     
623      public static Fraction operator /(Fraction left, double right)
624      {
625        return Multiply(left, Inverted(right));
626      }
627      #endregion
628
629      #region Modulus operators
630      public static Fraction operator %(Fraction left, Fraction right)
631      {
632        return Modulus(left, right);
633      }
634     
635      public static Fraction operator %(long left, Fraction right)
636      {
637        return Modulus(new Fraction(left), right);
638      }
639     
640      public static Fraction operator %(Fraction left, long right)
641      {
642        return Modulus(left, right);
643      }
644     
645      public static Fraction operator %(double left, Fraction right)
646      {
647        return Modulus(ToFraction(left), right);
648      }
649     
650      public static Fraction operator %(Fraction left, double right)
651      {
652        return Modulus(left, right);
653      }
654      #endregion
655
656      #region Equal operators
657      public static bool operator ==(Fraction left, Fraction right)
658      {
659        return left.CompareEquality(right, false);
660      }
661
662      public static bool operator ==(Fraction left, long right)
663      {
664        return left.CompareEquality(new Fraction(right), false);
665      }
666
667      public static bool operator ==(Fraction left, double right)
668      {
669        return left.CompareEquality(new Fraction(right), false);
670      }
671      #endregion
672
673      #region Not-equal operators
674      public static bool operator !=(Fraction left, Fraction right)
675      {
676        return left.CompareEquality(right, true);
677      }
678
679      public static bool operator !=(Fraction left, long right)
680      {
681        return left.CompareEquality(new Fraction(right), true);
682      }
683         
684      public static bool operator !=(Fraction left, double right)
685      {
686        return left.CompareEquality(new Fraction(right), true);
687      }
688      #endregion
689
690      #region Inequality operators
691      /// <summary>
692      /// Compares two Fractions to see if left is less than right
693      /// </summary>
694      /// <param name="left">The first Fraction</param>
695      /// <param name="right">The second Fraction</param>
696      /// <returns>True if <paramref name="left">left</paramref> is less
697      /// than <paramref name="right">right</paramref></returns>
698      /// <remarks>Special handling for indeterminates exists. <see>IndeterminateLess</see></remarks>
699      /// <exception cref="FractionException">Throws an error if overflows occur while computing the
700      /// difference with an InnerException of OverflowException</exception>
701      public static bool operator <(Fraction left, Fraction right)
702      {
703        return left.CompareTo(right) < 0;
704      }
705
706      /// <summary>
707      /// Compares two Fractions to see if left is greater than right
708      /// </summary>
709      /// <param name="left">The first Fraction</param>
710      /// <param name="right">The second Fraction</param>
711      /// <returns>True if <paramref name="left">left</paramref> is greater
712      /// than <paramref name="right">right</paramref></returns>
713      /// <remarks>Special handling for indeterminates exists. <see>IndeterminateLess</see></remarks>
714      /// <exception cref="FractionException">Throws an error if overflows occur while computing the
715      /// difference with an InnerException of OverflowException</exception>
716      public static bool operator >(Fraction left, Fraction right)
717      {
718        return left.CompareTo(right) > 0;
719      }
720
721      /// <summary>
722      /// Compares two Fractions to see if left is less than or equal to right
723      /// </summary>
724      /// <param name="left">The first Fraction</param>
725      /// <param name="right">The second Fraction</param>
726      /// <returns>True if <paramref name="left">left</paramref> is less than or
727      /// equal to <paramref name="right">right</paramref></returns>
728      /// <remarks>Special handling for indeterminates exists. <see>IndeterminateLessEqual</see></remarks>
729      /// <exception cref="FractionException">Throws an error if overflows occur while computing the
730      /// difference with an InnerException of OverflowException</exception>
731      public static bool operator <=(Fraction left, Fraction right)
732      {
733        return left.CompareTo(right) <= 0;
734      }
735         
736      /// <summary>
737      /// Compares two Fractions to see if left is greater than or equal to right
738      /// </summary>
739      /// <param name="left">The first Fraction</param>
740      /// <param name="right">The second Fraction</param>
741      /// <returns>True if <paramref name="left">left</paramref> is greater than or
742      /// equal to <paramref name="right">right</paramref></returns>
743      /// <remarks>Special handling for indeterminates exists. <see>IndeterminateLessEqual</see></remarks>
744      /// <exception cref="FractionException">Throws an error if overflows occur while computing the
745      /// difference with an InnerException of OverflowException</exception>
746      public static bool operator >=(Fraction left, Fraction right)
747      {
748        return left.CompareTo(right) >= 0;
749      }
750      #endregion
751
752      #region Implict conversion from primitive operators
753      /// <summary>
754      /// Implicit conversion of a long integral value to a Fraction
755      /// </summary>
756      /// <param name="value">The long integral value to convert</param>
757      /// <returns>A Fraction whose denominator is 1</returns>
758      public static implicit operator Fraction(long value)
759      {
760        return new Fraction(value);
761      }
762
763      /// <summary>
764      /// Implicit conversion of a double floating point value to a Fraction
765      /// </summary>
766      /// <param name="value">The double value to convert</param>
767      /// <returns>A reduced Fraction</returns>
768      public static implicit operator Fraction(double value)
769      {
770        return new Fraction(value);
771      }
772
773      /// <summary>
774      /// Implicit conversion of a string to a Fraction
775      /// </summary>
776      /// <param name="value">The string to convert</param>
777      /// <returns>A reduced Fraction</returns>
778      public static implicit operator Fraction(string value)
779      {
780        return new Fraction(value);
781      }
782      #endregion
783
784      #region Explicit converstion to primitive operators
785      /// <summary>
786      /// Explicit conversion from a Fraction to an integer
787      /// </summary>
788      /// <param name="frac">the Fraction to convert</param>
789      /// <returns>The integral representation of the Fraction</returns>
790      public static explicit operator int(Fraction frac)
791      {
792        return frac.ToInt32();
793      }
794
795      /// <summary>
796      /// Explicit conversion from a Fraction to an integer
797      /// </summary>
798      /// <param name="frac">The Fraction to convert</param>
799      /// <returns>The integral representation of the Fraction</returns>
800      public static explicit operator long(Fraction frac)
801      {
802        return frac.ToInt64();
803      }
804
805      /// <summary>
806      /// Explicit conversion from a Fraction to a double floating-point value
807      /// </summary>
808      /// <param name="frac">The Fraction to convert</param>
809      /// <returns>The double representation of the Fraction</returns>
810      public static explicit operator double(Fraction frac)
811      {
812        return frac.ToDouble();
813      }
814
815      /// <summary>
816      /// Explicit conversion from a Fraction to a string
817      /// </summary>
818      /// <param name="frac">the Fraction to convert</param>
819      /// <returns>The string representation of the Fraction</returns>
820      public static implicit operator string(Fraction frac)
821      {
822        return frac.ToString();
823      }
824      #endregion
825      #endregion
826
827      #region Equals and GetHashCode overrides
828      /// <summary>
829      /// Compares for equality the current Fraction to the value passed.
830      /// </summary>
831      /// <param name="obj">A  Fraction,</param>
832      /// <returns>True if the value equals the current fraction, false otherwise (including for
833      /// non-Fraction types or null object.</returns>
834      public override bool Equals(object obj)
835      {
836        if (obj == null || ! (obj is Fraction))
837          return false;
838
839        try
840        {
841          Fraction right = (Fraction)obj;
842          return this.CompareEquality(right, false);
843        }
844        catch
845        {
846          // can't throw in an Equals!
847          return false;
848        }
849      }
850         
851      /// <summary>
852      /// Returns a hash code generated from the current Fraction
853      /// </summary>
854      /// <returns>The hash code</returns>
855      /// <remarks>Reduces (in-place) the Fraction first.</remarks>
856      public override int GetHashCode()
857      {
858        // insure we're as close to normalized as possible first
859        ReduceFraction(ref this);
860
861        int numeratorHash = this.m_Numerator.GetHashCode();
862        int denominatorHash = this.m_Denominator.GetHashCode();
863
864        return (numeratorHash ^ denominatorHash);
865      }
866      #endregion
867
868      #region IComparable member and type-specific version
869      /// <summary>
870      /// Compares an object to this Fraction
871      /// </summary>
872      /// <param name="obj">The object to compare against (null is less than everything)</param>
873      /// <returns>-1 if this is less than <paramref name="obj"></paramref>,
874      ///  0 if they are equal,
875      ///  1 if this is greater than <paramref name="obj"></paramref></returns>
876      /// <remarks>Will convert an object from longs, doubles, and strings as this is a value-type.</remarks>
877      public int CompareTo(object obj)
878      {
879        if (obj == null)
880          return 1; // null is less than anything
881
882        Fraction right;
883
884        if (obj is Fraction)
885          right = (Fraction)obj;
886        else if (obj is long)
887          right = (long)obj;
888        else if (obj is double)
889          right = (double)obj;
890        else if (obj is string)
891          right = (string)obj;
892        else
893          throw new ArgumentException("Must be convertible to Fraction", "obj");
894
895        return this.CompareTo(right);
896      }
897
898      /// <summary>
899      /// Compares this Fraction to another Fraction
900      /// </summary>
901      /// <param name="right">The Fraction to compare against</param>
902      /// <returns>-1 if this is less than <paramref name="right"></paramref>,
903      ///  0 if they are equal,
904      ///  1 if this is greater than <paramref name="right"></paramref></returns>
905      public int CompareTo(Fraction right)
906      {
907        // if left is an indeterminate, punt to the helper...
908        if (this.m_Denominator == 0)
909        {
910          return IndeterminantCompare(NormalizeIndeterminate(this.m_Numerator), right);
911        }
912
913        // if right is an indeterminate, punt to the helper...
914        if (right.m_Denominator == 0)
915        {
916          // note sign-flip...
917          return - IndeterminantCompare(NormalizeIndeterminate(right.m_Numerator), this);
918        }
919
920        // they're both normal Fractions
921        CrossReducePair(ref this, ref right);
922
923        try
924        {
925          checked
926          {
927            long leftScale = this.m_Numerator * right.m_Denominator;
928            long rightScale = this.m_Denominator * right.m_Numerator;
929
930            if (leftScale < rightScale)
931              return -1;
932            else if (leftScale > rightScale)
933              return 1;
934            else
935              return 0;
936          }
937        }
938        catch (Exception e)
939        {
940          throw new FractionException(string.Format("CompareTo({0}, {1}) error", this, right), e);
941        }
942      }
943      #endregion
944
945      #region IFormattable Members
946      string System.IFormattable.ToString(string format, IFormatProvider formatProvider)
947      {
948        return this.m_Numerator.ToString(format, formatProvider) + "/" + this.m_Denominator.ToString(format, formatProvider);
949      }
950      #endregion
951
952      #region Reduction
953      /// <summary>
954      /// Reduces (simplifies) a Fraction by dividing down to lowest possible denominator (via GCD)
955      /// </summary>
956      /// <param name="frac">The Fraction to be reduced [WILL BE MODIFIED IN PLACE]</param>
957      /// <remarks>Modifies the input arguments in-place! Will normalize the NaN and infinites
958      /// representation. Will set Denominator to 1 for any zero numerator. Moves sign to the
959      /// Numerator.</remarks>
960      /// <example>2/4 will be reduced to 1/2</example>
961      public static void ReduceFraction(ref Fraction frac)
962      {
963        // clean up the NaNs and infinites
964        if (frac.m_Denominator == 0)
965        {
966          frac.m_Numerator = (long)NormalizeIndeterminate(frac.m_Numerator);
967          return;
968        }
969
970        // all forms of zero are alike.
971        if (frac.m_Numerator == 0)
972        {
973          frac.m_Denominator = 1;
974          return;
975        }
976             
977        long iGCD = GCD(frac.m_Numerator, frac.m_Denominator);
978        frac.m_Numerator /= iGCD;
979        frac.m_Denominator /= iGCD;
980         
981        // if negative sign in denominator
982        if ( frac.m_Denominator < 0 )
983        {
984          //move negative sign to numerator
985          frac.m_Numerator = - frac.m_Numerator;
986          frac.m_Denominator = - frac.m_Denominator; 
987        }
988      }
989
990      /// <summary>
991      /// Cross-reduces a pair of Fractions so that we have the best GCD-reduced values for multiplication
992      /// </summary>
993      /// <param name="frac1">The first Fraction [WILL BE MODIFIED IN PLACE]</param>
994      /// <param name="frac2">The second Fraction [WILL BE MODIFIED IN PLACE]</param>
995      /// <remarks>Modifies the input arguments in-place!</remarks>
996      /// <example>(3/4, 5/9) = (1/4, 5/3)</example>
997      public static void CrossReducePair(ref Fraction frac1, ref Fraction frac2)
998      {
999        // leave the indeterminates alone!
1000        if (frac1.m_Denominator == 0 || frac2.m_Denominator == 0)
1001          return;
1002
1003        long gcdTop = GCD(frac1.m_Numerator, frac2.m_Denominator);
1004        frac1.m_Numerator = frac1.m_Numerator / gcdTop;
1005        frac2.m_Denominator = frac2.m_Denominator / gcdTop;
1006
1007        long gcdBottom = GCD(frac1.m_Denominator, frac2.m_Numerator);
1008        frac2.m_Numerator = frac2.m_Numerator / gcdBottom;
1009        frac1.m_Denominator = frac1.m_Denominator / gcdBottom;
1010      }
1011      #endregion
1012
1013      #region Implementation
1014      #region Convert a double to a fraction
1015      private static Fraction ConvertPositiveDouble(int sign, double inValue)
1016      {
1017        // Shamelessly stolen from http://homepage.smc.edu/kennedy_john/CONFRAC.PDF
1018        // with AccuracyFactor == double.Episilon
1019        long fractionNumerator = (long)inValue;
1020        double fractionDenominator = 1;
1021        double previousDenominator = 0;
1022        double remainingDigits = inValue;
1023        int maxIterations = 594;  // found at http://www.ozgrid.com/forum/archive/index.php/t-22530.html
1024
1025        while (remainingDigits != Math.Floor(remainingDigits)
1026          && Math.Abs(inValue - (fractionNumerator / fractionDenominator)) > double.Epsilon)
1027        {
1028          remainingDigits = 1.0 / (remainingDigits - Math.Floor(remainingDigits));
1029
1030          double scratch = fractionDenominator;
1031
1032          fractionDenominator =(Math.Floor(remainingDigits) * fractionDenominator) + previousDenominator;
1033          fractionNumerator = (long)(inValue * fractionDenominator + 0.5);
1034
1035          previousDenominator = scratch;
1036
1037          if (maxIterations-- < 0)
1038            break;
1039        }
1040
1041        return new Fraction(fractionNumerator * sign, (long)fractionDenominator);
1042      }
1043      #endregion
1044
1045      #region Equality helper
1046      /// <summary>
1047      /// Compares for equality the current Fraction to the value passed.
1048      /// </summary>
1049      /// <param name="right">A Fraction to compare against</param>
1050      /// <param name="notEqualCheck">If true, we're looking for not-equal</param>
1051      /// <returns>True if the <paramref name="right"></paramref> equals the current
1052      /// fraction, false otherwise. If comparing two NaNs, they are always equal AND
1053      /// not-equal.</returns>
1054      private bool CompareEquality(Fraction right, bool notEqualCheck)
1055      {
1056        // insure we're normalized first
1057        ReduceFraction(ref this);
1058
1059        // now normalize the comperand
1060        ReduceFraction(ref right);
1061
1062        if (this.m_Numerator == right.m_Numerator && this.m_Denominator == right.m_Denominator)
1063        {
1064          // special-case rule, two NaNs are always both equal
1065          if (notEqualCheck && this.IsNaN())
1066            return true;
1067          else
1068            return ! notEqualCheck;
1069        }
1070        else
1071        {
1072          return notEqualCheck;
1073        }
1074      }
1075      #endregion
1076
1077      #region Comparison helper
1078      /// <summary>
1079      /// Determines how this Fraction, of an indeterminate type, compares to another Fraction
1080      /// </summary>
1081      /// <param name="leftType">What kind of indeterminate</param>
1082      /// <param name="right">The other Fraction to compare against</param>
1083      /// <returns>-1 if this is less than <paramref name="right"></paramref>,
1084      ///  0 if they are equal,
1085      ///  1 if this is greater than <paramref name="right"></paramref></returns>
1086      /// <remarks>NaN is less than anything except NaN and Negative Infinity. Negative Infinity is less
1087      /// than anything except Negative Infinity. Positive Infinity is greater than anything except
1088      /// Positive Infinity.</remarks>
1089      private static int IndeterminantCompare(Indeterminates leftType, Fraction right)
1090      {
1091        switch (leftType)
1092        {
1093          case Indeterminates.NaN:
1094            // A NaN is...
1095            if (right.IsNaN())
1096              return 0; // equal to a NaN
1097            else if (right.IsNegativeInfinity())
1098              return 1; // great than Negative Infinity
1099            else
1100              return -1;  // less than anything else
1101
1102          case Indeterminates.NegativeInfinity:
1103            // Negative Infinity is...
1104            if (right.IsNegativeInfinity())
1105              return 0; // equal to Negative Infinity
1106            else
1107              return -1;  // less than anything else
1108
1109          case Indeterminates.PositiveInfinity:
1110            if (right.IsPositiveInfinity())
1111              return 0; // equal to Positive Infinity
1112            else
1113              return 1; // greater than anything else
1114
1115          default:
1116            // this CAN'T happen, something VERY wrong is going on...
1117            return 0;
1118        }
1119      }
1120      #endregion
1121
1122      #region Math helpers
1123      /// <summary>
1124      /// Negates the Fraction
1125      /// </summary>
1126      /// <param name="frac">Value to negate</param>
1127      /// <returns>A new Fraction that is sign-flipped from the input</returns>
1128      private static Fraction Negate(Fraction frac)
1129      {
1130        // for a NaN, it's still a NaN
1131        return new Fraction( - frac.m_Numerator, frac.m_Denominator);
1132      }
1133
1134      /// <summary>
1135      /// Adds two Fractions
1136      /// </summary>
1137      /// <param name="left">A Fraction</param>
1138      /// <param name="right">Another Fraction</param>
1139      /// <returns>Sum of the Fractions. Returns NaN if either Fraction is a NaN.</returns>
1140      /// <exception cref="FractionException">Will throw if an overflow occurs when computing the
1141      /// GCD-normalized values.</exception>
1142      private static Fraction Add(Fraction left, Fraction right)
1143      {
1144        if (left.IsNaN() || right.IsNaN())
1145          return NaN;
1146
1147        long gcd = GCD(left.m_Denominator, right.m_Denominator); // cannot return less than 1
1148        long leftDenominator = left.m_Denominator / gcd;
1149        long rightDenominator = right.m_Denominator / gcd;
1150
1151        try
1152        {
1153          checked
1154          {
1155            long numerator = left.m_Numerator * rightDenominator + right.m_Numerator * leftDenominator;
1156            long denominator = leftDenominator * rightDenominator * gcd;
1157
1158            return new Fraction(numerator, denominator);
1159          }
1160        }
1161        catch (Exception e)
1162        {
1163          throw new FractionException("Add error", e);
1164        }
1165      }
1166     
1167      /// <summary>
1168      /// Multiplies two Fractions
1169      /// </summary>
1170      /// <param name="left">A Fraction</param>
1171      /// <param name="right">Another Fraction</param>
1172      /// <returns>Product of the Fractions. Returns NaN if either Fraction is a NaN.</returns>
1173      /// <exception cref="FractionException">Will throw if an overflow occurs. Does a cross-reduce to
1174      /// insure only the unavoidable overflows occur.</exception>
1175      private static Fraction Multiply(Fraction left, Fraction right)
1176      {
1177        if (left.IsNaN() || right.IsNaN())
1178          return NaN;
1179
1180        // this would be unsafe if we were not a ValueType, because we would be changing the
1181        // caller's values.  If we change back to a class, must use temporaries
1182        CrossReducePair(ref left, ref right);
1183
1184        try
1185        {
1186          checked
1187          {
1188            long numerator = left.m_Numerator * right.m_Numerator;
1189            long denominator = left.m_Denominator * right.m_Denominator;
1190
1191            return new Fraction(numerator, denominator);
1192          }
1193        }
1194        catch (Exception e)
1195        {
1196          throw new FractionException("Multiply error", e);
1197        }
1198      }
1199
1200      /// <summary>
1201      /// Returns the modulus (remainder after dividing) two Fractions
1202      /// </summary>
1203      /// <param name="left">A Fraction</param>
1204      /// <param name="right">Another Fraction</param>
1205      /// <returns>Modulus of the Fractions. Returns NaN if either Fraction is a NaN.</returns>
1206      /// <exception cref="FractionException">Will throw if an overflow occurs. Does a cross-reduce to
1207      /// insure only the unavoidable overflows occur.</exception>
1208      private static Fraction Modulus(Fraction left, Fraction right)
1209      {
1210        if (left.IsNaN() || right.IsNaN())
1211          return NaN;
1212
1213        try
1214        {
1215          checked
1216          {
1217            // this will discard any fractional places...
1218            Int64 quotient = (Int64)(left / right);
1219            Fraction whole = new Fraction(quotient * right.m_Numerator, right.m_Denominator);
1220            return left - whole;
1221          }
1222        }
1223        catch (Exception e)
1224        {
1225          throw new FractionException("Modulus error", e);
1226        }
1227      }
1228
1229      /// <summary>
1230      /// Computes the greatest common divisor for two values
1231      /// </summary>
1232      /// <param name="left">One value</param>
1233      /// <param name="right">Another value</param>
1234      /// <returns>The greatest common divisor of the two values</returns>
1235      /// <example>(6, 9) returns 3 and (11, 4) returns 1</example>
1236      private static long GCD(long left, long right)
1237      {
1238        // take absolute values
1239        if (left < 0)
1240          left = - left;
1241
1242        if (right < 0)
1243          right = - right;
1244             
1245        // if we're dealing with any zero or one, the GCD is 1
1246        if (left < 2 || right < 2)
1247          return 1;
1248
1249        do
1250        {
1251          if (left < right)
1252          {
1253            long temp = left;  // swap the two operands
1254            left = right;
1255            right = temp;
1256          }
1257
1258          left %= right;
1259        } while (left != 0);
1260
1261        return right;
1262      }
1263      #endregion
1264
1265      #region Indeterminate helpers
1266      /// <summary>
1267      /// Gives the culture-related representation of the indeterminate types NaN, PositiveInfinity
1268      /// and NegativeInfinity
1269      /// </summary>
1270      /// <param name="numerator">The value in the numerator</param>
1271      /// <returns>The culture-specific string representation of the implied value</returns>
1272      /// <remarks>Only the sign and zero/non-zero information is relevant.</remarks>
1273      private static string IndeterminateTypeName(long numerator)
1274      {
1275        // could also be NumberFormatInfo.InvariantInfo
1276        System.Globalization.NumberFormatInfo info = NumberFormatInfo.CurrentInfo;
1277
1278        switch (NormalizeIndeterminate(numerator))
1279        {
1280          case Indeterminates.PositiveInfinity:
1281            return info.PositiveInfinitySymbol;
1282
1283          case Indeterminates.NegativeInfinity:
1284            return info.NegativeInfinitySymbol;
1285
1286          default:    // if this happens, something VERY wrong is going on...
1287          case Indeterminates.NaN:
1288            return info.NaNSymbol;
1289        }
1290      }
1291
1292      /// <summary>
1293      /// Gives the normalize representation of the indeterminate types NaN, PositiveInfinity
1294      /// and NegativeInfinity
1295      /// </summary>
1296      /// <param name="numerator">The value in the numerator</param>
1297      /// <returns>The normalized version of the indeterminate type</returns>
1298      /// <remarks>Only the sign and zero/non-zero information is relevant.</remarks>
1299      private static Indeterminates NormalizeIndeterminate(long numerator)
1300      {
1301        switch (Math.Sign(numerator))
1302        {
1303          case 1:
1304            return Indeterminates.PositiveInfinity;
1305
1306          case -1:
1307            return Indeterminates.NegativeInfinity;
1308
1309          default:    // if this happens, your Math.Sign function is BROKEN!
1310          case 0:
1311            return Indeterminates.NaN;
1312        }
1313      }
1314
1315      // These are used to represent the indeterminate with a Denominator of zero
1316      private enum Indeterminates
1317      {
1318        NaN = 0
1319        , PositiveInfinity = 1
1320        , NegativeInfinity = -1
1321      }
1322      #endregion
1323
1324      #region Member variables
1325      private long m_Numerator;
1326      private long m_Denominator;
1327      #endregion
1328      #endregion
1329    }   //end class Fraction
1330
1331    /// <summary>
1332    /// Exception class for Fraction, derived from System.Exception
1333    /// </summary>
1334    public class FractionException : Exception
1335    {
1336      /// <summary>
1337      /// Constructs a FractionException
1338      /// </summary>
1339      /// <param name="Message">String associated with the error message</param>
1340      /// <param name="InnerException">Actual inner exception caught</param>
1341      public FractionException(string Message, Exception InnerException) : base(Message, InnerException)
1342      {
1343      }
1344    }   //end class FractionException
1345  }   //end namespace Mehroz
Note: See TracBrowser for help on using the repository browser.