Collection, Set, Queue, Deque e Stack

[João Batista Neto 448]

Esse tópico surgiu em http://forum.imasters.com.br/public/style_emoticons/default/seta.gif Armazenar valores de uma classe em um vetor e esse conteúdo foi separado em um novo tópico para melhor organização e para facilitar em futuras buscas.

 

Uma lista é uma sequencia N elementos.

 

Tipos de lista:

 

Queue -> Fila -> FIFO -> Igual a uma fila de banco, onde o primeiro a entrar na fila é o primeiro a ser atendido.

Deque -> Double Ended Queue -> Um deque é uma fila onde os elementos podem entrar e sair de qualquer uma das extremidades da lista.

Stack -> Pilha -> FILO -> Igual a uma pilha de pratos, onde o primeiro a entrar é o último a sair, você sempre pega o último prato da pilha.

 

Lista Encadeada -> Em uma lista encadeada, existe uma referência a um outro elemento da lista, isso permite que um elemento seja incluído em qualquer lugar da lista.

Lista Duplamente Encadeada -> É como uma lista encadeada, a diferença é que ela possui duas referências, uma para o próximo elemento e outra para o elemento anterior.

 

Nesse tópico, vamos ver como fazer uma implementação orientada a objetos:

 

A partir desse ponto, é fundamental o mínimo de entendimento de todos os conceitos de orientação a objetos, não explicarei OOP aqui, então, caso surja alguma dúvida referente ao tema, abram um novo tópico para isso no fórum principal.

 

Bom, a primeira coisa que faremos será definir um objeto Object, será a menor partícula da nossa implementação, todos os outros objetos descenderão dessa partícula, consequentemente, será uma interface conhecida e utilizada por toda a implementação.

 

application/org/base/Object.php

 

<?php/*** Classes e objetos de base da aplicação* @package	base* @category	oop*/namespace org\base;use \stdClass;use \ReflectionObject;/*** Objeto básico da aplicação* @package		base* @category	oop*/class Object extends stdClass {/** * Constroi o novo objeto */public function __construct(){	gc_enable();}/** * Destroi o objeto */public function __destruct(){	gc_collect_cycles();}/** * Recupera uma String que representa o objeto * @return string */public function __toString(){	return sprintf( '%s@%s' , $this->getReflection()->getName() , $this->hashCode() );}/** * Compara a igualdade entre dois objetos * @param Object $object */public function equals( Object $object ){	return $this->hashCode() == $object->hashCode();}/** * Recupera uma instância de ReflectionObject para o objeto * @return ReflectionObject */public function getReflection(){	return new ReflectionObject( $this );}/** * Recupera um hash para o objeto * @return string */public function hashCode(){	return base_convert( spl_object_hash( $this ) , 16 , 10 );}}

 

 

O objetivo da definição dessa partícula é conseguir o nível de abstração necessária para programação para interfaces, todos os objetos dessa ilustração serão capazes de trabalhar com qualquer implementação justamente por não programarmos para uma implementação. Ao programar para uma interface, deixamos que cada objeto faça seu trabalho utilizando um dos princípios fundamentais da orientação a objetos que é o encapsulamento, não precisamos saber como uma coisa realmente é feita, apenas confiaremos nos contratos que os objetos assinam ao implementar uma interface específica.

 

Para definição de nossas listas, vamos precisar de um Array na forma de objeto, não vamos utilizar o ArrayObject da SPL por dois motivos:

 

1. Existem algumas limitações e não temos o controle sobre ele.

2. Queremos demonstrar algumas interfaces da SPL.

 

application/org/base/ArrayObject.php

 

<?php/*** Classes e objetos de base da aplicação* @package		base* @category	oop*/namespace org\base;use \ReflectionClass;use \IteratorAggregate;use \ArrayAccess;use \Serializable;use \Countable;use org\base\exception\InvalidArgumentException;use org\base\exception\UndefinedIndexException;use org\base\exception\ClassNotFoundException;use org\base\exception\NoSuchElementException;use org\base\exception\CastException;/*** Implementação de uma matriz na forma de objeto* @package		base* @category	oop*/class ArrayObject extends Object implements ArrayAccess, Countable, IteratorAggregate, Serializable {/** * Dados do objeto * @var array */private $storage;/** * Classe do iterator que será utilizado pelo método getIterator * @var string */private $iteratorClass = '\ArrayIterator';/** * Constroi o novo objeto * @param array $array */public function __construct( array $array = array() ){	$this->storage = $array;}/** * Adiciona um novo elemento ao fim do objeto * @param mixed $value * @see ArrayObject::push() */public function append( $value ){	$this->storage[] = $value;}/** * Ordena uma matriz de forma que os índices mantém suas relações com os elementos da matriz * @param integer $flags */public function asort( $flags = null ){	asort( $this->storage , $flags );}/** * Recupera o total de itens do objeto * @return integer */public function count(){	return count( $this->storage );}/** * Recupera o último elemento da matriz, sem removê-lo * @return mixed Retorna NULL se o objeto estiver vazio */public function end(){	$ret = null;	if ( $this->count() > 0 ){		$ret = end( $this->storage );	}	return $ret;}/** * Recupera o primeiro elemento da matriz, sem removê-lo * @return mixed Retorna NULL se o objeto estiver vazio */public function first(){	$ret = null;	if ( $this->count() > 0 ){		$ret = $this->storage[ 0 ];	}	return $ret;}/** * Recupera uma cópia da matriz * @return array */public function getArrayCopy(){	return $this->storage;}/** * Recupera um iterator para o objeto * @return Iterator */public function getIterator(){	$reflection = new ReflectionClass( $this->iteratorClass );	return $reflection->newInstanceArgs( array( $this->storage ) );}/** * Recupera a classe que é utilizada para criar um iterator para o objeto * @return string */public function getIteratorClass(){	return $this->iteratorClass;}/** * Ordena a matriz mantendo a relação entre dados e chaves * @param integer $flags */public function ksort( $flags = null ){	ksort( $this->storage , $flags );}/** * Ordena a matriz utilizando o algorítimo de "ordem natural" não sensível a caixa */public function natCasesort(){	natcasesort( $this->storage );}/** * Ordena a matriz utilizando o algorítimo de "ordem natural" sensível a caixa */public function natsort(){	natsort( $this->storage );}/** * Verifica se um índice ou chave está definida no objeto * @param mixed $offset * @return boolean */public function offsetExists( $offset ){	return isset( $this->storage[ $offset ] );}/** * Recupera um elemento do objeto pelo offset * @param mixed $offset * @return mixed * @throws UndefinedIndexException Se o offset não estiver definido */public function offsetGet( $offset ){	if ( $this->offsetExists( $offset ) ){		return $this->storage[ $offset ];	} else {		throw new UndefinedIndexException( sprintf( 'O offset[ %s ] não está definido.' , $offset ) );	}}/** * Define um novo elemento ao objeto * @param mixed $offset * @param mixed $value */public function offsetSet( $offset , $value ){	if ( is_null( $offset ) ){		$this->append( $value );	} else {		$this->storage[ $offset ] = $value;	}}/** * Remove um elemento do objeto na posição especificada * @param mixed $offset * @throws UndefinedIndexException Se o offset não estiver definido */public function offsetUnset( $offset ){	if ( $this->offsetExists( $offset ) ){		unset( $this->storage[ $offset ] );	} else {		throw new UndefinedIndexException( sprintf( 'O offset[ %s ] não está definido.' , $offset ) );	}}/** * Remove um elemento do fim do objeto * @return mixed O elemento removido * @throws NoSuchElementException Se o objeto estiver vazio */public function pop(){	if ( $this->count() == 0 ){		throw new NoSuchElementException( 'O objeto está vazio' );	} else {		return array_pop( $this->storage );	}}/** * Adiciona um novo elemento ao fim da matriz * @param mixed $value * @return mixed O elemento adicionado * @see ArrayObject::append() */public function push( $value ){	$this->storage[] = $value;	return $value;}/** * Inverte a ordem dos elementos * @return ArrayObject */public function reverse(){	return new ArrayObject( array_reverse( $this->storage , true ) );}/** * Serializa o objeto * @return string */public function serialize(){	return serialize( $this->storage );}/** * Recupera uma fatia do objeto * @param integer $offset * @param integer $length * @param boolean $preserveKeys * @return ArrayObject */public function slice( $offset , $length = null , $preserveKeys = null ){	if ( !is_int( $length ) ) $length = $this->count();	return new ArrayObject( array_slice( $this->storage , $offset , $length , $preserveKeys ) );}/** * Remove o primeiro elemento do objeto * @return mixed O elemento removido * @throws UndefinedIndexException Se o offset não estiver definido */public function shift(){if ( $this->count() == 0 ){		throw new NoSuchElementException( 'O objeto está vazio' );	} else {		return array_shift( $this->storage );	}}/** * Define a classe que será utilizada pelo método getIterator() * @param string $class * @throws ClassNotFoundException Se a classe não existir * @throws CastException Se a classe não implementar a interface Iterator */public function setIteratorClass( $class ){	if ( class_exists( $class , false ) ){		if ( in_array( '\Iterator' , class_implements( $class , false ) ) ){			$this->iteratorClass = $class;		} else {			throw new CastException( sprintf( 'A classe %s precisa implementar a interface Iterator.' , $class ) );		}	} else {		throw new ClassNotFoundException( sprintf( 'A classe %s não foi encontrada.' , $class ) );	}}/** * Recupera uma cópia da matriz do objeto * @return array */public function toArrayCopy(){	return $this->storage;}/** * Ordena uma matriz de forma que os índices mantém suas relações com os elementos da matriz utilizando * uma função definida pelo usuário * @param Closure $callback */public function uasort( Closure $callback ){	uasort( $this->storage , $callback );}/** * Ordena a matriz mantendo a relação entre dados e chaves utilizando uma função definida pelo usuário * @param Closure $callback */public function uksort( Closure $callback ){	uksort( $this->storage , $callback );}/** * Retorna um objeto serializado para usa forma original * @param string $serialized */public function unserialize( $serialized ){	$data = unserialize( $serialized );	if ( is_array( $data ) ){		$this->storage =& $data;	} else {		throw new InvalidArgumentException( 'Dados inválidos.' );	}}/** * Adiciona um elemento ao início do objeto * @param mixed $value */public function unshift( $value ){	array_unshift( $this->storage , $value );}}

 

 

