Archivo

Archive for the ‘Tutorial’ Category

Todo lo que siempre quisiste saber sobre colecciones pero tenías miedo de preguntar… Genéricos: lo mismo pero más barato


El mundo de .NET Framework 1.0 y 1.1 no era perfecto. Y es obvio: un esfuerzo monumental como .NET no podía quedar completo en la primera versión. Faltaba algo que muchos programadores de C++ extrañábamos: programación genérica. Este concepto estaba bien desarrollado en el mundo de C++: clases cuyo tipo de dato es parametrizable. Esto es especialmente útil en el mundo de las colecciones. Y es algo de lo que adolesció .NET en sus primeros días. Para darnos una idea, revisa el siguiente código.

#include <iostream>
#include <vector>
#include <string>

using std::cout;
using std::vector;
using std::string;
...

vector<int> ints;
ints.push_back(1);
ints.push_back(5);
ints.push_back(10);
for (vector<int>::iterator i = ints.begin(); i != ints.end(); ++i)
{
    cout << *i << endl;
}

vector<string> strs;
strs.push_back("Hola");
strs.push_back("mundo");
strs.push_back("C++");
for (vector<string>::iterator i = strs.begin(); i != strs.end(); ++i)
{
    cout << *i << " " << endl;
}

El código anterior es un pequeño ejemplo en C++ que muestra la clase genérica vector. Esta clase representa un arreglo dinámico, similar a ArrayList de .NET, con la salvedad de que vector acepta como parámetro el tipo de dato. Es decir, la funcionalidad de vector no necesariamente depende del tipo de dato (a final de cuentas, la funcionalidad de un arreglo, como añadir elementos e iterar sobre ellos, es la misma si empleamos enteros o cadenas de texto). Esto es lo que muestra el ejemplo: cómo usamos una clase con un tipo de dato entero y posteriormente la misma clase, pero con cadenas de texto (o una clase creada para trabajar con cadenas de texto, como es std::string). Podemos apreciar, pues, la versatilidad de la programación genérica, cuando trabajamos con colecciones.

En .NET 1.0 y 1.1 este concepto no existía. Lo más que podíamos utilizar eran clases que aceptaran tipos de dato object, y como en C# cualquier tipo de dato tiene su clase base en object, cualquier tipo de dato es aceptable. Un ejemplo de esto es ArrayList. Y de hecho, todas las colecciones y diccionarios que hemos visto hasta el momento. Pero esto acarrea dos problemas fundamentales.

El primero es que las colecciones no son fuertemente tipadas. Es decir, no hay forma de forzar a ArrayList, Stack, Queue, Hashtable o a OrderedDictionary para que acepten un tipo de dato en particular. Uno puede añadirles enteros, decimales, cadenas de texto y no hay forma de prevenir esto. La alternativa para estos casos era derivar de CollectionBase o DictionaryBase e implementar los métodos que requerían el tipo de dato (como Add, Remove, IndexOf, etc) de forma manual (las cuales, por cierto, utilizan un ArrayList / Hashtable de forma interna), o bien sobreescribir algún método como OnInsert y OnSet y ahí revisar que el objeto insertado tenga el tipo de dato deseado (y si no, lanzar una excepción).

Pero aún haciendo esto, no hay forma de evitar el segundo problema: el boxing y unboxing de tipos de datos valor (int, decimal, Point, y en general cualquier estructura). El concepto de boxing y unboxing es el siguiente. Las estructuras (struct int, por ejemplo) son tipos de datos que se pasan por valor. Es decir, si tenemos un método que acepta una estructura, al invocarlo y pasarle el parámetro lo que sucede es que se crea una copia del objeto. Con los tipos de dato referencia (cualquier clase) esto no pasa. Sin embargo, todos los objetos, sean tipo referencia o tipo valor, heredan de object, que es un tipo referencia.

public void foo(object o)
{
    Console.WriteLine(o.ToString());
}
...

foo("Hola mundo");
foo(15);

 

En el código anterior, el método foo recibe cualquier objeto. Lo invocamos con una cadena de texto y con un entero. Pero como int es un tipo valor y object un tipo referencia, el runtime de .NET crea por abajo del agua un objeto que “envuelve” al tipo valor para que pueda ser tratado como tipo referencia. Esto es lo que se conoce como “boxing”. El proceso inverso, obtener un tipo valor a partir de un tipo referencia, se conoce como “unboxing”.

object obj = 15; //boxing: int (valor) a object (referencia)
int i = (int)obj; //unboxin: object (referencia) a int (valor)

 

Pero como habrás podido imaginar, el proceso de envolver/desenvolver tipos valor es un proceso que consume recursos, y de hecho hacer esto seguido puede causar daños en rendimiento a tu programa. Comprenderás ahora el problema de utilizar ArrayList (o cualquier colección de las que hemos visto) con tipos de dato valor. Y esto es algo que ni siquiera se soluciona heredando de CollectionBase/DictionaryBase. La única forma real de solventar esta situación sería crear una clase que implemente ICollection/IList/IDictionary y utilizar arrays, los cuales tendríamos que redimensionar manualmente. Y esto no es particularmente productivo.

La llegada de los genéricos en .NET 2.0 solucionó este problema. El poder usar genéricos nos evita los boxings y unboxings para las estructuras, y naturalmente, proporciona métodos y clases fuertemente tipadas. Podríamos reescribir el método foo de hace tres párrafos de la siguiente forma.

public void foo<T>(T t)
{
    Console.WriteLine(t.ToString());
}
...

foo("Hola mundo");
foo(15);

 

Así las cosas, a partir de .NET 2.0 se crearon muchas clases de colecciones genéricas, la mayoría bajo el espacio de nombres System.Collections.Generic. Algunas son resultado de portar directamente clases existentes. Otras a parte de portar añaden funcionalidad nueva. Otras son totalmente nuevas y añaden valor. En esta entrada veremos las versiones genéricas de colecciones que ya hemos visto.

Comencemos por las interfaces. En primer lugar, tenemos a IEnumerable<T>. Al igual que su contraparte IEnumerable, esta interfaz (que además hereda IEnumerable) define un método GetEnumerator, que regresa un IEnumerator<T>, la contraparte genérica de IEnumerator. De manera general, cualquier array además de implementar IEnumerable, implementa la versión genérica IEnumerable<T>, donde el tipo de dato T es el tipo de dato del arreglo.

string[] strs = new string[] { "Seiya", "Shiriu", "Yoga", "Shun", "Ikki" };
IEnumerable<string> strenum = strs;
foreach (string str in strenum)
    Console.WriteLine(str);

 

Luego tenemos ICollection<T>. Pero esta interfaz sí difiere de ICollection, salvo por las propiedades Count e IsReadOnly. En primer lugar, ICollection<T> define un método CopyTo, que a diferencia del de ICollection, éste es fuertemente tipado. Sin embargo, no implementa ni SyncRoot ni IsSynchronized. Y finalmente, ICollection<T> sí define cuatro métodos obvios para cualquier colección: Add, Clear, Contains y Remove, siendo (salvo Clear) métodos fuertemente tipados. Esto contrasta mucho con ICollection, pero la razón que hay detrás es que aquí sí sabemos el tipo de dato de la colección, de antemano, dado que éste es genérico y parametrizable. Así, ICollection<T> en realidad se parece más a IList que a ICollection.

Y hablando de listas, obvio que también tenemos IList<T>. Ésta interfaz, que hereda de ICollection<T>, solo define tres métodos más: IndexOf, Insert y RemoveAt, además de un indexador fuertemente tipado. Contrastándola con IList, muchos de los métodos de ésta ya están definidos en ICollection<T>. Recordemos que una de las razones por las que ICollection no define algunos métodos como Add, Remove e IndexOf es que éstos toman como parámetro un objeto cuyo tipo de dato sería el empleado en la colección. Dado que ICollection debe ser la interfaz base para todas las colecciones, los métodos anteriores sólo podrían tomar un parámetro de tipo object, y esto afectaría a las colecciones fuertemente tipadas (por ejemplo, aquellas que creásemos derivando de CollectionBase y DictionaryBase). Sin embargo, éste no es el caso con ICollection<T>, dado que esta interfaz es fuertemente tipada por definición.

Por supuesto, no podía faltar la interfaz IDictionary<K, V>, donde K define el tipo de dato de las llaves y V el de los valores. Comparándola con IDictionary, la versión genérica no implementa las propiedades IsFixedSize ni IsReadOnly. Pero añade algunos métodos, como ContainsKey (que regresa verdadero cuando una llave existe en el diccionario) y TryGetValue (que intenta obtener una llave existente y si no existe, regresa falso en lugar de lanzar una excepción).

Con respecto a las clases, la primera que tenemos es Queue<T>, contraparte de Queue. De forma similar, tenemos a Stack<T>, contraparte genérica de Stack. Ambas clases son símiles de sus versiones no genéricas, por lo que su comportamiento ya ha sido explicado. También una clase especializada, SortedList, tienen su versión genérica: SortedList<T>. Por otra parte, OrderedDictionary tiene una versión genérica similar: SortedDictionary<K, V>, que aunque no son iguales, son similares (SortedDictionary<K, V> mantiene al diccionario ordenado por la llave).

Una de las clases nuevas que nos encontramos es LinkedList<T>. Esta clase es una lista doblemente enlazada que realiza sus búsquedas internas recorriendo los nodos de la lista. En cierto sentido, se parece a ListDictionary, solo que aplicado a colecciones en lugar de diccionarios. LinkedList<T> contiene tres propiedades importantes: Count, First y Last. La primera se explica fácilmente. First y Last son dos propiedades de tipo LinkedListNode<T>, que representan el primer y el último nodo de la lista. Cada LinkedListNode<T> contiene una referencia a la lista enlazada a la que pertenece (List), una referencia al nodo anterior (Previous), la cual será nula si el nodo es la cabeza de la lista, una referencia al siguiente nodo (Next), igualmente nula si el nodo es la cola de la lista, y finalmente el valor del nodo actual (Value). El siguiente código muestra un pequeño ejemplo sobre cómo utilizar y recorrer esta clase.

LinkedList<string> list = new LinkedList<string>();
list.AddLast("Seiya");
list.AddLast("Shiriu");
list.AddLast("Yoga");
list.AddLast("Shun");
list.AddLast("Ikki");

 for (LinkedListNode<string> node = list.First; node != null; node = node.Next)
{
    string prev = node.Previous != null ? node.Previous.Value : "NULL";
    string next = node.Next != null ? node.Next.Value : "NULL";
    Console.WriteLine("[{0}] - {1} - [{2}]", prev, node.Value, next);
}

Pero quizás la clase más interesante de todas las genéricas sea List<T>. Esta clase en cierto sentido es la contraparte de ArrayList. Pero es mucho más. Añade muchísima funcionalidad (como ordenamiento y búsquedas binarias) y es por mucho una de las clases más empleadas en todo el .NET Framework. Así que vale la pena dedicarle especial atención. Pero antes de continuar, presento la definición de una clase sobre la cual estaremos trabajando en nuestros ejemplos.

enum ArmourType { Bronze, Silver, Gold }

class ZodiacKnight
{
    public string Name { get; set; }
    public string Sign { get; set; }
    public int Senses { get; set; }
    public ArmourType Type { get; set; }

    public ZodiacKnight(string name, string sign, ArmourType type, int senses)
    {
        Name = name;
        Sign = sign;
        Senses = senses;
        Type = type;
    }

    public ZodiacKnight(string name, string sign, ArmourType type)
        : this(name, sign, type, 6)
    {
    }

    public ZodiacKnight()
        : this(string.Empty, string.Empty, ArmourType.Bronze, 6)
    {
    }

    public override string ToString()
    {
        return string.Format("{0} - {1} - {2}", Name, Sign, Type);
    }
}

Ahora sí, continuemos. En primer lugar, List<T> cuenta con tres constructores. Los primeros dos deberían ya sernos familiares: el primero es el constructor por defecto y el segundo toma como parámetro la capacidad inicial de la lista. Recordemos que ciertas colecciones reservan memoria conforme la van necesitando, y este proceso puede ser costoso, por lo que si sabemos de antemano la capacidad inicial, la lista puede reservar suficiente espacio para no tener que estar redimensionando a cada rato. El tercer constructor toma como parámetro un IEnumerable<T> y añade cada elemento de la enumeración a la lista. Este constructor es particularmente útil, ya que nos permite inicializar la lista con una colección o inclusive una consulta hecha con LINQ.

ZodiacKnight[] knights = new ZodiacKnight[] {
    new ZodiacKnight("Seiya", "Pegasus", ArmourType.Bronze),
    new ZodiacKnight("Shiriu", "Dragon", ArmourType.Bronze),
    new ZodiacKnight("Yoga", "Cignus", ArmourType.Bronze),
    new ZodiacKnight("Shun", "Andromeda", ArmourType.Bronze),
    new ZodiacKnight("Ikki", "Phoenix", ArmourType.Bronze)
};
List<ZodiacKnight> list = new List<ZodiacKnight>(knights);
foreach (ZodiacKnight knight in list)
    Console.WriteLine(knight);
ZodiacKnight[] knights = new ZodiacKnight[] {
    new ZodiacKnight("Seiya", "Pegasus", ArmourType.Bronze),
    new ZodiacKnight("Shiriu", "Dragon", ArmourType.Bronze),
    new ZodiacKnight("Yoga", "Cignus", ArmourType.Bronze),
    new ZodiacKnight("Shun", "Andromeda", ArmourType.Bronze),
    new ZodiacKnight("Ikki", "Phoenix", ArmourType.Bronze)
};
List<ZodiacKnight> list = new List<ZodiacKnight>(knights);
foreach (ZodiacKnight knight in list)
    Console.WriteLine(knight);

List<T> implementa las interfaces IList<T>, ICollection<T>, IEnumerable<T>, así como IList, ICollection e IEnumerable. Por lo que es posible recorrer la lista usando un bucle foreach.

