Ir para conteúdo
João Batista Neto

PHP SPL - A biblioteca padrão do PHP: SplDoublyLinkedList

Recommended Posts

PHP SPL - A biblioteca padrão do PHP

 

Durante uma discussão no PHP Brasil, descobrimos que há uma baixa aceitação da SPL por conta de desconhecimento de sua própria existência. A proposta da série *PHP SPL - A biblioteca padrão do PHP* é justamente procurar resolver essa questão, apresentando cada um dos participantes da SPL, mostrando o que são, para que servem e como utilizá-los.

 

Listas ligadas e a SplDoublyLinkedList

 

Antes de abordar diretamente a SplDoublyLinkedList e mostrar como utilizá-la, precisamos compreender o que é, de fato, uma DoublyLinkedList ou lista duplamente ligada. Para isso, vamos começar descrevendo uma lista ligada simples antes de evoluir para a lista duplamente ligada.

 

Lista ligada

 

Linguagens de programação possuem estruturas de dados. Uma lista ligada ou duplamente ligada nada mais é do que uma estrutura de dados. Utilizamos com bastante frequência no PHP uma estrutura de dados chamada array. Independentemente da forma como é implementado no PHP - em PHP o array associativo tem um comportamento de HashTable -, arrays são, normalmente, estruturas de dados contínuas, ou seja, elas são armazenadas em memória ou no disco item por item de forma sequêncial.

 

Por ser sequencial, essas estruturas de dados possuem um custo relativamente alto em operações de exclusão ou insersão que não sejam no fim do array. Basicamente, num array como é normalmente implementado, precisamos cortar o array na posição desejada, criando dois arrays, colocar o novo item na posição desejada e, então, mesclar novamente os dois arrays.

 

A grande vantagem de uma lista ligada, em comparação com o array, está justamente no baixo custo que ela promove para essas operações e para o armazenamento - seja em memória, seja em disco. E esse tipo de estrutura de dados pode ser implementada de forma extremamente simples. Tudo o que precisamos é de duas referências: uma para o dado armazenado, outra para o próximo item da lista. Por exemplo:

 

 

<?php
printf("\n-----------[ Criação da lista ]------------\n\n");

$first = new stdClass();
$first->data = 1;

$second = new stdClass();
$second->data = 2;

$third = new stdClass();
$third->data = 3;

$first->next = $second;
$second->next = $third;

$item = null;

do {
$item = $item == null? $first: $item->next;

printf("%s\n", $item->data);
} while (isset($item->next));

A saída será:

 

-----------[ Criação da lista ]------------

1
2
3
Inserção e remoção de itens

 

Como pôde ser visto no exemplo anterior, implementar uma lista ligada e iterar por seus elementos é muito simples. Tão simples quanto implementar a lista, é adicionar um novo elemento no meio dela. Tudo o que precisamos é mudar a referência para o próximo item, no local onde queremos adicionar o novo item. Por exemplo:

 

 

<?php
printf("\n-----------[ Criação da lista ]------------\n\n");

$first = new stdClass();
$first->data = 1;

$second = new stdClass();
$second->data = 2;

$third = new stdClass();
$third->data = 3;

$first->next = $second;
$second->next = $third;

$item = null;

do {
$item = $item == null? $first: $item->next;

printf("%s\n", $item->data);
} while (isset($item->next));

printf("\n-----------[ Inserção no meio da lista ]------------\n\n");

$twonhalf = new stdClass();
$twonhalf->data = 2.5;

$second->next = $twonhalf;
$twonhalf->next = $third;

$item = null;

do {
$item = $item == null? $first: $item->next;

printf("%s\n", $item->data);
} while (isset($item->next));
A saída será:

 

-----------[ Criação da lista ]------------

1
2
3

-----------[ Inserção no meio da lista ]------------

1
2
2.5
3
E para a remoção, basta mudar a referência do próximo item, no item anterior ao queremos remover da lista. Por exemplo:

 

<?php
printf("\n-----------[ Criação da lista ]------------\n\n");

