Section 11.8. Sets

11.8 Sets

Most of the straightforward kinds of collections storage can be done in lists. The Set is a kind of expansion of List that allows you greater control over the elements contained in it. A Set is a List that does not allow duplicate elements. Because ColdFusion has no precisely corresponding storage mechanism, you might think of this as a primary key in a relational database table ”it is just a uniqueness constraint.

The Set classes include: SortedSet , TreeSet , and HashSet , which we will discuss here in turn . Any Set implements these methods , among others:

add() adds an element to the set. Returns boolean regarding success of the operation. Returns false if an attempt is made to add a duplicate element to the set.
contains(Object o) returns boolean true if the set contains the element specified.
equals(Object o) compares the object specified with this Set .
remove(Object o) removes the object from the Set . If not present, returns false .
size () returns an int representing the cardinality of the Set .

The Set is meant as an implementation of a mathematical abstract set. That means that logical (mathematical) operations standard to set theory (such as intersection, union, and so forth) can be performed on them.

Two sets are considered equal if they contain all of the same elements. It does not matter what order the elements are in; simple presence of all of the same elements is enough for them to be equal.

11.8.1 `TreeSet`

The TreeSet has certain features that distinguish it from other kinds of sets:

Elements are stored in ascending order.
You need to implement the java.lang.Comparable interface for your objects in order to perform sorting.

Note

The Comparable interface imposes an order on each implementing class in order to sort them alphabetically . Lists and arrays can be sorted automatically using Collections.sort() and Arrays.sort() .

SortedSet is an interface implemented by only one class in the JDK: the TreeSet . The chief purpose of the SortedSet is to allow you to extend the collections yourself. So we will demonstrate an example of TreeSets in the SetsTest.java listing.

11.8.2 `HashSet`

A HashSet implements the set interface, storing its data as an instance of HashMap . The following things are characteristics of HashSet :

The HashSet is not synchronized. That means you need to add your own synchronization if multiple threads might access the set concurrently. If you do not have an object available externally with which to wrap the set, then you should wrap your set using the Collections.synchronized() set method.
Sets operate on each element container (or "bucket") in even distribution. That means that you should not set the initial capacity of your set too high, or performance will be hindered unnecessarily.

A HashSet is often faster performing than a TreeSet . This is because the data in a TreeSet is ordered, and a HashSet 's data is not.

Note

A ColdFusion structure's data is unordered, like a HashSet .

11.8.3 Set Theory Operations

In set theory there are several kinds of relationships that can be defined between the elements of different sets. You may be familiar with some of these from working with relational databases. The three most commonly used in programming are probably union (which is actually an SQL keyword carried over from set theory), intersection, and difference.

11.8.3.1 UNION

A union of two sets creates a third set that is composed exclusively of the unique elements common to both sets. Say you had two sets of letters . The first set is composed of vowels , and the second set is composed of the first five letters of the alphabet:

Vowels = {a,e,i,o,u}

FirstFiveLetters = {a,b,c,d,e}

The union of these two sets is:

Union = {a,b,c,d,e,i,o,u}

The letter a is common to both sets, and is therefore not repeated in the union. The union of all winged creatures and all non-winged creatures is the set of all creatures .

The Java method Collection.addAll() will produce a union. That is, it adds all of the elements in the specified collection to this set if they are not already in it.

11.8.3.2 INTERSECTION

An intersection is different from a union. Performing an intersection on two sets creates a new set that contains all of the elements of both sets. An intersection using the letter sets above contains only one element: a.

The Java method Collection.retainAll() produces an intersection. That is, it retains only the elements in this set that are contained in the collection specified.

11.8.3.3 DIFFERENCE

The difference set of two sets contains varying results depending on the order in which you compare the two sets. For example, the difference between Vowels and FirstFiveLetters is {e,i,o,u}. The difference between FirstFiveLetters and Vowels is {b,c,d,e}.

The way to get a difference set in Java is to call the Collections.removeAll() method.

11.8.4 The Barber Paradox

I can't resist repeating this favorite set theory story, which illustrates the paradoxical nature of sets. Suppose there is a barber, who perhaps lives in Seville. This barber shaves all the men in the town who do not shave themselves . The paradox is clear: if he does not shave himself, he must shave himself. If he does shave himself, then he is not one of the people he shaves. In practical terms there are very easy ways to resolve the paradox. For instance, the barber could be a woman . But in purely theoretical terms it is interesting.

Let's write a quick example that populates two collections and compares their values, printing sets for the union, intersection, and difference of the values.

11.8.5 `SetsTest.java`

 package chp11;  import java.util.*; public class SetsTest {     public static void main (String[] a) {         String one="1";         String two = "2";         String three = "3";         String four = "4";         String five = "5";         String six = "6";         String seven = "7";         String eight = "8";         String nine = "9";         // create a hashset to hold         // prime numbers less than 10     TreeSet primes = new TreeSet();     primes.add(two);     primes.add(three);     primes.add(five);     primes.add(seven);         // create another hashset to hold         // odd numbers less than 10     TreeSet odds = new TreeSet();     odds.add(one);     odds.add(three);     odds.add(five);     odds.add(seven);     odds.add(nine);     System.out.println("Primes: " + primes);     System.out.println("Odds: " + odds);     TreeSet difference = new TreeSet(odds);     difference.removeAll(primes);     System.out.println("Difference: " + difference);         // get the intersection of the sets     TreeSet intersect = new TreeSet(primes);     intersect.retainAll(odds);     System.out.println("Intersection: " + intersect);             // get the union of the sets     TreeSet union =  new TreeSet (primes);     union.addAll(odds);     System.out.println("Union: " + union);     } }

The output is like this:

 Primes: [2, 3, 5, 7]  Odds: [1, 3, 5, 7, 9] Difference: [1, 9] Intersection: [3, 5, 7] Union: [1, 2, 3, 5, 7, 9]

11.8.6 Summary of Sets

Sets are collections of unique objects. Use them only if your storage scheme requires uniqueness. You need to implement the java.lang.Comparable interface when using a TreeSet , because this interface defines compareTo() , which TreeSet uses to put your objects in order. Remember that it is important not to change values once you have added them to a set. Changing a value could violate the uniqueness in your set.

Top