Com a interface do Object definida e nossa ArrayObject pronta, passamos a definir as interfaces que usaremos para a implementação de nossas listas:

 

application/org/util/Collection.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use \IteratorAggregate;use \Countable;use org\base\Object;/*** Define a interface de uma coleção de objetos* @package		util* @category	oop*/interface Collection extends IteratorAggregate, Countable {/** * Adiciona um novo objeto na coleção * @param Object $o * @return boolean */public function add( Object $o );/** * Adiciona todos os objetos de uma coleção nessa coleção * @param Collection $c * @return boolean */public function addAll( Collection $c );/** * Limpa a coleção atual deixando-a sem nenhum elemento * @return boolean * @see Collection::isEmpty() */public function clear();/** * Verifica se a coleção atual pussui um determinado objeto * @param Object $o * @return boolean */public function contains( Object $o );/** * Verifica se a coleção atual possui todos os objetos de outra coleção * @param Collection $c * @return boolean */public function containsAll( Collection $c );/** * Verifica se a coleção atual é igual a outro objeto * @param Object $o * @return boolean */public function equals( Object $o );/** * Recupera um hash para identificação da coleção * @return string * @see Object::hashCode() */public function hashCode();/** * Verifica se a coleção está vazia * @return boolean * @see Collection::clear() */public function isEmpty();/** * Remove um elemento da coleção * @param Object $o * @return boolean */public function remove( Object $o = null );/** * Remove todos os objetos de uma outra coleção da coleção atual * @param Collection $c * @return boolean */public function removeAll( Collection $c );/** * Mantém na coleção apenas os elementos existentes na coleção especificada * @param Collection $c * @return boolean */public function retainAll( Collection $c );/** * Recupera uma matriz contendo os elementos da coleção * @return array */public function toArray();}

 

 

Uma Collection, como o próprio nome pode sugerir, é uma coleção de objetos, em uma coleção podem ou não haver elementos duplicados, podem ou não estar ordenados, enfim, uma implementação de uma coleção pode ser muito específica e comportamentalmente totalmente diferente de outra.

 

Para facilitar uma implementação de uma coleção, definiremos uma abstração de uma implementação base, deixando para outras implementações o mínimo necessário:

 

application/org/util/AbstractCollection.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use org\base\Object;use org\base\ArrayObject;use org\base\exception\InvalidArgumentException;use org\base\exception\CastException;use org\util\Collection;/*** Essa classe é o esqueleto de uma implementação da interface Collection.* @abstract* @package		util* @category	oop*/abstract class AbstractCollection extends Object implements Collection {/** * Armazenamento dos dados * @access private * @var org\base\ArrayObject */protected $storage;/** * Constroi uma nova coleção * @param mixed $elements Os elementos iniciais da coleção<p> * $elements pode ser uma matriz, Collection ou um Iterator</p> * @throws LogicException Se algum item da lista inicial de elementos não for um Object * @throws CastException Se $elements não for um tipo válido */public function __construct( $elements = null ){	parent::__construct();	$this->clear();	if ( !is_null( $elements ) ){		if ( is_array( $elements ) || ( $elements instanceOf Collection ) || ( $elements instanceOf Iterator ) || ( $elements instanceOf IteratorAggregate ) ){			foreach ( $elements as $e ){				if ( $e instanceOf Object ){					$this->add( $e );				} else {					throw new CastException( 'Apenas objetos podem ser armazenados' );				}			}		} else {			throw new CastException( sprintf( '$emements precisa ser uma matriz, Collection ou Iterator, %s foi dado.' , gettype( $elements ) ) );		}	}}/** * Recupera a representação da coleção como string * @return string */public function __toString(){	return sprintf( '%s[%s]' , parent::__toString() , implode( ',' , $this->toArray() ) );}/** * Adiciona um novo objeto à coleção * @param Object $o * @return boolean * @throws CastException Se o objeto for de um tipo diferente da lista */public function add( Object $o ){	if ( $this->isValid( $o ) ){		$this->storage->append( $o );	}	return true;}/** * Adiciona todos os objetos de uma outra coleção a esta coleção * @param Collection $c * @return boolean */public function addAll( Collection $c ){	foreach ( $c->getIterator() as $o ){		$this->add( $o );	}	return true;}/** * Limpa a coleção deixando-a sem nenhum elemento * @return boolean */public function clear(){	$this->storage = new ArrayObject();	return true;}/** * Recupera o total de elementos da coleção * @return integer */public function count(){	return $this->storage->count();}/** * Verifica se a coleção contém um determinado elemento * @param Object $o O elemento que será verificado se está contido na coleção * @return boolean */public function contains( Object $o ){	foreach ( $this->getIterator() as $item ){		if ( $item->equals( $o ) ){			return true;		}	}	return false;}/** * Verifica se a coleção possui todos os elementos de outra coleção * @param Collection $c A coleção que possui os elementos que será verificados * @return boolean */public function containsAll( Collection $c ){	foreach ( $c->getIterator() as $o ){		if ( !$this->contains( $o ) ){			return false;		}	}	return true;}/** * Recupera um Iterator para a coleção * @return Iterator */public function getIterator(){	return $this->storage->getIterator();}/** * Verifica se a coleção está vazia * @return boolean * @see AbstractCollection::count(), AbstractCollection::clear() */public function isEmpty(){	return $this->count() == 0;}/** * Método que será utilizado para verificação de um objeto antes da inserção * @param Object $o * @return boolean */abstract protected function isValid( Object $o );/** * Remove um elemento da coleção * @param Object $o O objeto que se deseja remover * @return boolean */public function remove( Object $o = null ){	$ret = false;	if ( !is_null( $o ) ){		foreach ( $this->getIterator() as $key => $e ){			if ( $o->equals( $e ) ){				$this->storage->offsetUnset( $key );				$ret = true;			}		}	}	return $ret;}/** * Remove da coleção todos os elementos contidos em outra coleção * @param Collection $c A coleção que contém os elementos que se deseja remover * @return boolean TRUE Se todos os elementos contidos na coleção especificada tiverem sido removidos */public function removeAll( Collection $c ){	foreach ( $c->getIterator() as $e ){		if ( !$this->remove( $e ) ){			return false;		}	}	return true;}/** * Mantém apenas os elementos contidos na outra coleção * @param Collection $c A coleção que contém os elementos que se deseja manter * @return boolean */public function retainAll( Collection $c ){	foreach ( $this->getIterator as $e ){		if ( !$c->contains( $e ) ){			if ( !$this->remove( $e ) ){				return false;			}		}	}	return true;}/** * Recupera uma matriz com todos os elementos da coleção * @return array */public function toArray(){	return $this->storage->getArrayCopy();}}

 

 

Como podem ver, AbstractCollection é uma classe abstrata e, como tal, jamais poderá ser instanciada, somente implementações dessa classe poderão. Um outro aspecto da AbstractCollection é a falta de uma implementação base para o método isValid( Object $o ), esse método foi declarado como abstrato, o que significa que todas as implementações da AbstractCollection precisarão necessariamente definir esse método. Apesar de isValid() não ser um método público, ele é também conhecido como método de interface, porque, ao implementar AbstractCollection, os objetos derivados assinam um contrato com essa classe e, consequentemente, deverão implementar esse método, que será utilizado "nos bastidores" pela abstração.

Um outro detalhe sobre a implementação de AbstractCollection é que ela deriva Object, ou seja, AbstractCollection e todos seus herdeiros serão, por definição, Objects também.

 

