Standard PHP Library – SPL: Estructuras de datos – Parte 1

Desde la versión 5.0 – 5.1 de PHP disponemos de la Librería Estandar de PHP o Standard PHP Library (SPL), que como bien dice su nombre, nos ofrece un API estandar para implementar ciertas funcionalidades, por ejemplo, almacenamiento de información,  iteración de objetos, etc.

En esta librería podemos encontrar un conjunto de interfaces y clases eficientes con las que conseguiremos desarrollar aplicaciones que interactuen con el API de PHP y se acerquen un poco más al paradigma de la programación orientada a objetos.

Para conocer un poco mejor las posibilidades de esta librería veamos que nos ofrecerá la versión PHP 5.3 en cuanto a las estructuras de datos.

• Listas doblemente enlazadas
• Pilas
• Colas
• Vectores de tamaño fijo
• Cúmulos de mayor a menor
• Cúmulos de menor a mayor
• Colas con prioridad
• Objeto de almacenamiento SPL

SplDoublyLinkedList (PHP 5.3 o superior)

Lista doblemente enlazada

Este tipo de listas son interesantes ya que desde cualquier nodo de la lista podemos llegar fácilmente a cualquier extremo de la misma.

Las estructuras de Pila y Cola se han construido sobre la base de una lista doblemente enlazada y por lo tanto, reutilizan los métodos de esta.

• __construct (void);
  Constructor por defecto de la clase: Lista doblemente enlazada
   
• mixed bottom (void);
  Devuelve el elemento que se encuentra en la parte superior de la lista sin eliminarlo
   
• int count (void);
  Devuelve el número de elementos que hay en la lista
   
• mixed current (void);
  Devuelve el elemento actual. No lo elimina de la lista
   
• int getIteratorMode (void);
  Devuelve el modo de iteración
   
• bool isEmpty (void);
  Devuelve verdadero (true) en caso de que la lista esté vacía y falso (false) en caso que esta contenga algún elemento
   
• mixed key (void);
  Devuelve el indice del elemento actual
   
• void next (void);
  Mueve el indice al siguiente elemento de la lista
   
• bool offsetExists (mixed $index);
  Devuelve verdadero (true) en caso que el indice consultado exista en la lista y falso (false) en caso contrario
   
• mixed offsetGet (mixed $index);
  Devuelve el elemento que se encuentra en la posición indicada por $index
   
• void offsetSet (mixed $index, mixed $newval);
  Pone el elemento $newval en la posición de la lista indicada por $index
   
• void offsetUnset (mixed $index);
  Elimina el elemento que se encuentra en la posición indicada por $index

• mixed pop (void);
  Devuelve y elimina el elemento que se encuentra al final de la lista
   
• void prev (void);
  Mueve el indice de la lista al elemento anterior al actual
   
• void push (mixed $value);
  Agrega un nuevo elemento $value al final de la lista
   
• void rewind (void);
  Mueve el indice al principio de la lista
   
• void setIteratorMode (int $mode);
  Permite fijar el modo de iteración mediante el parámetro $mode

  Dirección del iterador:

  • SplDoublyLinkedList::IT_MODE_LIFO (Estilo Pila)
  • SplDoublyLinkedList::IT_MODE_FIFO (Estilo Cola)
     

   Comportamiento del iterador:

  • SplDoublyLinkedList::IT_MODE_DELETE (El iterador elimina los elementos)
  • SplDoublyLinkedList::IT_MODE_KEEP (El iterador mantiene los elementos en la lista)
     

  El modo por defecto es: SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_KEEP

• mixed shift (void);
  Extrae el elemento que se encuentra en la parte superior de la lista. Lo devuelve y lo elimina de la lista
   
• mixed top (void);
  Devuelve el elemento que se encuentra al final de la lista sin eliminarlo
   
• void unshift (mixed $value);
  Inserta el elemento $value al principio de la lista
   
• bool valid (void);
  Indica si la lista contiene más elementos