$first = new stdClass();
$first->data = 1;

$second = new stdClass();
$second->data = 2;

$third = new stdClass();
$third->data = 3;

$first->next = $second;
$second->next = $third;

$item = null;

do {
$item = $item == null? $first: $item->next;

printf("%s\n", $item->data);
} while (isset($item->next));

printf("\n-----------[ Inserção no meio da lista ]------------\n\n");

$twonhalf = new stdClass();
$twonhalf->data = 2.5;

$second->next = $twonhalf;
$twonhalf->next = $third;

$item = null;

do {
$item = $item == null? $first: $item->next;

printf("%s\n", $item->data);
} while (isset($item->next));

printf("\n-----------[ Remoção no meio da lista ]------------\n\n");

$first->next = $twonhalf;

$item = null;

do {
$item = $item == null? $first: $item->next;

printf("%s\n", $item->data);
} while (isset($item->next));
A saída será:

 

-----------[ Criação da lista ]------------

1
2
3

-----------[ Inserção no meio da lista ]------------

1
2
2.5
3

-----------[ Remoção no meio da lista ]------------

1
2.5
3
Lista duplamente ligada

 

Compreendido o que é uma lista ligada, fica fácil, já que é um tanto óbvio, compreender o que é uma lista duplamente ligada. Ao contrário da lista ligada, que possui referência apenas para o próximo item, a lista duplamente ligada também possui referência para o item anterior.

 

E por que temos duas referências? Bom, existem diversos motivos, entre eles o menor custo em algumas operações, mas o motivo mais simples é que haverá situações onde precisaremos iterar os itens de forma invertida, indo do último item até o primeiro item. Por exemplo:

 

 

<?php
$first = new stdClass();
$first->data = 1;

$second = new stdClass();
$second->previous = $first;
$second->data = 2;

$third = new stdClass();
$third->previous = $second;
$third->data = 3;

$first->next = $second;
$second->next = $third;

printf("\n-----------[ Iterando a lista do primeiro ao último ]------------\n\n");

$item = null;

do {
$item = $item == null? $first: $item->next;

printf("%s\n", $item->data);
} while (isset($item->next));

printf("\n-----------[ Iterando a lista do último ao primeiro ]------------\n\n");

$item = null;

do {
$item = $item == null? $third: $item->previous;

printf("%s\n", $item->data);
} while (isset($item->previous));
A saída será:

 

-----------[ Iterando a lista do primeiro ao último ]------------

1
2
3

-----------[ Iterando a lista do último ao primeiro ]------------

3
2
1
SplDoublyLinkedList

 

O objetivo da `SplDoublyLinkedList` é, justamente, facilitar a criação, manutenção e operações relacionadas com listas duplamente ligadas. Ela oferece uma interface que permite que adicionemos itens no início da lista, no fim da lista ou num lugar específico da lista. Ainda permite que a iteração ocorra para frente ou para trás, que possamos remover itens do início

 

FIFO - Criando uma fila com a SplDoublyLinkedList

 

Filas possuem um comportamento FIFO - First In First Out -, ou seja, o primeiro item a entrar na fila deve ser o primeiro item a sair da fila. Muito comum em operações coordenadas, filas de impressão, filas de atendimento em sistemas de help desk, etc.

 

Para esse tipo de implementação usamos o método `SplDoublyLinkedList::push`, que adicionará o novo elemento no final da fila e o método `SplDoublyLinkedList::shift`, que removerá e retornará o primeiro item da lista:

 

 

<?php
$fifo = new SplDoublyLinkedList();
$fifo->push(1);
$fifo->push(2);
$fifo->push(3);

while ($fifo->count()) {
printf("%s\n", $fifo->shift());
}
A saída será:

 

1
2
3
FILO - Criando uma pilha com SplDoublyLinkedList

 

Pilhas possuem um comportamento FILO - First In Last Out -, ou seja, se estivermos empilhando pratos para lavar, o primeiro prato a ser lavado será o do topo da pilha, ou o último a ser colocado nela. Muito comum em linguagens de programação para organizar a pilha de chamadas de funções.

 

