Un juego representa un grupo de objetos, conocidos como sus elementos.
Las juegos no permiten elementos duplicados y los mismos no están ordenados.
Los elementos de un juego no son accedidos a través de un índice. Por
el contrario su única forma de recuperación es uno a uno, secuencialmente.
En ingles set significa juego, surtido, coleccion, serie, grupo o clase.
+--------------+
| Iterador |
| |
| |
*--------* *--------* | *--------* | *--------* *--------* *--------* *--------* *--------* *--------*
| | | | | | | | | | | | | | | | | | | |
| | | | | |Elemento| | | | | | | | | | | | | |
| | | | X | | V | | | | | | | | | | | |
| | | | |Devuelto| | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | |
*--------* *--------* *--------* *--------* *--------* *--------* *--------* *--------* *--------*
Elemento Elemento Elemento Elemento Elemento Elemento Elemento Elemento Elemento
Elemento HH Elemento CC Elemento FF Elemento CC Elemento FF Elemento BB Elemento ZZ Elemento HH
adicion adicion adicion eliminacion adicion adicion adicion eliminacion
*-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------*
| | |Elemento HH| |Elemento HH| |Elemento HH| |Elemento HH| |Elemento HH| |Elemento HH| |Elemento HH| |Elemento FF|
*-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------*
| | | | |Elemento CC| |Elemento CC| |Elemento FF| |Elemento FF| |Elemento FF| |Elemento FF| |Elemento BB|
*-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------*
| | | | | | |Elemento FF| | | | | |Elemento BB| |Elemento BB| |Elemento ZZ|
*-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------*
| | | | | | | | | | | | | | |Elemento ZZ| | |
*-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------*
| | | | | | | | | | | | | | | | | |
*-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------*
| | | | | | | | | | | | | | | | | |
*-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------*
| | | | | | | | | | | | | | | | | |
*-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------*
| | | | | | | | | | | | | | | | | |
*-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------* *-----------*
Tiempo t1 Tiempo t2 Tiempo t3 Tiempo t4 Tiempo t5 Tiempo t6 Tiempo t7 Tiempo t8 Tiempo t9
int create()
boolean add(int c, Object obj)
void begin(int c)
Object next(int c)
boolean hasNext(int c)
void remove(int c)
El método create crea una Juego y retorna su identificador.
El método add adiciona un objeto al Juego y retorna true si la Juego cambio en virtud de la adición, de lo contrario retorna false, indicando que la Juego no ha cambiado. Por ejemplo, si se trata de adicionar un objeto que ya esta presente en el Juego la adición es rechazada, ya que no se aceptan duplicados.
El método begin ubica el iterador al comienzo de la Juego.
El método next recupera el siguiente objeto del Juego. Invocando repetidamente este método se visitan todos los objetos del Juego, uno a uno.
El método hasNext retorna true si existen más objetos en el Juego y retorna false en caso contrario. Siempre, antes de invocar la recuperación del siguiente objeto, debe consultarse si existen más objetos en el Juego.
El método remove elimina del Juego el último objeto recuperado.
int size(int c)
boolean isEmpty(int c)
boolean contains(int c, Object obj)
boolean containsAll(int c, Juego c)
boolean equals(int c, Object other)
boolean addAll(int c, Juego from)
boolean remove(int c, Object obj)
boolean removeAll(int c, Juego c)
void clear(int c)
boolean retainAll(int c, Juego c)
Object[] toArray(int c)
El método size retorna el número de elementos actualmente almacenados en el Juego.
El método isEmpty retorna true si no existen elementos en el Juego.
El método contains retorna true si el Juego contiene un objeto igual a obj.
El método containsAll retorna true si el Juego contiene todos los objeto del Juego other.
El método addAll retorna true si el Juego ha cambiado por la adición de todos los objetos del Juego other.
El método removeAll retorna true si el Juego ha cambiado por la eliminación de todos los objetos del Juego other.
El método clear elimina todos los objetos del Juego.
El método retainAll retorna true si el Juego ha cambiado por la eliminación de todos los objetos no iguales del Juego other.
El método toArray retorna un Arreglo formado por los objetos del Juego.
Las operaciones definidas en Juegos son utilies para ejecutar operaciones del
algebra de conjuntos. Veamos los siguientes ejemplos.
S1
*-----------------------*
| |
| S2 | S2 es un subset de S1 si
| *-------------* |
| | | |
| | | |
| | | |
| *-------------* | s1.containsAll(s2)
| |
*-----------------------*
S1
*-----------------------*
|///////////////////////|
|///////////////////////| S2 union de S1 y S2
|///////////////////*-------------*
|///////////////////|/////////////|
|///////////////////|/////////////|
|///////////////////|/////////////|
|///////////////////*-------------* s1.addAll(s2)
|///////////////////////|
*-----------------------*
S1
*-----------------------*
| |
| | S2 interseccion de S1 y S2
| *-------------*
| |//// |
| |//// |
| |//// |
| *-------------* s1.retainAll(s2)
| |
*-----------------------*
S1
*-----------------------*
|///////////////////////|
|///////////////////////| S2 diferencia de S1 y S2
|///////////////////*-------------*
|///////////////////| |
|///////////////////| |
|///////////////////| |
|///////////////////*-------------* s1.removeAll(s2)
|///////////////////////|
*-----------------------*
S1
*-----------------------*
| |
| | S2 diferencia de S2 y S1
| *-------------*
| | /////////|
| | /////////|
| | /////////|
| *-------------* s2.removeAll(s1)
| |
*-----------------------*
.........................
. .
. .
. .
. .
. Collection .
. .
. .
. .
.........................
.
.
.
.
.........................
. .
......................................................... .
. . .
. . .
. . Set .
. . .
. ............................ .
. . . .
. . .........................
. .
. .
. .
. .
*-----------------------* *-----------------------*
| | | |
| | | |
| | | |
| | | |
| HashSet | | TreeSet |
| | | |
| | | |
| | | |
*-----------------------* *-----------------------*
ASetis aCollectionthat cannot contain duplicate elements.Setmodels the mathematical set abstraction. TheSetinterface extendsCollectionand contains no methods other than those inherited fromCollection. It adds the restriction that duplicate elements are prohibited.Setalso adds a stronger contract on the behavior of theequalsandhashCodeoperations, allowingSetobjects with different implementation types to be compared meaningfully. TwoSetobjects are equal if they contain the same elements.The
Setinterface is shown below:The JDK contains two general-purposepublic interface Set { // Basic Operations int size(); boolean isEmpty(); boolean contains(Object element); boolean add(Object element); // Optional boolean remove(Object element); // Optional Iterator iterator(); // Bulk Operations boolean containsAll(Collection c); boolean addAll(Collection c); // Optional boolean removeAll(Collection c); // Optional boolean retainAll(Collection c); // Optional void clear(); // Optional // Array Operations Object[] toArray(); Object[] toArray(Object a[]); }Setimplementations.HashSet, which stores its elements in a hash table, is the best-performing implementation.TreeSet, which stores its elements in a red-black tree, guarantees the order of iteration.Here's a simple but useful
Setidiom. Suppose you have aCollection,c, and you want to create anotherCollectioncontaining the same elements, but with all duplicates eliminated. The following one-liner does the trick:It works by creating aCollection noDups = new HashSet(c);Set(which, by definition, cannot contain duplicates) initially containing all the elements inc. It uses the "standardCollectionconstructor" described in theCollectioninterface lesson.
Thesizeoperation returns the number of elements in theSet(its cardinality). TheisEmptymethod does exactly what you think it does. Theaddmethod adds the specified element to theSetif it's not already present, and returns a boolean indicating whether the element was added. Similarly, theremovemethod removes the specified element from theSetif it's present, and returns a boolean indicating whether the element was present. Theiteratormethod returns anIteratorover theSet.Here's a little program that takes the words in its argument list and prints out any duplicate words, the number of distinct words, and a list of the words with duplicates eliminated:
Now let's run the program:import java.util.*; public class FindDups { public static void main(String args[]) { Set s = new HashSet(); for (int i=0; i<args.length; i++) if (!s.add(args[i])) System.out.println("Duplicate detected: "+args[i]); System.out.println(s.size()+" distinct words detected: "+s); } }Note that the example code always refers to the collection by its interface type (% java FindDups i came i saw i left Duplicate detected: i Duplicate detected: i 4 distinct words detected: [came, left, saw, i]Set), rather than by its implementation type (HashSet). This is a strongly recommended programming practice, as it gives you the flexibility to change implementations merely by changing the constructor. If the variables used to store a collection, or the parameters used to pass it around, are declared to be of the collection's implementation type rather than its interface type, then all such variables and parameters must be changed to change the collection's implementation type. Furthermore, there's no guarantee that the resulting program will work; if the program uses any non-standard operations that are present in the original implementation type but not the new one, the program will fail. Referring to collections only by their interface keeps you honest, in the sense that it prevents you from using any non-standard operations.The implementation type of the
Setin the example above isHashSet, which makes no guarantees as to the order of the elements in theSet. If you want the program to print the word list in alphabetical order, all you have to do is to change the set's implementation type fromHashSettoTreeSet. Making this trivial one-line change causes the command line in the previous example to generate the following output:% java FindDups i came i saw i left Duplicate word detected: i Duplicate word detected: i 4 distinct words detected: [came, i, left, saw]
The bulk operations are particularly well suited toSets: they perform standard set-algebraic operations. Supposes1ands2areSets. Here's what the bulk operations do:To calculate the union, intersection, or set difference of two sets non-destructively (without modifying either set), the caller must copy one set before calling the appropriate bulk operation. The resulting idioms are shown below:
s1.containsAll(s2): Returnstrueifs2is a subset ofs1. (For example, sets1is a subset ofs2if sets2contains all the elements ins1.)s1.addAll(s2): Transformss1into the union ofs1ands2. (The union of two sets is the set containing all the elements contained in either set.)s1.retainAll(s2): Transformss1into the intersection ofs1ands2. (The intersection of two sets is the set containing only the elements that are common in both sets.)s1.removeAll(s2): Transformss1into the (asymmetric) set difference ofs1ands2. (For example, the set difference ofs1-s2is the set containing all the elements found ins1but not ins2.)The implementation type of the resultSet union = new HashSet(s1); union.addAll(s2); Set intersection = new HashSet(s1); intersection.retainAll(s2); Set difference = new HashSet(s1); difference.removeAll(s2);Setin the above idioms isHashSet, which is, as mentioned above, the best all-aroundSetimplementation in the JDK. However, any general-purposeSetimplementation could be substituted.Let's revisit the
FindDupsexample program above. Suppose you want to know which words in the argument list occur only once and which occur more than once, but you do not want any duplicates printed out repeatedly. This effect can be achieved by generating two sets, one containing every word in the argument list, and the other containing only the duplicates. The words that occur only once are the set difference of these two sets, which we know how to compute. Here's how the resulting program looks:Now let's run the revised program with the same same argument list we used before:import java.util.*; public class FindDups2 { public static void main(String args[]) { Set uniques = new HashSet(); Set dups = new HashSet(); for (int i=0; i<args.length; i++) if (!uniques.add(args[i])) dups.add(args[i]); uniques.removeAll(dups); // Destructive set-difference System.out.println("Unique words: " + uniques); System.out.println("Duplicate words: " + dups); } }A less common set-algebraic operation is the symmetric set difference: the set of elements contained in either of two specified sets, but not contained in both of them. The following code calculates the symmetric set difference of two sets non-destructively:% java FindDups2 i came i saw i left Unique words: [came, left, saw] Duplicate words: [i]Set symmetricDiff = new HashSet(s1); symmetricDiff.addAll(s2); Set tmp = new HashSet(s1); tmp.retainAll(s2); symmetricDiff.removeAll(tmp);
The array operations don't do anything special forSetsbeyond what they do for any otherCollection. They are described in the interface lesson.