La lista expone dos propiedades familiares: Count, que nos regresa el número de elementos que contiene la lista, y Capacity, que nos regresa el número de elementos que puede tener la lista antes de que ocurra un redimensionamiento. Éste ocurrirá al momento en que Count > Capacity, o bien cuando cambiemos Capacity manualmente. También cuenta con un indexador que toma como parámetro un número y regresa el objeto cuyo índice dentro de la colección coincida con el parámetro. Ojo que si este índice es menor a cero o mayor o igual a Count se lanzará un ArgumentOutOfRangeException.

ZodiacKnight knight = list[3]; // devuelve a Shun

Por supuesto, tenemos los métodos tradicionales Add y AddRange para añadir uno o más elementos, respectivamente, al final de la colección; Insert e InsertRange para añadir uno o más elementos en un índice determinado; Remove y RemoveRange para eliminar uno o más elementos; RemoveAt para eliminar un elemento en un índice determinado; y Clear para borrar todos los elementos de la lista. Adicionalmente, tenemos RemoveAll, que toma como parámetro un predicado: una función que recibe como parámetro un elemento de la lista, y devuelve un valor booleano, el cual, de ser verdadero, hará que se elimine dicho elemento de la colección. En otras palabras, RemoveAll elimina de la lista todos los elementos para los cuales el predicado se evalúe a verdadero.

En el siguiente ejemplo se eliminan todos los elementos de la lista cuyo nombre comience con S.

ZodiacKnight[] knights = new ZodiacKnight[] {
    new ZodiacKnight("Seiya", "Pegasus", ArmourType.Bronze),
    new ZodiacKnight("Shiriu", "Dragon", ArmourType.Bronze),
    new ZodiacKnight("Yoga", "Cignus", ArmourType.Bronze),
    new ZodiacKnight("Shun", "Andromeda", ArmourType.Bronze),
    new ZodiacKnight("Ikki", "Phoenix", ArmourType.Bronze)
};
List<ZodiacKnight> list = new List<ZodiacKnight>(knights);

list.RemoveAll(x => x.Name.StartsWith("s", StringComparison.CurrentCultureIgnoreCase));

foreach (ZodiacKnight knight in list)
    Console.WriteLine(knight);

El predicado lo pasamos en la forma de una expresión lambda, pero también pudimos haber usado la expresión de delegados tradicional.

static void Main(string[] args)
{
    ZodiacKnight[] knights = new ZodiacKnight[] {
        new ZodiacKnight("Seiya", "Pegasus", ArmourType.Bronze),
        new ZodiacKnight("Shiriu", "Dragon", ArmourType.Bronze),
        new ZodiacKnight("Yoga", "Cignus", ArmourType.Bronze),
        new ZodiacKnight("Shun", "Andromeda", ArmourType.Bronze),
        new ZodiacKnight("Ikki", "Phoenix", ArmourType.Bronze)
    };
    List<ZodiacKnight> list = new List<ZodiacKnight>(knights);

    list.RemoveAll(new Predicate<ZodiacKnight>(StartsWithS));

    foreach (ZodiacKnight knight in list)
        Console.WriteLine(knight);

    Console.ReadKey(true);
}

static bool StartsWithS(ZodiacKnight x)
{
    return x.Name.StartsWith("s", StringComparison.CurrentCultureIgnoreCase);
}

La clase List<T> cuenta, asimismo, con varios métodos que permiten realizar búsquedas de un elemento. Por supuesto, cuenta con Contains, que nos dice si un elemento existe o no dentro de la colección. Un método similar es Exists, el cual nos permite pasarle un predicado que nos devuelve verdadero cuando éste regresa verdadero para algún elemento. El siguiente código muestra su uso, utilizando una hermosa expresión lambda.

bool exists = list.Exists(x => x.Name.Equals("Shiriu"));
Console.WriteLine("Shiriu existe: {0}", exists);

Pero Exists solo regresa verdadero o falso, no nos devuelve el elemento. En contraste, el método Find sí que lo hace si encuentra algún elemento, en caso contrario nos regresa default(T), que sería null para tipos referencia.

ZodiacKnight shiriu = list.Find(x => x.Name.Equals("Shiriu"));
Console.WriteLine(shiriu);

Es de notar que Find regresa el primer elemento cuyo predicado devuelva verdadero, inclusive si existieran más. En contraste, FindLast nos devuelve el último elemento.

ZodiacKnight item = list.FindLast(x => x.Name.StartsWith("S"));
Console.WriteLine(item); // se salta a Seiya y a Shiriu, e imprime a Shun

Si queremos obtener no el primero ni el último elemento que concuerde con el predicado, sino todos, entonces usamos FindAll. Este método devuelve una lista con todos los elementos que concuerden. Así, si queremos obtener la lista de todos los elementos cuyo nombre comience son S, haríamos algo así:

List<ZodiacKnight> items = list.FindAll(x => x.Name.StartsWith("S"));
foreach (var item in items)
    Console.WriteLine(item);

Para obtener un índice dado un elemento determinado, hacemos uso del tradicional IndexOf que ya conocemos de otras colecciones. Este método cuenta con ciertas sobrecargas que nos permiten buscar en un rango acotado. Incluso contamos con LastIndexOf para buscar la última ocurrencia. Si quisiéramos buscar un índice, podríamos usar Find (o alguna de las variantes que hemos visto) y hacer un IndexOf con el elemento devuelto. Afortunadamente, List<T> nos provee métodos que hacen eso por nosotros, incluso dándonos la oportunidad de buscar en un rango de índices acotado: FindIndex, FindLastIndex.

Pero eso no es todo: ¡List<T> nos permite realizar incluso búsquedas binarias! El método en cuestión se llama BinarySearch, y nos devuelve el índice del elemento encontrado. Hacer una búsqueda binaria, especialmente sobre listas grandes, nos da un mejor rendimiento puesto que el número de comparaciones que hace se reduce drásticamente. Una sobrecarga de BinarySearch nos permite pasar como parámetro un IComparer, para que podamos nosotros hacer nuestas comparaciones sobre nuestros tipos de datos personalizados.

class ZodiacKnightComparer : IComparer<ZodiacKnight>
{
    public int Compare(ZodiacKnight x, ZodiacKnight y)
    {
        if (x == null)
            throw new ArgumentNullException("x");
        if (y == null)
            throw new ArgumentNullException("y");

        return x.Name.CompareTo(y.Name); 
    }
}

class Program
{
    static void Main(string[] args)
    {
        ZodiacKnight[] knights = new ZodiacKnight[] {
            new ZodiacKnight("Seiya", "Pegasus", ArmourType.Bronze),
            new ZodiacKnight("Shiriu", "Dragon", ArmourType.Bronze),
            new ZodiacKnight("Yoga", "Cignus", ArmourType.Bronze),
            new ZodiacKnight("Shun", "Andromeda", ArmourType.Bronze),
            new ZodiacKnight("Ikki", "Phoenix", ArmourType.Bronze)
        };
        List<ZodiacKnight> list = new List<ZodiacKnight>(knights);

        ZodiacKnightComparer comparer = new ZodiacKnightComparer();
        list.Sort(comparer);
        
        ZodiacKnight yoga = list.Find(x => x.Name.Equals("Yoga"));
        int index = list.BinarySearch(yoga, comparer);
        Console.WriteLine("Índice para Yoga: {0}", index);

        Console.ReadKey(true);
    }
}

El código anterior muestra en primera instancia una clase llamada ZodiacKnightComaprer, que implementa IComparer. En este caso, queremos que las comparaciones se hagan por el nombre y eso es lo que hace el método CompareTo. El método Main de la clase Program crea la lista y luego el comparador. Posteriormente, mostramos cómo hacer uso del BinarySearch para obtener el índice de un elemento determinado.

Habrás notado, por supuesto, que hacemos una llamada al método Sort. Éste método hace lo que promete: ordena los elementos de la lista. Tuvimos que hacer uso de Sort porque como bien recordarás, una búsqueda binaria sólo funciona si la colección de elementos a sobre la cuál buscará está ordenada. En este caso, la lista se ordena basándose en el comparador que le pasamos como parámetro (y por ende, la lista será ordenada en base al nombre). Una sobrecarga sin parámetros existe, y ésta usa el comparador por defecto que le encuentre al tipo de dato (en este caso, ZodiacKnight). Otra sobrecarga nos permite usar un delegado de tipo Comparison<T>, en cuyo caso podríamos usar una expresión lambda similar a esta:

list.Sort((x, y) => x.Name.CompareTo(y.Name));

Bien, ahora pasemos a ver métodos que nos ayudan a ejecutar acciones y transformaciones sobre los elementos de la lista. El primer método de ésta categoría es uno de mis favoritos. Supongamos que tenemos nuestra lista y queremos hacer algo con cada elemento de ésta, digamos, imprimir los elementos en la consola. ¿Qué hacemos? Pues un bucle foreach:

ZodiacKnight[] knights = new ZodiacKnight[] {
    new ZodiacKnight("Seiya", "Pegasus", ArmourType.Bronze),
    new ZodiacKnight("Shiriu", "Dragon", ArmourType.Bronze),
    new ZodiacKnight("Yoga", "Cignus", ArmourType.Bronze),
    new ZodiacKnight("Shun", "Andromeda", ArmourType.Bronze),
    new ZodiacKnight("Ikki", "Phoenix", ArmourType.Bronze)
};
List<ZodiacKnight> list = new List<ZodiacKnight>(knights);
foreach (ZodiacKnight knight in list)
    Console.WriteLine(knight);

Pues qué tedioso hacer eso. ¿No sería mejor tener alguna forma de ejecutar una acción en una sola línea? ¡Ese método existe! Y su nombre es, sorpresa-sorpresa, ForEach. Éste método toma un delegado de tipo Action<T>, el cuál pasa como parámetro cada elemento de la lista. Entonces, podríamos reemplazar el foreach anterior por la llamada a ForEach, utilizando una siempre útil expresión lambda:

list.ForEach(x => Console.WriteLine(x));

La vida es bella. Otro método útil es ConvertAll. Éste método nos permite transformar los elementos de la lista en otra lista con un tipo de dato diferente, si se requiere. Por ejemplo, supongamos que queremos crear una lista de cadenas de texto con los nombres de nuestros caballeros. Llamamos a ConvertAll, que toma como parámetro un delegado de tipo Converter<T, TOutput>, donde T es el tipo de dato de la lista (en este caso ZodiacKnight) y TOutput es el tipo de dato nuevo que queremos (en este caso, string). Y nos regresará un objeto List<TOutput>. Hacerlo no podría ser más sencillo.

List<ZodiacKnight> list = new List<ZodiacKnight>(knights);
List<string> names = list.ConvertAll(x => x.Name);

names.ForEach(x => Console.WriteLine(x));

Hay, por supuesto, otros métodos, pero éstos dos son mis favoritos. Tenemos, por ejemplo, a Reverse, que invierte el órden en el que se encuentran los elementos; los ya conocidos ToArray y CopyTo para convertir la lista a un arreglo, o bien copiar los elementos hacia otro arreglo, respectivamente; TrimExcess, que elimina los elementos cuyo índice sea mayor al parámetro; y AsReadOnly, que nos devuelve una colección de solo lectura, esto es, a la que no se le pueden añadir, cambiar ni eliminar elementos (el tipo de dato es ReadOnlyCollection<T>, que exploraremos en otra entrada de la serie).

Existe uno, sin embargo, que tiene utilidad bajo un escenario común. Por ejemplo, supongamos que queremos ver si todos los elementos de nuestra lista cumplen cierta condición. Lo tradicional sería hacer un foreach, probar cada elemento, y si alguno es falso, romper el bucle (con break) y listo. Pues bien, List<T> nos ofrece el método TrueForAll que hace precísamente eso: le pasamos como parámetro un predicado. Nuevamente, nos simplificamos mucho la vida:

List<ZodiacKnight> list = new List<ZodiacKnight>(knights);
bool allBronze = list.TrueForAll(x => x.Type == ArmourType.Bronze);
bool allGold = list.TrueForAll(x => x.Type == ArmourType.Gold);

Console.WriteLine("Todos son de bronce: {0}", allBronze);
Console.WriteLine("Todos son de oro: {0}", allGold);

Y ya para finalizar esta eulogía a List<T>, la cereza en el pastel: esta clase implementa IEnumerable<T>. Esto ya lo habíamos dicho, pero quiero resaltarlo, porque esto hace que además de todas las maravillas que nos ofrece, podemos realizar consultas con LINQ.

List<ZodiacKnight> list = new List<ZodiacKnight>(knights);
var query = from knight in list
            where knight.Name.StartsWith("S")
            select knight.Name;
var newList = query.ToList();
newList.ForEach(x => Console.WriteLine(x));

Con respecto a diccionarios, contamos con una clase que los implementa a la perfección: Dictionary<TKey, TValue>, de donde TKey es el tipo de dato de la llave y TValue, el del valor. A diferencia de List<T>, Dictionary<TKey, TValue> no es tan sofisticada, pero es cumplidora: implementa IDictionary<TKey, TValue> tal cual. El siguiente ejemplo muestra cómo utilizarla.

Dictionary<string, ZodiacKnight> dic = new Dictionary<string, ZodiacKnight>();
dic.Add("Pegasus", new ZodiacKnight("Seiya", "Pegasus", ArmourType.Bronze));
dic.Add("Dragon", new ZodiacKnight("Shiriu", "Dragon", ArmourType.Bronze));
dic.Add("Cignus", new ZodiacKnight("Yoga", "Cignus", ArmourType.Bronze));
dic.Add("Andromeda", new ZodiacKnight("Shun", "Andromeda", ArmourType.Bronze));
dic.Add("Phoenix", new ZodiacKnight("Ikki", "Phoenix", ArmourType.Bronze));

Console.WriteLine("Existe Cignus: {0}", dic.ContainsKey("Cignus"));
Console.WriteLine("Andromeda: {0}", dic["Andromeda"]);
Console.WriteLine();
foreach (var pair in dic)
    Console.WriteLine("Llave: {0}, Valor: {1}", pair.Key, pair.Value);