Além da Collection, vamos definir uma outra interface um pouco parecida, mas conceitualmente totalmente diferente, a interface Set. Um Set, assim como uma Collection é uma coleção de objetos, a diferença principal é que, conceitualmente, um Set jamais permite elementos duplicados.

 

application/org/util/Set.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use org\util\Collection;/*** Um Set é uma Collection, com a diferença que, por definição, um Set possui apenas elementos únicos* @package		util* @category	oop*/interface Set extends Collection {}

 

 

Como disse, um Set difere de uma Collection apenas conceitualmente, as interfaces são idênticas, agora, uma abstração de uma implementação de um Set para facilitar outras implementações:

 

application/org/util/AbstractSet.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use org\base\Object;use org\base\exception\LogicException;use org\util\AbstractCollection;use org\util\Set;/*** Essa classe é o esqueleto de uma implementação da interface Set.<p>* Um Set é uma Collection, com a diferença que, por definição, um Set possui apenas elementos únicos* </p>* @package		util* @category	oop*/abstract class AbstractSet extends AbstractCollection implements Set {/** * Verifica se o objeto é válido * @param Object $o * @return boolean */protected function isValid( Object $o ){	if ( $this->contains( $o ) ){		throw new LogicException( sprintf( 'O elemento %s já existe na lista.' , $o ) );	}	return true;}}

 

 

Agora a abstração começa a funcionar, não sabemos quem está implementando o Set, sabemos com certeza apenas que essa implementação terá necessariamente um método contains() que retornará um boolean dizendo se um objeto está contido no Set, dessa forma, sabemos se um objeto já está contém um outro objeto e, assim, podemos disparar uma exceção dizendo que nosso Set não aceita elementos duplicados.

 

Bom, até esse momento, apenas definimos a forma de entrada e saída referentes à Collection, passaremos agora, a definir as formas de saída das Listas, vamos usar Collection para as definições, primeiro de uma fila:

 

application/org/util/Queue.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use org\base\Object;/*** Interface para definição de uma fila FIFO* @package		util* @category	oop*/interface Queue extends Collection {/** * Recupera de forma não destrutiva o primeiro elemento da fila * @return Object * @see Queue::peek() * @throws NoSuchElementException Se a fila estiver vazia */public function element();/** * Oferece um elemento para ser inserido na lista * @param Object $o * @return boolean * @see Collection::add() */public function offer( Object $o );/** * Recupera de forma não destrutiva o primeiro elemento da fila * @return Object ou NULL se a fila estiver vazia * @see Queue::element() */public function peek();/** * Recupera de forma destrutiva o primeiro elemento da fila * @return Object ou NULL se a fila estiver vazia * @see Collection::remove() */public function pool();}

 

 

E agora uma abstração para uma fila:

 

application/org/util/AbstractQueue.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use org\base\exception\NoSuchElementException;use org\base\Object;/*** Essa classe é o esqueleto de uma implementação de uma fila FIFO* @abstract* @package		util* @category	oop*/abstract class AbstractQueue extends AbstractCollection implements Queue {/** * Constroi a fila */public function __construct(){	parent::__construct();}/** * Oferece um elemento para ser inserido na lista * @param Object $o * @return boolean * @see Collection::add() */public function offer( Object $o ){	return $this->add( $o );}/** * Recupera de forma não destrutiva o primeiro elemento da fila * @return Object * @see Queue::peek() * @throws NoSuchElementException Se a fila estiver vazia */public function element(){	if ( is_null( $ret = $this->peek() ) ){		throw new NoSuchElementException( 'A fila está vazia' );	}	return $ret;}/** * Recupera de forma não destrutiva o primeiro elemento da fila * @return Object ou NULL se a fila estiver vazia * @see Queue::element() */public function peek(){	$ret = null;	if ( $this->count() > 0 ){		$ret = $this->storage->first();	}	return $ret;}/** * Recupera de forma destrutiva o primeiro elemento da fila * @return Object ou NULL se a fila estiver vazia * @see Queue::remove() */public function pool(){	$ret = null;	if ( $this->count() > 0 ){		$ret = $this->storage->shift();	}	return $ret;}/** * Recupera de forma destrutiva o primeiro elemento da fila * @return Object * @see Queue::pool() * @throws NoSuchElementException Se a fila estiver vazia */public function remove( Object $o = null ){	if ( is_null( $ret = $this->pool() ) ){		throw new NoSuchElementException( 'A fila está vazia' );	}	return $ret;}}

 

 

Como, por definição, um Deque é uma fila (Queue), com a diferença de que os dados podem entrar e sair pelas duas extremidades, vamos utilizar a mesma interface Queue para definir nosso Deque:

 

application/org/util/Deque.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use org\base\Object;/*** Interface para definição de DEQue, Double Ended Queue* @package		util* @category	oop*/interface Deque extends Queue {/** * Adiciona um novo elemento ao início da lista * @param Object $o * @return boolean */public function addFirst( Object $o );/** * Adiciona um novo elemento ao final da lista * @param Object $o * @return boolean * @see Collection::add() */public function addLast( Object $o );/** * Recupera um iterator em ordem descendente * @return Iterator */public function descendingIterator();/** * Recupera de forma não destrutiva o primeiro elemento da lista * @return Objet * @see Queue::peek() */public function getFirst();/** * Recupera de forma não destrutiva o último elemento da lista * @return Object */public function getLast();/** * Oferece um elemento para ser adicionado ao início da lista * @param Object $o * @return boolean */public function offerFirst( Object $o );/** * Oferece um elemento para ser adicionado ao fim da lista * @param Object $o * @return boolean */public function offerLast( Object $o );/** * Recupera de forma não destrutiva o primeiro elemento da lista * @return Object ou NULL se a lista estiver vazia * @see Queue::element() */public function peekFirst();/** * Recupera de forma não destrutiva o último elemento da lista * @return Object ou NULL se a lista estiver vazia */public function peekLast();/** * Recupera de forma destrutiva o primeiro elemento da fila * @return Object ou NULL se a fila estiver vazia * @see Collection::remove() */public function poolFirst();/** * Recupera de forma destrutiva o último elemento da fila * @return Object ou NULL se a fila estiver vazia * @see Collection::remove() */public function poolLast();/** * Remove o último elemento da lista * @return Object */public function pop();/** * Adiciona um elemento ao final da lista * @param Object $o * @return Object */public function push( Object $o );/** * Recupera e remove o primeiro elemento da lista * @return Object */public function removeFirst();/** * Recupera e remove a primeira ocorrência do elemento da lista * @param Object $o * @return boolean */public function removeFirstOccurrence( Object $o );/** * Recupera e remove o último elemento da lista * @return Object */public function removeLast();/** * Recupera e remove a primeira ocorrência do elemento da lista * @param Object $o * @return Object */public function removeLastOccurrence( Object $o );}

 

 

E uma implementação de um Deque como um Array:

 

