>

LINQ: Implementação dos operadores TakeLast, TakeLastWhile, SkipLast e SkipLastWhile

Introdução

Há algum tempo necessitei de obter os últimos itens de uma sequência que satisfaziam um determinado critério e, olhando para os operadores disponíveis na classe Enumerable, apercebi-me de que tal operador não existia.

A única forma de obter o resultado pretendido era inverter a ordem dos itens na sequência, obter os itens que satisfaziam o critério e inverter os itens da sequência resultante. Algo como isto:

Sequence
.Reverse()
.TakeWhile(criteria)
.Reverse();

Parece simples, certo? Primeiro chamamos o método Reverse para produzir uma nova sequência com os mesmos itens mas na ordem inversa da sequência original, depois chamamos o método TakeWhile para obter os primeiros itens que satisfazem o critério e, finalmente, chamamos novamente o método Reverse para recuperar a ordem original dos itens.

O problema desta aproximação é que o método rev memoriza toda a sequência antes de iterar sobre os seus itens na ordem inversa – e o código acima usa-o duas vezes. Isto significa iterar sobre todos os itens da sequência original e memoriza-los, iterar sobre os primeiros itens que satisfazem o critério e memoriza-los e, finalmente, iterar sobre estes itens para produzir a sequência final.

Se estiveram a contar, chegaram à conclusão de que se iterou sobre todos os itens da sequência original uma vez e mais três vezes sobre os itens que satisfazem o critério. Se a sequência original for grande, isto pode consumir muita memória e tempo.

Existe ainda um problema adicional quando se usa a variante que usa o índice de item na sequência original na avaliação do critério de selecção (>). Quando se inverte a ordem dos itens, os índices destes serão invertidos e o predicado de avaliação do critério de selecção terá de ter isso em consideração, o que poderá não ser possível se não se souber o número de itens na sequência original.

Tinha de haver uma solução melhor, e é por isso que eu implementei os operadores Take Last.

TakeLast<TSource>(IEnumerable<TSource>)

Retorna o número especificado de elementos contínuos no fim da sequência.

int[] grades = { 59, 82, 70, 56, 92, 98, 85 };

var topThreeGrades = grades
 .OrderBy(grade => grade)
 .TakeLast(3);

Console.WriteLine("As notas mais altas são:");

foreach (int grade in topThreeGrades)
{
 Console.WriteLine(grade);
}
/*
Este código produz o seguinte resultado:

As notas mais altas são:
98
92
85
*/

TakeLastWhile<TSource>(IEnumerable<TSource>, Func<TSource, Boolean>)

Retorna os elementos do fim da sequência para os quais a condição especificada é verdadeira.

string[] fruits =
 {
 "maçã", "maracujá",
 "banana", "manga",
 "laranja", "mirtilo",
 "uva", "morango"
 };

var query = fruits
 .TakeLastWhile(fruit =>
 string.Compare("laranja",
 fruit, true) != 0);

foreach (string fruit in query)
{
 Console.WriteLine(fruit);
}

/*
Este código produz o seguinte resultado:

maracujá
uva
morango
*/

TakeLastWhile<TSource>(IEnumerable<TSource>, Func<TSource, Int32, Boolean>)

Retorna os elementos do fim da sequência para os quais a condição especificada é verdadeira.

string[] fruits =
 {
 "maçã", "maracujá",
 "banana", "manga",
 "laranja", "mirtilo",
 "uva", "morango"
 };

var query = fruits
 .TakeLastWhile((fruit, index) =>
 fruit.Length >= index);

foreach (string fruit in query)
{
 Console.WriteLine(fruit);
}

/*
Este código produz o seguinte resultado:

morango
*/

Tendo introduzido os operadores TakeLast, faz todo o sentido introduzido os seus duais: os operadores Skip Last.

SkipLast<TSource>(IEnumerable<TSource>)

Retorna todos os elementos da sequência à excepção do número especificado de elementos contínuos no fim da sequência.

int[] grades =
 { 59, 82, 70, 56, 92, 98, 85 };

var lowerGrades = grades
 .OrderBy(g => g)
 .SkipLast(3);

Console.WriteLine("Todas as notas excepto as top 3:");

foreach (int grade in lowerGrades)
{
 Console.WriteLine(grade);
}

/*
Este código produz o seguinte resultado:

As notas mais altas, excepto:
56
59
70
82
*/

