Sets

Sets

Set é uma coleção não ordenada de elementos únicos. Você pode pensar em um set como um dicionário, mas sem valores associados. Um set pode conter qualquer tipo de dado, mas todos os elementos em um set devem ser únicos.

ADT de um Set

Um set é uma coleção de elementos únicos. Cada elemento é acessado por uma chave. A chave é um valor que é único para

Operações de um set:

• inserção (add) - adiciona um elemento ao set;
• remoção (delete) - remove um elemento do set;
• busca (has) - verifica se um elemento está no set;
• união (union) - retorna um novo set com todos os elementos de dois sets;
• interseção (intersection) - retorna um novo set com todos os elementos que estão em ambos os sets;
• diferença (difference) - retorna um novo set com todos os elementos que estão em um set, mas não no outro;

Implementação

Sets podem ser implementados de várias formas. Aqui vamos ver uma implementação simples de um set em JavaScript.

TODO: implemetar set usando array

class Set {
    constructor() {
        this.data = [];
    }

    add(value) {
        if (!this.has(value)) {
            this.data.push(value);
        }
    }

    delete(value) {
        this.data = this.data.filter(v => v !== value);
    }

    has(value) {
        return this.data.includes(value);
    }

    union(otherSet) {
        let newSet = new Set();

        this.data.forEach(v => newSet.add(v));
        otherSet.data.forEach(v => newSet.add(v));

        return newSet;
    }

    intersection(otherSet) {
        let newSet = new Set();

        this.data.forEach(v => {
            if (otherSet.has(v)) {
                newSet.add(v);
            }
        });

        return newSet;
    }

    difference(otherSet) {
        let newSet = new Set();

        this.data.forEach(v => {
            if (!otherSet.has(v)) {
                newSet.add(v);
            }
        });

        return newSet;
    }
}

No próximo capítulo veremos Hashmaps que nos permite implementar sets de forma mais eficiente.

Nosso set implementado com array tem os seguintes tempos de execução:

• inserção: O(n)
• remoção: O(n)
• busca: O(n)
• união: O(n^2)
• interseção: O(n^2)
• diferença: O(n^2)
• espaço: O(n)