Para esse tipo de implementação usamos o método `SplDoublyLinkedList::push`, para adicionar um novo item ao final da pilha e o método `SplDoublyLinkedList::pop`, que removerá e retornará o último item da lista:

 

 

<?php
$filo = new SplDoublyLinkedList();
$filo->push(1);
$filo->push(2);
$filo->push(3);

while ($filo->count()) {
printf("%s\n", $filo->pop());
}
A saída será:

 

3
2
1
DEQUEUE - Criando uma fila com terminação dupla, duplamente terminada, etc.

 

Filas duplamente terminadas são aquelas onde podemos adicionar itens no fim da fila e no começo da fila. Normalmente utilizamos esse tipo de fila em alguma lista onde alguns itens possuem prioridades em relação aos outros. Por exemplo, numa fila de mercado, o primeiro a entrar na fila do caixa é o primeiro a ser atendido. Mas se um senhor de mais idade for ao caixa, então esse senhor deve ter prioridade em relação aos mais novos e pode entrar no começo da fila.

 

Para esse tipo de implementação usamos os métodos: `SplDoublyLinkedList::push`, para adicionar um novo item no fim da fila, o método `SplDoublyLinkedList::unshift`, para adicionar um novo item no começo da fila e o método `SplDoublyLinkedList::shift`, que removerá e retornará o primeiro item da lista:

 

 

<?php
$deque = new SplDoublyLinkedList();
$deque->push('Garotinho');
$deque->push('Jovem de 20');
$deque->push('Jovem de 30');

// O senhor de 80 tem prioridade no atendimento
$deque->unshift('Senhor de 80');

while ($deque->count()) {
printf("%s\n", $deque->shift());
}
A saída será:

 

Senhor de 80
Garotinho
Jovem de 20
Jovem de 30
Outros métodos

 

Além dos métodos acima, que descrevem alguns comportamentos comuns, também temos outros métodos que permitem alguns comportamentos específicos, por exemplo:

 

Adicionando elementos em posições específicas da lista

 

 

<?php
$list = new SplDoublyLinkedList();
$list->push(1);
$list->push(2);
$list->push(3);

// Adicionando o item 2.5 na posição 2 da lista
$list->add(2, 2.5);

foreach ($list as $item) {
printf("%s\n", $item);
}
A saída será:

 

1
2
2.5
3
Variando a ordem do Iterator

 

 

<?php
$list = new SplDoublyLinkedList();
$list->push(1);
$list->push(2);
$list->push(3);

printf("\nIterator como FIFO\n");

$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO); //First in First Out

foreach ($list as $item) {
printf("%s\n", $item);
}

printf("\nIterator como FILO\n");

$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO); //Last in First Out

foreach ($list as $item) {
printf("%s\n", $item);
}
A saída será:

 

Iterator como FIFO
1
2
3

Iterator como FILO
3
2
1
Conclusão

 

