União e Intersecção de Intervalos

Conjuntos são como clubes, associações, países, etc

Um conjunto é como se fosse um clube, uma associação de pessoas. Para fazer parte, o elemento precisa satisfazer certos critérios, certas condições.

Por exemplo, para ser membro (elemento) do Clube de Xadrez, a pessoa tem que jogar xadrez e pagar uma anuidade. Pra ser elemento de [3,4], um número x tem que satisfazer o critério 3 ≤ x ≤ 4.

Intervalos são um tipo de conjunto

Escrever 3 ≤ x ≤ é apenas uma abreviação para 3 ≤ x e x ≤ 4. Ou seja, x é maior ou igual a 3, e menor ou igual a 4. Isso significa que todo número real indo de 3 a 4 pertence a esse intervalo: por exemplo, 3,1, 3,2, ... 3,9, 3,9999, etc.

Até π=3,14159... pertence a esse intervalo, pois ele é maior ou igual a 3 (pois é maior que 3), e menor ou igual a 4 (pois é menor do que 4). Note que inclusive o 3 e o 4, pois eles passam no teste: 3 é maior ou igual a 3 (pois é igual), e menor ou igual a 4 (pois é menor). E 4 é maior ou igual a 3 (pois é maior), e menor ou igual a 4 (pois é igual).