SkipLastWhile<TSource>(IEnumerable<TSource>, Func<TSource, Boolean>)

Retorna todos os elementos da sequência à excepção dos elementos do fim da sequência para os quais a condição especificada é verdadeira.

int[] grades =
 { 59, 82, 70, 56, 92, 98, 85 };

var lowerGrades = grades
 .OrderBy(grade => grade)
 .SkipLastWhile(grade =>
 grade >= 80);

Console.WriteLine("Todas as notas menores que 80:");

foreach (int grade in lowerGrades)
{
 Console.WriteLine(grade);
}

/*
Este código produz o seguinte resultado:

Todas as notas menores que 80:
56
59
70
*/

SkipLastWhile<TSource>(IEnumerable<TSource>, Func<TSource, Int32, Boolean>)

Retorna todos os elementos da sequência à excepção dos elementos do fim da sequência para os quais a condição especificada é verdadeira.

int[] amounts =
 {
 5000, 2500, 9000, 8000,
 6500, 4000, 1500, 5500
 };

var query = amounts
 .SkipWhile((amount, index) => amount > index * 1000);

foreach (int amount in query)
{
 Console.WriteLine(amount);
}

/*
 Este código produz o seguinte resultado:

5000
2500
*/

Implementado os Operadores TakeLast

Implementando o operador TakeLast

O operador TakeLast retorna o número especificado de elementos contínuos do fim de uma sequência e é implementado como o método de extensão TakeLast.

Para implementar este operador, primeiro começamos por memorizar, pelo menos, o número requerido (count) de itens da sequência fonte (source) num array que funciona como uma memória intermédia (buffer) circular:

var sourceEnumerator = source.GetEnumerator();
var buffer = new TSource[count];
var numOfItems = 0;
int idx;

for (idx = 0; (idx < count) && sourceEnumerator.MoveNext(); idx++, numOfItems++)
{
 buffer[idx] = sourceEnumerator.Current;
}

Se o número de itens memorizados (numOfItems) for inferior ao número requerido (count), produzimos os itens memorizados:

if (numOfItems < count)
{
 for (idx = 0; idx < numOfItems; idx++)
 {
 yield return buffer[idx];
 }

 yield break;
}

Em seguida, iteramos pelos restantes itens e vamos os armazenando, de forma circular, na memória intermédia:

for (idx = 0; sourceEnumerator.MoveNext(); idx = (idx + 1) % count)
{
 buffer[idx] = sourceEnumerator.Current;
}

E finalmente, iteramos sobre os itens memorizados para produzir a sequência final:

for (; numOfItems > 0; idx = (idx + 1) % count, numOfItems--)
{
 yield return buffer[idx];
}

Há duas optimizações que ainda podemos fazer.

A primeira é óbvia, se o número de itens requerido for 0 (zero), retornamos uma sequência vazia:

if (count <= 0)
{
 return System.Linq.Enumerable.Empty<TSource>();
}

A segunda é se a sequência fonte (source) implementar a interface IList<T>. Os objectos que implementam esta interface têm uma propriedade Count e acesso indexado aos seus itens que nos permite optimizar a produção da sequência final.

A produção da sequência final passa por produzir o número de itens requeridos do fim da lista (ou todos se a lista contiver menos que os itens requeridos):

int listCount = list.Count;

for (int idx = listCount - ((count < listCount) ? count : listCount); idx < listCount; idx++)
{
 yield return list[idx];
}

Implementando o operador TakeLastWhile

O operador TakeLastWhile retorna os últimos elementos contíguos que satisfazem o critério especificado e é implementado como os métodos de extensão TakeLastWhile.

Para implementar este operador, primeiro começamos com uma memória intermédia (buffer) vazia e, para cada item que satisfaça o critério implementado pelo predicado (predicate), memorizamos esse item. Sempre que ocorrer um item que não satisfaça o critério de selecção, a memória intermédia é limpa:

var buffer = new List<TSource>();

foreach (var item in source)
{
 if (predicate(item))
 {
 buffer.Add(item);
 }
 else
 {
 buffer.Clear();
 }
}
var buffer = new List<TSource>();

foreach (var item in source)
{
 if (predicate(item))
 {
 buffer.Add(item);
 }
 else
 {
 buffer.Clear();
 }
}
foreach (var item in buffer)
{
 yield return item;
}

A diferença para o método que tem em conta o índice do item no predicado (predicate) de selecção é apenas na invocação deste:

var buffer = new List<TSource>();
var idx = 0;

