<?php
/*

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.


Author: Matt Johnson <matt@satchamo.com>
Website: http://satchamo.com
Date: 2008-09-28
Description:
	This class performs basic addition, subtraction, multiplication, and division on 2 or more fraction objects
Installation:
	Include this file in your program and run the following methods:
		Fractions::add(Fraction $fraction, Fraction $fraction [, Fraction $fraction...])
		Fractions::subtract(Fraction $fraction, Fraction $fraction [, Fraction $fraction...])
		Fractions::multiply(Fraction $fraction, Fraction $fraction [, Fraction $fraction...])
		Fractions::divide(Fraction $fraction, Fraction $fraction [, Fraction $fraction...])
License:
	The MIT License
FYI:
	- The format method has two parameters that control the style of the fraction string. They are defaulted to return the string in a proper, lowest terms format
	- A fraction_parts array can have 2 or 3 elements. If it contains two elements, the elements are the numerator and denominator, if it contains three elements the elements are whole, numerator, and denominator
Revisions:
	2009-04-19:
		- Added MIT license stuff
		- Removed that $_GET stuff from Fractions::format(). I copied that over from my demo page accidentally. 
	2008-09-29:
		Renamed the last two parameters in format() to better reflect what they do
	2008-10-01:
		- A fraction is now it's own data type. Its read only properties are numerator and denominator. It has two accessors for those properties.
		- gcf() has been revised. I got the new code from the wikipedia. I don't understand any of it, but I'm hoping it's more efficient than the old gcf()
		- The Fractions class now parses fraction strings (Fractions::parseString()) and arrays containing 2 or 3 integers (Fractions::parseArray()).
		- All fraction operations (add, subtract, multiply, divide) can calculate with 2 or more fraction objects. I believe there is a better way to calculate the gcf in addition and subtraction operations, but I haven't had the time to find a better solution.
Example Usage:

$x = Fractions::fromArray(array(1, 2));
$y = new Fraction(1, 3);
$z = Fractions::fromString('-1/2');
$sum = Fractions::add($x, $y, $z);
echo $sum->toString();


*/


// I think you can figure this out on your own
class Fraction
{
	private $numerator;
	private $denominator;
	
	function __construct($numerator, $denominator)
	{
		$this->numerator = $numerator;
		$this->denominator = $denominator;
	}
	
	function getNumerator()
	{
		return $this->numerator;
	}
	
	function getDenominator()
	{
		return $this->denominator;
	}
	
	function toString($mixed = true, $lowest_terms = true)
	{
		return Fractions::toString($this, $mixed, $lowest_terms);
	}
}

// the meat of the program
class Fractions
{		
	// parses a fraction string into a Fraction object
	function fromString($fraction_str)
	{
		// if the fraction is numeric, that means there is just a whole part
		if(is_numeric($fraction_str))	
		{
			$fraction = new Fraction($fraction_str, 1);
		}
		else
		{
			// split the fraction on the slash
			$part1 = explode('/', $fraction_str);
			
			// split the fraction on the space (for mixed numbers)
			$part2 = explode(' ', $part1[0]);
			
			if(count($part2) == 2) // we have a whole number in the fraction
			{
				$fraction_parts = array($part2[0], $part2[1], $part1[1]);	
			}
			else
			{
				$fraction_parts = array(0, $part1[0], $part1[1]);	
			}
					
			// make it improper since a Fraction object only has a denominator and numerator
			$fraction = self::toImproper($fraction_parts);
		}
		
		return $fraction;
	}
	
	// Makes the fraction improper, e.g. convert 1 1/2 to 3/2. It only takes a fraction_parts array
	function toImproper($fraction_parts)
	{
		$fraction_parts_count = count($fraction_parts);
		
		// if there is a whole part to the fraction, do the math
		if($fraction_parts_count == 3)
		{		
			// calculate the new numerator
			$numerator = $fraction_parts[2] * abs($fraction_parts[0]) + abs($fraction_parts[1]);
			
			// if the whole part or numerator is negative, make sure it's negative (the abs() in the previous line screws it up)
			if($fraction_parts[0] < 0 || $fraction_parts[1] < 0)
				$numerator = $numerator * -1;

			// rebuild fraction
			$fraction = new Fraction($numerator, $fraction_parts[2]);
		}
		else
		{
			$fraction = new Fraction($fraction_parts[0], $fraction_parts[1]);
		}
		
		return $fraction;
	}	
	
	// parses a fraction array and returns a Fraction object
	function fromArray($fraction_array)
	{
		$fraction_array_count = count($fraction_array);
		
		if($fraction_array_count == 1) // means there is just a whole part
		{
			$fraction = new Fraction($fraction_array[0], 1);
		}
		else if($fraction_array_count == 2) // there is a numerator and denominator
		{
			$fraction = new Fraction($fraction_array[0], $fraction_array[1]);
		}
		else if($fraction_array_count == 3) // fraction with whole part, numerator and denominator, just run through toImproper()
		{
			$fraction = self::toImproper($fraction_array);
		}
				
		return $fraction;
	}
	
		
	// returns the least common multiple of two integers
	function lcm($a, $b)
	{
		$a = abs($a);
		$b = abs($b);
		return $a * $b / self::gcf($a, $b);
	}
	