Ahora sí, hemos llegado al final de esta entrada. Hemos visto las maravillas que hacen los genéricos y en particular cómo benefician a las colecciones. Vimos los equivalentes genéricos a ciertas colecciones como Stack y Queue, vimos algunas nuevas y sobre todo, hicimos un repaso a profunidad de la clase List<T>, y le echamos un vistazo a Dictionary<TKey, TValue>. Todavía queda más en esta serie, pero creo que por ahora hay mucho que repasar antes de continuar.

Aprovecho también para dedicarle este trabajo a alguien quien por casi veintiocho años fue fuente de inspiración para mí: mi abuelo, Pedro Gómez Mijares, quién tristemente nos dejó apenas la semana pasada. Finalmente, me gustaría desearles a todos una feliz Navidad. Con suerte publico algo antes de que acabe el mes… pero si no, pues feliz año nuevo y los mejores deseos siempre.

Categorías:.NET Framework, C#, Tutorial Etiquetas: ,

Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Colecciones y diccionarios base


A lo largo de la serie hemos platicado sobre el funcionamiento general de colecciones (aquellas clases que implementan ICollection o IList) y diccionarios (aquellas clases que implementan IDictionary). Hemos visto también diferentes tipos de colecciones, como ArrayList, Stack, Queue, y diferentes tipos de diccionarios, como Hashtable y OrderedDictionary. Todas estas colecciones, que salieron en las primeras versiones de .NET, han sido diseñadas con propósitos muy particulares. Así, mientras ArrayList permite tener un arreglo de elementos dinámico con acceso aleatorio, Stack y Queue permite implementar patrones de primeras-entradas-primeras salidas y últimas-entradas-primeras-salidas, y ListDictionary e HybirdDictionary nos permiten optimizar el acceso a pares llave-valor basados en el número de elementos que contiene, entre muchos otros ejemplos, hay ocasiones en las que las clases existentes simplemente no son suficientes y no satisfacen los requerimientos que podemos necesitar bajo un cierto escenario. En estos casos, no nos queda de otra que crear nuestras propias colecciones.

Para hacer esto, no tenemos otra cosa que hacer más que crearnos una clase que implemente ICollection o IList, o bien IDictionary para los diccionarios. Hacer esto desde cero, sin embargo, puede ser una labor tediosa. En principio, implementar ICollection significa que tenemos que implementar a manita propiedades y métodos como IsSynchronized, IsReadOnly y CopyTo. Para implementar un IList, adicionalmente tendremos que implementar nuestros propios métodos Add, Remove y Clear, por citar algunos. Y ya no hablemos de implementar un diccionario: las propiedades Keys, Values vienene a la mente, además del enumerador (IDictionaryEnumerator). Implementar nuestras propias colecciones desde cero no solo es tedioso, sino además no es una tarea productiva.

Afortunadamente, cuando salió el .NET Framework, Microsoft pensó en estos escenarios. Y para ello, tenemos tres clases abstractas importantes, ubicadas en System.Collections: CollectionBase, ReadOnlyCollectionBase y DictionaryBase. Veamos.

CollectionBase

La primera clase que veremos es CollectionBase. Esta clase sirve de base para crear colecciones, e implementa las tres interfases importantes: IList, ICollection e IEnumerable. Esta clase cuenta con una colección interna en la cuál podemos guardar los elementos de la misma. Esta colección interna la podemos acceder mediante dos propiedades: List e InnerList, la primera de tipo IList y la segunda de tipo ArrayList. La diferencia entre ambas es que cuando usamos IList para agregar, modificar, remover y cambiar elementos, se disparan una serie de eventos que podemos utilizar para realizar validaciones extras, como veremos más adelante.

CollectionBase expone las siguientes propiedades y métodos públicos, naturales a cualquier colección: Capacity, Count, Clear, GetEnumerator y RemoveAt. Sin embargo, algunos otros métodos, que podríamos esperar en una colección como Add, AddRange, Remove, IndexOf y Contains no existen. Esto es por dos razones. La primera, que podamos controlar de qué forma agregamos los elementos. Por ejemplo, podríamos crear nuestro método Add que acepte una serie de parámetros a través del cuál construir el objeto deseado (útil cuando queremos implementar el patrón de diseño de fábrica de calses, por ejemplo). La segunda, que podamos proveer métodos fuertemente tipados. Es decir, si tengo mi clase Employee y creo EmployeeCollection derivada de CollectionBase, queremos que nuestro método Add acepte como parámetro un Employee en lugar de un object cualquiera. En la mayoría de los casos, simplemente crearemos los métodos fuertemente tipados y le pasaremos el control ya sea a InnerList o a List, según nos convenga. En otros casos quizás querramos realizar validaciones previas. Esto nos da la oportunidad de crear colecciones enteramente a nuestro antojo, sin tener que preocuparnos por la talacha.

Consideremos un ejemplo. Supongamos que tenemos una clase Employee sencilla.

class Employee
{
    public Employee(string name, string role, float salary)
    {
        Name = name;
        Role = role;
        Salary = salary;
    }

    public Employee()
        : this(string.Empty, string.Empty, 0f)
    {
    }

    public string Name { get; set; }
    public string Role { get; set; }
    public float Salary { get; set; }
}

Ahora queremos crear un EmployeeCollection. Nuestro cascarón quedaría así.

class EmployeeCollection : CollectionBase
{
    public EmployeeCollection()
        : base()
    {
    }
}

Vamos ahora, por partes, a implementar nuestra colección. Lo primero que nos viene en mente es que queremos contar con un método Add que nos acepte un Employee, pero también un método Add que nos acepte un nombre, el rol y el salario. Estos métodos lucirían de esta forma.

public void Add(Employee employee)
{
    List.Add(employee);
}

public Employee Add(string name, string role, float salary)
{
    Employee employee = new Employee(name, role, salary);
    Add(employee);

    return employee;
}

Como ves, toda la labor interna la realizamos a través de la propiedad List. Nota que pudimos emplear InnerList, pero en mi opinión siempre es mejor List, por la notificación de eventos que veremos adelante.

Posteriormente, queremos implementar un método AddRange que nos permita agregar varios elementos a la vez. Digamos, un arreglo. Fácil:

public void AddRange(IEnumerable employees)
{
    if (employees == null)
        throw new ArgumentNullException("employees");

    foreach (Employee employee in employees)
        Add(employee);
}

Nota que pedimos como parámetro un IEnumerable. Dado que cualquier arreglo (como cualquier colección) implementa IEnumerable, podemos ahora agregar los elementos de cualquier colección.

Un método que no debe faltar es IndexOf. Este método nos permite obtener el índice de un elemento determinado. Añadamos una sobrecarga que tome como parámetro el nombre y nos regrese el índice del empleado cuyo nombre concuerde con el parámetro (podemos emplear Linq para hacer la búsqueda, o un simple bucle foreach).

public int IndexOf(Employee employee)
{
    return List.IndexOf(employee);
}

public int IndexOf(string name)
{
    var query = from Employee employee in this
                where employee.Name == name
                select employee;

    Employee foundEmployee = query.FirstOrDefault();
    int index = -1;
    if (foundEmployee != null)
        index = IndexOf(foundEmployee);

    return index;
}

Una vez implementados estos, podemos crear nuestros métodos Contains, como se muestran a continuación. El primero le delega la tarea a List, mientras que el segundo hace lo propio pero con IndexOf.

public bool Contains(Employee employee)
{
    return List.Contains(employee);
}

public bool Contains(string name)
{
    return IndexOf(name) >= 0;
}

Lo que sigue ahora es implementar un método Remove que tome como parámetro el Employee a remover. Pero también queremos dar la facilidad de eliminar un elemento por nombre. Easy-peacy.

public void Remove(Employee employee)
{
    List.Remove(employee);
}

public void Remove(string name)
{
    int index = IndexOf(name);
    if (index >= 0)
        RemoveAt(index);
}

No es necesario implementar un RemoveAt, que elimine por índice, ya que éste ya lo provee CollectionBase. Lo que sí queremos y no puede faltar, es un indexador que nos permita acceder a los elementos por su índice.

public Employee this[int index]
{
    get { return List[index] as Employee; }
    set { List[index] = value; }
}

Ahora bien, como decía anteriormente, CollectionBase dispara ciertos eventos (en la forma de métodos virtuales protegidos) cuando se añaden, eliminan o cambian elementos. La siguiente lista muestra estos métodos.

  • OnClear y OnClearComplete se invocan antes y después de ejecutar el vaciado de elementos, a través del método List.Clear.
  • OnInsert y OnInsertComplete se invocan antes y después de añadir un elemento, a través de List.Add y List.Insert.
  • OnRemove y OnRemoveComplete se invocan antes y después de eliminar un elemento de la colección, a través de List.Remove y List.RemoveAt.
  • OnSet y OnSetComplete se invocan antes y después de que se establece el valor de una colección, usualmente a través del indexador de List.
  • OnValidate se llama en diversas ocasiones (al insertar, remover o cambiar elementos, por ejemplo) y su finalidad es que podamos ejecutar validaciones genéricas sobre el elemento en cuestión.

Continuando con el ejemplo, supongamos que nuestro EmployeeCollection debe seguir ciertas reglas de negocio cuando agregamos elementos: no debe ser nulo, el objeto a agregar debe ser de tipo Employee, no puede estar repetido y no puede haber otro elemento que tenga el mismo nombre que el que se pretende añadir. Esto lo podemos agregar sobreescribiendo el método OnInsert y lanzando una excepción si las reglas no se cumplen.

protected override void OnInsert(int index, object value)
{
    if (value == null)
        throw new ArgumentNullException("value");
    if (index < 0 || index > Count)
        throw new IndexOutOfRangeException();

    Employee employee = value as Employee;
    if (employee == null)
        throw new InvalidCastException("The value must be of type Employee.");
    if (Contains(employee) || Contains(employee.Name))
        throw new ArgumentException("The employee already exists.");

    base.OnInsert(index, value);
}

Y ya para finalizar, añadamos un par de métodos que nos permita obtener los empleados por rol, así como aquellos que estén en un rango determiando de valores. Yo utilizo Linq, pero puedes emplear un bucle foreach junto con un yield return. Ahora sí que es a tu gusto.

public Employee[] GetBySalary(float min, float max)
{
    var query = from Employee employee in this
                where employee.Salary >= min && employee.Salary <= max
                select employee;

    return query.ToArray();
}

public Employee[] GetByRole(string role)
{
    var query = from Employee employee in this
                where employee.Role.Equals(role, StringComparison.CurrentCultureIgnoreCase)
                select employee;

    return query.ToArray();
}

Y listo, hemos creado nuestra primera colección personalizada. El siguiente código muestra todo el programa completo, así como un ejemplo de cómo podríamos usar nuestra nueva colección.

using System;
using System.Collections;
using System.Linq;

namespace Blogoso
{
    class Employee
    {
        public Employee(string name, string role, float salary)
        {
            Name = name;
            Role = role;
            Salary = salary;
        }

        public Employee()
            : this(string.Empty, string.Empty, 0f)
        {
        }

        public string Name { get; set; }
        public string Role { get; set; }
        public float Salary { get; set; }

        public override string ToString()
        {
            return string.Format("{0} - {1} - ${2}", Name, Role, Salary);
        }
    }

    class EmployeeCollection : CollectionBase
    {
        public EmployeeCollection()
            : base()
        {
        }

        public Employee this[int index]
        {
            get { return List[index] as Employee; }
            set { List[index] = value; }
        }

        public void Add(Employee employee)
        {
            List.Add(employee);
        }

        public Employee Add(string name, string role, float salary)
        {
            Employee employee = new Employee(name, role, salary);
            Add(employee);

            return employee;
        }

        public void AddRange(IEnumerable employees)
        {
            if (employees == null)
                throw new ArgumentNullException("employees");

            foreach (Employee employee in employees)
                Add(employee);
        }

        public void Remove(Employee employee)
        {
            List.Remove(employee);
        }

        public void Remove(string name)
        {
            int index = IndexOf(name);
            if (index >= 0)
                RemoveAt(index);
        }

        public int IndexOf(Employee employee)
        {
            return List.IndexOf(employee);
        }

        public int IndexOf(string name)
        {
            var query = from Employee employee in this
                        where employee.Name == name
                        select employee;

            Employee foundEmployee = query.FirstOrDefault();
            int index = -1;
            if (foundEmployee != null)
                index = IndexOf(foundEmployee);

            return index;
        }

        public bool Contains(Employee employee)
        {
            return List.Contains(employee);
        }

        public bool Contains(string name)
        {
            return IndexOf(name) >= 0;
        }

        public Employee[] GetBySalary(float min, float max)
        {
            var query = from Employee employee in this
                        where employee.Salary >= min && employee.Salary <= max
                        select employee;

            return query.ToArray();
        }

        public Employee[] GetByRole(string role)
        {
            var query = from Employee employee in this
                        where employee.Role.Equals(role, StringComparison.CurrentCultureIgnoreCase)
                        select employee;

            return query.ToArray();
        }

        protected override void OnInsert(int index, object value)
        {
            if (value == null)
                throw new ArgumentNullException("value");
            if (index < 0 || index > Count)
                throw new IndexOutOfRangeException();

            Employee employee = value as Employee;
            if (employee == null)
                throw new InvalidCastException("The value must be of type Employee.");
            if (Contains(employee) || Contains(employee.Name))
                throw new ArgumentException("The employee already exists.");

            base.OnInsert(index, value);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            EmployeeCollection employees = new EmployeeCollection();

            employees.Add(new Employee("Fernando", "Manager", 25000f));
            employees.Add("Catalina", "Manager", 30000f);

            Employee[] array = new Employee[] {
                new Employee("Antonio", "CEO", 40000f),
                new Employee("Moisés", "Diseñador", 20000f),
                new Employee("Joan", "Programador", 22000f),
                new Employee("Jorge", "Programador", 15000f)
            };
            employees.AddRange(array);

            foreach (Employee employee in employees)
                Console.WriteLine(employee);

            array = employees.GetByRole("Manager");
            foreach (Employee employee in array)
                Console.WriteLine(employee);

            array = employees.GetBySalary(20000f, 25000f);
            foreach (Employee employee in array)
                Console.WriteLine(employee);

            try {
                employees.Add("Fernando", "Manager", 25000f);
            } catch (Exception e) {
                Console.WriteLine(e.Message);
            }

            int index = employees.IndexOf("Catalina");
            Console.WriteLine("El índice para Catalina es {0}", index);

            bool contains = employees.Contains("Moisés");
            Console.WriteLine("El empleado Moisés existe: {0}", contains);

            Console.ReadKey(true);
        }
    }
}