Ejemplo con listas doblemente enlazadas

  // Lista doblemente enlazada  
  $dll = new SplDoublyLinkedList ();
 
  // Insertamos los elementos en la lista  
  $dll->push ('Perro');
  $dll->push ('Gato');
  $dll->push ('Loro');
  $dll->push ('Caballo');
 
  // Reiniciamos el indice
  $dll->rewind();
 
  while ($dll->valid())
  {
    echo $dll->current() . "<br />";
    $dll->next();
  }
 
  echo "<p>Despu&eacute;s de la primera iteracion, la lista " . (($dll->isEmpty()) ? 'NO' : 'SI') . " contiene elementos." .       "Concretamente {$dll->count()} elementos</p>";
 
  $primer_elemento = $dll->shift();
 
  echo "<p>Extraemos el primer elemento de la lista ({$primer_elemento}) </p>";
 
  $ultimo_elemento = $dll->pop();
 
  echo "<p>Extraemos el ultimo elemento de la lista ({$ultimo_elemento}) </p>";
 
  // Cambiamos el modo de recorrer los elementos
  // Estilo Pila con eliminacion de elementos
  echo "<p>Cambiamos el modo de iteracion a estilo Cola (Modo: {$dll->getIteratorMode()})</p>";
 
  $dll->setIteratorMode (SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_DELETE);
 
  // Reiniciamos el indice  $dll->rewind();
  while ($dll->valid())
  {
    echo $dll->current() . "<br />";
    $dll->next();
  }
 
  echo "<p>Despu&eacute;s de la segunda iteracion, la lista " . (($dll->isEmpty()) ? 'NO' : 'SI') . " contiene elementos " .       "({$dll->count()} elementos)</p>";
 
  // SALIDA:
  //  Perro
  //  Gato
  //  Loro
  //  Caballo
  //
  //  Despu&eacute;s de la primera iteracion, la lista SI contiene elementos. Concretamente 4 elementos
  //
  //  Extraemos el primer elemento de la lista (Perro)
  //
  //  Extraemos el ultimo elemento de la lista (Caballo)
  //
  //  Cambiamos el modo de iteracion a estilo Pila (Modo: 0)
  //  Loro
  //  Gato
  //
  //  Despu&eacute;s de la segunda iteracion, la lista NO contiene elementos (0 elementos)

A la hora de iterar la lista mediante: current(), next(), prev(), es importante emplear el método rewind() en caso que deseemos mostrar todos los elementos desde el inicio.

Si hacemos uso del método rewind() y a continuación insertamos un nuevo elemento, éste seguirá insertándose al final de la lista.

  // Listas doblemente enlazadas
  $dll = new SplDoublyLinkedList();
 
  // Insertamos un elemento
  $dll->push ('Perro');
 
  // Reiniciamos el indice
  $dll->rewind();
 
  // Insertamos un nuevo elemento
  $dll->push ('Gato');
 
  // Reinciamos el indice
  $dll->rewind();
 
  while ($dll->valid())
  {
    echo $dll->current() . "<br />";
 
    $dll->next();
  }
 
  // SALIDA:
  //   Perro
  //   Gato

Como se puede observar en la salida de este ejemplo, el elemento Gato se ha insertado al final y no al comienzo, aunque hayamos empleado el método rewind() previamente.

SplStack (PHP 5.3 o superior)

Pilas

Esta es una de las primeras estructuras con la que nos familiarizamos desde bien pequeños y una de las más extendidas en la vida cotidiana. Desde nuestra infancia aprendemos a apilar las piezas de un castillo, un lego, los platos, etc.

Las Torres de Hanoi es uno de los juegos más conocidos en el entorno del desarrollo y los algoritmos. El juego consiste en trasladar la pila de aros de un extremo al otro, manteniendo el orden de las piezas (de menor a mayor) y disponemos de tres posiciones (tres pilas) donde podemos ir situando las piezas hasta conseguir el resultado deseado.

Métodos:

La clase SplStack hereda de la Lista doblemente enlazada, por tanto, reutiliza todos los métodos mencionados anteriormente, aunque redefine el método: setIteratorMode(int $mode)