	// returns the greatest common factor of two integers
	function gcf($u, $v)
	{
		$u = abs($u);
		$v = abs($v);
		/* GCD(0,x) := x */
		if ($u == 0 || $v == 0)
			return $u | $v;
		
		/* Let shift := lg K, where K is the greatest power of 2
		dividing both u and v. */
		for ($shift = 0; (($u | $v) & 1) == 0; ++$shift) 
		{
			$u >>= 1;
			$v >>= 1;
		}
		
		while (($u & 1) == 0)
			$u >>= 1;
		
		/* From here on, u is always odd. */
		do 
		{
			while (($v & 1) == 0)  /* Loop X */
				$v >>= 1;
		
			/* Now u and v are both odd, so diff(u, v) is even.
			Let u = min(u, v), v = diff(u, v)/2. */
			if ($u < $v) 
			{
				$v -= $u;
			} 
			else 
			{
				$diff = $u - $v;
				$u = $v;
				$v = $diff;
			}
			$v >>= 1;
		} 
		while ($v != 0);
		
		return $u << $shift;
	}
	
	function toMixed($fraction)
	{
		$numerator = $fraction->getNumerator();
		if(abs($fraction->getNumerator()) >= $fraction->getDenominator()) // using abs() because we might be in negative teritory
		{
			// gotta use two different functions because of the negative issue
			if($fraction->getNumerator() > 0)
			{
				$whole = floor($fraction->getNumerator() / $fraction->getDenominator());	
			}
			else
			{
				$whole = ceil($fraction->getNumerator() / $fraction->getDenominator());	
			}
			
			// recalculate the numerator
			$numerator = $fraction->getNumerator() - ($whole * $fraction->getDenominator()); 
		}				
		
		return array($whole, $numerator, $fraction->getDenominator());
	}
	
	// Reduces the numerator and denominator of a fraction
	function reduce($fraction)
	{
		// get the greatest common factor and divide the numer and denom by it
		$gcf = self::gcf($fraction->getNumerator(), $fraction->getDenominator());
		return new Fraction($fraction->getNumerator() / $gcf, $fraction->getDenominator() / $gcf);
	}
	
	
	// turns the numerator and denominator into a mixed, proper fraction (by default) and returns a pretty string
	function toString($fraction, $mixed = true, $lowest_terms = true)
	{
		$whole = 0;
		$numerator = $fraction->getNumerator();
		$denominator = $fraction->getDenominator();
		
		if($mixed)
		{
			$fraction_array = self::toMixed($fraction);
			$whole = $fraction_array[0];
			$numerator = $fraction_array[1];
			$denominator = $fraction_array[2];
			$fraction = new Fraction($numerator, $denominator);
		}
		
		if($lowest_terms)
		{
			$fraction = self::reduce($fraction);
			$numerator = $fraction->getNumerator();
			$denominator = $fraction->getDenominator();
		}
		
		// don't need to show a zero
		if($whole == 0)
			$whole = ''; 
		else // need to show a space so the numerator isn't touching whole part
			$whole .= " "; 
		
		// if the numerator is zero, no need to show a numerator or denominator
		if($numerator == 0)
		{
			$numerator = '';
			$denominator = '';
		}
		else // tack on a slash to seperate the numerator and denominator
			$numerator .= "/";
			
		// if the fraction is zero, then just show a zero
		if($whole == 0 && $numerator == 0)
		{ 
			return 0;
		}
		else
		{
			$fraction_str = $whole . $numerator . $denominator;
			
			// the sign could be in a weird place, so stick it in the front (there is probably a better way to do this)
			$fraction_str = str_replace('-', '', $fraction_str);
			if($numerator < 0)
				$fraction_str = "-" . $fraction_str;
			
			return $fraction_str;
		}
	}
	
	function add()
	{
		// get the fractions and get a count
		$fractions = func_get_args();
		$fractions_count = count($fractions);
		
		// calculate the common denominator
		$denominator = $fractions[0]->getDenominator();
		
		$i = 1; // starting from one because we don't need to run through first fraction
		for($i = 1; $i < $fractions_count; ++$i)
		{
			$denominator = self::lcm($denominator, $fractions[$i]->getDenominator());
		}
		
		// add up all the adjusted numerators
		foreach($fractions as $k => $v)
		{
			$numerator += $fractions[$k]->getNumerator() * ($denominator / $fractions[$k]->getDenominator());
		}
		
		return new Fraction($numerator, $denominator);
	}	

	function subtract()
	{
		// get the fractions and get a count
		$fractions = func_get_args();
		$fractions_count = count($fractions);
		
		// calculate the common denominator (trying to find a better way since lcm() is expensive)
		$denominator = $fractions[0]->getDenominator();
		for($i = 1; $i < $fractions_count; ++$i)
		{
			$denominator = self::lcm($denominator, $fractions[$i]->getDenominator());
		}
		
		// set the inital adjusted $numerator and subtract the rest of the adjusted numerators
		$numerator = $fractions[0]->getNumerator() * ($denominator / $fractions[0]->getDenominator());
		for($i = 1; $i < $fractions_count; ++$i)
		{
			$numerator = $numerator - $fractions[$i]->getNumerator() * ($denominator / $fractions[$i]->getDenominator());
		}
		
		return new Fraction($numerator, $denominator);
	}
	
	function multiply()
	{
		// get the fractions and get a count

		$fractions = func_get_args();
		$fractions_count = count($fractions);
		
		// assign to 1 because they'd be 0 otherwise 
		$numerator = 1;
		$denominator = 1;
		
		// multiply
		foreach($fractions as $k => $v)
		{
			$numerator *= $fractions[$k]->getNumerator();
			$denominator *= $fractions[$k]->getDenominator();
		}
			
		return new Fraction($numerator, $denominator);
	}
	
	function divide()
	{
		// get the fractions and get a count
		$fractions = func_get_args();
		$fractions_count = count($fractions);
		
		// cross multiply
		$numerator = $fractions[0]->getNumerator();
		$denominator = $fractions[0]->getDenominator();
		
		for($i = 1; $i < $fractions_count; $i++)
		{
			$numerator *= $fractions[$i]->getDenominator();
			$denominator *= $fractions[$i]->getNumerator();
		}	
					
		return new Fraction($numerator, $denominator);		
	}	
}

?>