<?php
/**
* @category Estrutura de Dados
*
*/
class ArvoreOrdemN {
	
	/**
	* @var integer
	* @access private
	*/
	private $alturaMaxima = 4; //a arvore pode ter no máximo X de altura

	/**
	* Só libera o próximo nível (altura) ao preencher todos do nível atual
	* @var integer
	* @access private
	*/
	public $nivelMaximaLiberado = 1;
	
	/**
	* Checa quando todos os campos daquele nível foram preenchidos
	* @var integer
	* @access private
	*/
	public $mudarContagem = 0;

	/**
	* @var integer
	* @access private
	*/
	private $ordem = 3; //cada nó pode ter no máximo N dados

	/**
	* @var integer
	* @access private
	*/
	private $totalInserido = 0; //Quantos dados foram inseridos

	/**
	* @var integer
	* @access private
	*/
	private $arvore = []; 


	/**
	* Tenta adicionar uma pessoa na raiz. Se não puder tenta na função recursiva com os filhos
	* @access public
	* @uses $arv->addPessoa(['nome' => 'Carlos', 'cod' => 12323]);
	* @param $dados array
	* @return bool | true -> conseguiu inserir e false -> não foi possível inserir
	*/
	public function addPessoa($dados = []) {
		$dados['filhos'] = [];

		if (empty($this->arvore)) { //no raiz
			$this->arvore[] = $dados; 
			$this->totalInserido = 1;
			return true; //inserido com sucesso
		} else {  //no interno ou folha
			//tenta inserir em um no não raiz
			return $this->addNoInterno($this->arvore[0]['filhos'], $dados, 1);	
		}
	}

	/**
	* Tenta inserir um valor em um nó existente
	* @access private
	* @param $no | array -> no passado via referencia
	* @param $dados | array
	* @param $altura | integer (altura do nó atual)
	* @return bool | true -> conseguiu inserir e false -> não foi possível inserir 
	*/
	private function addNoInterno(&$no, $dados, $altura, $inseriFilho = true) {
		
		//Passou da altura
		if ($altura > $this->alturaMaxima)
			return false; //'Não pode inserir além daqui';

		//Não poderá inserir em (nivel) maior do que o maior nivel sem filho
		if ($altura - $this->nivelMaximaLiberado > 0) 
			return false; //Ainda há nó sem filho, não pode inserir em neto

		//Pode inserir no nó atual (Tem menos de 3 valores)
		if (sizeof($no) < $this->ordem) {
			$no[] = $dados;
			$this->totalInserido++;
			$this->mudarContagem++; //Verifica quantos itens foram adicionados naquele nivel
			
			//Verifica se já foi inserido todo mundo naquele nível, liberando o próximo
			if (($this->mudarContagem) % ($this->ordem**$this->nivelMaximaLiberado) == 0) {
				$this->nivelMaximaLiberado++;
				$this->mudarContagem = 0;
			}
			return true;	
		} elseif ($inseriFilho)  {
			$altura++;
			for ($i = 0; $i < $this->ordem; $i++) {
				if ($this->addNoInterno($no[$i]['filhos'], $dados, $altura, false))
					return true; //conseguiu inserir em um nó abaixo		
			}

			for ($i = 0; $i < $this->ordem; $i++) {
				if ($this->addNoInterno($no[$i]['filhos'], $dados, $altura)) {
					
					return true; //conseguiu inserir em mais de um nó abaixo
				}
			}
		}
		return false; //não conseguiu inserir em nenhum dos valores dos nós
	}
	
	/**
	* Retorna a árvore em forma de array
	* @access public
	* @return array 
	*/
	public function getArvore() {
		return $this->arvore;
	} 

	/**
	* Retorna o total de elementos inseridos nessa arvore
	* @access public
	* @return array 
	*/
	public function getTotal() {
		return $this->totalInserido;
	}
}