application/org/util/ArrayDeque.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use org\base\exception\NoSuchElementException;use org\base\Object;/*** Essa classe é o esqueleto de uma implementação de uma fila FIFO* @abstract* @package		util* @category	oop*/class ArrayDeque extends AbstractCollection implements Deque {/** * Adiciona um novo elemento ao início da lista * @param Object $o * @return boolean */public function addFirst( Object $o ){	$ret = false;	if ( $this->isValid( $o ) ){		$this->storage->unshift( $o );		$ret = true;	}	return $ret;}/** * Adiciona um novo elemento ao final da lista * @param Object $o * @return boolean * @see Collection::add() */public function addLast( Object $o ){	return $this->add( $o );}/** * Recupera um iterator em ordem descendente * @return Iterator */public function descendingIterator(){	return new ArrayIterator( $this->storage->reverse()->toArrayCopy() );}/** * Recupera o primeiro elemento da fila * @return Object * @see ArrayDeque::getFirst() * @throws NoSuchElementException Se a lista estiver vazia */public function element(){	$ret = $this->storage->first();	if ( is_null( $ret ) ){		throw new NoSuchElementException( 'A lista está vazia' );	}	return $ret;}/** * Recupera de forma não destrutiva o primeiro elemento da lista * @return Objet * @throws NoSuchElementException Se a lista estiver vazia */public function getFirst(){	$ret = $this->element();	return $ret;}/** * Recupera de forma não destrutiva o último elemento da lista * @return Object * @throws NoSuchElementException Se a lista estiver vazia */public function getLast(){	$ret = $this->storage->end();	if ( is_null( $ret ) ){		throw new NoSuchElementException( 'A lista está vazia' );	}	return $ret;}/** * Método que utilizado para verificação de um objeto antes da inserção * @param Object $o * @return boolean */protected function isValid( Object $o ){	return true;}/** * Adiciona um elemento ao final da lista * @param Object $o * @return boolean */public function offer( Object $o ){	return $this->offerLast( $o );}/** * Oferece um elemento para ser adicionado ao início da lista * @param Object $o * @return boolean */public function offerFirst( Object $o ){	return $this->addFirst( $o );}/** * Oferece um elemento para ser adicionado ao final da lista * @param Object $o * @return boolean */public function offerLast( Object $o ){	return $this->addLast( $o );}/** * Recupera de forma não destrutiva o primeiro elemento da lista * @return Object ou NULL se a lista estiver vazia */public function peek(){	return $this->peekFirst();}/** * Recupera de forma não destrutiva o primeiro elemento da lista * @return Object ou NULL se a lista estiver vazia * @see Queue::element() */public function peekFirst(){	try {		return $this->getFirst();	} catch ( NoSuchElementException $e ){		return null;	}}/** * Recupera de forma não destrutiva o último elemento da lista * @return Object ou NULL se a lista estiver vazia */public function peekLast(){	try {		return $this->getLast();	} catch ( NoSuchElementException $e ){		return null;	}}/** * Recupera de forma destrutiva o primeiro elemento da fila * @return Object */public function pool(){	return $this->poolFirst();}/** * Recupera de forma destrutiva o primeiro elemento da fila * @return Object ou NULL se a fila estiver vazia * @see Collection::remove() */public function poolFirst(){	return $this->removeFirst();}/** * Recupera de forma destrutiva o último elemento da fila * @return Object ou NULL se a fila estiver vazia * @see Collection::remove() */public function poolLast(){	return $this->removeLast();}/** * Remove o último elemento da lista * @return Object */public function pop(){	return $this->removeFirst();}/** * Adiciona um elemento ao final da lista * @param Object $o * @return Object */public function push( Object $o ){	$this->addFirst( $o );}/** * Recupera e remove o primeiro elemento da lista * @return Object * @throws NoSuchElementException Se a lista estiver vazia */public function removeFirst(){	return $this->storage->shift();}/** * Recupera e remove a primeira ocorrência do elemento da lista * @param Object $o * @return boolean */public function removeFirstOccurrence( Object $o ){	$ret = false;	foreach ( $this->getIterator() as $offset => $e ){		if ( $e->equals( $o ) ){			$ret = true;			$this->storage->offsetUnset( $offset );			break;		}	}	return $ret;}/** * Recupera e remove o último elemento da lista * @return Object * @throws NoSuchElementException Se a lista estiver vazia */public function removeLast(){	return $this->storage->pop();}/** * Recupera e remove a primeira ocorrência do elemento da lista * @param Object $o * @return Object */public function removeLastOccurrence( Object $o ){	$ret = false;	foreach ( $this->descendingIterator() as $offset => $e ){		if ( $e->equals( $o ) ){			$ret = true;			$this->storage->offsetUnset( $offset );			break;		}	}	return $ret;}}

 

 

A implementação de ArrayDeque não é abstrata e, ao contrário das abstrações, ArrayDeque já é uma classe utilizável.

 

Até agora trabalhamos com filas, restando-nos a Pilha. Ao contrário de uma fila, uma pilha trabalha ao contrário, o primeiro elemento a entrar, será o último a sair, existem muitos casos onde trabalhamos com pilhas em computação, entre elas, as pilhas de chamadas de funções.

Para implementar nossa pilha, usaremos como base um Vetor que implementa uma Lista:

 

application/org/util/Lists.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use \ArrayAccess;use org\base\Object;/*** Interface para definição de uma lista* @package		util* @category	oop*/interface Lists extends Collection, ArrayAccess {/** * Recupera um elemento associado ao $offset na lista * @param integer $offset * @return Object */public function get( $offset );/** * Recupera a posição do elemento na lista * @param Object $o * @return integer * @see Lists::get() */public function indexOf( Object $o );/** * Recupera a última posição do elemento na lista * @param Object $o * @return integer * @see Lists::indexOf() */public function lastIndexOf( Object $o );/** * Recupera um ListIterator para os elementos da lista * @param integer $fromIndex * @return Iterator */public function listIterator( $fromIndex = 0 );/** * Redefine um elemento na posição $offset * @param integer $offset * @param Object $o * @return Object */public function set( $offset , Object $o );/** * Cria uma sub-lista da lista atual * @param $fromIndex * @param $toIndex * @return Lists */public function subList( $fromIndex , $toIndex );}

 

 

Como é notório, uma Lists é uma Collection especializada e com a possibilidade de acesso aos seus elementos através de seus índices, utilizando a interface SPL ArrayAccess, da mesma forma que ocorreu anteriormente, vamos definir uma abstração para uma lista:

 

application/org/util/AbstractLists.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use org\base\Object;use org\base\exception\IndexOutOfBoundsException;use org\base\exception\UndefinedIndexException;use org\base\exception\UnsupportedOperationException;use org\base\exception\InvalidArgumentException;/*** Essa classe é o esqueleto de uma implementação da interface Lists.* @abstract* @package		util* @category	oop*/abstract class AbstractLists extends AbstractCollection implements Lists {/** * Verifica os limites da lista * @param integer $offset * @return boolean * @throws InvalidArgumentException Se $offset não for um inteiro * @throws IndexOutOfBoundsException Se $offset estiver fora dos limites da lista * @throws UndefinexIndexException Se $offset não estiver definido */protected function boundsCheck( $offset ){	$ret = false;	if ( is_int( $offset ) ){		if ( ( $offset < 0 ) || ( $offset > $this->count() - 1 ) ){			throw new IndexOutOfBoundsException( sprintf( 'Offset[ %d ] está fora dos limites da lista.' , $offset ) );		} elseif ( !isset( $this->storage[ $offset ] ) ){			throw new UndefinedIndexException( sprintf( 'Offset[ %d ] não está definido.' , $offset ) );		} else {			$ret = true;		}	} else {		throw new InvalidArgumentException( sprintf( '%s espera um offset inteiro, %s foi dado.' , __METHOD__ , gettype( $offset ) ) );	}	return $ret;}/** * Recupera um elemento associado ao $offset na lista * @param integer $offset * @return Object * @throws InvalidArgumentException Se $offset não for um inteiro * @throws IndexOutOfBoundsException Se $offset for menor que 0 ou maior que o limite da lista * @throws UndefinedIndexException Se o $offset não tiver sido definido */public function get( $offset ){	if ( $this->boundsCheck( $offset ) ){		return $this->storage->offsetGet( $offset );	}}/** * Recupera a posição do elemento na lista * @param Object $o * @return integer * @see Lists::get() */public function indexOf( Object $o ){	foreach ( $this->getIterator() as $offset => $item ){		if ( $item->equals( $o ) ){			return $offset;		}	}	return -1;}/** * Recupera a última posição do elemento na lista * @param Object $o * @return integer * @see Lists::indexOf() */public function lastIndexOf( Object $o ){	$iterator = $this->getIterator();	$offset = $iterator->count() - 1;	while ( $offset >= 0 ){		$iterator->seek( $offset );		$current = $iterator->current();		if ( !is_null( $current) && $current->equals( $o ) ){			return $offset;		}		--$offset;	}	return -1;}/** * Verifica se um offset está definido * @param integer $offset * @return boolean */public function offsetExists( $offset ){	$ret = false;	try {		if ( $this->boundsCheck( $offset ) && ( $this->storage->offsetExists( $offset ) ) ){			$ret = true;		}	} catch ( UndefinedIndexException $e ){		$ret = false;	}	return $ret;}/** * Recupera um elemento associado ao $offset na lista * @param integer $offset * @return Object * @throws InvalidArgumentException Se $offset não for um inteiro * @throws IndexOutOfBoundsException Se $offset for menor que 0 ou maior que o limite da lista * @throws UndefinedIndexException Se o $offset não tiver sido definido */public function offsetGet( $offset ){	return $this->get( $offset );}/** * Redefine um elemento na posição $offset * @param integer $offset * @param Object $value * @throws UnsuportedOperationException */public function offsetSet( $offset , $value ){	$this->set( $offset , $value );}/** * Remove um offset da lista * @param integer $offset */public function offsetUnset( $offset ){	if ( $this->boundsCheck( $offset ) ){		$this->storage->offsetUnset( $offset );	}}/** * Redefine um elemento na posição $offset * @param integer $offset * @param Object $o * @return Object * @see AbstractLists::offsetSet * @throws CastException Se $offset não for um inteiro ou se o objeto não for aceito pela lista * @throws IndexOutOfBoundsException Se $offset for menor que 0 ou maior que o limite da lista * @throws UnsuportedOperationException Se a lista não permitir modificação dos elementos */public function set( $offset , Object $o ){	if ( $this->boundsCheck( $offset ) ){		if ( $this->isValid( $o ) ){			throw new UnsupportedOperationException( 'Operação não suportada pela lista.' );		}	}}/** * Cria uma sub-lista da lista atual * @param $fromIndex * @param $toIndex * @return Lists */public function subList( $fromIndex , $toIndex ){	if ( $this->boundsCheck( $fromIndex ) && $this->boundsCheck( $toIndex ) ){		return $this->getReflection()->newInstanceArgs( array( $this->storage->slice( $fromIndex , $toIndex - $fromIndex + 1 ) ) );;	}}}

 

 

