<?php

// Based On: "A mathematical approach to the boolean minimization problem" By "Adrian Duşa" 2007
// Author: Armin Randjbar-Daemi <www.omnistream.co.uk>
// Demo: http://www.omnistream.co.uk/minimization/
// Last Modified: 2008-01-05

class Minimization {
//data members
	var $VARI;
	var $minterm;
	var $marks;
	//The differences matrix
	var $differences;
	//Temp Forward Pairs
	var $flag;
	var $forward_pair1;
	var $forward_pair2;
	//Primary Results
	var $PrimeImplicants;

/////////////////////
//Constructor
/////////////////////

function Minimization($var_num,$minterm)
	{
		$this->VARI=$var_num;
		$this->minterm=$minterm;
		
		$this->Create_differences($this->VARI);
		$this->StrToBase10();
		$this->MainComparison(0,count($this->minterm));
		$this->PrimaryResult();
	}

function Create_differences($k)
	{
		for ($each_block=pow(3,$k-1),$total_blocks=1; $total_blocks<=pow(3,$k-1); $each_block/=3,$total_blocks*=3)
		{
		$start_with = 1 + $each_block;
		$finish_with = pow(3,$k) - $each_block;
		$total_num = ($finish_with - $start_with) + 1;
		
		if ($total_blocks == "1") $gap_size = "0";
		else $gap_size = ($total_num - ($total_blocks * $each_block)) / ($total_blocks - 1);
		
		for ($i=$start_with; $i<=$finish_with; $i+=$gap_size+$each_block)
			for ($j=0; $j<$each_block; $j++)
				$temp_differences[] = $i+$j;
				
		$this->differences[] = $temp_differences;
		$temp_differences = NULL;
		}
	}

function MainComparison($m,$n)
	{
		$this->flag = "0";
		$this->forward_pair1 = NULL;
		$this->forward_pair2 = NULL;
		
		for ($x = 0; $x < $this->VARI; $x++) //select an array from $differences matrix
			for ($y = $m; $y < $n; $y++)//select a minterm
				$this->CreateForwardPair($x,$y);
				
		//applying the 2x-y rule, and add PrimeImplicants to $this->minterm array
		for ($i = 0; $i < count($this->forward_pair1); $i++)
			$this->CreatePrimeImplicant($i);
		
		if ($this->flag=="1") $this->MainComparison($n,count($this->minterm));//call the function again
	}
	
function PrimaryResult()
	{
		for ($q = 0; $q < count($this->minterm); $q++)
			if (!isset($this->marks[$q]))
				$this->PrimeImplicants[] = $this->minterm[$q];
				
		$this->DecToBase3();
		$this->Base3ToBin();
	}


function StrToBase10()
	{
		$this->minterm=explode(" ",$this->minterm);
		
		for ($a = 0; $a < count($this->minterm); $a++)
			{
				$this->DecToBin($a);
				$this->MoreZero($a);
			}
		$this->BinToBase3();
		$this->Base3ToDec();
	}

function DecToBin($a)
	{
		$this->minterm[$a]=decbin($this->minterm[$a]);
	}

function MoreZero($a)
	{
		$more_zero="";
		if($this->VARI-strlen($this->minterm[$a])>"0")
		for($z = 0; $z < $this->VARI-strlen($this->minterm[$a]); $z++) $more_zero.="0";
		$this->minterm[$a]=$more_zero.$this->minterm[$a];
	}

function BinToBase3()
	{
		for ($i = 0; $i < count($this->minterm); $i++)
			for ($j = 0; $j < strlen($this->minterm[$i]); $j++)
				$this->minterm[$i]{$j} = $this->minterm[$i]{$j} + 1;
	}

function Base3ToDec()
	{
		for ($i = 0; $i < count($this->minterm); $i++)
			$this->minterm[$i] = base_convert($this->minterm[$i],3,10) + 1;//Line Nombers 1 2 3 ...
	}

function CreateForwardPair($x,$y)
	{
		$yPrime = $this->minterm[$y] + pow(3,$this->VARI-($x+1));
		if (in_array($this->minterm[$y],$this->differences[$x])){
			if (in_array($yPrime,$this->minterm))
			{
				$this->flag = "1";
				$this->forward_pair1[] = $this->minterm[$y];
				$this->forward_pair2[] = $yPrime;
				//mark the combining minterms
				$yPrimeKey = array_search($yPrime,$this->minterm);
				$this->marks[$y] = "1";
				$this->marks[$yPrimeKey] = "1";
			}}
	}

function CreatePrimeImplicant($i)
	{
		$temp_imp = (2*$this->forward_pair1[$i]) - $this->forward_pair2[$i];
		if (!in_array($temp_imp,$this->minterm))
			$this->minterm[] = $temp_imp;
	}

function DecToBase3()
	{
		for ($i = 0; $i < count($this->PrimeImplicants); $i++)
		{
			$this->PrimeImplicants[$i] = base_convert($this->PrimeImplicants[$i]-1,10,3);
			$more_zero="";
			if ($this->VARI-strlen($this->PrimeImplicants[$i])>"0")
			for ($z = 0; $z < $this->VARI-strlen($this->PrimeImplicants[$i]); $z++) $more_zero.="0";
			$this->PrimeImplicants[$i]=$more_zero.$this->PrimeImplicants[$i];
		}
	}

function Base3ToBin()
	{
		for ($i = 0; $i < count($this->PrimeImplicants); $i++)
			for ($j = 0; $j < strlen($this->PrimeImplicants[$i]); $j++)
				$this->PrimeImplicants[$i]{$j} = $this->PrimeImplicants[$i]{$j} - 1;
	}

}//Class END
?>