• void setIteratorMode(int $mode);
  Permite fijar el modo de iteración mediante el parámetro $mode
  

   Comportamiento del iterador:

  • SplDoublyLinkedList::IT_MODE_DELETE (El iterador elimina los elementos)
  • SplDoublyLinkedList::IT_MODE_KEEP (El iterador mantiene los elementos en la lista)
     

  La dirección de iteración no puede variarse y el modo por defecto es:

  SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_KEEP

PHP 5.3 ofrece varias opciones a la hora de agrear o extraer elementos de una pila pero, cúal de estas opciones es la más óptima?

Veamos una comparativa entre tres posibles formas de agregar un elemento a una pila (array_push(), SplStack::push(), $array[]), para poder tomar una decisión (descargar comparativa en PHP).

Nota: en la comparativa no se ha tenido en cuenta el coste que supone la creación del objeto o la creación de un array, simplemente se calcula el coste de agregar un elemento.

array_push vs SplStack::push() vs $array []

Ahora aplicaremos el mismo sistema para calcular el coste de cada método a la hora de extraer elementos de una pila.

array_pop vs SplStack::pop()

Ejemplo con Pilas – Las torres de Hanoi

  function hanoi ($numero_aros, &$inicio, &$final, &$aux)
  {
    if ($numero_aros == 1)
    {
      $final[] = $inicio->pop();
    }
    else
    {
      hanoi($numero_aros - 1, $inicio, $aux, $final);
      $final[] = $inicio->pop();
      hanoi($numero_aros - 1, $aux, $final, $inicio);
    }
  }
 
  // Primera pila
  $ini_stack = new SplStack ();
 
  // Pila intermedia
  $aux_stack = new SplStack ();
 
  // Pila final
  $final_stack = new SplStack ();
 
  // Inicialmente todas las piezas
  // se encuentran en la primera pila
  $ini_stack[] = 'IIIIIIIIII';
  $ini_stack[] = '  IIIIII  ';
  $ini_stack[] = '    II    ';     
 
  hanoi ($ini_stack->count(), $ini_stack, $final_stack, $aux_stack);
 
  // Aros en la pila inicial
  echo "<p>Aros en la pila inicial</p>";
 
  foreach ($ini_stack as $aro)
  {
    echo "{$aro} <br />";
  }
 
  // Aros en la pila intermedia
  echo "<p>Aros en la pila intermedia</p>";
 
  foreach ($aux_stack as $aro)
  {
    echo "{$aro} <br />";
  }
 
  // Aros en la pila final
  echo "<p>Aros en la pila final</p>";
 
  $final_stack->rewind();
 
  while ($final_stack->valid())
  {
    echo "{$final_stack->current()}<br />";
    $final_stack->next();
  }
 
  // Estado inicial
  //
  // Pila inicial
  //     II
  //   IIIIII
  // IIIIIIIIII
  //
  // Pila Intermedia
  //
  // Pila Final
  //
  ////////////////////
  //
  // Estado final
  //
  // Pila inicial
  //
  // Pila Intermedia
  //
  // Pila Final
  //     II
  //   IIIIII
  // IIIIIIIIII

SplQueue  (PHP 5.3 o superior)

Colas

Las colas también son bien conocidas en la vida real (la cola del cine, la cola del paro , etc) y por lo general se suelen resolver de la misma forma: la primera persona que llega es la primera en ser atendida y por tanto, la primera en salir de la cola (FIFO – First In First Out).

Las colas son de gran ayuda a la hora de realizar recorridos en estructuras más complejas como los árboles y los grafos.

Al igual que en el caso de las pilas, PHP 5.3 dispone de varios métodos para agregar o extraer elementos de una cola. Nos encontraremos ante la misma duda a resolver: ¿Cúal de los métodos posibles permite una inserción y/o una extracción más óptima?

Veamos en este caso una comparativa entre dos opciones para agregar un elemento a una cola (array_unshift(), SplStack::enqueue()).

Nota: en la comparativa no se ha tenido en cuenta el coste que supone la creación del objeto o la creación de un array, simplemente se calcula el coste de agregar un elemento a la cola.

array_unshift vs SplQueue::enqueue

Comparemos ahora las opciones disponibles para extraer elementos.

array_shift vs SplQueue::dequeue

Métodos:

Esta estructura también extiende las funcionalidades de las Listas doblemente enlazadas, manteniendo todos sus métodos, redefiniendo el método: setIteratorMode(int $mode) y agregando los métodos: enqueue() y dequeue().

• void setIteratorMode(int $mode);
  Permite fijar el modo de iteración mediante el parámetro $mode
  

   Comportamiento del iterador:

  • SplDoublyLinkedList::IT_MODE_DELETE (El iterador elimina los elementos)
  • SplDoublyLinkedList::IT_MODE_KEEP (El iterador mantiene los elementos en la lista)
     

  La dirección de iteración no puede variarse y el modo por defecto es:

  SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_KEEP

• void enqueue (mixed $value);
  Añade un nuevo elemento $value al final de la cola. Tiene el mismo efecto que el método push()

• mixed dequeue (void);
  Extrae el primer elemento de la cola.

Ejemplo con Colas

El siguiente ejemplo ha sido tomado de la EUITIO (Escuela Universitaria de Ingeniería Técnica Informática de Oviedo) y ha sido adaptado para correr sobre PHP 5.3.

Un camionero conduce desde un punto de origen hasta un destino determinado siguiendo una ruta dada y llevando un camión que le permite, con el tanque de gasolina lleno, recorrer n kilómetros sin parar. El camionero dispone de un mapa de carreteras que le indica las distancias entre las gasolineras que hay en su ruta. Como va con prisa, el camionero desea pararse a repostar el menor número de veces posible. Deseamos diseñar un algoritmo ávido para determinar en qué gasolineras tiene que parar y demostrar que el algoritmo encuentra siempre la solución óptima.

<?php
/**
 * @author Pablo Gonzalez Jimenez, Pablo Alvarez Menendez, Lino Vazquez Tenorio
 * @version 1.0
 * @category Teoria de la programacion
 */
class Gasolinera 
{
  private $numeroGasolinera;
  private $distanciaProxima;
 
  public function Gasolinera($numeroGasolinera, $distanciaProxima) 
  {
    $this->numeroGasolinera = $numeroGasolinera;
    $this->distanciaProxima = $distanciaProxima;
  }
 
  public function getNumeroGasolinera() 
  {
    return $numeroGasolinera;
  }
 
  public function setNumeroGasolinera($numeroGasolinera) 
  {
    $this->numeroGasolinera = $numeroGasolinera;
  }
 
  public function getDistanciaProxima() 
  {
    return $this->distanciaProxima;
  }
 
  public function setDistanciaProxima($distanciaProxima) 
  {
    $this->distanciaProxima = $distanciaProxima;
  }
 
  public function __toString()
  {
    $cadena="";
    $cadena .= "Gasolinera n&uacute;mero: ". $this->numeroGasolinera . ", tienes que repostar.";
 
  return $cadena;
  }
}
?>

<?php
/**
 * @author Pablo Gonzalez Jimenez, Pablo Alvarez Menendez, Lino Vazquez Tenorio
 * @version 1.0
 * @category Teoria de la programacion
 */
 
require "Gasolinera.php";
 
class SplQueueTester
{
  private $gasolineras;
  private $repostar;
  private $deposito;
 
  public function __construct() 
  {
    $this->inicializar();
    $this->mostrarParadas();
  } 
 