O intervalo ]3;4[ é parecido, mas a condição agora é sem o "ou igual": 3 < x < 4. O número tem que ser maior do que 3, e menor do que 4. Isso significa que o 3 e o 4 não estão nesse intervalo. 3 não está porque não é maior do que 3 (um número nunca é maior do que si mesmo) e 4 não está nesse intervalo porque não é menor do que si mesmo, 4!

A notação usando colchetes é sugestiva: quando escrevemos "[3", estamos incluindo o 3. Pode-se pensar que o colchete está "abraçando" o 3, incluindo-o. Já "]3" está dando as costas para o 3, excluindo-o. O mesmo vale para "4]" (incluindo) e "4[" (excluindo).

Uma forma de ler em voz alta o intervalo [3;4] é "intervalo de 3 inclusive a 4 inclusive". Lemos "]3;4[" como "o intervalo de 3 exclusive a 4 exclusive". Podemos inclusive misturar os dois casos: ]3,4] exclui o 3 mas inclui o 4. [3,4[ inclui o 3, mas exclui o 4.

Voltando a conjuntos sendo como clubes

Mas voltando à idéia de que conjuntos são clubes com critérios de admissão: quando ninguém satisfaz o critério, o clube fica vazio. Por exemplo, o clube (conjunto) dos números primos pares e maiores do que 5 é o conjunto vazio, pois o único número primo par é 2 e ele não é maior do que 5. Ele era o único que talvez satisfizesse a condição, mas nem ele satisfaz.

Outro clube vazio é o clube dos números pares ímpares (lógico).

Esses "clubes vazios" são simplemente o conjunto vazio, denotado por { } ou ∅.

Às vezes um clube tem um único membro: o clube dos números primos pares só tem o elemento 2 lá, nenhum outro número satisfaz. A gente denota esse conjunto como { 2 }.

União, e União de Intervalos

Certos clubes são especiais pois o critério para pertencer a eles é pertencer a outros clubes. Por exemplo, o conjunto união de [3, 5] e [5, 6] exige que para fazer parte, o elemento tem que fazer parte ou de [3;5], ou de [5;6]. Isso resulta em todos os numeros em [3,6], portanto [3;6] é a união de [3;5] e [5;6].

A regra geral para união é a seguinte: um elemento pertence à união dos conjuntos A1,...,An se, e somente se, ele pertence a pelo menos um dos conjuntos A1,...,An (note que isso inclui o caso em que ele pertence a mais de um desses conjuntos, ou mesmo de todos).

A União Européia é um clube parecido. Pra ser cidadão da União Européia, a pessoa tem que ser cidadã ou de Portugal, ou da França, ou da Alemanha, etc... O resultado é o conjunto de todas as pessoas dos países da União Européia.

Veja bem, união não precisa ser só de intervalos, mas serve para qualquer conjunto. Intervalo é só um tipo de conjunto. Um exemplo de conjunto que não é intervalo é, por exemplo, {1, 4, 5, 6}, que é um conjunto com 4 números. Ele conjunto tem "buracos" entre os elementos -- o 2, por exemplo, não pertence a ele -- e não é um intervalo.

Mesmo com conjuntos que não são intervalos, podemos falar da união. Por exemplo, a união dos conjuntos [0, 1, 2} e { 1, 2, 4, 5, 6} é o conjunto {0, 1, 2, 4, 5, 6}, ou seja, todos os elementos que fazem parte de pelo menos um dos conjuntos originais.

Note que acima o 1 e 2 pertencem a ambos os conjuntos. Isso não impede que eles pertençam à união, pois pra pertencer a União basta pertencer a pelo menos um conjunto. Quem pertence aos dois conjuntos pertence a pelo menos um deles!

Intersecção, e Intersecção de Intervalos

A intersecção também é um tipo de clube que tem como condição o fato de pertencer a outros clubes. A diferença é que pra pertencer à intersecção, um elemento deve pertencer a todos os conjuntos sendo interseccionados. A intersecção de {1,2,3}, {2, 3, 4} e {0,2,3,5} é {2,3} pois apenas esses dois elementos pertencem todos os três conjuntos. A intersecção de {2, 3, 4} e {0, 1, 7} é o conjunto vazio, pois nenhum número pertence a ambos esses conjuntos.

Se a intersecção for de vários conjuntos, um elemento deve pertencer a todos eles pra poder pertencer à intersecção. Por exemplo, a intersecção de {0,1,2], {-1,0,2} e {2,4,5} é o conjunto unitário {2}, pois só o 2 pertence a todos os conjuntos. Note que o 0 pertence a dois deles, mas como não está no terceiro, é rejeitado na hora de entrar na intersecção.

A intersecção dos países da União Européia é o conjunto vazio, pois pra pertecer à intersecção de todos aqueles países, a pessoa teria que ser cidadão de todos os países: ser cidadão de Portugal E cidadão da França E cidadão da Alemanha. Acho que não existe ninguém que seja cidadão de todos esses países ao mesmo tempo, então a intersecção é o conjunto vazio.

Lembre-se: um intervalo é nada mais, nada menos do que um "clube", com uma condição para pertencer que toma a forma de a ≤ x ≤ b, (ou < ao invés de ≤ para intervalos abertos). Os números 3, 3,5 e 4 pertencem a [3,4], enquanto 3 e 3,5 pertencem a [3;4[ mas o 4 não pertence.

Intervalos d tipo ]-infinito; 3] significam "maior do que -infinito e menor ou igual a 3". Como todo número é "maior do que -infinito", isso é a mesma coisa que simplesmente dizer: "menor ou igual a 3".

O mesmo raciocínio se aplica para [4;+infinito[. Todo número maior ou igual a 4 pertence a esse intervalo, pois todos não "menores que infinito".

Exercícios

Dadas todas essas explicações, pratique resolvendo esses exercícios:

1. Quantos pontos estão contidos nos seguintes intervalos: a. [2;2] b. [2;2[ c. ]2;2[

2. Quais as seguintes intersecções:

a. [1;3] ∩ [0; 2] b. [-1;3] ∩ [0; 2] c. [3;4] ∩ [4,8] d. [3,4[ ∩ ]4, 8] e. [0;1] ∩ [3;4] f. [0;1] ∩ [1;2]

3. Quais as seguintes uniões (Note que as uniões não são necessariamente intervalos):

a. [3;4] ∪ [4;8] b. ]-infinito,;7] ∪ [7;+infinito[ c. [2;4] ∪ [6,8]

Respostas

1. Quantos pontos estão contidos nos seguintes intervalos:

a. [2;2] = {2}, pois apenas x = 2 satisfaz 2 ≤ x ≤ 2. b. [2;2[ = ∅, pois nenhum x satisfaz 2 ≤ x < 2, nem mesmo o 2, pois não é verdade que 2 < 2. c. ]2;2[ = ∅, pois nenhum x satisfaz 2 < x < 2, nem mesmo o 2, pois não é verdade que 2 < 2.

2. Quais as seguintes intersecções:

a. [1;3] ∩ [0; 2] = [1;2] b. [-1;3] ∩ [0; 2] = [0;2] c. [3;4] ∩ [4,8] = {4}, pois apenas 4 pertence a ambos os intervalos d. [3,4[ ∩ ]4, 8] = ∅, pois nem o 4 pertence a ambos os intervalos e. [0;1] ∩ [3;4] = ∅ pois nenhum número pode ser ≤ 1 e maior ou igual a 3 ao mesmo tempo. f. [0;1] ∩ [1;2] = {1}, pois apenas o 1 está nos dois intervalos.

3. Quais as seguintes uniões (Note que as uniões não são necessariamente intervalos):

a. [3;4] ∪ [4;8] = [3;8], pois todos os números em [3;8] estão ou em [3;4] ou em [4;8] b. ]-infinito,;7] ∪ [7;+infinito[ = ]-infinito;+infinito[, ou seja, todos os números reais. c. [2;4] ∪ [6,8] = { x : 2 ≤ x ≤ 4 ou 6 ≤ x ≤ 8 }, que se lê assim: "o conjunto dos números x tais que 2 ≤ x ≤ 4 ou 6 ≤ x ≤ 8". Infelizmente não há um modo de descrever esse conjunto como um intervalo (por exemplo [2;8]), pois essa união não é um intervalo por ter um "buraco" no meio: os números entre 4 e 6 exclusive não pertencem à essa união pois não pertencem a nenhum dos dois intervalos originais. Se tivéssemos escrito [2;8], estaríamos incluindo esses números indevidamente.

ArrayHashSet, a Set in Java with random access and list iterators

Java offers a very useful Set implementation called LinkedHashSet, which keeps a parallel list to a HashSet that keeps the original insertion order available for iteration. This leads to more predictable outcomes with minimum overhead.

I've already wondered why they have not provided an analogous ArrayHashSet implementation in which an ArrayList fills the role of the parallel list, which would make middle-insertion slower, but on the other hand would offer random access.

Also, I don't know why they don't let LinkedHashSet provide a list iterator for more flexible iteration.

Anyway, given all that, I have implemented ArrayHashSet, which provides random access and list iterator. Here's the code:

/*
 * Copyright (c) 2013, SRI International
 * All rights reserved.
 * Licensed under the The BSD 3-Clause License;
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 * 
 * http://opensource.org/licenses/BSD-3-Clause
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright
 * notice, this arrayList of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright
 * notice, this arrayList of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the aic-expresso nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.sri.ai.util.collect;

import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.ListIterator;

/**
 * Analogous to {@link LinkedHashSet}, but with an {@link ArrayList} instead of a {@link LinkedList},
 * offering the same advantages (random access) and disadvantages (slower addition and removal of elements),
 * but with the extra advantage of offering an iterator that is actually a {@link ListIterator}.
 * @author braz
 *
 * @param
 */
public class ArrayHashSet extends AbstractSet {

private HashSet   set;
private ArrayList arrayList;

public ArrayHashSet() {
this.set  = new HashSet();
this.arrayList = new ArrayList();
}

// additional random access methods

public ArrayHashSetIterator listIterator() {
return new ArrayHashSetIterator(arrayList.listIterator());
}

public ArrayHashSetIterator listIterator(int index) {
return new ArrayHashSetIterator(arrayList.listIterator(index));
}

public E get(int index) {
return listIterator(index).next();
}

public void set(int index, E element) {
ArrayHashSet.ArrayHashSetIterator listIterator = listIterator(index);
listIterator.next();
listIterator.set(element);
}

// end of additional random access methods

// required implementations

public ArrayHashSet(Collection collection) {
this();
addAll(collection);
}

@Override
public boolean add(E element) {
boolean modified = set.add(element);
if (modified) {
arrayList.add(element);
}
return modified;
}

@Override
public ArrayHashSetIterator iterator() {
return new ArrayHashSetIterator(arrayList.listIterator());
}

@Override
public int size() {
return set.size();
}

// end of required implementations

// methods not required to be implemented, but more efficient

@Override
public boolean contains(Object o) {
return set.contains(o);
}

@Override
public Object[] toArray() {
return arrayList.toArray();
}

@Override
public T[] toArray(T[] a) {
return arrayList.toArray(a);
}

@Override
public boolean remove(Object o) {
boolean removed = set.remove(o);
if (removed) {
arrayList.remove(o);
}
return removed;
}

@Override
public void clear() {
set.clear();
arrayList.clear();
}

// end of methods not required to be implemented, but more efficient

private class ArrayHashSetIterator implements ListIterator {

private ListIterator arrayListIterator;
private E lastElementProvided;

public ArrayHashSetIterator(ListIterator arrayListIterator) {
this.arrayListIterator = arrayListIterator;
}

@Override
public boolean hasNext() {
return arrayListIterator.hasNext();
}

@Override
public E next() {
return lastElementProvided = arrayListIterator.next();
}

@Override
public void add(E element) {
if (set.add(element)) {
arrayListIterator.add(element);
}
}

@Override
public boolean hasPrevious() {
return arrayListIterator.hasPrevious();
}

@Override
public int nextIndex() {
return arrayListIterator.nextIndex();
}

@Override
public E previous() {
return lastElementProvided = arrayListIterator.previous();
}

@Override
public int previousIndex() {
return arrayListIterator.previousIndex();
}

@Override
public void remove() {
arrayListIterator.remove();
set.remove(lastElementProvided);
}

@Override
public void set(E element) {
if (element.equals(lastElementProvided)) {
// no need to do anything
}
else {
if (set.contains(element)) {
// cannot add because element would appear more than once
throw new IllegalArgumentException("Cannot set already-present element in a different position in ArrayHashSet.");
}
else {
arrayListIterator.set(element);
set.remove(lastElementProvided);
set.add(element);
}
}
}
}
}


and here is a unit testing class:

/*
 * Copyright (c) 2013, SRI International
 * All rights reserved.
 * Licensed under the The BSD 3-Clause License;
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 * 
 * http://opensource.org/licenses/BSD-3-Clause
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the aic-util nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.sri.ai.test.util.collect;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import java.util.NoSuchElementException;

import org.junit.Before;
import org.junit.Test;

import com.sri.ai.util.Util;
import com.sri.ai.util.collect.ArrayHashSet;

public class ArrayHashSetTest {

@Before
public void setUp() throws Exception {
}

@Test
public void test() {

ArrayHashSet set;

set = new ArrayHashSet();
assertTrue(set.isEmpty());
assertEquals(set.size(), 0);

assertEquals(Util.list(), Util.listFrom(set.iterator())); // tests iteration order

set.add("tree");
assertFalse(set.isEmpty());
assertEquals(set.size(), 1);
assertEquals("tree", set.get(0));

set.add("almond");
assertFalse(set.isEmpty());
assertEquals(set.size(), 2);
assertEquals("tree", set.get(0));
assertEquals("almond", set.get(1));

assertEquals(Util.list("tree", "almond"), Util.listFrom(set.iterator())); // tests iteration order

set.clear();
assertTrue(set.isEmpty());
assertEquals(set.size(), 0);

set.add("almond");
assertFalse(set.isEmpty());
assertEquals(set.size(), 1);
assertEquals("almond", set.get(0));

set.add("tree");
assertFalse(set.isEmpty());
assertEquals(set.size(), 2);
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));

set.add("leaf");
assertFalse(set.isEmpty());
assertEquals(set.size(), 3);
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));

assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.remove("tree");
assertFalse(set.isEmpty());
assertEquals(set.size(), 2);
assertEquals("almond", set.get(0));
assertEquals("leaf", set.get(1));

assertEquals(Util.list("almond", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.remove("leaf");
assertFalse(set.isEmpty());
assertEquals(set.size(), 1);
assertEquals("almond", set.get(0));

assertEquals(Util.list("almond"), Util.listFrom(set.iterator())); // tests iteration order

set.remove("almond");
assertTrue(set.isEmpty());
assertEquals(set.size(), 0);

assertEquals(Util.list(), Util.listFrom(set.iterator())); // tests iteration order

set.add("almond");
set.add("tree");
set.add("tree");
set.add("almond");
set.add("leaf");
set.add("tree");

assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.set(2, "trunk");
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("trunk", set.get(2));
assertEquals(Util.list("almond", "tree", "trunk"), Util.listFrom(set.iterator())); // tests iteration order

set.set(2, "leaf");

assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.set(2, "leaf");

assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

try {
set.set(2, "almond"); // cannot add an already-present element in a different position
fail("Should have thrown an exception");
}
catch (IllegalArgumentException e) {
// good, did what it had to do
}
catch (Exception e) {
fail("Should have thrown an IllegalArgumentException but threw " + e);
}

try {
set.set(3, "almond"); // cannot set a non-existing position
fail("Should have thrown an exception");
}
catch (NoSuchElementException e) {
// good, did what it had to do
}
catch (Exception e) {
fail("Should have thrown an NoSuchElementException but threw " + e);
}

// should remain the same after failed operations
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order
}
}