foreach (var item in source)
{
 if (predicate(item, idx++))
 {
 buffer.Add(item);
 }
 else
 {
 buffer.Clear();
 }
}

foreach (var item in buffer)
{
 yield return item;
}

Implementando os Operadores SkipLast

Implementando o operador SkipLast

O operador SkipLast retorna o número especificado de elementos contínuos do fim de uma sequência e é implementado como o método de extensão SkipLast.

Para implementar este operador, começamos por memorizar, pelo menos, o número requerido (count) de itens da sequência fonte (source) num array que funciona como uma memória intermédia (buffer) circular:

var sourceEnumerator = source.GetEnumerator();
var buffer = new TSource[count];
int idx;

for (idx = 0; (idx < count) && sourceEnumerator.MoveNext(); idx++)
{
 buffer[idx] = sourceEnumerator.Current;
}

Em seguida, iteramos pelos restantes itens da sequência fonte (source) memorizando circularmente cada item e produzindo o item armazenado anteriormente na mesma posição:

idx = 0;

while (sourceEnumerator.MoveNext())
{
 var item = buffer[idx];

 buffer[idx] = sourceEnumerator.Current;

 idx = (idx + 1) % count;

 yield return item;
}

Se o número de itens a excluir for igual ou superior ao número de itens existentes na sequência fonte (source), o método sourceEnumerator.MoveNext() retornará false na primeira iteração do ciclo while e será produzida uma sequência vazia.

Tal como acontecia com o operador TakeLast, podem-se fazer algumas optimizações.

A primeira é óbvia, se o número de itens requeridos for 0 (zero) ou inferior, retornamos uma sequência equivalente à fonte (source):

if (count <= 0)
{
 return source.Select(i => i);
}

A segunda é se a sequência fonte (source) implementar a interface IList<T>. Os objectos que implementam esta interface têm uma propriedade Count e acesso indexado aos seus itens que nos permite optimizar a produção da sequência final.

Se o número de itens a excluir for igual ou superior ao número de itens da sequência fonte (source), retornamos uma sequência vazia:

var list = source as IList<TSource>;

if (list != null)
{
 if (count >= list.Count)
 {
 return System.Linq.Enumerable.Empty<TSource>();
 }

 // ...
}

Se o número de itens da sequência fonte (source) for superior ao número de itens a excluir, produzir a sequência final consiste em produzir todos os itens da sequência fonte (source) excepto os últimos count itens:

int returnCount = list.Count - count;

for (int idx = 0; idx < returnCount; idx++)
{
 yield return list[idx];
}

Implementando o operador SkipLastWhile

O operador SkipLastWhile retorna os últimos elementos contíguos que satisfazem o critério especificado e é implementado como os métodos de extensão SkipLastWhile.

Para implementar este operador, primeiro começamos com uma memória intermédia (buffer) vazia e, para cada item que satisfaça o critério implementado pelo predicado (predicate), memorizamos esse item. Sempre que ocorrer um item que não satisfaça o critério de selecção, a memória intermédia é limpa e o item que não satisfaz o critério é produzido:

var buffer = new List<TSource>();

foreach (var item in source)
{
 if (predicate(item))
 {
 buffer.Add(item);
 }
 else
 {
 if (buffer.Count > 0)
 {
 foreach (var bufferedItem in buffer)
 {
 yield return bufferedItem;
 }

 buffer.Clear();
 }

 yield return item;
 }
}

A diferença para o método que tem em conta o índice do item no predicado (predicate) de selecção é apenas na invocação deste:

var buffer = new List<TSource>();
var idx = 0;

foreach (var item in source)
{
 if (predicate(item, idx++))
 {
 buffer.Add(item);
 }
 else
 {
 if (buffer.Count > 0)
 {
 foreach (var bufferedItem in buffer)
 {
 yield return bufferedItem;
 }

 buffer.Clear();
 }

 yield return item;
 }
}

Conclusão

Como podem ver, implementar este tipo de operadores é muito fácil, pelo que, não se deve evitar a sua implementação sempre que se justifique. Implementar um específico para a nossa aplicação pode significar uma melhor legibilidade do código e até um aumento de performance.

Podem encontrar a implementação completa destes operadores (e outros) no meu projecto de utilitários e operadores para LINQ no CodePlex: PauloMorgado.Linq.

Recursos

Publicado na edição 26 (PDF) da Revista PROGRAMAR.