  /**
   * En este metodo se crean los objetos gasolinera. Cada uno tendra un numero
   * y la distancia a la que se encuentra de el punto anterior.
   * 
   * Se crean las colas en las que se insertaran todas las gasolineras
   * disponibles y otra en la que se insertaran solo en las que se vaya a
   * parar.
   * 
   * Se define la autonomia del camion en la variable "deposito".
   * 
   */
  public function inicializar() 
  {
    $this->deposito	= 30;
    $this->gasolineras	= new SplQueue();
    $this->repostar	= new SplQueue();
 
    $this->gasolineras->enqueue(new Gasolinera(1, 10));
    $this->gasolineras->enqueue(new Gasolinera(2, 30));
    $this->gasolineras->enqueue(new Gasolinera(3, 15));
    $this->gasolineras->enqueue(new Gasolinera(4, 30));
  }
 
  /**
   * Este metodo imprime por pantalla las gasolineras en las que se debe parar.
   * 
   */
  public function mostrarParadas() 
  {
    try 
    {
      $this->calcularGasolineras();
      $tamano = count($this->repostar);
 
      if ($tamano == 0) 
      {
        echo "No le hace falta parar a repostar.";
      } 
      else 
      {
         for ($i = 0; $i < $tamano; $i++) 
         {
           echo "<br />" . $this->repostar->dequeue();
         }
      }
    } 
    catch (Exception $e) 
    {
      echo $e->getMessage();
    }
 
    echo "<br />El programa ha concluido.";
  }
 
  /**
   * Este metodo lo utilizamos para poder calcular en que gasolineras tiene
   * que parar el camionero a repostar.
   */
 
  //Solucion al problema "Camionero con prisa", con la tecnica "Algoritmo voraz".
  private function calcularGasolineras() 
  {
    $aux = $this->gasolineras->dequeue();
    $aux2 = $aux;
 
    $kmRecorridos = 0;
 
    while ($aux != null) 
    {
      if ($aux->getDistanciaProxima() > $this->deposito) 
      {
        throw new Exception("Su viaje es inviable.");
      }
 
      $kmRecorridos += $aux->getDistanciaProxima();
 
      if ($kmRecorridos > $this->deposito) 
      {
        $kmRecorridos = 0;
        $this->repostar->enqueue($aux2);
      } 
      elseif (!$this->gasolineras->isEmpty()) 
      {
        $aux2 = $aux;
        $aux = $this->gasolineras->dequeue();
      }
      else
      {
        $aux = null;
      }
    }
  }
}
 
new SplQueueTester ();
?>

En el ejemplo se utiliza un vehículo con un deposito que permite realizar 30 Km sin repostar y esto le permite realizar todo el trayecto, ya que, la distancia máxima entre las gasolineras es de 30 Km.

Si en vez de utilizar la configuración:

    $this->gasolineras->enqueue(new Gasolinera(1, 10));
    $this->gasolineras->enqueue(new Gasolinera(2, 30));
    $this->gasolineras->enqueue(new Gasolinera(3, 15));
    $this->gasolineras->enqueue(new Gasolinera(4, 30));

Utilizamos la siguiente:

    $this->gasolineras->enqueue(new Gasolinera(1, 10));
    $this->gasolineras->enqueue(new Gasolinera(2, 35));
    $this->gasolineras->enqueue(new Gasolinera(3, 15));
    $this->gasolineras->enqueue(new Gasolinera(4, 35));

La respuesta del sistema será que no es posible realizar el trayecto (su viaje es inviable), debido a que nuestro deposito está preparado para realizar 30 Km y la distancia hasta la segunda gasolinera desde la primera es de 35 Km y lo mismo sucede entre la tercera y la cuarta.

Estructuras de datos con SPL – Segunda parte

En la segunda parte de este artículo, comentaré el resto de estructuras de datos y publicaré todos los códigos utilizados (ejemplos, pruebas, códigos de pChart para generar los gráficos…), pero de momento podéis echarle un vistazo al webinar publicado por PHP | Architect sobre las estructuras de datos en PHP 5.3 (en inglés).

Entradas relacionadas

• PHP 5.3 en Wamp Server 2.0i
• Netbeans 6.8 con soporte para PHP 5.3 y Symfony
• PHP 5.3 – Publicada
• PHP 5.3 – Funciones lambda y Closures
• PHP 5.3 – Declarar y usar Namespaces

Tags: PHP 5.3, SPL