ReadOnlyCollectionBase

Una clase muy similar a CollectionBase es ReadOnlyCollectionBase. La finalidad de ésta es que podamos crear colecciones de solo lectura. Es decir, que no podamos añadir o eliminar elementos, solo leerlos. Por ello ReadOnlyCollectionBase solo cuenta con la propiedad pública Count y el método GetEnumerator. Y cuenta además con InnerList, de tipo ArrayList. La ventaja de utilizar esta colección es que podemos agregar métodos útiles de búsqueda y ordenamiento (como GetByRole y GetBySalary del ejemplo anterior) además de otros tradicionales como IndexOf y Contains, lo cual nos da más funcionalidad del que nos provee un simple array.

El siguiente código muestra nuestra colección modificada para que sea de solo lectura. Obviamente métodos como Add, Remove y Clear ya no se implementan. Nota que el constructor acepta un arreglo de elementos, que serán los que contendrá la colección.

using System;
using System.Collections;
using System.Linq;

namespace Blogoso
{
    class Employee
    {
        public Employee(string name, string role, float salary)
        {
            Name = name;
            Role = role;
            Salary = salary;
        }

        public Employee()
            : this(string.Empty, string.Empty, 0f)
        {
        }

        public string Name { get; set; }
        public string Role { get; set; }
        public float Salary { get; set; }

        public override string ToString()
        {
            return string.Format("{0} - {1} - ${2}", Name, Role, Salary);
        }
    }

    class EmployeeCollection : ReadOnlyCollectionBase
    {
        public EmployeeCollection(IEnumerable employees)
            : base()
        {
            foreach (Employee employee in employees)
                InnerList.Add(employee);
        }

        public Employee this[int index]
        {
            get { return InnerList[index] as Employee; }
            set { InnerList[index] = value; }
        }

        public int IndexOf(Employee employee)
        {
            return InnerList.IndexOf(employee);
        }

        public int IndexOf(string name)
        {
            var query = from Employee employee in this
                        where employee.Name == name
                        select employee;

            Employee foundEmployee = query.FirstOrDefault();
            int index = -1;
            if (foundEmployee != null)
                index = IndexOf(foundEmployee);

            return index;
        }

        public bool Contains(Employee employee)
        {
            return InnerList.Contains(employee);
        }

        public bool Contains(string name)
        {
            return IndexOf(name) >= 0;
        }

        public Employee[] GetBySalary(float min, float max)
        {
            var query = from Employee employee in this
                        where employee.Salary >= min && employee.Salary <= max
                        select employee;

            return query.ToArray();
        }

        public Employee[] GetByRole(string role)
        {
            var query = from Employee employee in this
                        where employee.Role.Equals(role, StringComparison.CurrentCultureIgnoreCase)
                        select employee;

            return query.ToArray();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Employee[] array = new Employee[] {
                new Employee("Fernando", "Manager", 25000f),
                new Employee("Catalina", "Manager", 30000f),
                new Employee("Antonio", "CEO", 40000f),
                new Employee("Moisés", "Diseñador", 20000f),
                new Employee("Joan", "Programador", 22000f),
                new Employee("Jorge", "Programador", 15000f)
            };
            EmployeeCollection employees = new EmployeeCollection(array);

            foreach (Employee employee in employees)
                Console.WriteLine(employee);

            array = employees.GetByRole("Manager");
            foreach (Employee employee in array)
                Console.WriteLine(employee);

            array = employees.GetBySalary(20000f, 25000f);
            foreach (Employee employee in array)
                Console.WriteLine(employee);

            int index = employees.IndexOf("Catalina");
            Console.WriteLine("El índice para Catalina es {0}", index);

            bool contains = employees.Contains("Moisés");
            Console.WriteLine("El empleado Moisés existe: {0}", contains);

            Console.ReadKey(true);
        }
    }
}

DictionaryBase

Hasta el momento hemos hablado de puras colecciones. Sin embargo, también existe una clase análoga a CollectionBase, solo que para diccionarios: DictionaryBase. La clase está estructurada de forma similar a su contraparte. Existen los miembros Count, Clear, CopyTo y GetEnumerator como públicos, así como los métodos para realizar validaciones(OnClear, OnInsert, OnGet, OnSet, OnRemove, OnValidate, etc.) solo que acomodados para poder recibir pares llave-valor. La diferencia más grande (aparte de que esta clase implementa IDictionary en lugar de IList) es que esta clase tiene dos propiedades públicas, Dictionary (de tipo IDictionary) e InnerHashtable (de tipo Hashtable), contrapertes de List e InnerList respectivamente. Ambas representan el diccionario subyacente de DictionaryBase.

class EmployeeCollection : DictionaryBase
{
    public EmployeeCollection()
        : base()
    {
    }

    public Employee this[int id]
    {
        get { return Dictionary[id] as Employee; }
        set { Dictionary[id] = value; }
    }

    public void Add(int id, Employee employee)
    {
        Dictionary.Add(id, employee);
    }

    public Employee Add(int id, string name, string role, float salary)
    {
        Employee employee = new Employee(name, role, salary);
        Add(id, employee);

        return employee;
    }

    public void Remove(int id)
    {
        Dictionary.Remove(id);
    }

    public bool Contains(int id)
    {
        return Dictionary.Contains(id);
    }

    public Employee[] GetBySalary(float min, float max)
    {
        var query = from Employee employee in Dictionary.Values
                    where employee.Salary >= min && employee.Salary <= max
                    select employee;

        return query.ToArray();
    }

    public Employee[] GetByRole(string role)
    {
        var query = from Employee employee in Dictionary.Values
                    where employee.Role.Equals(role, StringComparison.CurrentCultureIgnoreCase)
                    select employee;

        return query.ToArray();
    }

    protected override void  OnInsert(object key, object value)
    {
        if (value == null)
            throw new ArgumentNullException("value");

        int id = (int)key;
        if (Contains(id))
            throw new ArgumentException("El ID ya existe.");

        Employee employee = value as Employee;
        if (employee == null)
            throw new InvalidCastException("The value must be of type Employee.");
        
        base.OnInsert(id, employee);
    }
}

El código anterior muestra cómo podriamos crear un diccionario que asocie un ID numérico a un empleado. Como puedes ver, es muy similar a CollectionBase, con la diferencia (claro) de tratarse de un diccionario.

Finalmente…

Como puedes ver, las tres colecciones presentadas: CollectionBase, ReadOnlyCollectionBase y DictionaryBase nos proveen un punto de inicio para crear nuestras propias colecciones, y su finalidad es ahorrarnos trabajo. Por supuesto, hay otras opciones, como derivar de clases ya existentes (sobre todo las genéricas, de las cuales todavía no hemos hablado en esta serie). De hecho, con el advenimiento de los genéricos en .NET 2 (y colecciones como List<T>, Collection<T> y Dictionary<K, V>, las clases aquí presentadas han caído en desuso. Toma en cuenta, sin embargo, que estas clases salieron antes de los genéricos, y que en ese entonces proveían una gran ayuda. Incluso hoy en día lo son, cuando ninguna de las clases existentes satisfacen nuestras necesidades.

Y por cierto, ese será el tema de la siguiente entrada: los genéricos. Así que estate atento a esta serie. Misma hora, mismo canal.

Categorías:.NET Framework, C#, Tutorial Etiquetas:

Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Tres diccionarios especializados

noviembre 30, 2010 1 comentario

Hasta el momento, la serie de artículos dedicados a colecciones solo ha presentado un simple diccionario: Hashtable. Como habíamos visto antes, éste diccionario agrupa los pares llave-valor basándose en el hash de la llave. Ahora bien, este tipo de ordenamientos suele ser eficiente, sobre todo cuando tenemos diccionarios enormes. Pero hay situaciones en las que Hashtable no es tan eficiente, o bien bajo ciertas circunstancias algun enfoque diferente puede ser mejor. En esta entrada vamos a analizar tres diccionarios que se encuentran dentro del espacio de nombres System.Collections.Specialized, y que ofrecen dichos enfoques para escenarios muy específicos: ListDictonary, HybridDictionary y OrderedDictionary.

Comencemos por estudiar ListDictionary. A primera vista, ListDictionary luce como una implementación normal de IDictionary, y de hecho así es. No añade métodos nuevos. Cuenta con los métodos y propiedades que implementan ICollection, como Count, IsSynchronized, SyncRoot, CopyTo; y también con propiedades y métodos propios de un IDictionary, como IsFixedSize, IsReadOnly, Keys, Values, Add, Clear, Contains, Remove y el indexador para acceder a los valores dada una llave; todos estos miembros que ya hemos explicado en entradas anteriores. De hecho, incluso contiene menos métodos que Hashtable. Entonces la pregunta es: ¿para qué nos sirve ListDictionary?

La respuesta es que mientras Hashtable almacena los pares llave-valor en bloques de memoria que son accesibles vía el código hash de la llave, ListDictionary los almacena como si fuera una lista enlazada. Es decir, el primer elemento contiene el par llave-valor, más un apuntador (o referencia, en el argot de C#) al elemento siguiente, y así sucesivamente hasta llegar al final de la lista. Esto implica que ListDictionary no manipula la memoria (o al menos, no de la forma en que Hashtable lo hace) y por lo tanto el acceso a los elementos es más eficiente en términos de memoria y procesamiento.

Sin embargo esto tiene su precio. Si recuerdas tus viejas clases de estructuras de datos que llevaste en la universidad, sabrás entonces que una lista enlazada tiene un mal rendimiento cuando intentamos acceder a los elementos de forma secuencial. De hecho, esta es la diferencia más grande que hay entre un array o vector (donde los elementos se almacenan en bloques de memoria contigua, haciendo posible el acceso secuencial) y la lista enlazada, donde se comienza a navegar por la cabeza de la lista, yendo de uno en uno hasta localizar el elemento que nos interesa. Luego entonces, el rendimiento de una lista (y por ende, de ListDictionary) al querer acceder a un elemento disminuye considerablemente conforme el número de elementos contenidos aumenta.

Para probar lo anterior, consideremos el siguiente código.

using System;
using System.Collections;
using System.Collections.Specialized;

namespace Blogoso
{
    class Program
    {
        static void Main(string[] args)
        {
            const int elements = 10;

            IDictionary dic = new ListDictionary();
            for (int i = 0; i < elements; i++)
            {
                string key = i.ToString();
                string val = string.Format("Cadena {0}", i);
                dic.Add(key, val);
            }

            DateTime start = DateTime.Now;
            for (int i = 0; i < elements; i++)
            {
                var key = i.ToString();
                var val = dic[key];
                Console.WriteLine("{0}: {1}", key, val);
            }

            TimeSpan duration = DateTime.Now - start;
            Console.WriteLine("Duración: {0}", duration);

            Console.ReadKey(true);
        }
    }
}

En este pequeño programita, creamos un ListDictionary (línea 13), le añadimos un número determinado de elementos (especificado en la constante definida en la línea 11) y posteriormente recorremos todo el diccionario y lo mostramos en la consola. Para hacer el ejemplo más interesante, tomamos el tiempo de inicio (línea 21) y el tiempo final (línea 29) y mostramos el tiempo que tardó el diccionario en obtener los valores. Si ejecutamos el programa, obtendríamos un resultado similar al siguiente (puede variar dependiendo de las características de la máquina que lo ejecute).

0: Cadena 0
1: Cadena 1
2: Cadena 2
3: Cadena 3
4: Cadena 4
5: Cadena 5
6: Cadena 6
7: Cadena 7
8: Cadena 8
9: Cadena 9
Duración: 00:00:00.0020001

Después de ejecutar el programa en repetidas ocasiones, el tiempo empleado suele estar entre 2 y 3 milésimas de segundo. Ahora bien, si en lugar de diez elementos cambiamos la línea 11 para que sean mil, el tiempo de ejecución me aparece entre 186 y 199 milésimas de segundo. Para comparar, cambiemos la línea 13 para que en lugar de un ListDictionary creemos un Hashtable:

IDictionary dic = new Hashtable();

Si añadimos diez elementos, el tiempo promedio se encuentra entre 3 y 4 milésimas de segundo, un pequeño aumento con respecto a ListDictionary. Sin embargo, al añadir mil elementos, obtengo un tiempo promedio de entre los 155 y 170 milésimas. Una baja sensible con respecto a ListDictionary. Repitiendo el ejercicio pero ahora con 10,000 elementos, tenemos que mientras Hashtable me da tiempos de entre 800 milésimas y 1.06 segundos, ListDictionary me da tiempos de entre 2.9 y 3.2 segundos.

Este pequeño experimento nos permite concluir que ListDictionary es más eficiente que Hashtable cuando nuestro conjunto de datos es pequeño, pero que conforme dicho conjunto crece, el rendimiento comienza a bajar considerablemente. De hecho, el último ejercicio con diez mil elementos mostró que el rendimiento de Hashtable con respecto a ListDictionary puede ser entre 200% y 300% mayor.

Luego entonces tenemos la premisa de ListDictionary: es un diccionario optimizado para trabajar con pocos elementos (la documentación dice que no más de diez), de tal suerte que si el número de elementos es grande, es preferible utilizar otro tipo de diccionario, pero que si el número permanece bajo se obtendrán mejores resultados con ListDictionary.

Y esto precísamente nos lleva al segundo diccionario especializado a tratar. Supongamos que tenemos un escenario en el cual tenemos un diccionario que generalmente tiene pocos elementos. Pero que bajo ciertas circunstancias, éste puede crecer. Para no perder el rendimiento, tendríamos que usar ListDictionary y cuando éste crezca, copiar todos los elementos a un Hashtable. Pues bien, hay una colección que hace precísamente eso: HybridDictionary. Esta clase emplea de forma interna un ListDictionary cuando el número de elementos se mantiene bajo, pero que cambia a Hashtable cuando el número crece.

Al igual que ListDictionary, HybridDictionary implementa las mismas propiedades y métodos que definen ICollection e IDictionary, con la salvedad que el constructor nos permite especificar el número de elementos que contendrá la colección de forma inicial. Pero evidentemente la fortaleza de la clase radica en las estrategias utilizadas para optimizar el acceso a los pares llave-valor. Para mostrar esto, tomemos el ejercicio que habíamos practicado anteriormente y modifiquémoslo para utilizar HybridDictionary.

using System;
using System.Collections;
using System.Collections.Specialized;

namespace Blogoso
{
    class Program
    {
        static void Main(string[] args)
        {
            const int elements = 10;

            IDictionary dic = new HybridDictionary();
            for (int i = 0; i < elements; i++)
            {
                string key = i.ToString();
                string val = string.Format("Cadena {0}", i);
                dic.Add(key, val);
            }

            DateTime start = DateTime.Now;
            for (int i = 0; i < elements; i++)
            {
                var key = i.ToString();
                var val = dic[key];
                Console.WriteLine("{0}: {1}", key, val);
            }

            TimeSpan duration = DateTime.Now - start;
            Console.WriteLine("Duración: {0}", duration);

            Console.ReadKey(true);
        }
    }
}

Cuando ejecuto en repetidas ocasiones este código, obtengo un tiempo promedio de entre 2 y 3 milésimas, similar al que obteníamos usando ListDictionary. Pero si cambiamos el número de elementos de diez a diez mil, en lugar de obtener el promedio de entre 2.9 y 3.2 segundos, obtenemos un promedio de 0.88 a 0.92 segundos, similar al que habíamos obtenido con Hashtable. Esto es así, en efecto, debido al comportamiento interno de HybridDictionary.

El tercer diccionario especializado que vamos a tratar, a diferencia de los dos anteriores, no se distingue de Hashtable o algún otro diccionario por la optimización hecha en base al número de elementos que contenga, sino más bien porque permite el acceso aleatorio a los elementos: es decir, a través de un índice. La clase se llama OrderedDictionary y, como su nombre lo sugiere, es un diccionario que mantiene ordenados los elementos basados en la llave de los mismos en bloques de memoria contigua, de forma muy similar a como los almacena un array o un vector. La principal ventaja de esto es que podemos acceder a los elementos no solamente a través de la llave, sino también a través de un índice.

using System;
using System.Collections;
using System.Collections.Specialized;

namespace Blogoso
{
    class Program
    {
        static void Main(string[] args)
        {
            OrderedDictionary dic = new OrderedDictionary();
            dic.Add("John", "Imagine");
            dic.Add("Ringo", "Photograph");
            dic.Add("Paul", "Another day");
            dic.Add("George", "My sweet lord");

            for (int i = 0; i < dic.Count; i++)
            {
                Console.WriteLine("{0} - {1}", i, dic[i]);
            }

            Console.ReadKey(true);
        }
    }
}

El ejemplo anterior muestra cómo podemos usar el indexador de OrderedDictionary para acceder por medio del índice. Esto es algo que no podemos lograr con Hashtable, y nos proporciona la comodidad de poder iterar sobre los elementos sin tener que conocer las llaves de antemano.

Un aspecto importante de esta clase es que, como hemos mencionado, internamente mantiene ordenados los elementos. Por lo mismo, es necesario poder contar con una forma de controlar el cómo comparar elementos, y es por ello que el constructor de OrderedDictionary admite una interfaz de tipo IEqualityComparer. Esta interfaz nos permite comparar dos objetos, además de obtener un código hash para alguno de ellos. A través de esto, podemos controlar cómo la colección ordena sus elementos. Por ejemplo, si las llaves son cadenas de texto (como en el ejemplo) podríamos crear una clase que implemente dicha interfaz para que las comparaciones se hicieran sin distinguir entre mayúsculas y minúsculas. Por ejemplo:

using System;
using System.Collections;
using System.Collections.Specialized;

namespace Blogoso
{
    class StringComparer : IEqualityComparer
    {
        public StringComparer()
        {
        }

        public bool Equals(object x, object y)
        {
            string xstr = x as string;
            string ystr = y as string;

            return xstr.Equals(ystr, StringComparison.InvariantCultureIgnoreCase);
        }

        public int GetHashCode(object obj)
        {
            string str = obj as string;
            str = str.ToUpper();

            return str.GetHashCode();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            StringComparer comparer = new StringComparer();
            OrderedDictionary dic = new OrderedDictionary(comparer);
            dic.Add("John", "Imagine");
            dic.Add("Ringo", "Photograph");
            dic.Add("Paul", "Another day");
            dic.Add("George", "My sweet lord");

            for (int i = 0; i < dic.Count; i++)
            {
                Console.WriteLine("{0} - {1}", i, dic[i]);
            }

            Console.ReadKey(true);
        }
    }
}

La clase StringComparer que creamos compara dos cadenas de texto sin distinguir entre mayúsculas y minúsculas (método Equals), mientras que GetHashCode regresa el código hash de la cadena de texto en mayúsculas, de tal suerte que “John”, “JOHN” y “john” regresen el mismo código. Y ahora sí, inicializamos nuestro OrderedDictionary con una instancia de este comparador.

A lo largo de esta entrada analizamos los tres diccionarios especializados que nos ofrece .NET, cada uno con sus ventajas, virtudes y desventajas. Vimos cómo ListDictionary y HybridDictionary nos pueden ayudar a optimizar nuestro código, mientras que OrderedDictionary nos permite acceder a valores mediante un índice, sin necesidad de conocer las llaves de antemano. Así las cosas, la regla a seguir pudiera expresarse así. Si un diccionario tiene un número bajo de elementos, ListDictionary es la opción con mejor rendimiento. Si el diccionario tiene un número inicial bajo de elementos, pero es posible que éste crezca, la mejor opción es utilizar HybridDictionary. Por otra parte, si el número de elementos inicial es alto, es mejor utilizar Hashtable desde un principio. Finalmente, si tenemos un diccionario cuyas llaves no son conocidas, o en algún punto no se tiene alguna forma de inferirlas, podemos optar por emplear OrderedDictionary, que nos provee esta funcionalidad.

Después de leer esta entrada, pudieras pensar que a final de cuentas los tres diccionarios especializados son una pérdida de tiempo. Al fin y al cabo, Hashtable puede hacer todo el trabajo, y quizás una diferencia de dos segundos no parezca significativa para un programa de negocios tradicional. Pero estas tres clases muestran la riqueza del .NET Framework, dado que proveen opciones para escenarios muy específicos. Y ciertamente, vale la pena, creo, conocerlos para poder sacarles provecho cuando nos encontremos en una situación similar.

Ahora que por supuesto, estos tres diccionarios no son los únicos que hay. En entradas futuras veremos otros tipos de diccionarios diseñados para otras situaciones específicas, pero también algunos de propósito general. No te pierdas las siguientes entradas en la serie, para conocer más sobre este fascinante y amplio tema de las colecciones en .NET.

Categorías:.NET Framework, C#, Tutorial Etiquetas:

Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Algunas colecciones para trabajar con texto


A lo largo de esta serie “Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar” hemos tratado con implementaciones de colecciones y diccionarios que vieron la luz del día en la primera versión del .NET Framework, cuando todavía no había clases genéricas. En aquella época, la norma era que cuando se necesitaba una colección fuertemente tipada el programador creaba una clase que implementara ICollection o IDictionary, internamente utilizara un ArrayList o un Hashtable, y actuara como envoltorio sobre ésta. Por supuesto, con la llegada de Generics en .NET 2.0, ésta práctica comenzó a caer en desuso (por ejemplo, ahora es más común derivar de List<T>, de Collection<T> o Dictionary<TKey, TValue>, pero todavía falta para que veamos Generics en esta serie).

Sin embargo, los propios programadores de .NET crearon una serie de clases para este escenario, sobre todo que utilizaran mucho. Por ejemplo, la clase System.Web.HttpRequest tiene una propiedad llamada QueryString, que se utiliza para acceder a un diccionario en donde la llave y el valor son ambos cadenas de texto.

Así, en este apunte vamos a explorar algunas de las clases que podemos utilizar, en particular, para trabajar con cadenas de texto: StringCollection, StringDictionary y NameValueCollection, todas dentro del espacio de nombres System.Collections.Specialized.

La primera clase es StringCollection. Como seguramente habrás inferido, ésta representa una colección de cadenas de texto, y está particularmente optimizada para trabajar con cadenas de texto. Recordemos que en .NET las cadenas de texto son inmutables, por lo que el empleo de éstas debe realizarse de forma cuidadosa para evitar caer en problemas de rendimiento.

Como cabría esperar, la colección cuenta con varias propiedades estándares, como SyncRoot e IsSynchronized para temas de concurrencia y sincronización en el acceso a elementos; Count para obtener el número de elementos que tiene la colección; IsReadOnly para saber si podemos agregar o eliminar elementos, y finalmente un indexador, a través del cuál podemos acceder a las cadenas de texto dado un índice determinado.

Además, también cuenta con los métodos tradicionales: Add y Remove para añadir o eliminar una cadena determinada; Insert para añadir una cadena en una determinada posición; AddRange para añadir un array de cadenas de texto de un solo golpe, y Clear para remover todas las cadenas existentes; CopyTo para copiar el contenido de la colección a un array unidimensional e IndexOf para obtener el índice de un elemento determinado (o –1 si no encuentra algo).

Realmente es una colección sencilla, y su razón de ser es precisamente ser una colección fuertemente tipada. El siguiente programita muestra un sencillo ejemplo sobre el uso de StringCollection.

using System;
using System.Collections.Specialized;
using System.Linq;

namespace Fermasmas.Wordpress.Com
{
    class Program
    {
        static void Main(string[] args)
        {
            StringCollection strings = new StringCollection();
            strings.Add("Jetzt laden die Vampire zum Tanz");

            string[] strs = new string[] {
                "Steckt den Himmel im Brand",
                "und streut Luzifer Rosen!",
                "die Welt gehört den Lüngern",
                "und den Rücksichtlosen"
            };
            strings.AddRange(strs);
            strings.Insert(1, "Wir wollen alles und Ganz!");

            if (strings.Contains("Jetzt laden die Vampire zum Tanz"))
            {
                int index = strings.IndexOf("Jetzt laden die Vampire zum Tanz");
                Console.WriteLine(strings[index]);
            }

            foreach (string str in strings)
                Console.WriteLine(str);
            Console.WriteLine();

            var query = from string str in strings
                        where str.Contains("und")
                        select str;
            foreach (string str in query)
                Console.WriteLine(str);

            strings.Clear();

            Console.ReadKey(true);
        }
    }
}

StringCollection no cuenta con métodos sofisticados para realizar búsquedas. Sin embargo, nada nos detiene de utilizar algún método en particular, digamos LINQ, como se muestra en las líneas 33 a 37 del ejemplo anterior. A continuación, la salida del programa.

Jetzt laden die Vampire zum Tanz
Jetzt laden die Vampire zum Tanz
Wir wollen alles und Ganz!
Steckt den Himmel im Brand
und streut Luzifer Rosen!
die Welt gehört den Lüngern
und den Rücksichtlosen

Wir wollen alles und Ganz!
und streut Luzifer Rosen!
und den Rücksichtlosen

La segunda clase que me gustaría mostrar es StringDictionary. Así como StringCollection es una implementación similar a ArrayList pero fuertemente tipada, StringDictionary implementa un Hashtable pero fuertemente tipado para emplear cadenas de texto.

Por ende, podemos encontrar métodos similares a los que tenemos en StringCollection: Add y Remove para añadir y quitar pares llave-valor del diccionario, ContainsKey y ContainsValue para saber si una llave o un valor están determinadas, y las propiedades Count, Keys y Values para contar el número de elementos, obtener todas las llaves y todos los valores, respectivamente.

using System;
using System.Collections.Specialized;
using System.Linq;
using System.Collections;

namespace Fermasmas.Wordpress.Com
{
    class Program
    {
        static void Main(string[] args)
        {
            StringDictionary dic = new StringDictionary();
            dic.Add("Chorus 1", "Steckt den Himmel in Brand");
            dic.Add("Chorus 2", "und streut Luzifer Rosen!");
            dic.Add("Chorus 3", "die Welt gehört den Lüngern");
            dic.Add("Chorus 4", "und den Rücksichtlosen");

            Console.WriteLine("Chorus 1: {0}", dic["Chorus 1"]);
            Console.WriteLine();

            foreach (DictionaryEntry entry in dic)
                Console.WriteLine("{0}: {1}", entry.Key, entry.Value);

            foreach (string key in dic.Keys)
                Console.WriteLine(key);

            Console.ReadKey(true);
        }
    }
}

El programa anterior genera esta salida.

Chorus 1: Steckt den Himmel in Brand

chorus 3: die Welt gehört den Lüngern
chorus 2: und streut Luzifer Rosen!
chorus 4: und den Rücksichtlosen
chorus 1: Steckt den Himmel in Brand
chorus 3
chorus 2
chorus 4
chorus 1

Nota que en la salida, cuando pintamos las llaves, nos regresa un valor en minúsculas, cuando nosotros las añadimos en mayúsculas. Esto es importante, dado que internamente StringDictionary no distingue entre mayúsculas y minúsculas para las llaves, una característica a tener en cuenta.

Finalmente, tenemos la colección NameValueCollection. En la práctica, ésta se comporta de forma muy similar a StringDictionary: nos permite agrupar pares llave-valor. Pero esta clase es una colección, no un diccionario, y ahí radica la principal diferencia. Por principio, NameValueCollection nos permite acceder a los elementos vía un índice, además de la llave. Además cuenta con constructores un poco más versátiles que nos permiten especificar el comparador (si es sensible a mayúsculas y minúsculas, por ejemplo).

using System;
using System.Collections.Specialized;
using System.Linq;
using System.Collections;

namespace Fermasmas.Wordpress.Com
{
    class Program
    {
        static void Main(string[] args)
        {
            NameValueCollection col = new NameValueCollection();
            col.Add("Chorus 1", "Steckt den Himmel in Brand");
            col.Add("Chorus 2", "und streut Luzifer Rosen!");
            col.Add("Chorus 3", "die Welt gehört den Lüngern");
            col.Add("Chorus 4", "und den Rücksichtlosen");

            Console.WriteLine("Chorus 1: {0}", col["Chorus 1"]);
            Console.WriteLine();

            foreach (string key in col.AllKeys)
                Console.WriteLine(key);
            Console.WriteLine();

            for (int i = 0; i < col.Count; i++)
                Console.WriteLine("{0}: {1}", col.GetKey(i), col.Get(i));

            Console.ReadKey(true);
        }
    }
}

Su salida:

Chorus 1: Steckt den Himmel in Brand

Chorus 1
Chorus 2
Chorus 3
Chorus 4

Chorus 1: Steckt den Himmel in Brand
Chorus 2: und streut Luzifer Rosen!
Chorus 3: die Welt gehört den Lüngern
Chorus 4: und den Rücksichtlosen

Notarás que la forma de emplear esta clase difiere un poquito de StringDictionary, pero se obtiene prácticamente el mismo resultado.

NameValueCollection se utiliza en muchos lugares del .NET Framework, como en los parámetros de consulta de una página web o bien para leer archivos de configuración. De ahí la importancia que tiene.

¿Cómo saber cuándo usar NameValueCollection y StringDictionary? En esencia, la respuesta se base en si necesitas tener una colección (ICollection) o un diccionario (IDictionary) respectivamente. Aunque se ha de reconocer que NameValueCollection es un poquitín más versátil de StringDictionary.

Ya para terminar, me gustaría que leyeras este pequeño artículo sobre cómo leer la configuración de la aplicación en un archivo web.config, que se encuentra en MSDN, para que veas una aplicación más de NameValueCollection.

Jetzt laden die Vampire zum Tanz, wir wollen alles und ganz!

Categorías:.NET Framework, C#, Tutorial Etiquetas: , ,

Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Banderas y arreglos de bits


Para esta serie de “todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar” me he dado a la tarea de documentar y tratar de explicar las clases que se utilizan para las colecciones, con el propósito de que conozcamos todo lo que el .NET Framework tiene que darnos, en aras de evitar escribir código más estandarizado y robusto. En esta ocasión hablaré de una pequeña clase poco utilizada que bien nos puede salvar de problemas cuando tengamos que trabajar con muchos valores lógicos (booleanos): BitArray.

Esta clase, ubicada en el espacio de nombres System.Collections, nos permite manipular valores booleanos de forma fácil y sencilla. Esto podría no parecer de mucha utilidad, pero hay veces en los que necesitamos crear sistemas que manipulen el estado de un objeto (por ejemplo, una máquina de estados). Cada estado puede ser representado por un valor booleano, o bandera: verdadero o falso, prendido o apagado, etc. Por supuesto, lo primero que viene a la mente es crear una variable de tipo bool para cada bandera. Pero esto puede ser engorroso si tenemos muchas banderas: no solo hace nuestro manejo de banderas algo verboso, sino que hacer operaciones lógicas puede hacernos escribir grandes líneas de código. Es aquí donde BitArray puede sernos de utilidad.

Comencemos por exponer información sobre la clase. Un BitArray, en primer lugar, no permite agregar o añadir elementos: algo contra-intuitivo tratándose de una colección (BitArray implementa ICollection, después de todo). Pero piénsalo de esta forma: un conjunto de estados de un objeto determinado suele estar definido de antemano. En consecuencia, el tamaño del arreglo se determina en el constructor. Veamos algunos constructores.

BitArray bits1 = new BitArray(10);

BitArray bits2 = new BitArray(bits1);

boo[] boolArray = new bool[] { true, true, false, true, false, false, false };
BitArray bits3 = new BitArray(boolArray);

BitArray bits4 = new BitArray(10, true);

byte[] byteArray = new byte[] { 0xff, 0x00 };
BitArray bits5 = new BitArray(byteArray);

La primera llamada nos genera un array con diez bits. La segunda llamada nos genera un array el cual copia el tamaño y los bits contenidos en el primer array. El tercer arreglo se crea con siete bits de la forma 1101000, y la siguiente llamada nos genera un arreglo de diez bits, todos inicializados a 1. Finalmente, la quinta llamada nos genera un array de 16 bits, con los primeros ocho bits establecidos a 1 y los siguientes ocho establecidos a 0.

Como puedes ver, crear un BitArray no es nada complicado. Una vez creado, podemos emplear métodos útiles, de los cuales algunos se implementan de ICollection y otros nos permiten manipular los bits y hacer cálculos sobre ellos. Por ejemplo, Clone nos permite crear un nuevo BitArray copiando los valores del actual, mientras que CopyTo nos permite copiar los valores a un array cualquiera. Get y Set nos permiten leer y escribir un bit en determinada posición, mientras que SetAll establece todos los bits a 1 o 0.

Asimismo, BitArray cuenta con algunos métodos para hacer operaciones lógicas a nivel de bits. And y Or nos permite hacer una comparación lógica conjuntiva y disyuntiva, respectivamente, mientras que Not niega cada uno de los bits. Xor es similar a Or, pero es una disyunción excluyente. Nota que al hacer estas operaciones, se modifica el objeto actual con el resultado. Un ejemplo:

BitArray bits1 = new BitArray(new byte[] { 0xF });
var val = new bool[] { true, true, false, true, true, false, false, true })
BitArray bits2 = new BitArray(val);

bits1.Print();              // 11110000
bits2.Print();              // 11011001
bits1.And(bits2).Print();   // 11010000
bits1.Xor(bits2).Print();   // 00001001
bits1.Or(bits2).Print();    // 11011001
bits1.Not().Print();        // 00100110

El siguiente ejemplo muestra cómo podemos utilizar un BitArray para almacenar el estado de un objeto. Para este caso, creamos una clase llamada Order, que simula una orden de trabajo. Algunos métodos cambian el estado del mismo, por lo que podemos apreciar cómo va evolucionando.

using System;
using System.Collections;
using System.Text;

namespace Fermasmas.Wordpress.Com
{
    class Order
    {
        private BitArray _status;
        private string _number;

        public Order()
        {
            _number = string.Empty;
            _status = new BitArray(8, false);
            _status.Set(0, true);
        }

        public bool IsNew { get { return _status.Get(0); } }
        public bool IsDirty { get { return _status.Get(1); } }
        public bool IsDeleted { get { return _status.Get(2); } }
        public bool IsShipping { get { return _status.Get(3); } }
        public bool IsCanceled { get { return _status.Get(4); } }
        public bool IsComplete { get { return _status.Get(5); } }
        public bool IsError { get { return _status.Get(6); } }
        public bool IsClosed { get { return _status.Get(7); } }

        public override string ToString()
        {
            return new StringBuilder()
                .AppendFormat("New: {0}\n", IsNew)
                .AppendFormat("Dirty: {0}\n", IsDirty)
                .AppendFormat("Deleted: {0}\n", IsDeleted)
                .AppendFormat("Shipping: {0}\n", IsShipping)
                .AppendFormat("Canceled: {0}\n", IsCanceled)
                .AppendFormat("Complete: {0}\n", IsComplete)
                .AppendFormat("Error: {0}\n", IsError)
                .AppendFormat("Closed: {0}\n\n", IsClosed)
                .ToString();
        }

        public string Number
        {
            get { return _number; }
            set
            {
                _number = value;
                _status.Set(1, true);
            }
        }

        public void Delete()
        {
            _status.Set(2, true);
        }

        public void Save()
        {
            _status.Set(1, false);
        }

        public void ShipOrder()
        {
            _status.Set(3, true);
        }

        public void Cancel()
        {
            _status.Set(4, true);
        }

        public void Complete()
        {
            _status.Set(5, true);
        }

        public void ReportError()
        {
            _status.Set(6, true);
        }

        public void Close()
        {
            _status.Set(7, true);
        }

    }

    class Program
    {
        static void Main(string[] args)
        {
            Order order = new Order();
            Console.WriteLine(order);

            order.Number = "99901";
            Console.WriteLine(order);
            order.Save();
            order.ShipOrder();
            Console.WriteLine(order);
            order.ReportError();
            order.Cancel();
            order.Close();
            Console.WriteLine(order);

            Console.ReadKey(true);
        }
    }
}

La salida de este programa es la siguiente.

New: True
Dirty: False
Deleted: False
Shipping: False
Canceled: False
Complete: False
Error: False
Closed: False


New: True
Dirty: True
Deleted: False
Shipping: False
Canceled: False
Complete: False
Error: False
Closed: False


New: True
Dirty: False
Deleted: False
Shipping: True
Canceled: False
Complete: False
Error: False
Closed: False


New: True
Dirty: False
Deleted: False
Shipping: True
Canceled: True
Complete: False
Error: True
Closed: True

Como puedes ver, BitArray es una clase útil de conocer, aunque concedido, no siempre se utiliza. Pero también puedes ver que cuando trabajamos con muchos estados puede ser una forma más eficiente de solucionar el problema.

Eso es todo por el momento. Noi ci vediamo!

ADDENDUM

BitArray tiene una clase muy similar, hermana diría yo: BitVector32, ubicada en el espacio de nombres System.Collections.Specialized. Al igual que BitArray, esta clase se utiliza para guardar valores booleanos (banderas), pero con ciertas diferencias.

En primer lugar, BitVector32 es una estructura, y por tanto, un tipo-valor. Esto quiere decir que si yo asigno una instancia a una variable, dicha instancia será copiada. Y en segundo lugar, BitVector32 tiene un tamaño fijo: 32 bits. Esto la hace más eficiente en ciertos escenarios, dado que BitArray mantiene estados para hacer crecer el tamaño de bits que utiliza.

BitVector32 cuenta, además, con un método (estático) utilísimo cuando tratamos con banderas: CreateMask. Este método genera máscaras de bits en base a una máscara anterior. Por ejemplo, CreateMask() regresa un BitVector con la máscara 00000001. Si llamo otra vez a CreateMask, pasándole como parámetro la primera máscara, me regresa 00000010. Una nueva llamada en forma similar, regresaría 00000100. Y así sucesivamente.

No dejes de darle una revisada a la documentación en MSDN.

Categorías:.NET Framework, C#, Tutorial Etiquetas: ,

Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Hashtable


Retomando la serie de las colecciones, tras un período de silencio… Hoy me gustaría comenzar a hablar sobre los diccionarios. Este tema es un poquito más complicado que las listas. Ya en otra entrada había hablado un poco sobre diccionarios. Ahora me interesa ver lo que probablemente sea el diccionario más sencillo (y quizás uno de los más potentes) que existe desde la primera versión del .NET Framework: Hashtable.

Esta clase se define en el espacio de nombres System.Collections. Y lo primero que hay que tener en cuenta es que es un diccionario, y por lo tanto funciona como cualquier otro diccionario. El siguiente ejemplo muestra cómo utilizar el Hashtable.

using System;
using System.Collections;

namespace Fermasmas.Wordpress.Com
{
  enum Gender { Male, Female }

  class God
  {
    public string Name { get; set; }
    public Gender Gender { get; set; }
    public string Influence { get; set; }

    public God()
      : this(string.Empty, Gender.Female, string.Empty)
    {
    }

    public God(string name, Gender gender, string influence)
    {
      Name = name ?? string.Empty;
      Gender = gender;
      Influence = influence;
    }

    public override string ToString()
    {
      return string.Format("{0} ({1}) - {2:C}", Name, Gender, Influence);
    }
  }

  class Program
  {    
    static void Main(string[] args)
    {
      Hashtable hash = new Hashtable();
      hash.Add("Odin", new God("Odin", Gender.Male, "Cielo"));
      hash.Add("Freyja", new God("Freyja", Gender.Female, "Fertilidad"));
      hash.Add("Thor", new God("Thor", Gender.Male, "Humanos"));
      hash.Add("Skadi", new God("Skadi", Gender.Female, "Muerte"));
      hash.Add("Loki", new God("Loki", Gender.Male, "Aire"));

      Console.WriteLine(hash["Odin"]);
      Console.WriteLine(hash["Loki"]);
      Console.WriteLine(hash["Thor"]);
      Console.WriteLine();

      foreach (DictionaryEntry entry in hash)
      {
        Console.WriteLine("{0} - {1}", entry.Key, entry.Value);
      }

      Console.ReadKey(true);
    }
  }
}

Este código no tiene mucha ciencia. Inicializamos una instancia de la clase Hashtable y le agregamos algunos elementos, que son objetos de la clase God que creamos unas líneas arriba y que representan uno de los dioses nórdicos Asgard. Al agregar un elemento, especificamos la llave (que en nuestro caso, sería el nombre del dios nórdico que representa el objeto). Tras agregas cinco objetos, vemos que podemos obtener el objeto en cuestión dada su llave. Esto era de esperarse, ya que Hashtable es un diccionario.

Ahora bien, hay algunas cosillas a considerar. En primer lugar, para iterar sobre los elementos de un diccionario, lo tenemos que hacer sobre objetos de tipo DictionaryEntry. Esta clase contiene dos propiedades: Key y Value, que contienen la llave y el valor.

Por otra parte, si no queremos usar DictionaryEntry, también podemos iterar sobre todas las llaves disponibles, a través de Hashtable.Keys, y con eso obtener el valor usando el indexador:

foreach (string key in hash.Keys)
{
    Console.WriteLine("{0} - {1}", key, hash[key]);
}

y obtenemos el mismo resultado.

Una cuestión importante del Hashtable es la forma en la que el diccionario ordena los elementos. Internamente, cuando se agrega un nuevo elemento, el diccionario lo guarda especialmente utilizando lo que se conoce como “hash code”, el cual es un número que no debe de cambiar bajo las mismas condiciones. Por ejemplo, si genero un hash code para un entero cuyo valor es igual a 5, otro entero con el mismo valor me debe regresar el mismo hash code. Esta técnica hace que los objetos (siempre de forma interna) se almacenen en ciertas ubicaciones de memoria, lo cual hace que cuando queremos obtener el valor dada una llave determinada, se obtenga dicha ubicación por medio del hash code sin tener que hacer tantas comparaciones de las llaves. Y esto es lo que hace del Hashtable uno de los diccionarios más eficientes.

De lo anterior se desprenden tres cosas. Primero, el objeto que se usa como llave debe permanecer inmutable mientras actúe como tal, si no se pueden obtener resultados erróneos. Segundo, por consiguiente, las llaves no pueden ser nulas. Y tercero, es imprescindible que cuando dos llaves contengan el mismo valor (o que se encuentren en el mismo estado) el hash code regresado sea el mismo. En otras palabras, cuando dos objetos obj1 y obj2 son iguales (es decir, obj1.Equals(obj2) regresa true) entonces los hash codes de ambos deben ser iguales.

Ahora bien, ¿cómo se regresa ese hash code? Hay dos formas que son esencialmente las mismas. Habrás notado que la clase object define unos cuántos métodos como ToString, GetType e Equals. Pues bien, el otro método es ni más ni menos que GetHashCode. Hashtable utiliza el valor retornado por GetHashCode. Así, el primer método consiste en sobreescribir GetHashCode y que éste valor regrese un número apropiado. Y por las reglas que establece .NET, al sobreescribir GetHashCode es necesario sobreescribir Equals. A la luz de lo expuesto, ésto tiene lógica: si dos llaves son iguales, entonces el hash code debe ser el mismo.

La segunda forma consiste en implementar la interfaz IEqualityComparer (a partir de .NET 2; en .NET 1 y .NET 1.1 las interfaces son IHashCodeProvider y IComparer). Esta interfaz define (tatatatáaaan) dos métodos. Equals y GetHashCode. Por lo que es prácticamente lo mismo que usar la primera técnica. Nota mental: yo pienso que la única ventaja de implementar IEqualityComparer es que ésta se puede implementar de forma explícita, de tal suerte que se puede dejar la versión original de Equals y GetHashCode tal cual.

En .NET framework y C#, todos los tipos de datos primitivos que son tipos-valor (estructuras) son naturalmente inmutables. Un int, un decimal y un float lo son (asignarle un valor a una variable implica crear una nueva instancia del tipo de dato). Y por definición, ningún tipo-valor puede ser nulo. Finalmente, cada tipo de dato primitivo implementa GetHashCode en función del valor mismo, de tal suerte que éstos siempre serán únicos. Por lo que todos los tipos de datos primitivos que son tipo-valor se pueden emplear sin problemas como llaves para un Hashtable.

Adicionalmente, los tipos de datos string, a pesar de ser referencias, también son inmutables (la especificación de tipos de datos comunes así lo garantiza), y además implementan como cabría esperar GetHashCode, de tal suerte que siempre que una cadena no sea nula, será también susceptible de emplearse en un Hashtable. Es por esto que nuestro ejemplo anterior funciona correctamente.

Los problemas pueden comenzar cuando queramos utilizar nuestras propias clases como llaves para nuestro Hashtable. En este caso, será nuestra responsabilidad que la clase que usemos como llave implemente Hashtable de forma correcta.

A guisa de ejemplo para ilustrar lo anterior, imaginemos este escenario. Supongamos que queremos hacer una relación entre dioses nórdicos y el equivalente dios (o semidiós) romano. Por ejemplo, queremos relacionar a Odín con Júpiter, a Thor con Hércules y a Freyja con Venus. En este caso, usaremos la clase God como llave y como valor, por lo que tenemos que implementar GetHashCode. Tomemos estos objetos:

God odin = new God("Odín", Gender.Male, "Cielo");
God thor = new God("Thor", Gender.Male, "Humanos");
God freyja = new God("Freyja", Gender.Female, "Fertilidad");

God jupiter = new God("Júpiter", Gender.Male, "Cielo");
God hercules = new God("Hércules", Gender.Male, "Humanos");
God venus = new God("Venus", Gender.Female, "Fertilidad");

Entonces, para garantizar que nuestro Hashtable siempre funcione (especialmente cuando tenemos muchas llaves) de forma eficiente, tenemos que garantizar que dos instancias con “Odín”, Gender.Male, “Cielo” siempre regresen verdadero y que además el hash code que retornen sea el mismo. Si hacemos:

Console.WriteLine(odin.Equals(jupiter));
Console.WriteLine(odin.GetHashCode() == jupiter.GetHashCode());

pues ya valió queso, porque al ejecutar ambas líneas de código, se escribirá “False” dos veces. Entonces no queda remedio más que implementar GetHashCode, y por añadidura, Equals.

Una buena regla a seguir consiste en pensar primero en Equals. ¿De qué forma dos objetos como los anteriores serían iguales? La primera respuesta natural que viene a la mente es que las propiedades de ambos objetos sean iguales. Así, la implementación de Equals en la clase God podría quedar como sigue.

public override bool Equals(object obj)
{
    God god = obj as God;
    return god != null
        && Name == god.Name
        && Gender == god.Gender
        && Influence == god.Influence;
}

Ahora bien, si la igualdad es determinada por las tres propiedades, suena lógico que GetHashCode la implementemos con base en estas tres. Pero necesitamos garantizar que éstas sean siempre iguales cuando Equals sea igual. ¿Cómo se te ocurre que podría ser?

Si pensamos, al combinar los caracteres de las tres propiedades (representadas como cadena de texto)  siempre serán las mismas cuando Equals regrese true (por ejemplo, “OdínMaleCielo”). Y como el hash code de una cadena de texto garantiza ser el mismo para todas, pues ya estuvo: podemos usar esta técnica y GetHashCode luciría así:

public override int GetHashCode()
{
    string code = string.Format("{0}{1}{2}", Name, Gender, Influence);
    return code.GetHashCode();
}

Supremo, ¿no? Ahora sí, podemos probar este código:

God odin1 = new God("Odín", Gender.Male, "Cielo");
God odin2 = new God("Odín", Gender.Male, "Cielo");
Console.WriteLine(odin1.Equals(odin2));
Console.WriteLine(odin1.GetHashCode() == odin2.GetHashCode());

Y obtendremos dos valores True en la consola. Ahora sí, ya podemos usar sin temor alguno la clase God como llave en el Hashtable. El programa completo luce algo similar a esto:

using System;
using System.Collections;

namespace Fermasmas.Wordpress.Com
{
    enum Gender { Male, Female }

    class God
    {
        public string Name { get; set; }
        public Gender Gender { get; set; }
        public string Influence { get; set; }

        public God()
            : this(string.Empty, Gender.Female, string.Empty)
        {
        }

        public God(string name, Gender gender, string influence)
        {
            Name = name ?? string.Empty;
            Gender = gender;
            Influence = influence;
        }

        public override string ToString()
        {
            return string.Format("{0} ({1}) - {2:C}", Name, Gender, Influence);
        }

        public override int GetHashCode()
        {
            string code = string.Format("{0}{1}{2}", Name, Gender, Influence);
            return code.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            God god = obj as God;
            return god != null
                && Name == god.Name
                && Gender == god.Gender
                && Influence == god.Influence;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            God odin = new God("Odín", Gender.Male, "Cielo");
            God thor = new God("Thor", Gender.Male, "Humanos");
            God freyja = new God("Freyja", Gender.Female, "Fertilidad");

            God jupiter = new God("Júpiter", Gender.Male, "Cielo");
            God hercules = new God("Hércules", Gender.Male, "Humanos");
            God venus = new God("Venus", Gender.Female, "Fertilidad");

            Hashtable hash = new Hashtable();
            hash.Add(odin, jupiter);
            hash.Add(thor, hercules);
            hash.Add(freyja, venus);

            Console.WriteLine("Odín: {0}", hash[odin]);
            Console.WriteLine("Thor: {0}", hash[thor]);
            Console.WriteLine("Freyja: {0}", hash[freyja]);
            Console.WriteLine();

            Console.ReadKey(true);
        }
    }
}

Evidentemente, la forma en la que determinemos los valores de GetHashCode a emplear lo determina la semántica de la clase. Por ejemplo, en el código anterior puedes pensar que un dios que tenga el mismo nombre sean siempre iguales sin importar su género y su influencia. En este caso, Equals compararía nada más la propiedad Name, y GetHashCode regresaría el hash code devuelto por Name. Esto puede parecer ilógico, pero es natural cuando trabajamos con clases que representan objetos de negocio cuyo contenido se extrae de una base de datos: las llaves de la tabla son las que definen los valores únicos del regristro. Por lo que cabría esperar que Equals y GetHashCode se definan en función de las propiedades que representan las llaves de la tabla.

Y ya para finalizar este artículo, me gustaría comentar algunas propiedades y métodos útiles con los que cuenta Hastable. Es decir, adicionales a las esperadas en un diccionario. En primera instancia, tenemos que los métodos ContainsKey y ContainsValue se pueden usar para saber si una llave o un valor existen dentro de la colección. CopyTo, por su parte, copia los elementos a un array unidimensional.

Bueno mis estimados, hemos visto ya cómo utilizar Hashtable, así como las bondades que nos ofrece, pero también los cuidados que hemos de proporcionarle. Sin embargo, hay que reconocerlo, en la mayoría de los casos no necesitamos diccionarios tan eficientes como Hashtable. Existen otras opciones de diccionarios introducidas a partir de .NET 2, sobresaliendo System.Generics.Dictionary<T, T>, el cual además tiene la ventaja de contar con llaves y valores fuertemente tipados. Pero esto será tema de otro post. Así que hasta aquí llegamos. Espera la continuación de esta serie en unos días.

Categorías:.NET Framework, C#, Tutorial Etiquetas: ,

Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Pilas y colas


Cualquier programador que haya estudiado estructuras de datos conocerá las pilas y las colas. Junto con las listas enlazadas, los arrays y los diccionarios, forman el conjunto básico de estructuras de datos. El .NET Framework implementa clases para estas estructuras, y que son colecciones porque derivan de ICollection. Sin embargo, difieren en concepto e implementación de las listas y los diccionarios que hasta el momento hemos visto.

Definición

Una pila (stack, en inglés) es una estructura de datos a la que se le van agregando objetos y no cuenta con acceso aleatorio (es decir, a través de un indexador) sino secuencial. La secuencia en la que se obtienen los objetos almacenados es de la forma últimas entradas primeras salidas.

Considera un montón de monedas que queremos apilar. Conforme vamos colocando las monedas queda patente que la última que colocamos es la que está hasta arriba, es decir, la primera que vemos. Si añadimos una de un peso, una de dos, una de cinco y una de diez, y en este momento comenzamos a remover, las iríamos escogiendo en orden inverso a como fueron colocadas: primero la de diez pesos, luego la de cinco, la siguiente es la de dos y por último, la de un pesito. Este es precisamente el concepto de pila y más general, el concepto de últimas entradas y primeras salidas.

Nota también que al ir añadiendo monedas, una vez que coloco la moneda de dos pesos la de uno queda totalmente inaccesible, a menos que primero quite la de dos y ahora sí la de un peso. Esto ilustra una propiedad de las pilas: no cuentan con acceso aleatorio. Aunque de hecho en el ejemplo en cuestión sí podría obtener la moneda de uno, pero tendría que partir la pila en dos y remover de golpe las monedas que hay arriba, con el riesgo de que la pila puede caerse. Es decir, el proceso de hacerlo es costoso y la ventaja de tener la pila se pierde totalmente.

Una cola es muy similar a una pila. Tampoco cuentan con acceso aleatorio, sino secuencial. Esta secuencia sigue la forma de primeras entradas primeras salidas.

Un ejemplo que encaja a la perfección es la fila de personas frente a una taquilla de boletos en un estadio de Sudáfrica para el encuentro entre México y Francia (el cual, debo añadir orgullosamente, ganamos esta tarde por marcador de dos a cero). Conforme la gente va llegando a la fila, en ese orden se le vende el boleto de entrada: el vendedor atiende al primero que llegó, luego al que está atrás, etcétera. Un intento por saltar este orden terminaría en un grupo numeroso de aficionados enojados.

Estos conceptos son sencillos y sin embargo muy útiles, y por ello el .NET Framework les dedica especial atención al proveer dos clases en el espacio de nombres System.Collections: Stack para las pilas y Queue para las colas.

La clase Stack

Comencemos por la clase Stack. En primera instancia, esta clase implementa las interfaces IEnumerable, que nos permite enumerar los elementos de la pila, e ICollection, que de buenas a primeras nos permite contar el número de elementos, copiar el contenido a un array y tener un acceso sincronizado a los elementos.

Stack cuenta con tres constructores: uno por defecto, uno que toma como parámetro un ICollection y que agrega los elementos de dicha colección a la pila, y uno que toma un número entero indicando la capacidad inicial (recuerda que las colecciones crecen al paso del tiempo, y cada vez que crecen tienen que aumentar su tamaño en memoria; por ende si sabemos anticipadamente cuántos elementos tendrá la colección podemos especificar la capacidad para no tener que estar haciendo redimensionamiento, obteniendo un mejor rendimiento del procesador).

Posteriormente contamos con algunos métodos que nos son familiares. Clear elimina todo el contenido de la pila, Contains nos indica si la colección contiene un objeto determinado, CopyTo copia el contenido de la pila aun array y ToArray regresa un array con los elementos que contiene la pila.

Pero quizás los métodos más importantes sean Push y Pop. Push es muy similar al Add de las listas: nos permite añadir un elemento a la pila, mientras que Pop regresa el último elemento añadido (recuerda: últimas entradas primeras salidas) y lo elimina de la colección. El siguiente ejemplo crea un objeto Stack, le añade algunos elementos usando Push y luego los obtiene usando Pop.

Stack stack = new Stack(10);
stack.Push("Carlos Salcido");
stack.Push("Rafael Márquez");
stack.Push("Javier Hernández");
stack.Push("Giovani Dos Santos");
stack.Push("Carlos Vela");

while (stack.Count > 0)
{
    string mexicanPlayer = stack.Pop() as string;
    Console.WriteLine(mexicanPlayer);
}

Console.ReadKey(true);

Al ejecutar este programa obtenemos la siguiente salida en la consola.

Carlos Vela
Giovani Dos Santos
Javier Hernández
Rafael Márquez
Carlos Salcido

Como era de esperarse, la salida de los nombres de algunos jugadores de la Selección Mexicana de Fútbol se da en el orden inverso al que fueron añadidos: últimas entradas primeras salidas.

Ahora bien, al hacer uso de Pop obtenemos el elemento pero también lo removemos de la colección. Esto puede convertirse en un lío cuando solo queramos leer el siguiente elemento, sin removerlo de la colección. Para solventar este problema, contamos con el método Peek. Este método devuelve el mismo elemento que devolvería Pop, pero sin eliminarlo de la colección.

Stack stack = new Stack(10);
stack.Push("Carlos Salcido");
stack.Push("Rafael Márquez");
stack.Push("Javier Hernández");
stack.Push("Giovani Dos Santos");
stack.Push("Carlos Vela");

string mexicanPlayer = stack.Peek() as string;
Console.WriteLine("Jugador: {0}", mexicanPlayer);
Console.WriteLine();

foreach (string player in stack)
    Console.WriteLine(player);

En este ejemplo, usamos Peek para obtener el siguiente jugador de la pila (es decir, el último) que en este caso será Carlos Vela. Luego hacemos un foreach, que imprime a los cinco jugadores, demostrando cómo Peek no elimina el elemento de la colección.

La clase Queue

La clase Queue representa una cola, y es muy similar a la clase Stack. También implementa IEnumerable e ICollection y tiene prácticamente los mismos métodos que Stack. Sin embargo, en lugar de Push y Pop, esta clase cuenta con los métodos Enqueue y Dequeue para añadir un elemento a la fila y para obtener y remover el primer elemento de la cola (recuerda: primeras entradas, primeras salidas. Por lo demás, las clases son prácticamente idénticas.

Queue queue = new Queue(5);
queue.Enqueue("Carlos Salcido");
queue.Enqueue("Rafael Márquez");
queue.Enqueue("Javier Hernández");
queue.Enqueue("Giovani Dos Santos");
queue.Enqueue("Carlos Vela");

while (queue.Count > 0)
{
    string mexicanPlayer = queue.Dequeue() as string;
    Console.WriteLine(mexicanPlayer);
}

Como cabría esperar, este código imprime los nombres de los jugadores en el orden en el que fueron añadidos a la colección.

Carlos Salcido
Rafael Márquez
Javier Hernández
Giovani Dos Santos
Carlos Vela

Un método extra que tiene Queue pero no tiene Stack es el método TrimToSize. Este método redimensiona el bloque de memoria interna para que su tamaño sea equivalente al número de elementos de la colección. Esto es útil en caso de que tengamos una cola con muchos elementos, digamos mil, y removemos una gran cantidad, digamos quinientos. Aunque removamos los elementos, la cola seguirá almacenando suficiente memoria para mil elementos, convirtiéndose en un desperdicio de memoria. Si sabemos que por el momento la cola no aumentará de tamaño, sería bueno invocar a TrimToSize para liberar la memoria reservada.

Y bueno, eso es todo con respecto a estas clases. Realmente son muy sencillas y su manejo no debería darnos problemas.

Escenarios de uso

Quizás no te quede claro bajo qué circunstancias podríamos emplear alguna de estas clases. Pues bien, la parte final de esta entrada te mostrará algunos escenarios de uso para las pilas y colas.

Mensajes

Quizás una de las aplicaciones de las colas más comunes son los mensajes. Considera este escenario: tienes un método que realiza ciertas operaciones y cada operación puede lanzar un mensaje que deberá ser procesado por otra entidad en el orden en el que fueron creados.

El sistema gráfico de Windows es un ejemplo de ello. Cada vez que se genera algún evento en la interfaz gráfica (un clic del ratón o una tecla pulsada) se genera un Windows Message (WM). Cada WM se almacena en una cola, y hasta que el sistema operativo le pasa el control a la aplicación, ésta deberá responder uno a uno a los mensajes enviados, conforme fueron generados. Esta forma de trabajo se hace en forma paralela, así que múltiples hilos entran en juego.

El siguiente código emula un sistema de mensajes donde un hilo se encarga de generar dichos mensajes mientras que el hilo principal está a la espera de éstos. Cuando encuentra un mensaje, lo imprime en la consola, y si no encuentra nada entonces se duerme algunas décimas de segundo antes de volver a revisar la cola por si hay más mensajes disponibles.

using System;
using System.Collections;
using System.Threading;

namespace Fermasmas.Wordpress.Com
{
    class Program
    {
        // este es nuestra cola de mensajes. 
        static volatile Queue _messages;

        static void Main(string[] args)
        {
            _messages = new Queue();

            // inicializamos el generador de mensajes en un hilo aparte.
            Thread thread = new Thread(new ThreadStart(MessagePump));
            thread.Start();

            // revisamos la cola de mensajes mientras el hilo trabajador esté 
            // activo o existan mensajes por procesar. 
            while (thread.IsAlive || _messages.Count > 0)
            {
                if (_messages.Count > 0)
                {
                    // hay que bloquear la cola de mensajes por si el otro 
                    // hilo intenta añadir más. de no hacer esto podríamos 
                    // tener problemas de sincronización. 
                    lock (_messages.SyncRoot)
                    {
                        // removemos el mensaje y lo imprimimos en la consola.
                        string message = _messages.Dequeue() as string;
                        Console.WriteLine(message);
                    }
                }
                else
                {
                    // no hay mensajes todavía, dormimos el hilo principal
                    // antes de continuar. 
                    Console.WriteLine("Durmiendo...");
                    Thread.Sleep(500);
                }
            }

            // el hilo trabajador terminó de hacer su proceso y ya no hay más
            // mensajes por mostrar, así que es hora de terminar la 
            // aplicacón. 
            Console.WriteLine("Terminado...");
            Console.ReadKey(true);
        }

        static void MessagePump()
        {
            for (int i = 0; i < 10; i++)
            {
                Thread.Sleep(300);

                string message = string.Format("Mensaje {0}", i + 1);
                lock (_messages.SyncRoot)
                {
                    _messages.Enqueue(message);
                }
                
            }
        }
    }
}

La salida de este programa es similar a la siguiente.

Durmiendo...
Mensaje 1
Durmiendo...
Mensaje 2
Mensaje 3
Durmiendo...
Mensaje 4
Durmiendo...
Mensaje 5
Mensaje 6
Durmiendo...
Mensaje 7
Mensaje 8
Durmiendo...
Mensaje 9
Durmiendo...
Mensaje 10
Terminado...

Rastreo de actividades

Quizás haz notado que las excepciones en .NET cuentan con la propiedad StackTrace. Esta propiedad devuelve una cadena de texto que contiene los nombres de las funciones que se fueron ejecutando. Esto es de invaluable ayuda al depurar el programa ya que podemos darnos una idea sobre cómo se ejecutó el programa.

Pues bien, este rastreo se puede implementar utilizando una pila. Al iniciar un método, haces un Push con el nombre del método, y al terminarlo haces un Pop. De tal suerte, si surge una excepción, la pila sabrá exactamente en qué método te encuentras. No en vano se le llama StackTrace (o rastreo de pila).

El siguiente programa muestra una serie de funciones que se llaman entre sí. Al inicio, el programa le pide al usuario que escriba el nombre de la función que lanzará una excepción. Así, si escribo “Foo7” la función Foo7 lanzará una excepción cuando sea invocada. Dado que las funciones Foo1 a Foo7 se llaman entre sí, podremos ver cómo se hace el rastreo al guardar información sobre el método que se llama. Cuando se lanza la excepción, se muestra el rastreo que hacemos a mano y se compara contra el rastreo que hace la clase Exception.

using System;
using System.Collections;

namespace Fermasmas.Wordpress.Com
{
  class Program
  {
    static Stack _log;
    static string _failure;

    static void Main(string[] args)
    {
      _log = new Stack();

      Console.WriteLine("¿En qué función fallará?");
      _failure = Console.ReadLine();
      Console.Clear();

      try
      {
        Console.WriteLine("Iniciando proceso...");
        Foo1();
        Console.WriteLine("Terminando proceso...");
      }
      catch (Exception ex)
      {
        Console.WriteLine("Hubo un error... rastreo habilitado: ");
        while (_log.Count > 0)
        {
          Console.WriteLine("en {0}", _log.Pop());
        }
        Console.WriteLine();

        Console.WriteLine("Rastreo de Exception.StackTrace: ");
        Console.WriteLine(ex.StackTrace);
      }

      Console.ReadKey(true);
    }

    static void DoWork()
    {
      string current = _log.Peek() as string;
      if (current.IndexOf(_failure) >= 0)
      {
        _log.Push("DoWork... ");
        throw new Exception();
      }
    }

    static void Foo1()
    {
      _log.Push("Estamos en Foo1");

      DoWork();
      Foo2();
      Foo3();
      Foo4();

      _log.Pop();
    }

    static void Foo2()
    {
      _log.Push("Estamos en Foo2");
      DoWork();
      _log.Pop();
    }

    static void Foo3()
    {
      _log.Push("Estamos en Foo3");
      DoWork();
      Foo5();
      Foo6();
      _log.Pop();
    }

    static void Foo4()
    {
      _log.Push("Estamos en Foo4");
      DoWork();
      Foo5();
      _log.Pop();
    }

    static void Foo5()
    {
      _log.Push("Estamos en Foo5");
      DoWork();
      _log.Pop();
    }

    static void Foo6()
    {
      _log.Push("Estamos en Foo6");
      DoWork();
      Foo7();
      _log.Pop();
    }

    static void Foo7()
    {
      _log.Push("Estamos en Foo7");
      DoWork();
      _log.Pop();
    }
  }
}

Al ejecutar este programa, y decirle que quiero una excepción en Foo5, esta es la salida. Al comparar el rastreo manual que hacemos junto con el que hace Exception.StackTrace, veremos que son prácticamente idénticos.

Iniciando proceso...
Hubo un error... rastreo habilitado:
en DoWork...
en Estamos en Foo6
en Estamos en Foo3
en Estamos en Foo1

Rastreo de Exception.StackTrace:
   at Fermasmas.Wordpress.Com.Program.DoWork() in C:\[...]\Program.cs:line 47
   at Fermasmas.Wordpress.Com.Program.Foo6() in C:\[...]\Program.cs:line 97
   at Fermasmas.Wordpress.Com.Program.Foo3() in C:\[...]\Program.cs:line 75
   at Fermasmas.Wordpress.Com.Program.Foo1() in C:\[...]\Program.cs:line 57
   at Fermasmas.Wordpress.Com.Program.Main(String[] args) in C:\[...]\Program.cs:line 22

 

Deshacer acciones

Otro de los ejemplos clásicos sobre aplicaciones de pilas es el hacer y deshacer acciones. Editores de texto como Word o el Visual Studio cuentan con esta funcionalidad para deshacer el texto previamente escrito. Esta funcionalidad se puede fácilmente alcanzar con una pila. Conforme ingresamos texto, lo agregamos a la pila, y al hacer el "undo” tomamos el último elemento escrito (es decir, hacemos un Pop) y lo eliminamos del editor de texto. Hacer un “redo” es muy similar: lo que sacamos del “undo” lo metemos en otra pila y listo.

El siguiente programa es un pequeño editor de texto estilo vim y emacs, muy básico, que soporta la funcionalidad de hacer y deshacer. Utiliza :q para salir, :n para añadir un salto de línea, :c para borrar todo el contenido, :u para deshacer y :r para rehacer. Todo lo demás será agregado al texto y se mostrará en la consola.

using System;
using System.Text;
using System.Collections;

namespace Fermasmas.Wordpress.Com
{
  class Program
  {
    static Stack _undo;
    static Stack _redo;
    static string _text;
    
    static void Main(string[] args)
    {
      _undo = new Stack();
      _redo = new Stack();
      _text = string.Empty;

      string query = string.Empty;

      do
      {
        Console.Clear();
        Console.Write(_text);

        Console.WriteLine("\n\n\n\n");
        Console.WriteLine("Ingrese texto o :q para terminar.");
        Console.Write("> ");

        query = Console.ReadLine();
        if (query == ":n")
        {
          _undo.Push("\n");
          _redo.Clear();
          _text += "\n";
        }
        else if (query == ":c")
        {
          _undo.Clear();
          _redo.Clear();
          _text = string.Empty;
        }
        else if (query == ":u")
        {
          if (_undo.Count > 0)
          {
            string undo = _undo.Pop() as string;
            _redo.Push(undo);
            int index = _text.LastIndexOf(undo);
            _text = _text.Remove(index, undo.Length);
          }
        }
        else if (query == ":r")
        {
          if (_redo.Count > 0)
          {
            string redo = _redo.Pop() as string;
            _undo.Push(redo);
            _text += redo;
          }
        }
        else if (query == ":?")
        {
          Console.Clear();
          Console.WriteLine("Comandos");
          Console.WriteLine(":n - salto de línea");
          Console.WriteLine(":c - borrar");
          Console.WriteLine(":u - deshacer última acción");
          Console.WriteLine(":r - rehacer última acción deshecha");
          Console.WriteLine(":q - quitar");
          Console.WriteLine("Presione una tecla para continuar...");
          Console.ReadKey(true);
        }
        else if (query != ":q")
        {
          _undo.Push(query);
          _redo.Clear();
          _text += query;
        }
      }
      while (query != ":q");
    }
  }
}

Conclusiones

Bueno, pues eso es todo por ahora. Hay muchos más ejemplos, pero creo (espero) que estos son ilustrativos. Por supuesto, puedes reemplazar una pila y una cola con arrays o listas, pero bueno, tendrías que hacer las validaciones a manita.

Utiliza sabiamente las pilas y las colas, ya que el abusar de ellas también puede acarrear problemas de escalamiento o rendimiento de recursos.

Y ahora sí, a festejar que México le ganó a Francia…

Categorías:.NET Framework, C#, Tutorial Etiquetas: ,