Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- <?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;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement