Referência da Template de Classe persistence::deque3::Deque< T >

Descrição Detalhada

template<class T>
class persistence::deque3::Deque< T >

Deque persistente de Kaplan e Tarjan.

Uma deque é uma lista que permite adições e remoções em suas duas pontas. Implementamos aqui uma deque persistente que também permite acesso ao k-ésimo elemento. Esta utiliza uma tecnica descrita por Kaplan e Tarjan [2] .

A deque armazena elementos do tipo T, e só assume que esse tipo tem um construtor de cópia. Uma diferença do código discutido no Capítulo 5 da tese é que aqui as funções não recebem a deque, mas são métodos desta. Além disso, as funções Pop não retornam o objeto removido, apenas a nova deque.

O objeto é imutável, e como a implementação é funcional, podemos usá-la de forma persistente, como no seguinte exemplo:

using namespace deque3;
Deque<int> d1; // ()
Deque<int> d2 = d1.PushFront(1); // (1)
Deque<int> d3 = d2.PushFront(2); // (2, 1)
Deque<int> d4 = d3.PushBack(0); // (2, 1, 0)
Deque<int> d5 = d2.PopBack(); // (2)
d4.Front(); // retorna 2
d4.Back(); // retorna 0
d4.K_th(1); // retorna 1

Métodos Públicos
	Deque ()
	Construtor vazio. Mais...
	Deque (const Deque &o)
Deque &	operator= (const Deque &o)

Campos de Dados
Node *	node
	Nó principal. Mais...

Funções auxiliares
Estas funções, detalhadas no Capítulo 5, são utilizadas pelas funções internas da deque.
void	Check (Node *a)
	Checa e restaura a regularidade. Mais...
Node *	Copy (const Node *a)
	Cópia de nó. Mais...
int	Digit (const Node *a, bool last)
	Dígito do nível a. Mais...
void	Fix (Node *a)
	Transforma uma estrutura semi-regular em regular. Mais...
void	FixDeques (SubDeque< any * > &l, SubDeque< any * > &r, SubDeque< any * > &L, SubDeque< any * > &R)
	Balanceia as sub-deques l e r. Mais...

Operações de Acesso
const T &	Front () const
	Acesso ao primeiro elemento. Mais...
const T &	Back () const
	Acesso ao último elemento. Mais...
const T &	K_th (int k) const
	Acesso ao k-ésimo elemento. Mais...

Operações de Modificação
Estas funções retornam uma cópia modificada da deque, e não alteram o objeto na qual são chamadas.
Deque< T >	PushFront (const T &x) const
	Inserção no início. Mais...
Deque< T >	PushBack (const T &x) const
	Inserção no final. Mais...
Deque< T >	PopFront () const
	Remoção do início. Mais...
Deque< T >	PopBack () const
	Remoção do final. Mais...

Construtores & Destrutores

template<class T>

persistence::deque3::Deque< T >::Deque

(

)

Construtor vazio.

Constrói uma deque sem nenhum elemento.

Métodos

template<class T>

const T& persistence::deque3::Deque< T >::Back

(

)

const

Acesso ao último elemento.

Retorna

O valor do último elemento da deque.

Pré-Condição

A deque não deve estar vazia.

template<class T>

const T& persistence::deque3::Deque< T >::Front

(

)

const

Acesso ao primeiro elemento.

Retorna

O valor do primeiro elemento da deque.

Pré-Condição

A deque não deve estar vazia.

template<class T>

const T& persistence::deque3::Deque< T >::K_th

(

int

k

)

const

Acesso ao k-ésimo elemento.

Parâmetros

k	O índice do elemento desejado. 0 é o primeiro elemento.

Retorna

O valor do k-ésimo elemento da deque.

Pré-Condição

0 ≤ k < n, onde n é o tamanho da deque.

template<class T>

Deque<T> persistence::deque3::Deque< T >::PopBack

(

)

const

Remoção do final.

Retorna

Uma cópia da deque, mas sem seu último elemento.

Pré-Condição

A deque não deve estar vazia.

template<class T>

Deque<T> persistence::deque3::Deque< T >::PopFront

(

)

const

Remoção do início.

Retorna

Uma cópia da deque, mas sem seu primeiro elemento.

Pré-Condição

A deque não deve estar vazia.

template<class T>

Deque<T> persistence::deque3::Deque< T >::PushBack

(

const T &

x

)

const

Inserção no final.

Parâmetros

x	Valor a ser adicionado no final da deque.

Retorna

Uma cópia da deque, mas com x como último elemento.

template<class T>

Deque<T> persistence::deque3::Deque< T >::PushFront

(

const T &

x

)

const

Inserção no início.

Parâmetros

x	Valor a ser adicionado no início da deque.

Retorna

Uma cópia da deque, mas com x como primeiro elemento.

Amigas e Funções Relacionadas

template<class T>

void Check ( Node *  a )

related

Checa e restaura a regularidade.

Checa se a estrutura é regular, se não for, chama Fix para a tornar regular novamente.

Parâmetros

a	Nó raiz da deque.

Aviso

Essa função deve ser chamada com uma cópia do nó, já que ela modifica a.

template<class T>

Node * Copy ( const Node *  a )

related

Cópia de nó.

Retorna uma cópia do nó, ou um novo nó vazio se a é nulo.

Parâmetros

a	Nó a ser copiado

Retorna

Cópia de a.

template<class T>

int Digit ( const Node *  a, bool  last  )

related

Dígito do nível a.

Parâmetros

a	Nível cujo dígito é retornado.
last	Booleano indicando se este é o último nível.

Retorna

Dígitio do nó a.

template<class T>

void Fix ( Node *  a )

related

Transforma uma estrutura semi-regular em regular.

Parâmetros

a	Primeiro nó com dígito 2.

Aviso

Essa função deve ser chamada com uma cópia do nó, já que ela modifica a.

template<class T>

void FixDeques ( SubDeque< any * > &  l, SubDeque< any * > &  r, SubDeque< any * > &  L, SubDeque< any * > &  R  )

related

Balanceia as sub-deques l e r.

Dado que l e são sub-deques do primeiro nível com dígito 2 e a estrutura é semi-regular, esse procedimento transforma o dígito do nível em 0, aumentando o do próximo em nó máximo 1, ou esvaziando este nível.

Parâmetros

l,r	Sub-deques de um nível i.
L,R	Sub-deques do nível i+1.

Pré-Condição

Devem existir mais de 3 elementos de nível i entre todas as sub-deques, ou seja, l.size() + r.size() + 2*L.size() + 2*R.size() > 3.

Campos

template<class T>

Node* persistence::deque3::Deque< T >::node

Nó principal.

Este é o nó que representa a deque inteira.

Veja também

Node para saber a razão desta classe não ter o tipo T .

---

A documentação para esta classe foi gerada a partir do seguinte arquivo:

• /home/travis/build/yancouto/mestrado/source/persistence/Deque3.hpp