Beginning Algorithms (2006)

Chapter 12

Because a set may contain any given value only once, adding a value may not always be successful; if the value already exists, it won’t be added again. For this reason, the add() operation indicates whether the value was added. Similarly, delete() indicates whether the value was deleted — that is, whether it existed or not.

In addition to adding and deleting values, you can query a set to determine whether a value is contained, check the size of the set, and iterate through all the values. Iterating over a set differs from iterating through a list in that lists guarantee an explicit ordering of values, whereas sets make no such promise; although ordering is not prohibited — ordered set implementations are entirely possible — in general, sets treat all values equally and make no guarantees as to the order of iteration.

294

Sets

Sets can be combined in various interesting and useful ways.

Assume you have the two sets shown in Figure 12-2.

B H

E I F I F

K

A D D

C

J G

X Y

Figure 12-2: Two sets: X = {A, B, D, E, F, I, J} and Y = {C, D, F, G, H, I, K}.

The union of two sets is another set containing all the values from both, remembering of course that a set has no duplicates. You can also think of this as adding two sets together. Figure 12-3 shows the union of the two sets X and Y. Notice that even though both sets contain some overlapping values — D, I, and F — the resulting set contains no duplicates.

Figure 12-3: The union of two sets: X + Y.

295

Chapter 12

The intersection of two sets is another set that contains only those values that are common to both, again remembering that a set can contain no duplicate values. Figure 12-4 shows the intersection of the two sets X and Y. Notice that the result contains only those values that exist in both X and Y.

Figure 12-4: The intersection of two sets: X ∩ Y.

The difference between two sets is all elements from one set that are not also members of another. You can think of this as subtracting one set from another. Figure 12-5 shows what happens when set Y is subtracted from set X. Notice that the result contains only those values from X that aren’t also contained in Y.

Figure 12-5: The difference between two sets: X – Y.

So that you can easily plug in different set implementations depending on the needs of your application, and, just as important, so that you can easily test each type of set, in the next Try It Out section you create an interface that defines all of the required methods.

296

Sets

Try It Out Creating a Generic Set Interface

Create the Set interface as follows:

package com.wrox.algorithms.sets;

public interface Set extends Iterable { public boolean add(Object value); public boolean delete(Object value);

public boolean contains(Object value); public void clear();

public int size(); public boolean isEmpty();

}

How It Works

The Set interface has all of the operations listed in Table 12-1 converted directly into methods on a Java interface. In addition, you’ve extended the Iterable interface, which defines the iterator() method, enabling a set to be used anywhere an Iterable is required.

Testing Set Implementations

So that you can be sure that every set implementation you create behaves correctly, in the next Try It Out section you develop a suite of tests that will work for any type of set.

Create the abstract test class as follows:

package com.wrox.algorithms.sets;

import com.wrox.algorithms.iteration.Iterator;

import com.wrox.algorithms.iteration.IteratorOutOfBoundsException; import com.wrox.algorithms.iteration.ReverseIterator;

import com.wrox.algorithms.lists.LinkedList; import com.wrox.algorithms.lists.List; import junit.framework.TestCase;