Agora, utilizando isso, um Vector é definido como:

 

application/org/util/Vector.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use \Serializable;use org\base\Object;use org\base\exception\InvalidArgumentException;use org\base\exception\NoSuchElementException;/*** Um Vetor é um objeto que se comporta como uma matriz, permitindo acesso direto* aos seu índices e que pode ser serializado.* @package		util* @category	oop*/class Vector extends AbstractLists implements Serializable {/** * Copia os elementos desse vetor em uma matriz * @param array $array */public function copyInto( array &$array ){	$array = $this->storage->toArrayCopy();}/** * Recupera um elemento de uma posição específica * @param integer $offset * @return Object * @throws InvalidArgumentException Se $offset não for um inteiro * @throws IndexOutOfBoundsException Se $offset for menor que 0 ou maior que o limite da lista * @throws UndefinedIndexException Se o $offset não tiver sido definido */public function elementAt( $offset ){	return $this->offsetGet( $offset );}/** * Recupera o primeiro elemento do vetor (posição 0) * @return Object * @see Vector::elementAt(), AbstractLists::offsetGet() * @throws NoSuchElementException Se o $offset 0 não tiver sido definido */public function firstElement(){	try {		return $this->storage->first();	} catch ( NoSuchElementException $e ){		throw new NoSuchElementException( 'Não existe um primeiro elemento.' );	}}/** * Insere um elemento em u ma posição específica * @param Object $o * @param integer $offset * @throws InvalidArgumentException Se $offset não for um inteiro * @throws CastException Se o elemento for de um tipo diferente da lista */public function insertElementAt( Object $o , $offset ){	$this->offsetSet( $offset , $o );}/** * Verifica se o objeto é válido * @param Object $o * @return boolean */protected function isValid( Object $o ){	return true;}/** * Recupera o último elemento do vetor * @return Object * @throws NoSuchElementException Se o $offset 0 não tiver sido definido */public function lastElement(){	if ( $this->count() > 0 ){		return $this->storage->end();	} else {		throw new NoSuchElementException( 'Não existe um último elemento.' );	}}/** * Recupera um ListIterator para os elementos da lista * @param integer $fromIndex * @return Iterator */public function listIterator( $fromIndex = 0 ){	$retIterator = new ArrayIterator( $this->storage->slice( $fromIndex )->toArrayCopy() );	return $retIterator;}/** * Remove todos os elementos do vetor * @see Collection::clear() */public function removeAllElements(){	$this->clear();}/** * Remove um elemento específico do vetor * @param Object $o * @return boolean */public function removeElement( Object $o ){	$ret = false;	while ( ( $offset = $this->indexOf( $o ) ) >= 0 ){		$this->offsetUnset( $offset );		$ret = true;	}	return $ret;}/** * Remove os elementos do vetor que estão em um intervalo específico * @param integer $fromIndex * @param integer $toIndex */public function removeRange( $fromIndex , $toIndex ){	$this->removeAll( $this->subList( $fromIndex , $toIndex ) );}/** * Serializa o objeto para ser guardado em um banco de dados, sessão ou arquivo * na forma de uma string * @return string */public function serialize(){	return serialize( array( 'storage' => $this->storage ) );}/** * Redefine um elemento na posição $offset * @param integer $offset * @param Object $o * @return Object * @see AbstractLists::offsetSet * @throws CastException Se $offset não for um inteiro ou se o objeto não for aceito pela lista * @throws IndexOutOfBoundsException Se $offset for menor que 0 ou maior que o limite da lista * @throws UnsuportedOperationException Se a lista não permitir modificação dos elementos */public function set( $offset , Object $o ){	$ret = false;	if ( is_null( $offset ) ){		$offset = $this->limit;	}	if ( $this->isValid( $o ) ){		try {			$ret = $this->boundsCheck( $offset );		} catch ( UndefinedIndexException $e ){			$ret = true;			++$this->limit;		}		if ( $ret ){			$this->storage[ $offset ] = $o;		}	}	return $ret;}/** * Redefine um elemento na posição $offset * @param Object $o * @param integer $offset * @see AbstractLists::offsetSet * @throws CastException Se $offset não for um inteiro ou se o objeto não for aceito pela lista * @throws IndexOutOfBoundsException Se $offset for menor que 0 ou maior que o limite da lista * @throws UnsuportedOperationException Se a lista não permitir modificação dos elementos */public function setElementAt( Object $o , $offset ){	$this->set( $offset , $o );}/** * Transforma uma string previamente serializada de volta no objeto * @param string $serialized * @return Vector */public function unserialize( $serialized ){	$data = unserialize( $serialized );	$storage =& $data[ 'storage' ];	if ( $storage instanceOf ArrayObject ){		$this->storage = $storage;	} else {		throw new InvalidArgumentException( 'Dados inválidos.' );	}	return $storage;}}

 

 

Bom, recaptulando, um Vector é uma derivação de AbstractLists que por sua vez deriva de AbstractCollection que é um Object, por consequencia, Vector é também um Object e, assim como ArrayDeque, Vector não é uma abstração e já pode ser utilizado como objeto.

Mas definimos um Vector para definir uma pilha, então vamos defini-la:

 

application/org/util/Stack.php

 

<?php/*** Classes utilitárias para a aplicação* @package		util* @category	oop*/namespace org\util;use org\base\exception\NoSuchElementException;use org\base\Object;/*** Implementação de uma Pilha FILO* @package		util* @category	oop*/class Stack extends Vector {/** * Recupera de forma não destrutiva o elemento do topo da pilha * @return Object */public function peek(){	return $this->lastElement();}/** * Recupera de forma destrutiva o elemento do topo da pilha * @return Object */public function pop(){	$ret = $this->storage->pop();	return $ret;}/** * Adiciona um novo elemento ao topo da pilha * @param Object $o * @return Object */public function push( Object $o ){	$this->add( $o );	return $o;}/** * Retorna a distância do objeto em relação ao topo da pilha * @param Object $o * @return integer */public function search( Object $o ){	$offset = $this->indexOf( $o );	if ( $offset >= 0 ){		return $this->count() - $offset;	} else {		throw new NoSuchElementException( 'O elemento não está na pilha.' );	}}}

 

 

Ai está, temos uma fila(FIFO), um Deque(double ended queue) e uma pilha(FILO), agora vamos demonstrá-los:

 

Para a demonstração, utilizaremos uma interface bem simples de um cliente:

 

application/com/model/Clients.php

 

<?phpnamespace com\model;/*** Interface para definição de um cliente*/interface Clients {/** * Recupera o nome do cliente * @return string */public function getName();}

 

 

E uma implementação de um Clients:

 

application/com/model/SimpleClient.php

 

<?phpnamespace com\model;use org\base\Object;/*** Um cliente qualquer*/final class SimpleClient extends Object implements Clients {/** * Nome do cliente * @var string */private $name;/** * Constroi um novo cliente definindo seu nome * @param string $name O nome do cliente */public function __construct( $name ){	parent::__construct();	$this->name = $name;}/** * Recupera o nome do cliente * @return string */public function getName(){	return $this->name;}}

 

 

Como ocorreu até agora, utilizamos nossa partícula Object para definição do nosso SimpleClient, agora vamos ver 3 tipos de listas, mas antes, a definição da interface dessas listas:

 

application/com/model/ClientLists.php

 

<?phpnamespace com\model;/*** Interface para uma lista de clientes*/interface ClientsLists {/** * Adiciona um cliente * @param Clients $client */public function add( Clients $client );/** * Recupera umm cliente * @return Clients */public function get();}

 

 

Implementando uma lista de clientes como uma FILA:

 

application/com/model/ClientsQueue.php

 

<?phpnamespace com\model;use org\base\Object;use org\base\exception\CastException;use org\util\AbstractQueue;/*** Implementação de uma lista de clientes como uma fila*/class ClientsQueue extends AbstractQueue {/** * Verifica se o objeto é válido * @param Object $o * @return boolean * @throws CastException Se o objeto passado não for uma instância de Clients */protected function isValid( Object $o ){	$reflection = $o->getReflection();	if ( !$reflection->implementsInterface( 'com\model\Clients' ) ){		throw new CastException( sprintf( 'ClientsDeque aceita apenas Clients, %s foi dado.' , $reflection->getName() ) );	}	return true;}}

 

 

Implementando uma lista de clientes como um Deque:

 

application/com/model/ClientsDeque.php

 

