Sets en JavaScript
Ahora que ya hemos visto arrays y objetos en más detalle, vamos a explorar otras estructuras de datos menos genéricas, que nos pueden ayudar a representar ciertos problemas y soluciones. En este caso vamos a ver sets (conjuntos).
“A set is a collection of unique elements. The elements of a set are called members. The two most important properties of sets are that the members of a set are unordered and that no member can occur in a set more than once.”
Fuente: Michael McMillan, Data Structures and Algorithms with JavaScript, O’Reilly Media, 2014.
“Un set es una colección de elementos únicos”. Podemos visualizar un set como un array en el que de alguna forma garantizamos que nunca hay elementos repetidos. Otra característica de los sets, es que los elementos no están ordenados de ninguna forma en particular, pero además de eso no hay mucho más que podamos decir desde el punto de vista de la estructura de datos en sí.
Lo importante de este tipo de estructuras es que son abstracciones, mediante las cuales comunicamos una intención y “escondemos” detalles de implementación. Las abstracciones nos permiten expresar nuestra lógica de forma más clara. Más allá de cómo está implementada una abstracción, lo importante es que le damos un nombre a una “cosa” que tiene unas características determinadas que todos podemos entender.
De hecho, podemos implementar el comportamiento de un set sin tener que usar o declarar un objeto de tipo Set como tal. Pero usar un Set nos da información sobre tal o cual variable — nos dice que contiene un conjunto sin elementos repetidos — nos sugiere una API (una manera de interactuar con la estructura) además de operaciones comunes entre conjuntos.
Al hablar de sets, se me vienen siempre a la cabeza los diagramas de Venn (como el de arriba), para los cuales, los sets como estructura de datos son perfectos. Al final de este artículo vamos a ver un caso práctico usando este tipo de visualización.
JavaScript (a partir de ES6, creo) incluye un constructor Set, que implementa parte de la funcionalidad que uno esperaría en un objeto de tipo set, pero no es una implementación completa y no está disponible en todos los navegadores, así que para ilustrar los sets como estructura de datos vamos a ver nuestra propia implementación.
API
Los sets por lo general van a conformar a una API (Application Programming Interface) que nos permita manipularlos de la manera esperada. Vamos a ver cómo podríamos implementar nuestros propios sets. Para ello vamos a empezar con una función (un constructor):
function Set() {
this.data = [];
}Ahora, si instanciamos un objeto usando new Set(), esto va a producir un objeto que por ahora sólo tiene un atributo (this.data), pero todavía no hace nada interesante. Probablemente el primer método que queramos implementar sea add(), que nos permitirá añadir elementos al set, y garantizar que sólo se añaden elementos que todavía no están en el set.
Set.prototype.add = function (value) { if (this.data.indexOf(value) < 0) {
this.data.push(value);
return true;
} return false;
}
En este ejemplo estamos añadiendo nuestros métodos a Set.prototype, lo que significa que todos los objetos creados con new Set() van a tener estos métodos en su prototipo, y así vamos a ir construyendo la “interfaz” de nuestros sets. Como vemos, el método add() es muy sencillo, simplemente añade el valor que le pasemos a nuestro arreglo this.data, pero siempre asegurándonos de sólo añadirlo si todavía no está en el arreglo (para eso la condición if (this.data.indexOf(value) < 0)).
De la misma forma implementemos un método delete() para poder borrar elementos de nuestros sets. Antes de modificar this.data vamos a verificar que el valor de hecho exista en el arreglo.
Set.prototype.delete = function (value) {
var pos = this.data.indexOf(value);
if (pos > -1) {
this.data.splice(pos, 1);
return true;
}
return false;
};Una vez que ya podemos tanto añadir (add) como borrar (delete), el siguiente paso sería implementar un método has() que nos permita comprobar si un valor está en el set.
Set.prototype.has = function (value) {
if (this.data.indexOf(value) > -1) {
return true;
}
return false;
};Otra cosa importante que vamos a necesitar es saber el “tamaño” de un set (el número de valores que son parte del set), así que para ello vamos a implementar un método size() que en este ejemplo puede simplemente retornar this.data.length:
Set.prototype.size = function () {
return this.data.length;
};Llegado a este punto, usando nuestra implementación ya podríamos crear un set, añadir y borrar elementos, comprobar su tamaño y si contiene un valor:
var mySet = new Set();
mySet.size(); // 0
mySet.add(1); // true
mySet.size(); // 1
mySet.has(1); // true
mySet.has(true); // false
mySet.add('foo'); // true
mySet.size(); // 2
mySet.add(1); // false
mySet.size(); // 2
mySet.delete(1); // true
mySet.size(); // 1Siguiendo este patrón implementaríamos otros métodos como clear() para resetear el set, además de otras “utilidades”. También modificaríamos nuestro constructor para que acepte un array (o un objeto iterable) como argumento y así poder inicializar el set. Acá pueden ver esta implementación de ejemplo.
Operaciones comunes
Listo, ya tenemos una implementación de Set que cumple los requisitos básicos, y de hecho hemos escrito una “clase” Set que hace prácticamente lo mismo que el Set de ES6. Pero para hacer nuestros sets un poco más útiles, sería interesante que implementen las operaciones más comunes entre sets: intersección, diferencia, unión, …
Veamos brevemente cómo podríamos implementar el método intersect():
Set.prototype.intersect = function (set) {
var intersection = new Set();
for (var i = 0; i < this.data.length; ++i) {
if (set.has(this.data[i])) {
intersection.add(this.data[i]);
}
}
return intersection;
};Como vemos nuestra implementación hace uso de nuestro constructor Set para crear un nuevo set con el resultado. De la misma forma podemos implementar otras operaciones comunes. De hecho, en vez de entrar en detalles en este post, que ya está bastante largo, el código fuente de este ejemplo está GitHub y las invito a que propongan métodos, comentarios, fixes, … y manden pull requests ;-)
Protocolo de Iteración
Cabe mencionar que tanto los sets “nativos” de JavaScript como la versión de este ejemplo implementan el “protocolo iterable”. Esto básicamente quiere decir que son objetos “iterables” al igual que Array, arguments o NodeList y podemos usarlos en estructuras de iteración como for...of.
Si tienen curiosidad de ver cómo nuestro Set implementa el protocolo “iterable” vean el método Set.prototype[Symbol.iterator].
Un ejemplo
Ahora sí, para terminar un ejemplo de uso. Imaginemos que tenemos un array en el que cada elemento representa una alumna, y cada alumna está representada a si mismo por una array de los lenguajes de programación que le encantan (♡). Por ejemplo:
var alumnas = [
['JavaScript'], // a la 1era alumna le encanta el JavaScript
['HTML', 'CSS'], // a la 2nda alumna le encantan el HTML y el CSS
['JavaScript', 'HTML', 'CSS'], ...
...
];Lo que queremos hacer es un diagrama de Venn que represente los conjuntos de alumnas a las que les gustan cada uno de los lenguajes y sus intersecciones. Algo así:
Para “dibujar” el diagrama vamos a usar dos librerías: D3 y Venn.js. Sabemos que Venn.js espera que le pasemos la data del diagrama en un arreglo de objetos, en el que cada objeto tiene dos llaves, sets y size. La llave sets es un array de strings que puede tener uno o más elementos. Cuando tiene un solo elemento el objeto representa un conjunto y su tamaño (size), mientras que cuando sets tiene más de un elemento el objeto representa la intersección entre los sets. Por ejemplo:
var data = [
{sets: ['A'], size: 5}, // tamaño del set A
{sets: ['B'], size: 8}, // tamaño del set B
{sets: ['A', 'B'], size: 4}, // tamaño de intersección entre A y B
...
];Nuestro script tiene que crear el array data a partir del array alumnas para poder pasárselo a Venn.js. Traten de implementar esto como ejercicio, y como referencia pueden ver esta solución:
Código fuente:
Gráfica terminada:
https://lupomontero.github.io/set.js/example/
