Location: PHPKode > projects > XMLNuke Web Development Framework XML > xmlnuke-php5-v3.5r356/xmlnuke-php5/bin/com.xmlnukedb/btree.class.php
<?php
/*
*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
*  Copyright:
*
*  XMLNuke: A Web Development Framework based on XML.
*
*  Main Specification: Joao Gilberto Magalhaes, joao at byjg dot com
*
*  This file is part of XMLNuke project. Visit http://www.xmlnuke.com
*  for more information.
*
*  This program is free software; you can redistribute it and/or
*  modify it under the terms of the GNU General Public License
*  as published by the Free Software Foundation; either version 2
*  of the License, or (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program; if not, write to the Free Software
*  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*
*=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
*/

class BTree
{

	const T = 3;

	/** Indicates how many data items are stored in this node.  For all
	*  nodes except the root of the tree, this will be somewhere between
	*  (t-1) and (2t-1).
	*@var int
	*/
	private $_n;

	/** An array of data items.  Each such array will be allocated (2t-1)
	*  slots.
	*@var IBTreeNode
	*/
	private $_keys;

	/** An array of pointers to child nodes.  Each such array will be
	*  allocated 2t slots.
	*@var BTree
	*/
	private $_children;

	//end of line delimiters
	const LF = "\n";


	/** Construct an empty B-tree node; we mark this constructor as
	*  private because the values in the constructed node will not
	*  be valid until further initialization has been carried out.
	*@param IBTreeNode $value = null
	*/
	private function BTree($value = null)
	{
		if($value==null)
		{
			$this->_n  = 0;
		}
		else
		{
			$this->_n       = 1;
			$this->_keys[0] = $value;
		}
	}

	/** 
	*Determine whether the root node of a (non-null) B-tree is full.
	*@return bool
	*/
	public function full()
	{
		return ($this->_n == 2*self::T-1);
	}

	/** Determine whether a particular value occurs in this tree.
	*  Parameters : $value type IBTreeNode/$btree type BTree
	*@param IBTreeNode $value
	*@param BTree $btree
	*@return bool
	*/
	public static function contains($value, $btree)
	{
		while ($btree!=null)
		{
			$i = 0;
			for (; $i<$btree->_n; $i++)
			{
				if ($value->equalsTo($btree->_keys[$i]))
				{
					return true;
				}
				else if ($value->lessThan($btree->_keys[$i]))
				{
					break;
				}
			}
			$btree = $btree->_children[$i];
		}
		return false;
	}

	/**
	*@param IBTreeNode $value
	*@param BTree $btree
	*@return IBTreeNode;
	*/
	public static function containsNode($value, $btree)
	{
		while ($btree!=null)
		{
			$i = 0;
			for (; $i<$btree->_n; $i++)
			{
				if ($value->equalsTo($btree->_keys[$i]))
				{
					return $btree->_keys[$i];
				}
				else if ($value->lessThan($btree->_keys[$i]))
				{
					break;
				}
			}
			$btree = @$btree->_children[$i];
		}
		return null;
	}


	/** Insert a value into a B-tree node.
    *@param  IBTreeNode $value
    *@param  BTree $BTree
    *@return BTree
    */
	public static function insert($value, $btree)
	{
		if ($btree==null)
		{
			return new BTree($value);
		}
		else
		{
			/**
			*@var IBTreeNode
			*/
			$bnode=self::containsNode($value, $btree);
			if ($bnode == null)
			{

				if ($btree->full())
				{
					$root       = new BTree($btree->_keys[self::T-1]);
					$root->_children[0] = $btree;
					$root->_children[1] = $btree->split();
					$btree	    = $root;
				}
				// At this point, we can guarantee that btree
				// is a non-null and non-full BTree node.

				self::insertNonFull($value, $btree);
			}
			else
			{			       
				$values = $value->values(); 
				$bnodeValues = $bnode->values();
				
				foreach($values as $o )
				{
					$found = array_search($o, $bnodeValues);
					if ($found === false)
					{
						$bnode->addValue($o);
					}
				}
			}
		}

		return $btree;
	}