public abstract class AbstractSetTestCase extends TestCase { private static final Object A = “a”;

private static final Object B = “b”; private static final Object C = “c”; private static final Object D = “d”; private static final Object E = “e”; private static final Object F = “f”;

private Set _set;

protected void setUp() throws Exception { _set = createSet();

297

Chapter 12

_set.add(C); _set.add(A); _set.add(B); _set.add(D);

}

protected abstract Set createSet();

public void testContainsExisting() { assertTrue(_set.contains(A)); assertTrue(_set.contains(B)); assertTrue(_set.contains(C)); assertTrue(_set.contains(D));

}

public void testContainsNonExisting() { assertFalse(_set.contains(E)); assertFalse(_set.contains(F));

}

public void testAddNewValue() { assertEquals(4, _set.size());

assertTrue(_set.add(E)); assertTrue(_set.contains(E)); assertEquals(5, _set.size());

assertTrue(_set.add(F)); assertTrue(_set.contains(F)); assertEquals(6, _set.size());

}

public void testAddExistingValueHasNoEffect() { assertEquals(4, _set.size()); assertFalse(_set.add(C));

assertEquals(4, _set.size());

}

public void testDeleteExisting() { assertTrue(_set.delete(B)); assertFalse(_set.contains(B)); assertEquals(3, _set.size());

assertTrue(_set.delete(A)); assertFalse(_set.contains(A)); assertEquals(2, _set.size());

assertTrue(_set.delete(C)); assertFalse(_set.contains(C)); assertEquals(1, _set.size());

assertTrue(_set.delete(D)); assertFalse(_set.contains(D));

298

Sets

assertEquals(0, _set.size());

}

public void testDeleteNonExisting() { assertEquals(4, _set.size()); assertFalse(_set.delete(E)); assertEquals(4, _set.size()); assertFalse(_set.delete(F)); assertEquals(4, _set.size());

}

public void testClear() { assertEquals(4, _set.size()); assertFalse(_set.isEmpty());

_set.clear();

assertEquals(0, _set.size()); assertTrue(_set.isEmpty());

assertFalse(_set.contains(A)); assertFalse(_set.contains(B)); assertFalse(_set.contains(C)); assertFalse(_set.contains(D));

}

public void testIteratorForwards() { checkIterator(_set.iterator());

}

public void testIteratorBackwards() {

checkIterator(new ReverseIterator(_set.iterator()));

}

private void checkIterator(Iterator i) { List values = new LinkedList();

for (i.first(); !i.isDone(); i.next()) { values.add(i.current());

}

try { i.current(); fail();

} catch (IteratorOutOfBoundsException e) {

}

assertEquals(4, values.size()); assertTrue(values.contains(A)); assertTrue(values.contains(B)); assertTrue(values.contains(C)); assertTrue(values.contains(D));

}

}

299

Chapter 12

How It Works

The class AbstractSetTestCase extends TestCase in order to make it a proper JUnit-compatible test class. It also defines some sample entries and a map for testing. The set is assigned a value in the

setUp() method — which runs just prior to each test case — and the first four sample values are added:

package com.wrox.algorithms.sets;

import com.wrox.algorithms.iteration.Iterator; import com.wrox.algorithms.iteration.ReverseIterator;

import com.wrox.algorithms.iteration.IteratorOutOfBoundsException; import com.wrox.algorithms.lists.LinkedList;

import com.wrox.algorithms.lists.List; import junit.framework.TestCase;

public abstract class AbstractSetTestCase extends TestCase { private static final Object A = “a”;

private static final Object B = “b”; private static final Object C = “c”; private static final Object D = “d”; private static final Object E = “e”; private static final Object F = “f”;

private Set _set;

protected void setUp() throws Exception { _set = createSet();

_set.add(C); _set.add(A); _set.add(B); _set.add(D);

}

protected abstract Set createSet();

...

}

The contains() method should return true for any value that is contained within the set, or false otherwise. You know that four of the sample values do exist, so in testContainsExisting(), you check to ensure that contains() returns true for each one:

public void testContainsExisting() { assertTrue(_set.contains(A)); assertTrue(_set.contains(B)); assertTrue(_set.contains(C)); assertTrue(_set.contains(D));

}

Conversely, testContainsNonExisting() ensures that contains() returns false for values that are known not to exist:

300

Sets

public void testContainsNonExisting() { assertFalse(_set.contains(E)); assertFalse(_set.contains(F));

}

The testAddNewKey() method first checks the initial size of the set before adding two values. Each time add() is called, the return value is checked to ensure it is true, indicating there was no existing value; contains() is then called to ensure that the new value exists, and the size is checked to ensure it has increased by one:

