A evolução de enumeradores C#
Introdução
Outro dia precisei de uma estrutura de dados em árvore. Infelizmente, o C#/.NET não fornece uma, então implementei uma simples. A necessidade era criar uma hierarquia de pastas a partir de uma estrutura simples de dados, na qual cada nó contivesse sua id, e sua id paterna. A lista não estava particularmente ordenada, nem em profundidade ou amplitude. Contudo, nós pais sempre antecediam nós filhos, de forma que quando um nó fosse adicionado à árvore, era garantido que o nó pai já estivesse lá.
Essa não era a parte importante do exercício. A principal coisa que eu queria fazer era realizar uma primeira busca em profundidade mostrando o conteúdo recortado do nó, apontando a profundidade com que ele ocorre na árvore.
Uma vez que isso foi escrito em C# e .NET, espera-se que as coleções suportem a interface IEnumerable. Eu não queria apenas implementar uma árvore walker básica, mas fazer isso de forma que estivesse em conformidade com o paradigma .NET. Como já tem um tempo que implementei uma árvore e esta é a primeira em vez que uso enumeradores C#2.0, acabei tendo que fazer 3 iterações de enumeradores até chegar ao que julgo um enumerador de estilo .NET apropriado. Este artigo descreve esta evolução.
Note, por favor, que a segurança não é considerada, e pouca atenção foi dada a erros ou a condições inválidas.
O código a seguir mostra a implementação mínima da barra da árvore de qualquer código de enumeração.
class Node
{
public static Node MakeRoot()
{
return new Node(0);
}
private Node(int id) { id_ = id; }
public bool Add(int id, int parentId)
{
if (parentId == id_)
{
children_.Add(new Node(id));
return true;
}
else
{
foreach (Node child in children_)
if (child.Add(id, parentId) == true)
return true;
return false;
}
}
public int Id { get { return id_; } }
private int id_ = -1;
ArrayList children_ = new ArrayList();
}
O programa principal carrega apenas uma árvore simples.
Node root = Node.MakeRoot();
root.Add(1, 0);
root.Add(2, 0);
root.Add(3, 0);
root.Add(11, 1);
root.Add(12, 1);
root.Add(13, 1);
root.Add(121, 12);
root.Add(122, 12);
root.Add(1211, 121);
root.Add(12111, 1211);
A abordagem C
Fazer uma pesquisa inicial em profundidade não é difícil. A forma mais fácil de implementá-la é usando recursão. Abaixo, uma rápida implementação que provou que a árvore estava funcionando perfeitamente.
Note que isso é um membro da classe Node.
public void Walk(int level)
{
for (int i = 0; i < level; ++i)
Console.Write("t");
Console.WriteLine(id_);
foreach (Node node in children_)
node.Walk(level + 1);
}
Essa implementação é a forma como uma árvore teria entrado na era da programação em C. No mundo OO e .NET. isso tem alguns problemas:
- Quebra a encapsulação como código de aplicação, ou seja, o código da exibição é misturado com o da estrutura de dados. O uso do código C puro poderia ser ajustado fazendo com que o método usasse um marcador de função como um argumento que seria solicitado para cada nó para exibir o nó. No C++, isso poderia ser melhorado com o uso de um functor, ou implementando o todo como um iterador STL compatível.
- O método é executado até o final, ou seja, não é possível obter um item da árvore e executar alguma ação sobre ele e então recuperar o próximo item, ou abandonar o processamento completo. No entanto, o método poderia ser estendido para fornecer um mecanismo para interrupção antecipada, dependendo do valor de retorno do método invocado.
- Coleções NET 2.0 devem implementar a interface IEnumerable, o que significa que elas devem fornecer um IEnumertor GetEnumerator (). Isso permite que a coleção possa ser usada por qualquer entidade .NET que reconheça a enumeração de interfaces padrão, em particular a palavra-chave foreach, que é reconhecida como o melhor mecanismo para enumerar uma coleção.
A abordagem C# 1.0
Esses problemas podem ser resolvidos através da aplicação da árvore walker como um enumerador. A principal dificuldade para fazer isso é que um enumerador é uma operação iterativa, o que significa que uma chamada é feita em separado para avançar as iterações, enquanto que a árvore walker é chamada uma vez e só retorna quando a passagem foi concluída.
Um enumerador para estruturas de dados que estão aptos a atravessamentos recursivos pode ser implementado utilizando várias técnicas. Primeiramente, na chamada inicial, o enumerador pode percorrer a árvore de forma recursiva e construir uma estrutura de dados linear que é ideal para iteração, ou seja, criar uma lista de primeira passagem em profundidade, cujos membros referenciem os nós reais da árvore e depois façam a iteração com os demais membros da lista.
O método que escolhi foi copiar a recursão mantendo o contexto no enumerador, que mediante a chamada seguinte o levaria para o lugar de onde veio. O enumerador é implementado em uma classe separada que pode manter o estado e, conforme o padrão do iterador, permitir a coexistência de múltiplas instâncias.
O código a seguir mostra a implementação, mas note que, mesmo não explicitamente mostrado, esta é uma nested class, de forma que tem acesso aos membros privados dos Nodes e não é visível ao caller que trabalha somente na interface IEnumerator. É essa interface que requer a implementação de MoveNext(), Current & Reset().
class WalkNode : IEnumerator
{
public WalkNode(Node root)
{
root_ = root;
}
bool IEnumerator.MoveNext()
{
if (current_ == null)
{
current_ = root_;
activeIts_.Push(root_.children_.GetEnumerator());
return true;
}
else
{
while (activeIts_.Count > 0)
{
IEnumerator it = (IEnumerator)activeIts_.Pop();
if (it.MoveNext() == true)
{
current_ = (Node)it.Current;
activeIts_.Push(it);
activeIts_.Push(current_.children_.GetEnumerator());
return true;
}
}
return false;
}
}
object IEnumerator.Current
{
get
{
// Need to handle invalid current_
return new NodeAndLevel(current_, activeIts_.Count - 1);
}
}
void IEnumerator.Reset() { current_ = null; activeIts_.Clear(); }
Node root_;
Node current_;
Stack activeIts_ = new Stack();
}
A coisa interessante acontece no MoveNext (). Ele é chamado para avançar o enumerador e deve ser chamado para definir o enumerador para o primeiro item antes de utilizar o seu valor, ou seja, chamando a propriedade Current.
Na primeira chamada, o nó corrente é definido como o nó raiz. Isso significa que se a propriedade Current é chamada, o nó raiz será retornado. Em segundo lugar, ela define o enumerador para a chamada seguinte, pela obtenção um enumerador para os nós raiz filhos, e empurrando-o para uma pilha armazenada no enumerador. É essa pilha que efetivamente imita a recursividade, mantendo o enumerador para o nó atual e para aqueles no ramo acima em cada chamada, e assim mantendo a referência para o próximo nó a ser visitado, e para qual retornar quando não houver mais filhos.
Na próxima (nó não-raiz) chamada e nas chamadas subsequentes, um teste é feito para ver se a pilha contém algum item. Caso não tenha, isso significa que não há mais nós a visitar e que a árvore foi totalmente atravessada. Quando chamada pela segunda vez, a pilha conterá o enumerador para os nós raiz de filhos. Devido à natureza da classe Node, um nó sempre será capaz de prover um enumerador mesmo se não houver filhos, mas a primeira chamada para MoveNext() retornará falsa, indicando o fim dos filhos, ou seja, nenhum. Se a raiz não tiver filhos, o enumerador (para seus filhos) obtido da pilha retornará falso, a contagem da pilha será zero, o loop terminará e o MoveNext() principal retornará falso, indicando o fim do atravessamento. Isto também acontecerá quando o atravessamento tiver sido feito para todos os filhos da raiz.
O outro caso é quando a raiz tem filhos, e a chamada interna para MoveNext(), usando o enumerador da pilha, retornará verdadeira, situação em que o membro variável corrente usado para implementar a propriedade Current será definido para o nó filho obtido da propriedade Current do enumerador interno. Como essa é uma primeira pesquisa em profundidade, o próximo nó a ser atravessado deve ser o primeiro filho desse nó, de forma que o enumerador atual seja empurrado para a pilha juntamente com o enumerador interno recentemente obtido para o nó do filho atual, de forma que na próxima chamada seus filhos sejam enumerados. Verdadeiro é então retornado.
No caso da parte inferior de uma ramificação ser alcançada, a chamada interna para MoveNext() do enumerador recém-exibido retornará falso. Como a pilha ainda contém os enumeradores pais, o loop não terminará, diferentemente do caso de um nó raiz sem filhos, ou tendo sido atravessado até o fim. Isso resulta em o enumerador do nó pai se transforma no enumerador atual, permitindo que o próximo filho seja atravessado, se houver um. Isso continua até que a pilha seja exibida, de forma que o enumerador interno atual seja aquele do nó raiz. Se ele contiver mais filhos, cada um desses nós é atravessado em profundidade até que não haja mais filhos, fazendo o loop terminar, já que a pilha está vazia e finalmente retornando falso, indicando o fim do atravessamento.
A desvantagem da abordagem imitativa é o número de enumeradores internos que são mantidos ativos na pilha à medida que atravessam filhos em níveis mais profundos. Se o ponto mais profundo da árvore tiver 100 nós de profundidade, então requererá que 100 enumeradores ativos internos estejam na pilha. O enumerador mais profundo, de número 100, corresponderá ao nó final e não apresentará filhos.
Em vez de retornar a referência para um nó, uma instância de um tipo de invólucro (wraper) é retornado, o que permite o fornecimento do próximo nível de informação. A definição disso é mostrada abaixo.
class NodeAndLevel
{
public NodeAndLevel(Node node, int level)
{
node_ = node;
level_ = level;
}
public Node Contents { get { return node_; } }
public int Level { get { return level_; } }
readonly Node node_;
readonly int level_;
}
A outra modificação é que o Node implementa a interface IEnumerable, o que significa que ela deve implementar o método GetEnumerator(), o que ela realmente faz. Isso cria uma instância do enumerador WalkNode que acabamos de discutir, como pode ser visto abaixo:
IEnumerator IEnumerable.GetEnumerator()
{
return new WalkNode(this);
}
A abordagem C# 2.0
A versão 2.0 do C# adicionou suporte de linguagem para fazer a implementação dos enumeradores mais simples. Isso permite que a implementação desse enumerador em particular seja reduzida e simplificada dramaticamente.
class Node : IEnumerable
{
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumeratorWithLevel(0);
}
private IEnumerator GetEnumeratorWithLevel(int level)
{
yield return new NodeAndLevel(this, level);
foreach (Node node in children_)
{
using (IEnumerator it = node.GetEnumeratorWithLevel(level + 1))
{
while (it.MoveNext())
yield return it.Current;
}
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumeratorWithLevel(0);
}
...o resto é o mesmo que o Node no início.
O código inteiro do enumerador foi reduzido agora à implementação do GetEnumerator(), bem, quase. O auxiliar do GetEnumeratorWithLevel() também é requerido, de forma que um argumento adicional pode ser passado. Enquanto o GetEnumerator() estiver implementando a interface IEnumerable<> herdada do Node, sua assinatura não pode variar, razão pela qual ele chama o método helper. Como o IEnumerable<> deriva da interface C#1.0 IEnumerable como usada no exemplo anterior, o weakly typed IEnumerable.GetEnumerator() deve também ser implementado, mas isso é feito chamando a strongly typed version, como você pode ver.
Como genéricos estão disponíveis, o código da árvore foi transmutado para o uso de genéricos. Essa é uma coisa boa, uma vez que o caller do enumerador está lidando com objetos strongly typed, que não requerem mais um runtime cast.
A classe do enumerador não desapareceu, mas o compilador a implementou como uma nested class, exatamente como teríamos de fazer manualmente na versão anterior. Novamente, da mesma forma que a implementação C# que usava uma pilha para manter o estado recursivo, o código gerado também mantém o estado. A chave que permite o compilador fazer isso são os yield return statements. Isso informa ao compilador onde o enumerador deve retornar, e que a chamada subsequente para MoveNext() deve começar imediatamente depois.
Nesse exemplo, o enumerador é inicialmente chamado com o nó raiz. Isso então proporciona retorno imediato, criando uma nova instância de NodeLevel que será acessível através da Current Property gerada.
A próxima chamada leva o enumerador a criar um enumerador interno (como na implemetação C#1.0) do nó filho atual, ou seja, do children_ list. Isso então chamará MoveNext() nesse enumerador interno. Se o nó raiz não tiver filhos, então ele será encerrado e falso será retornado, indicando que o atravessamento foi completado. Caso haja crianças, então o yield causará um retorno verdadeiro, e o nó atual se transformará nesse filho. Como o enumerador foi criado chamando o GetEnumeratorWithLevel(), isso é efetivamente uma chamada recursiva, mas com o yield ocasionando o retorno com o código gerado, mantendo o estado, e inclusive armazenando as referências para todos os enumeradores internos.
Embora o código gerado seja difícil de ler, o uso do Reflector permite que o código gerado seja visto. Como isso implementa IEnumerator<> e o IEnumerator, Current é implementado para ambos e Reset implementado para o último. Adicionalmente, como IEnumerator<> também é derivado do IDisposable, Dispose também é criado. Essa é a razão pela qual a aparente chamada recursiva para o GetEnumeratorWithLevel() encapsula (wrap) a chamada resultante com o uso de um statement, de tal forma que Dispose é chamado.
O código gerado ainda tem que fazer tudo que a versão de codificação manual faz, incluindo manter abertos quaisquer enumeradores ativos. Como é gerada, deve ser mais rápida, mas não testei isso. Contudo, isso nos libertou de ter que escrever e manter esse código.
?
Texto original disponível em http://petebarber.blogspot.com/2007/02/evolution-of-c-enumerators.html