<?phpnamespace com\model;use org\base\Object;use org\base\exception\CastException;use org\util\ArrayDeque;/*** Implementação de uma lista de clientes como um Deque*/class ClientsDeque extends ArrayDeque {/** * Verifica se o objeto é válido * @param Object $o * @return boolean * @throws CastException Se o objeto passado não for uma instância de Clients */protected function isValid( Object $o ){	$reflection = $o->getReflection();	if ( !$reflection->implementsInterface( 'com\model\Clients' ) ){		throw new CastException( sprintf( 'ClientsDeque aceita apenas Clients, %s foi dado.' , $reflection->getName() ) );	}	return true;}}

 

 

Implementando uma lista de cliente como uma pilha:

 

application/com/model/ClientsStack.php

 

<?phpnamespace com\model;use org\base\Object;use org\base\exception\CastException;use org\util\Stack;/*** Implementação de uma lista de clientes como uma pilha*/class ClientsStack extends Stack {/** * Verifica se o objeto é válido * @param Object $o * @return boolean * @throws CastException Se o objeto passado não for uma instância de Clients */protected function isValid( Object $o ){	$reflection = $o->getReflection();	if ( !$reflection->implementsInterface( 'com\model\Clients' ) ){		throw new CastException( sprintf( 'ClientsDeque aceita apenas Clients, %s foi dado.' , $reflection->getName() ) );	}	return true;}}

 

 

Bom, para quem leu até aqui e estiver se perguntando: "Porque definimos uma interface ClientsLists ?"

 

Bom, as interfaces de Stack, Queue e Deque são compatíveis apenas até certo ponto, então, precisaremos de alguns adaptadores:

 

Adaptador para Fila:

 

application/com/model/ClientsListsQueueAdapter.php

 

<?phpnamespace com\model;use org\base\Object;use org\base\exception\InvalidArgumentException;use org\util\Queue;/*** Adaptador para uma lista de clientes que utiliza Queue*/class ClientsListsQueueAdapter extends Object implements ClientsLists {/** * @var Queue */private $list;public function __construct( Queue $queue ){	$this->list = $queue;}/** * Adiciona um cliente * @param Clients $client */public function add( Clients $client ){	$this->list->add( $client );}/** * Recupera um cliente * @return Clients */public function get(){	return $this->list->pool();}}

 

 

Adaptador para Deque:

 

application/com/model/ClientsListsDequeAdapter.php

 

<?phpnamespace com\model;use org\base\Object;use org\base\exception\InvalidArgumentException;use org\util\Deque;/*** Adaptador para uma lista de clientes que utiliza Deque*/class ClientsListsDequeAdapter extends Object implements ClientsLists {/** * Usa o Deque como fila */const QUEUE = 1;/** * Usa o Deque como pilha */const STACK = 2;/** * @var Deque */private $list;/** * Ponta que será utilizada * @var integer */private $end = self::QUEUE;public function __construct( Deque $deque , $end = self::QUEUE ){	$this->list = $deque;	switch ( $end ){		case self::QUEUE:		case self::STACK:			$this->end = $end;			break;		default:			throw new InvalidArgumentException( sprintf( 'Era esperado para $end ClientsListsDequeAdapter::QUEUE ou ClientsListsDequeAdapter::STACK, %s foi dado.' , $end ) );	}}/** * Adiciona um cliente * @param Clients $client */public function add( Clients $client ){	$this->list->add( $client );}/** * Recupera um cliente * @return Clients */public function get(){	if ( $this->end == self::QUEUE ){		return $this->list->poolFirst();	} else {		return $this->list->poolLast();	}}}

 

 

Adaptador para Stack:

 

application/com/model/ClientsListsStackAdapter.php

 

<?phpnamespace com\model;use org\base\Object;use org\base\exception\InvalidArgumentException;use org\util\Stack;/*** Adaptador para uma lista de clientes que utiliza Stack*/class ClientsListsStackAdapter extends Object implements ClientsLists {/** * @var Stack */private $list;public function __construct( Stack $stack ){	$this->list = $stack;}/** * Adiciona um cliente * @param Clients $client */public function add( Clients $client ){	$this->list->add( $client );}/** * Recupera um cliente * @return Clients */public function get(){	return $this->list->pop();}}

 

 

Utilizando a fila:

 

<?phpuse com\model\ClientsQueue;use com\model\ClientsListsQueueAdapter;use com\model\SimpleClient;$lista = new ClientsListsQueueAdapter( new ClientsQueue() );$lista->add( new SimpleClient( 'João' ) );$lista->add( new SimpleClient( 'Batista' ) );$lista->add( new SimpleClient( 'Neto' ) );var_dump( $lista->get()->getName() );var_dump( $lista->get()->getName() );var_dump( $lista->get()->getName() );

 

 

Saída:

string(5) "João"

string(7) "Batista"

string(4) "Neto"

 

Utilizando o Deque:

 

<?phpuse com\model\ClientsDeque;use com\model\ClientsListsDequeAdapter;use com\model\SimpleClient;$lista = new ClientsListsDequeAdapter( new ClientsDeque() );$lista->add( new SimpleClient( 'João' ) );$lista->add( new SimpleClient( 'Batista' ) );$lista->add( new SimpleClient( 'Neto' ) );var_dump( $lista->get()->getName() );var_dump( $lista->get()->getName() );var_dump( $lista->get()->getName() );

 

 

Saída:

string(5) "João"

string(7) "Batista"

string(4) "Neto"

 

Como no Deque podemos usar as duas pontas:

 

 

<?phpuse com\model\ClientsDeque;use com\model\ClientsListsDequeAdapter;use com\model\SimpleClient;$lista = new ClientsListsDequeAdapter( new ClientsDeque() , ClientsListsDequeAdapter::STACK );$lista->add( new SimpleClient( 'João' ) );$lista->add( new SimpleClient( 'Batista' ) );$lista->add( new SimpleClient( 'Neto' ) );var_dump( $lista->get()->getName() );var_dump( $lista->get()->getName() );var_dump( $lista->get()->getName() );

 

 

Saída:

string(4) "Neto"

string(7) "Batista"

string(5) "João"

 

Usando a pilha:

 

<?phpuse com\model\ClientsStack;use com\model\ClientsListsStackAdapter;use com\model\SimpleClient;$lista = new ClientsListsStackAdapter( new ClientsStack() );$lista->add( new SimpleClient( 'João' ) );$lista->add( new SimpleClient( 'Batista' ) );$lista->add( new SimpleClient( 'Neto' ) );var_dump( $lista->get()->getName() );var_dump( $lista->get()->getName() );var_dump( $lista->get()->getName() );

 

 

Saída:

string(4) "Neto"

string(7) "Batista"

string(5) "João"

 

[Bruno Augusto 417]

:o

 

Esse sim foi um Sr. Tópico. Mas não seria melhor quebrá-lo, dividindo-o no básico, um para cada "tipo" (FIFO, FILO, DEQue) e outro para o exemplo de uso?

 

Botãozinho de "editar" sem vergonha <_<

 

Espero que as dúvidas do artigo possam ser tratadas aqui mesmo, ao invés de ter um tópico separado.

 

Como todos os tipos estão juntos acabei me perdendo. Tentei implementar para ajudar nesse problema e não consegui.

 

Os exemplos demonstram bem Queue, Deck e Stack, mas pelo que compreendi eu preciso de um nível mais básico, o Set, para não duplicar os objetos.

 

Tentei assim:

 

public function clean( array $data, array $exclude = array() ) {

       $set = new FilterSet();

       $chain = array( new Zend_Filter_StringTrim(),
                       new Zend_Filter_StripTags(),
                       new Zend_Filter_StripNewlines(),
                       new Zend_Filter_HtmlEntities(),
                       new Zend_Filter_HtmlEntities(), new Zend_Filter_StringTrim() );

       foreach( $chain as $object ) {

           $set -> add( new SimpleFilter( $object ) );
       }

       print '<pre>'; print_r( $set ); exit;
   }

Por enquanto não usei os parâmetros.

 

Meu FilterSet eu fiz como ClientsQueue, só que extendi AbstractSet e renomeei a interface requerida e meu SimpleFilter ficou como SimpleClient, só que as variáveis renomeadas para refletir o tema "filtros".

 

Teste e funcionou a adição dos filtros. Mas quando coloqueium duplicado, ele foi adicionado do mesmo jeito.

 

P.S.: Podem excluir o post anterior?

[João Batista Neto 448]

O AbstractSet utiliza o método contains() da Collection que, para verificar se um objeto existe, utiliza o hash do objeto.

 

A questão é que esse hash é diferente para cada instância, afinal, cada uma é tratada diferentemente na memória, veja uma ilustração:

 

<?php
class Teste {
}

$a = new Teste();
$b = new Teste();

var_dump( spl_object_hash( $a ) , spl_object_hash( $b ) );

 

A saída será:

string(32) "0000000011bafb6000000000642e2f4b"

string(32) "0000000011bafb6300000000642e2f4b"

 

Ou seja, duas instâncias de dois objetos são de fato diferentes, mesmo que sejam do mesmo tipo.

 