Muitas vezes não usamos alguma coisa simplesmente porque não sabemos para que tal coisa serve. Não adiantaria se tivéssemos uma documentação detalhada da API da classe `SplDoublyLinkedList`, com a descrição de cada um de seus métodos, parâmetros e comportamentos, se não tivermos o conhecimento sobre para que, exatamente, aquela coisa serve. Essa é, justamente, a proposta da série *PHP SPL - A biblioteca padrão do PHP*: promover o conhecimento sobre a SPL através da descrição dos problemas que seus participantes pretendem resolver.

  • +1 2

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar Agora

  • Conteúdo Similar

    • Por BTK
      Boa noite, estou tentando criar um curl que faz cadastro no site(o proprietário está ciente disso) porem ele está me retornando (HTTP/1.1 100 Continue HTTP/1.1 302 Moved Temporarily)

       $ch = curl_init();   
          
                                                                                                                     
          curl_setopt($ch, CURLOPT_URL, "https://www.cafefacil.com.br/customer/account/create/");                                     
          curl_setopt($ch, CURLOPT_HEADER, true);                                                                                                   
          curl_setopt($ch, CURLOPT_USERAGENT, 'Mozilla/5.0 (Windows NT 6.1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/72.0.3626.121 Safari/537.36');                                                                                                                                               
          curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, 0);                                                                                         
          curl_setopt($ch, CURLOPT_SSL_VERIFYHOST, 0);                                                                                       
          curl_setopt($ch, CURLOPT_FOLLOWLOCATION, true);                                                                                       
          curl_setopt($ch, CURLOPT_RETURNTRANSFER, true);  
          curl_setopt($ch, CURLOPT_COOKIESESSION, true);                                                                             
          curl_setopt($ch, CURLOPT_COOKIEJAR, getcwd().'/cafefacil.txt');
          curl_setopt($ch, CURLOPT_COOKIEFILE, getcwd().'/cafefacil.txt'); 
          
          
          
          
          $b1 = curl_exec($ch);
          
          $form_key = value($b1, 'type="hidden" name="form_key" value="', '"');
          
          curl_setopt($ch, CURLOPT_URL, 'https://www.cafefacil.com.br/customer/account/createpost/');                                     
          curl_setopt($ch, CURLOPT_HEADER, true);                                                                                                   
          curl_setopt($ch, CURLOPT_USERAGENT, 'Mozilla/5.0 (Windows NT 6.1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/72.0.3626.121 Safari/537.36');                                                                                                                                                  
          curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, 0);                                                                                         
          curl_setopt($ch, CURLOPT_SSL_VERIFYHOST, 0);                                                                                    
          curl_setopt($ch, CURLOPT_FOLLOWLOCATION, true);                                                                                       
          curl_setopt($ch, CURLOPT_RETURNTRANSFER, true); 
          curl_setopt($ch, CURLOPT_COOKIESESSION, true);   
          curl_setopt($ch, CURLOPT_REFERER, 'https://www.cafefacil.com.br/customer/account/create/');                                                                           
          curl_setopt($ch, CURLOPT_COOKIEJAR, getcwd().'/cafefacil.txt');
          curl_setopt($ch, CURLOPT_COOKIEFILE, getcwd().'/cafefacil.txt'); 
          curl_setopt($ch, CURLOPT_POST, 1);                                                                                                    
          $boundary = '---------------------------WebKitFormBoundaryRQ3KHJbpfmPf11v6';
          
          $data = '-----------------------------'.$boundary.'
          Content-Disposition: form-data; name="success_url"
          
          
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="error_url"
          
          
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="form_key"
          
          '.$form_key.'
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="tipopessoa"
          
          15
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="firstname"
          
          NomeTest SobreNomeTest
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="nomefantasia"
          
          
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="inscricaoestadual"
          
          
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="email"
          
          nometestsobrenometest@gmail.com
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="day"
          
          01
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="month"
          
          01
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="year"
          
          1990
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="dob"
          
          01/01/1990
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="taxvat"
          
          199.758.750-50
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="celular"
          
          (11)4712-8491
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="password"
          
          senhatest
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="confirmation"
          
          senhatest
          -----------------------------'.$boundary.'
          Content-Disposition: form-data; name="persistent_remember_me"
          
          on
          -----------------------------'.$boundary.'--';
          
          $header[] = "Content-Type: multipart/form-data; boundary=".$boundary;
          curl_setopt($ch, CURLOPT_HTTPHEADER, $header);
          curl_setopt($ch, CURLOPT_POSTFIELDS, $data); 
          
            
          echo $exec = curl_exec($ch);
          curl_close($ch);
    • Por allencar.limma
      Tento incluir as informações de um formulário no banco de dados e não consigo. conforme código abaixo.
      <? /*Incluir as informações no formulario */ include "config.php"; $nome = trim($_POST['nome']); $masp = trim($_POST['masp']); $cpf = trim($_POST['cpf']); $telefone = trim($_POST['telefone']); $email = trim($_POST['email']); $endereco = trim($_POST['endereco']); $data_nascimento = trim($_POST['data_nascimento']); $unidade_lotacao = trim($_POST['unidade_lotacao']); /* Vamos checar algum erro nos campos */ if ((!$nome) || (!$masp) || (!$cpf) || (!$telefone) || (!$email) || (!$endereco) || (!$data_nascimento) || (!$unidade_lotacao)){ echo "ERRO: <br /><br />"; if (!$nome){ echo "Nome Completo é requerido.<br />"; } if (!$masp){ echo "Masp é requerido.<br />"; } if (!$cpf){ echo "CPF é requerido.<br /)>"; } if (!$telefone){ echo "Telefone é requerido.<br />"; } if (!$email){ echo "Email é requerido.<br />"; } if (!$endereco){ echo "Endereço é requerido.<br />"; } if (!$data_nascimento){ echo "Data de Nascimento é requerido.<br />"; } if (!$unidade_lotacao){ echo "Unidade de Lotação é requerido.<br>"; } echo "Preencha os campos abaixo: <br />"; include "formulario_cadastro.php"; }else { /* Vamos checar se o nome de Usuário escolhido e/ou Email já existem no banco de dados */ $sql_email_check = mysql_query( "SELECT COUNT(usuario_id) FROM usuarios WHERE email='{$email}'" ); $sql_masp_check = mysql_query( "SELECT COUNT(usuario_id) FROM usuarios WHERE masp='{$masp}'" ); $sql_cpf_check = mysql_query( "SELECT COUNT(usuario_id) FROM usuarios WHERE cpf='{$cpf}'" ); $eReg = mysql_fetch_array($sql_email_check); $uReg = mysql_fetch_array($sql_masp_check); $uReg = mysql_fetch_array($sql_cpf_check); $email_check = $eReg[0]; $masp_check = $uReg[0]; $cpf_check = $uReg[0]; if (($email_check > 0) || ($masp_check > 0) || ($cpf_check > 0)){ echo "<strong>ERRO</strong>: <br /><br />"; if ($email_check > 0){ echo "Este email já está sendo utilizado.<br /><br />"; unset($email); } if ($masp_check > 0){ echo "Este Masp já está sendo utilizado.<br /><br />"; unset($masp); } if ($cpf_check > 0){ echo "Este CPF já está sendo utilizado.<br /><br />"; unset($cpf); } include "formulario_cadastro.php"; }else{ /* Se passarmos por esta verificação ilesos é hora de finalmente cadastrar os dados. Vamos utilizar uma função para gerar a senha de forma randômica*/ function makeRandomPassword(){ $salt = "abchefghjkmnpqrstuvwxyz0123456789"; srand((double)microtime()*1000000); $i = 0; while ($i <= 7){ $num = rand() % 33; $tmp = substr($salt, $num, 1); $pass = $pass . $tmp; $i++; } return $pass; } $senha_randomica = makeRandomPassword(); $senha = md5($senha_randomica); // Inserindo os dados no banco de dados //$cpf = htmlspecialchars($cpf); ***RETIRADO PELO FATO DE NÃO ESTA SENDO USADO $sql = mysql_query( "INSERT INTO usuarios (none, masp, cpf, telefone, email, endereco, data_nascimento, unidade_lotacao) VALUES ('$nome', '$masp', '$cpf', '$telefone', '$email', '$endereco', '$data_nascimento', '$unidade_lotacao', now())") or die( mysql_error() ); if (!$sql){ echo "Ocorreu um erro ao criar sua conta, entre em contato."; }else{ $usuario_id = mysql_insert_id(); // Enviar um email ao usuário para confirmação e ativar o cadastro! $headers = "MIME-Version: 1.0\n"; $headers .= "Content-type: text/html; charset=iso-8859-1\n"; $headers .= "From: RCI - <rci@rcionline.com.br>"; $subject = "Confirmação de cadastro - www.rcionline.com.br"; $mensagem = "Prezado {$nome} {$masp},<br /> Obrigado pelo seu cadastro em nosso site, <a href='http://www.rcionline.com.br'> http://www.rcionline.com.br</a>!<br /> <br /> Para confirmar seu cadastro e ativar sua conta em nosso site, podendo acessar à áreas exclusivas, por favor clique no link abaixo ou copie e cole na barra de endereço do seu navegador.<br /> <br /> <a href='http://www.rcionline.com.br/ativar.php?id={$usuario_id}&code={$senha}'> http://www.rcionline.com.br/ativar.php?id={$usuario_id}&code={$senha} </a> <br /> <br /> Após a ativação de sua conta, você poderá ter acesso ao conteúdo exclusivo efetuado o login com os seguintes dados abaixo:<br > <br /> <strong>Usuario</strong>: {$usuario_id}<br /> <strong>Senha</strong>: {$senha_randomica}<br /> <br /> Obrigado!<br /> <br /> Webmaster<br /> <br /> <br /> Esta é uma mensagem automática, por favor não responda!"; mail($email, $subject, $mensagem, $headers); echo "Foi enviado para seu email - ( ".$email." ) um pedido de confirmação de cadastro, por favor verifique e sigas as instruções!"; } } } ?>  
    • Por vinicius.david
      Gostaria que fosse possível encontrar produtos pela marca no Opencart 2.3.0.2. Quando a pessoa digitar no buscar a marca do produto, ele deveria mostrar todos os produtos que pertencem aquela marca. Em catalog/model/catalog/product.php já existe por padrão a função de procurar por fabricante: 

      if (!empty($data['filter_manufacturer_id'])) {                 $sql .= " AND p.manufacturer_id = '" . (int) $data['filter_manufacturer_id'] . "'";             }
      Mas ela não faz a função de procurar por marca. Alguém já encontrou alguma solução na internet para este caso?
    • Por manolegal
      Bom dia.
      Recebo em meu formulário um dado em forma de url.
      Extraio desta url o CNPJ da empresa. A seguir faço uma pesquisa para verificar se este CNPJ está em minha base de dados, sendo que se estiver trago dados da empresa para preenchimento do campo empresa do formulário.
      Estando a empresa no BD, consigo trazer os dados corretamente, porém estes dados não passados para o formulário para serem o valor inicial do campo empresa.
      $cnpj_numero = 12345678910; $Sql_cnpj = "SELECT id_empresa as id_empresa_bd_ext, upper(empresas.empresa) as fornecedor_bd_ext FROM empresas WHERE empresas.cnpj = '$cnpj_numero'"; $Resultado_cnpj = executa($Sql_cnpj); while ($linha_cnpj = pg_fetch_array($Resultado_cnpj)){ $empresa_bd_ext = $linha_cnpj["fornecedor_bd_ext"]; $forn_hid_bd_ext = $linha_cnpj["id_empresa_bd_ext"]; } echo "Fornecedor BD: $empresa_bd_ext - $forn_hid_bd_ext<br><hr>"; // Está mostrando dados corretamente // Definir valor a ser recebido pelo campo Empresa do Formulário if ($cnpj_numero != ""){ $empresa = $empresa_bd_ext; $forn_hid = $forn_hid_bd_ext; }else{ // Caso url não tenha trazido CNPJ, atribuo outro valor $empresa = $empresa_bd; $forn_hid = $forn_hid_bd; } O campo empresa do formulário não está recebendo o valor de $empresa. Considerando que exista um CNPJ, onde pode estar o problema?
    • Por edvaldo123
      Olá para todos, preciso de um código em PHP ou HMTL que mostre cotações de moedas, pra colocar em um site de notícias. Vou deixar um link abaixo onde tem exatamente o que preciso, porém queria remover algumas linhas desse código para não identificar seu site de origem.

      http://www.precododolar.com/widgets/cotacao.php
×

Informação importante

Ao usar o fórum, você concorda com nossos Termos e condições.