Sets en JS

Querido diario… hoy seguiremos con las estructuras de datos, veremos sets en Javascript, una estructura de datos que nos permite guardar datos, al igual que los diccionarios y las hash tables.

Ejemplo de sets…

Los sets se usan para guardar elementos únicos de cualquier tipo, solo datos primitivos (string, number, boolean, null, undefined, symbol), un dato primitivo es: un tipo de dato que no es un objeto ni posee métodos. Si se trata de agregar un elemento que ya existe, este nuevo elemento no será agregado, ya que la principal propiedad de los Sets es que solo almacenan datos únicos.

A continuación definiré el TDA(Tipo de Dato Abstracto, ver más) para implementar mi propio Set.

Primero definiremos un objeto MySet, esto debido a que javascript ya tiene una implementación de Set[1] (ver más). Nuestra clase MySet contendrá una propiedad llamada items, que será un objeto literal de javascript {}, este objeto nos permitirá almacenar y operar sobre las valores que se vayan ingresando.

Los métodos que definen la interfaz de mi set, son los siguientes:

  • add (value): añade un nuevo elemento al set.
  • delete(value): elimina un valor dado en el set.
  • has(value): retorna true si el valor existe, sino, retorna false.

Otros métodos típicos son: clear, size, values, entre otros.

Método has

Con la ayuda del método hasOwnProperty(key) verificaremos si el valor dado, se encuentra definido dentro de nuestro objeto literal items.

has (value) {
return this.items.hasOwnProperty(value)
}

Si el valor existe, este método retornará true, de otra forma, retornará false.

Método add

Para este método y como especificamos previamente, debemos recibir un valor, para agregarlo en nuestro objeto items, esto lo haremos de la siguiente forma:

add (value) {
if (!this.has(value)) {
this.items[value] = value
return true
}

return false
}

Esto nos permite crear una llave nueva en nuestro objeto this.items, con un valor value. Además antes de agregar cualquier dato, revisamos que este valor no exista, si es que llegase a existir, el elemento no se agrega. Esto lo hacemos para cumplir la propiedad que solo puede existir un único valor value.

Método delete

Para el método delete deberemos comprobar si el valor que buscamos existe, si no existe retornaremos false indicando que ese valor no ha sido ingresado.

delete (value) {
if (this.has(value)) {
delete this.items[value]
return true
}

return false
}

Para poder verificar la existencia de un valor value usaremos nuestro anterior método has, el cual revisa si un valor dato existe o no en nuestra variable this.items. Luego de haber encontrado la llave, usamos el operador delete que tiene javascript, este operador nos permite borrar una llave de un objeto, con lo cual se borra también el valor que esta llave contiene.

A continuación, os dejo la implementación completa de la clase MySet. Al final del código se puede ver su uso.

Como pueden apreciar en el código, su implementación es bastante simple y muy útil si queremos guardar elemento único que estén asociados a una llave en particular.


Teoria de conjuntos aplicadas en Sets.

Diagrama de venn: unión, intersección y sustraer.

“La idea de agrupar objetos de la misma naturaleza para clasificarlos en “colecciones” o “conjuntos” es parte de la vida diaria de los seres humanos. Por ejemplo, el conjunto de libros de una biblioteca, el conjunto de árboles en un terreno, el conjunto de zapatos en un negocio de venta al público, el conjunto de utensilios en una cocina, etcétera. En todos estos ejemplos, se utiliza la palabra conjunto como una colección de objetos.”[2]

Ya implementamos un set en javascript, ahora tomemos este código y utilicémoslo para algo un poco más entretenido. Ahora que podemos formar conjuntos o sets, podemos operar sobre estos conjuntos utilizando opera-ciones definidas por las matemáticas, estás operaciones las paso a listar y definir a continuación:

  • Unión: Crea un nuevo conjunto con elementos de ambos conjuntos.
Unión de A y B
  • Intersección: Crea un nuevo conjunto con los elementos que ambos conjuntos tienen en común.
Intersección de A y B
  • Sustraer: Crea un nuevo conjunto con los elementos que solo existen en el primer conjunto, si el primer conjunto tiene elementos en común, estos elementos no son considerados.
Sustracción de A y B.
  • Subconjunto: Verifica si un conjunto es subconjunto de otro.

Pero, ¿De qué forma podemos programar esto? Muy simple y lo pueden ver en los siguientes códigos.

Unión

const union = (set1, set2) => {
const set3 = new MySet()
for (let key in set1.items) {
set3.add(set1.items[key])
}
for (let key in set2.items) {
set3.add(set2.items[key])
}
return set3
}

Intersección

const intersection = (set1, set2) => {
const set3 = new MySet()
for (let key in set2.items) {
// Comprobamos si el valor del set2 existe en el set1.
// Si existe, agregamos el valor que existe en ambos sets
if (set1.has(set2.items[key])) {
set3.add(set2.items[key])
}
}

return set3
}

Sustracción

const subtract = (set1, set2) => {
const set3 = new OwnSet()
// agregamos los elementos de set1.
for (let key in set1.items) {
set3.add(set1.items[key])
}
for (let key in set2.items) {
// si set2 tiene un valor en set1, lo sacamos
if (set1.has(set2.items[key])) {
set3.delete(set1.items[key])
}
}

return set3
}

Ejemplo:


Referencias

Libro 1 — Learning Javascript Data Structures and Algorithms, Segunda edición, Loiane Groner.

Libro 2 — Data Structures & Algorithms with Javascript, Michael McMillan.

[1]https://developer.mozilla.org/en/docs/Web/JavaScript/Reference/Global_Objects/Set

[2]http://www.profesorenlinea.cl/quinto/5TeoriaConjuntos.htm