Para se ter o mesmo resultado você precisaria passar o mesmo objeto duas vezes:

 

<?php
class Teste {
}

$a = new Teste();

var_dump( spl_object_hash( $a ) , spl_object_hash( $a ) );

 

Cuja saída seria:

string(32) "000000001618ce5c000000006cbe001d"

string(32) "000000001618ce5c000000006cbe001d"

 

Para resolver o problema, você precisará sobrescrever o método hashCode() da Object para que você tenha um método diferente para criar os hashes:

<?php
namespace com\zend;

use org\base\Object;
use org\util\AbstractSet;

interface Filter {
}

class Zend_Filter_StringTrim {
}
class Zend_Filter_StripTags {
}
class Zend_Filter_StripNewlines {
}
class Zend_Filter_HtmlEntities {
}

class FilterAdapter extends Object implements Filter {
private $filter;

public function __construct( $filter ){
	$this->filter = $filter;
}

/**
 * Sobrescrevemos o método Object::hashCode() para que tenhamos o comportamento esperado
 * @return string
 */
public function hashCode(){
	return base_convert( md5( get_class( $this->filter ) ) , 16 , 10 );
}
}

class FilterSet extends AbstractSet {
/**
 * Verifica se o objeto é válido
 * @param Object $o
 * @return boolean
 * @throws CastException Se o objeto passado não for uma instância de Clients
 */
protected function isValid( Object $o ){
	$reflection = $o->getReflection();

	if ( !$reflection->implementsInterface( 'com\zend\Filter' ) ){
		throw new CastException( sprintf( 'FilterSet aceita apenas Filter, %s foi dado.' , $reflection->getName() ) );
	} else {
		return parent::isValid( $o );
	}

}
}

 

Agora, o comportamento será o esperado pelo Set:

 

<?php
use org\base\exception\LogicException;
use com\zend\FilterSet;
use com\zend\FilterAdapter;
use com\zend\Zend_Filter_StringTrim;
use com\zend\Zend_Filter_StripTags;
use com\zend\Zend_Filter_StripNewlines;
use com\zend\Zend_Filter_HtmlEntities;

$chain = array( new Zend_Filter_StringTrim(),
	new Zend_Filter_StripTags(),
	new Zend_Filter_StripNewlines(),
	new Zend_Filter_HtmlEntities(),
	new Zend_Filter_HtmlEntities(), new Zend_Filter_StringTrim() );

$filters = new FilterSet();

foreach ( $chain as $filter ){
try {
	$filters->add( new FilterAdapter( $filter ) );
} catch ( LogicException $e ){
	echo 'O filtro[ ' , get_class( $filter ) , '] não foi adicionado porque já estava no Set' , PHP_EOL;
}
}

 

E a saída será:

O filtro[ com\zend\Zend_Filter_HtmlEntities] não foi adicionado porque já estava no Set

O filtro[ com\zend\Zend_Filter_StringTrim] não foi adicionado porque já estava no Set

 

;)

[Jackson Dias 68]

O conteúdo é muito bom João.

Como já tenho falado por MSN você é um mestre no PHP.

Parabéns pela contribuição.

[Bruno Augusto 417]

Hmmm...

 

Não foi bem isso que retornou, ou, se foi, eu pensava que seria diferente.

 

Se eu não duplicar propositalmente, tudo certo. Se eu duplicar:

 

Uncaught exception 'rpo\base\exception\LogicException' with message 'O elemento FilterAdapter@320076454395377206242606088424444406260 j� existe na lista.

E a operação é abortada.

 

Tentei "anular" o catch(), deixando-o vazio, mas também nada.

 

Daí eu reverti a modificação de FilterSet, que retorna o isValid() de AbsractList, ao estado "original", só retornando TRUE.

 

Parou de ser abortado, porém permitiu duplicação.

[WellingtonSG 0]

Olá João Batista Neto, Parabéns pelo tópico.

 

E se eu quiser adicionar mais elementos? Como endereço, CEP, idade...

 

Amigo Poderia colocar os arquivos em um rar?

 

 

 

Att;

[João Batista Neto 448]

Se eu não duplicar propositalmente, tudo certo. Se eu duplicar:

 

Não compreendi isso, você precisará explicar melhor o que ocorre.

 

Daí eu reverti a modificação de FilterSet, que retorna o isValid() de AbsractList, ao estado "original", só retornando TRUE.

 

Set não retorna apenas TRUE, ele usa o método Collection::contains() e só e somente só se o objeto que está sendo adicionado não estiver contido na lista que retornará TRUE, do contrário uma exceção é disparada.

 

Olá João Batista Neto, Parabéns pelo tópico.

 

;)

 

E se eu quiser adicionar mais elementos? Como endereço, CEP, idade...

 

Isso é simples, a interface Clients é o contrato que as classes que a implementem deverão possuir, para adicionar outras propriedades e seus respectivos getters, basta que você adapte a interface a sua necessidade, o fato é que a interface Cliente foi realmente construída para ser o mais simples possível, visando única e exclusivamente a ilustração de todo esse código. Você deverá construir suas próprias interfaces e objetos que as implementam se quiser utilizar esse código em produção.

 

Um exemplo de como ficaria:

 

application/com/model/Clients.php

<?php
namespace com\model;

/**
* Interface para definição de um cliente
*/
interface Clients {
/**
 * Recupera o endereço do cliente
 * @return string
 */
public function getAddress();

/**
 * Recupera o nome do cliente
 * @return string
 */
public function getName();

/**
 * Recupera o CEP do cliente
 * @return string
 */
public function getZip();
}

 

E agora uma implementação:

 

application/com/model/SimpleClient.php

<?php
namespace com\model;

use org\base\Object;

/**
* Um cliente qualquer
*/
final class SimpleClient extends Object implements Clients {
/**
 * Endereço do cliente
 * @var string
 */
private $address;

/**
 * Nome do cliente
 * @var string
 */
private $name;

/**
 * CEP do cliente
 * @var string
 */
private $zip;

/**
 * Constroi um novo cliente definindo seu nome
 * @param string $name O nome do cliente
 */
public function __construct( $name , $address , $zip ){
	parent::__construct();

	$this->address = $address;
	$this->name = $name;
	$this->zip = preg_replace( '/[^\d]/' , null , $zip );
}

/**
 * Recupera o endereço do cliente
 * @return string
 */
public function getAddress(){
	return $this->address;
}

/**
 * Recupera o nome do cliente
 * @return string
 */
public function getName(){
	return $this->name;
}

/**
 * Recupera o CEP do cliente
 * @return string
 */
public function getZip(){
	return vsprintf( '%02d.%03d-%03d' , sscanf( $this->zip , '%2d%3d%3d' ) );
}
}

 

O resto é exatamente a mesma coisa.

 

;)

[Bruno Augusto 417]

 

Se eu não duplicar propositalmente, tudo certo. Se eu duplicar:

 

Não compreendi isso, você precisará explicar melhor o que ocorre.

 

Se eu propositalmente não adicionar objetos duplicados na cadeia $chain funciona. Mas a intenção de utilizar um Set para resolver o problema do link passado é considerar a possibilidade de exclusão de filtros da cadeia, já que o ZF não tem um removeFilter()

 

 

Daí eu reverti a modificação de FilterSet, que retorna o isValid() de AbsractList, ao estado "original", só retornando TRUE.

 

Set não retorna apenas TRUE, ele usa o método Collection::contains() e só e somente só se o objeto que está sendo adicionado não estiver contido na lista que retornará TRUE, do contrário uma exceção é disparada.

 

Bom eu só "reverti" pois construi o FilterAdapter, me baseando no SimpleClient sob AbstractQueue.

 

Esse tipo comportamento diferenciado entre Set e Queue poderia ser mencionado ^^

Pelo menos demonstrando que aquele else deveria existir chamando o parent::isValid()

 

Mas se vai abortar por já existir, então não tem jeito? Pelo visto ao invés de considerar exclusão da cadeia, terei de fazer inclusão nela. É mais trabalhoso para usuário, já que terá de saber os nomes dos filtros, mas pelo menos...

[João Batista Neto 448]

já que o ZF não tem um removeFilter()

já olhou o método Collection::remove( Object )???

 

Talvez seja o que você procura.

 

Utilizando em conjunto com o método Collection::contains( Object ) você pode remover os objetos duplicados.

 

Esse tipo comportamento diferenciado entre Set e Queue poderia ser mencionado ^^

 

Mas foi mencionado:

Além da Collection, vamos definir uma outra interface um pouco parecida, mas conceitualmente totalmente diferente, a interface Set. Um Set, assim como uma Collection é uma coleção de objetos, a diferença principal é que, conceitualmente, um Set jamais permite elementos duplicados.

 

Como Queue deriva de Collection, uma Queue é uma Collection por definição, consequentemente, uma Queue permite elementos duplicados.

[Bruno Augusto 417]