	/** Insert a value into a non-full (and non-null) B-tree node.
    *@param  IBTreeNode $value
    *@param  BTree $BTree
    *@return BTree
    */
	private static function insertNonFull($value, $btree)
	{
		$i = 0;
		while ($i<$btree->_n && $value->greaterThan($btree->_keys[$i]))
		{
			$i++;
		}
		if (@$btree->_children[$i]==null)
		{		       // Leaf node
			$btree->shiftUp($i, $value);
			$btree->_children[$i+1] = null;
		}
		elseif ($btree->_children[$i]->full())
		{	       // Full child
			$pivot = $btree->_children[$i]->_keys[self::T-1];
			$btree->shiftUp($i, $pivot);
			$btree->_children[$i+1] =  $btree->_children[$i]->split();
			self::insertNonFull($value,  $btree->_children[($value->greaterThan($pivot)) ? ($i+1) : $i]);
		}
		else
		{				       // Non-full child
			self::insertNonFull($value, $btree->_children[$i]);
		}
	}


	/** Insert a value into a B-tree node.
	*@param int $i
	*@package IBTreeNode $key
	*@return void
	*/
	private function shiftUp($i, $key)
	{
		for ($j=$this->_n; $j>$i; $j--)
		{
			$this->_keys[$j] = $this->_keys[$j-1];
			$this->_children[$j+1] = @$this->_children[$j];
		}
		$this->_keys[$i] = $key;
		$this->_n++;
	}

	
	/** Split a full B-tree node, modifying the receiver (the left half)
	*  and returning the new node (the right half).  We assume that this
	*  method is invoked only on full tree nodes, meaning that btree.n
	*  will be 2*t-1.
	*@return BTree
	*/
	private function split()
	{
		$right = new BTree();

		for ($i=0; $i<self::T-1; $i++)
		{
			$right->_keys[$i]      = $this->_keys[self::T+$i];
			$right->_children[$i]  = $this->_children[self::T+$i];
			$this->_children[self::T+$i];
		}

		$right->_children[self::T-1]  = $this->_children[2*self::T-1];
		$this->_children[2*self::T-1] = null;
		$this->_n	       = (self::T-1);
		$right->_n	      = (self::T-1);

		return $right;

	}

	/**
	*@param BTree $btree
	*@param string $filename
	*@return void
	*/
	public static function save($btree, $filename)
	{
		$handle = fopen($filename, "w");

		self::saveLoop($btree,$handle);

		fclose ($handle);

	}

	//Metodo anteriormente chamado de save
	//Parameters: $btree type BTree / $handle
	private static function saveLoop($btree,$handle)
	{
		if ($btree==null)
		{
			return null;
		}
		else
		{
			$i = 0;
			for (; $i<$btree->_n; $i++)
			{
				fwrite($handle,$btree->_keys[$i]->getKey().self::LF);
				foreach($btree->_keys[$i]->values() as $s)
				{
					fwrite($handle,"+".$s.self::LF);
				}
				self::saveLoop(@$btree->_children[$i],$handle);
			}
			self::saveLoop($btree->_children[$i],$handle);
		}

	}

	//Parameter: $filename type string
	public static function load($filename)
	{
		$btree = null;

		if (!file_exists($filename))
		{
			return null;
		}
		$lines = file($filename);

		foreach ($lines as $i=>$linha)
		{
			if (substr($linha,0,1) != '+')
			{
				$bnode = new BTreeNode($linha);
				$btree = BTree::insert($bnode, $btree);
			}
			else
			{
				$bnode->addValue(substr($linha,1));
			}
		}
		return $btree;
	}

}



/*METODO DE TESTE

public static function teste()
{   echo 'LF :'.self::LF;
echo 't '.self::T;
echo 'Entrou no teste<br>';

echo '<BR>Teste de construtor<br>';
$array = array(10,20,30,40,50);
$BtreeNode= new BTreeNode('chave',$array);

$Btree= new BTree($BtreeNode);

echo 'Numero de linhas '.$Btree->_n.'<br>';
echo 'KEY: '.$Btree->_keys[0]->getKey().'<br>';
echo 'VALUES: ';
print_r($Btree->_keys[0]->values());
echo '<br>Fim de teste de construtor<br>';

echo '<br>Teste do metodo save<br>';
$fileName = "../apagar_modificado.txt";
self::save($Btree,$fileName);

echo '<br>Fim de teste do metodo save<br>';

echo '<br>Teste do metodo load<br>';
$fileName = "../apagar_modificado.txt";
$btree2 = self::load($fileName);
echo '<br>btree2-KEY:  '.$btree2->_keys[0]->getKey().'<br>';
echo 'btree2-VALUES: ';
print_r($btree2->_keys[0]->values());
$fileName2 = "../teste.txt";
self::save($btree2,$fileName2);
echo '<br>Fim de teste do metodo load<br>';

echo '<br>Saiu do teste';
}

}
METODO DE TESTE*/


?>
Return current item: XMLNuke Web Development Framework XML