Fancy Uses of Collection-Views: Map Algebra

When applied to the Collection-views, the bulk operations (containsAll, removeAll and retainAll) are a surprisingly potent tool. For starters, suppose you want to know whether one Map is a submap of another, that is, whether the first Map contains all of the key-value mappings in the second. The following idiom does the trick:

if (m1.entrySet().containsAll(m2.entrySet())) {
    ...
}

Along similar lines, suppose that you want to know if two Map objects contain mappings for all the same keys:

if (m1.keySet().equals(m2.keySet())) {
    ...
}

Suppose you have a map that represents a collection of attribute-value pairs, and two sets, representing required attributes and permissible attributes. (The permissible attributes include the required attributes.) The following snippet determines whether the attribute map conforms to these constraints, and prints a detailed error message if it doesn't:

boolean valid = true;
Set attributes = attributeMap.keySet();
if(!attributes.containsAll(requiredAttributes)) {
    Set missing = new HashSet(requiredAttributes);
    missing.removeAll(attributes);
    System.out.println("Missing required attributes: "+missing);
    valid = false;
}

if (!permissibleAttributes.containsAll(attributes)) {
    Set illegal = new HashSet(attributes);
    illegal.removeAll(permissibleAttributes);
    System.out.println("Contains illegal attributes: "+illegal);
    valid = false;
}

if (valid)
    System.out.println("OK");

Suppose you want to know all the keys common to two Map objects:

Set commonKeys = new HashSet(a.keySet());
commonKeys.retainAll(b.keySet());

A similar idiom gets you the common values, and the common key-value pairs. Extra care is needed if you get the common key-value pairs, as the elements of the resulting Set, which are Map.Entry objects, may become invalid if the Map is modified. All the idioms presented thus far have been "non-destructive": They don't modify the backing Map. Here are a few that do. Suppose you want to remove all the key-value pairs that one Map has in common with another:

m1.entrySet().removeAll(m2.entrySet());

Suppose you want to remove from one Map all the keys that have mappings in another:

m1.keySet().removeAll(m2.keySet());

And what happens when you start mixing keys and values in the same bulk operation? Suppose you have a Map called managers that maps each employee in a company to the employee's manager. We'll be deliberately vague about the types of the key and value objects. It doesn't matter, so long as they're the same. Now suppose you want to know who all the "individual contributors" are. (This is corporate-speak for employees who are not managers.) The following one-liner tells you exactly what you want to know:

Set individualContributors = new HashSet(managers.keySet());
individualContributors.removeAll(managers.values());

Suppose you want to fire all of the employees who report directly to some manager (we'll call him herbert):

Employee herbert = ... ;
managers.values().removeAll(Collections.singleton(herbert));

Note that this idiom makes use of Collections.singleton, a static factory method that returns an immutable Set with the single, specified element. Once you've done this, you may have a bunch of employees whose managers no longer work for the company (if any of herbert's direct-reports were themselves managers). The following code tells you all of the employees whose manager no longer works for the company:

Map m = new HashMap(managers);
m.values().removeAll(managers.keySet());
Set slackers = m.keySet();

This example is a bit tricky. First it makes a temporary copy of the Map. Then it removes from the temporary copy all entries whose (manager) value is a key in the original Map. Recall that the original Map contains an entry for every employee. Thus, the remaining entries in the temporary Map comprise all the entries from the original Map whose (manager) values are no longer employees. The keys in the temporary copy, then, represent precisely the employees that we're looking for. If you stare at the example for a little while, this should all become clear. If it doesn't, now would be a good time to get a steaming hot mug of freshly brewed Java. There are many, many more idioms like the ones contained in this section but it would be impractical and tedious to list them all. Once you get the hang of it, it's not that hard to come up with the right one when you need it.