Mencionado com exemplos, porque as vezes demoro pra pegar no tranco ^^

 

Bom, vou ver o que posso fazer aqui, utilizando mais o conceito do artigo do que os códigos dele e fazer algo mais certo.

 

Vindo de você, isso é algum Design Pattern? Se sim, tem nome? Ou Collection, Set e etc já é nome dele?

 

[ Ponto de Mesclagem ]

 

Reescrevi classe por classe, para poder realmente entender e, consequentemente, acabei modificando algumas coisas.

 

A primeira foi a não adição de vários métodos não requeridos pelas interfaces nativas, que existiam para auxiliar algumas tarefas.

 

A segunda, foi remover contratos da interface Collection, mantendo apenas os essenciais, pelo menos para as minhas coleções :P

 

A terceira foi modificar o comportamento do isValid em AbstractSet, para não disparar uma exceção e sim, apenas retornar FALSE, para que a adição do filtro à cadeia seja negada sem abortar o procedimento.

 

Considerados esses pontos, a utilização do Set ficou:

 

    public function clean( array $data, array $exclude = array() ) {

       // Supported Filters

       $chain = array( 'StringTrim'      => new Zend_Filter_StringTrim(),
                       'StripTags'       => new Zend_Filter_StripTags(),
                       'StripNewLines'   => new Zend_Filter_StripNewlines(),
                       'HtmlEntities'    => new Zend_Filter_HtmlEntities() );

       // Looping through input array

       foreach( $data as $field => $value ) {

        $filters[ $field ] = new FilterSet;

        // Looping through supported filters, creating the Filters Chain

        foreach( $chain as $name => $filter ) {

                   if( ! isset( $exclude[ $field ] ) ||
                       ( isset( $exclude[ $field ] ) && ! in_array( $name, $exclude[ $field ] ) ) ) {

                       $filters[ $field ] -> add( new Filter( $filter ) );
                   }
        }

        // Looping through Filter Collection

        foreach( $filters[ $field ] -> getIterator() as $item ) {

           if( is_array( $value ) ) {

               $data[ $field ] = $this -> clean( $value );

           } else {
               $data[ $field ] = $item -> getFilter() -> filter( $value );
           }
        }
       }

       return $data;
   }

Funcionou perfeitamente, solucionando o problema da recursividade. Se o filtro estiver marcado para não ser adicionado, ele realmente não será adicionado, mesmo na recursividade.

 

Entretanto, observei um comportamento indesejado que só ocorreu após agregar os Zend_Filter's à um Set.

 

Mesmo que $chain possua uma ordem específica e o foreach que opera sobre ele respeite essa ordem, quando invoco getFilter() a partir do iterador, para poder acessar o método filter() dos filtros,o Zend_Filter_HtmlEntities que deve ser OU o último a ser aplicado OU vir depois de Zend_Filter_StripTags passou a vir antes.

 

Na prática isso faz com que uma tag HTML que deveria ser REMOVIDA por Zend_Filter_StripTags, de fato não está, pois o filtro está recebndo astags codificadas em suas respectivas entidades por Zend_Filter_HtmlEntities, fazendo com que:

 

<script>alert('oi');</script>

Me retorne:

 

<script>alert('oi');</script>

Com isso fica a pergunta? O Set está de alguma forma invertendo a ordem do array onde os filtros são adicionados?

[João Batista Neto 448]

Com isso fica a pergunta? O Set está de alguma forma invertendo a ordem do array onde os filtros são adicionados?

 

Sim, é possível, o Set não tem a responsabilidade de manter a ordem de entrada.

 

Agora, como você modificou vários comportamentos, não tenho mais como ajudá-lo, já que não conheço mais o código.

 

;)

[Bruno Augusto 417]

Mudar, mudar mesmo, só mudei o AbstractSet.

 

De resto continua igual, eu apenas removi os métodos que, pra mim, não tinham utilidade, deixando apenas estritamente os métodos de contrato das interfaces implementadas nos códigos do artigo.

 

Mas mesmo assim, eis os códigos "novos" (namespaces removidos)

 

Ah! Outra coisa que mudei e havia esquecido. Adicionei Fluent Interfaces add() e remove() de AbstractCollection, mas mesmo que apenas retornasse TRUE como antes, o impasse persiste, logo o recurso continua válido.

[Bruno Augusto 417]

Posso mudar de assunto? Minhas perguntas acima podem ser desconsideradas <_<

 

Em eu tendo um storage da AbstractCollection e mãos, posso fazer:

 

$collection -> getIterator() -> offsetGet( 9 ) -> metodo();

E funciona pois eu uso o método metodo() da classe presente no nono índice.

 

Mas isso é muito fixo pois, se outra pessoa da Equipe (em formação) for usar e, por acidente, inverter a ordem a que os objeto são adicionados à Collection, vai dar pau xD

 

Seria possível sem "desmanchar" o conceito da Collection permitir que o add() dela, crie uma estrutura tanto de índices numéricos como em strings?

 

Eu arriscaria fazer alterando o add() da AbstractCollection, e consequentemente, o append() da ArrayObject. Mas, como disse, não sei se isso "desmancha" o conceito da Collection.

 

Sem isso teria que fazer, na classe que extende AbstractCollection, loop dentro de loop, comparação sobre comparação para fazer algo que, por exemplo, um $k em um foreach sobre $collection -> getIterator(), resolveria.

 

Outra solução, mais elegante acredito eu, seria a possibilidade de buscar um objeto dentro de uma coleção, retornando o índice em que se encontra no storage.

 

Eu fiz algo aqui mas... confesso que chutei:

 

public function appendAttributes( Unit $unit ) {

   $iterator = $unit -> getIterator();

   foreach( $iterator as $offset => $u ) {

       foreach( $this -> getIterator() as $equipment ) {

           if( $equipment -> equals( $u ) ) {

               $current = $iterator -> offsetGet( $offset ) -> get();

               $iterator -> offsetGet( $offset ) -> set( $current + $equipment -> get() );

           } else {

               $unit -> add( $equipment );
           }
       }
   }
}

Recebo uma Unidade, determinada pela interface Unit

 

Percorro a Collection dessa unidade e a Collection daquilo que será "pendurado" à ela.

 

Se algum desses objetos já existir na Unidade, obtenho o valor da única propriedade dele, através do meu método get(), na classe abstrata de atributos e, a partir da Unidade e redefino seu valor, acrescentando à ela o valor desse objeto novo.

 

Se não existir, adiciono ele à Collection.

 

Certo?

[João Batista Neto 448]

buscar um objeto dentro de uma coleção, retornando o índice

Veja a interface Lists, método indexOf e lastIndexOf

[Bruno Augusto 417]

http://forum.imasters.com.br/public/style_emoticons/default/clap.gif

 

Certinho, agora minha Unit derivando de Vector, já que direto com AbstractLists dá erro de ausência do método listIterator(), consigo pegar o valor com um loop a menos:

 

$current = $unit -> get( $unit -> indexOf( $equipment ) ) -> get();

O primeiro get() é da List, o segundo é da minha classe abstrata de atributos.

 

Mas...

 

Eu tentei atualizar o objeto do índice obtido com indexOf() através do set(), mas não consegui nada.

 

Fui olhar o método e ele não tem nada que de fato modifique, apenas faz duas verificações (que, aliás, não entendi porque a Exception foi disparada quando isValid() fosse verdadeiro).

 

E offsetSet() invoca o próprio set(), que não faz "nada".

 

Então, o que eu fiz? Através do meu set(), da classe abstrata de Atributos, alterei o valor da propriedade devida e substitui o objeto do atributo a partir da Unit.

 

Mas isso não é certo é?

 

Hmmmm... Tentando aqui, acho que descobri porque o set() da Vector não funciona. Foi tirar a instrução de dentro do bloco IF com isValid(), que funcionou.

 

Não sei se realmente não faz sentido mas acompnhe:

 

- O isValid() da Vector retorna TRUE.

- Para funcionar eu tirei a instrução desse IF do isValid() (comentando) logo, executou como se o Objeto passado fosse verdadeiro, já que nada definiu isso como FALSE.

- Com isso, o TRUE do isValid() não deveria forçar a continuação, como um TRUE "invisível" gerado pela ausência de um FALSE?

 

E mais, de onde veio $this->limit?

 

Porque ele só está definido se $offset for NULL e, se for informado manualmente um NULL para set() é disparada a InvalidArgumentException de AbstractLists::boundsCheck()

 

Se for informado um zero, para que passasse pela boundCheck() e, talvez, o tal cast burro considerasse como nulo, $this->limit ainda assim não existe.

 

Em suma, tirei o isValid() ( :D ) e deu certo, mas será isso um erro?

 

P.S.: Ficou assim:

 

public function set( $offset, Object $o ){

   try {

       if( $this -> boundsCheck( $offset ) ) {
           $this->storage[ $offset ] = $o;
       }

   } catch( UndefinedIndexException $e ) {}
}