public void testAddNewValue() { assertEquals(4, _set.size());

assertTrue(_set.add(E)); assertTrue(_set.contains(E)); assertEquals(5, _set.size());

assertTrue(_set.add(F)); assertTrue(_set.contains(F)); assertEquals(6, _set.size());

}

The method testAddExistingValueHasNoEffect() simply attempts to add all the values again. Each time a duplicate is added, the return value and size are checked to ensure that the call has had no effect:

public void testAddExistingValueHasNoEffect() { assertEquals(4, _set.size());

assertFalse(_set.add(A)); assertEquals(4, _set.size());

assertFalse(_set.add(B)); assertEquals(4, _set.size());

assertFalse(_set.add(C)); assertEquals(4, _set.size());

assertFalse(_set.add(D)); assertEquals(4, _set.size());

}

Next, testDeleteExisting() removes each of the four values that were used to populate the set initially. Each time delete() is called, the return value and size of the set are checked to ensure they reflect the deletion:

public void testDeleteExisting() { assertEquals(4, _set.size());

assertTrue(_set.delete(B)); assertFalse(_set.contains(B)); assertEquals(3, _set.size());

assertTrue(_set.delete(A));

301

Chapter 12

assertFalse(_set.contains(A)); assertEquals(2, _set.size());

assertTrue(_set.delete(C)); assertFalse(_set.contains(C)); assertEquals(1, _set.size());

assertTrue(_set.delete(D)); assertFalse(_set.contains(D)); assertEquals(0, _set.size());

}

Naturally, you also test what happens when trying to delete a non-existing value. After checking the size of the set, testDeleteNonExisting() calls delete() to remove two values known not to exist. Each time, the size is checked to ensure it hasn’t changed:

public void testDeleteNonExisting() { assertEquals(4, _set.size());

assertFalse(_set.delete(E)); assertEquals(4, _set.size());

assertFalse(_set.delete(F)); assertEquals(4, _set.size());

}

The method testClear() first ensures that the set is not empty. Then clear() is called and the set is once again checked to ensure that it no longer contains any values:

public void testClear() { assertEquals(4, _set.size()); assertFalse(_set.isEmpty());

_set.clear();

assertEquals(0, _set.size()); assertTrue(_set.isEmpty());

assertFalse(_set.contains(A)); assertFalse(_set.contains(B)); assertFalse(_set.contains(C)); assertFalse(_set.contains(D));

}

Finally, you verify that iterating through the contents of a set — both forwards and backwards — returns all the expected values. The method checkIterator() does most of the work. It first iterates over all the values in the set, adding them to a list. Then, after ensuring the iterator throws the appropriate exception once it has completed, the list is checked to ensure that it contains all the expected values:

private void checkIterator(Iterator i) { List values = new LinkedList();

for (i.first(); !i.isDone(); i.next()) {

302

Sets

values.add(i.current());

}

try { i.current(); fail();

}catch (IteratorOutOfBoundsException e) {

//expected

}

assertEquals(4, values.size()); assertTrue(values.contains(A)); assertTrue(values.contains(B)); assertTrue(values.contains(C)); assertTrue(values.contains(D));

}

Then, to test forwards iteration, testIteratorForwards() simply obtains an iterator from the set and hands it off to checkIterator():

public void testIteratorForwards() { checkIterator(_set.iterator());

}

Finally, to test reverse iteration, testIteratorBackwards() wraps the iterator in a ReverseIterator (see Chapter 2) before calling checkIterator(). In this way, all calls to first() and next() are redirected to last() and previous(), respectively, meaning you don’t have to write a separate set of tests:

public void testIteratorBackwards() {

checkIterator(new ReverseIterator(_set.iterator()));

}

A List Set

In the next Try It Out section, you create a set that uses a list as the underlying storage mechanism. The implementation is very straightforward and easy to follow, and although it isn’t particularly efficient, it is useful for small data sets.

Start by creating the list set tests:

package com.wrox.algorithms.maps;

public class ListMapTest extends AbstractMapTestCase { protected Map createMap() {

return new ListMap();

}

}

303