Thursday, February 24, 2011

Chapter 48: Backed Collections

Backed Collections is actually a new and unique topic that is part of the exam. Am not going to give you any clue that would spoil the fun and suspense.

So, lets get started!!!

Backed Collections

Some of the classes in the java.util package support the concept of “backed collections”. Lets take a look at a simple example to learn more about it:

TreeMap map = new TreeMap();
map.put("a", "Ferrari"); map.put("d", "Dodge"); map.put("h", "Subaru");

SortedMap submap;
submap = map.subMap("b", "g"); // #1 create a backed collection

System.out.println(map + " " + submap); // #2 show contents

map.put("b", "BMW"); // #3 add to original
submap.put("f", "Suzuki"); // #4 add to copy

map.put("r", "Rover"); // #5 add to original - out of range
// submap.put("p", "Fiat"); // #6 add to copy - out of range

System.out.println(map + " " + submap); // #7 show final contents

This should produce something like this:

{a=Ferrari, d=Dodge, h=Subaru} {d=Dodge}
{a=Ferrari, b=BMW, d=Dodge, f=Suzuki, h=Subaru, r=Rover} {b=BMW, d=Dodge, f=Suzuki}

The important method in this code is the TreeMap.subMap() method. It’s easy to guess (and it’s correct), that the subMap() method is making a copy of a portion of the TreeMap named map. The first line of output verifies the conclusions we’ve just drawn.

What happens next is powerful and a little bit unexpected. When we add key-value pairs to either the original TreeMap or the partial-copy SortedMap, the new entries were automatically added to the other collection—sometimes. When submap was created, we provided a value range for the new collection. This range defines not only what should be included when the partial copy is created, but also defines the range of values that can be added to the copy. As we can verify by looking at the second line of output, we can add new entries to either collection within the range of the copy, and the new entries will show up in both collections. In addition, we can add a new entry to the original collection, even if it’s outside the range of the copy. In this case, the new entry will show up only in the original—it won’t be added to the copy because it’s outside the copy’s range. Notice that we commented out line #6. If you attempt to add an out-of-range entry to the copied collection an exception will be thrown.

For the exam, you’ll need to understand the basics just explained, plus a few more details about three methods from TreeSet—(headSet(), subSet(), and tailSet()), and three methods from TreeMap (headMap(), subMap(), and tailMap()). As with the navigation-oriented methods we just discussed,

we can see a lot of parallels between the TreeSet and the TreeMap methods. The headSet() / headMap() methods create a subset that starts at the beginning of the original collection and ends at the point specified by the method’s argument. The tailSet() / tailMap() methods create a subset that starts at the point specified by the method’s argument and goes to the end of the original collection. Finally, the subSet() / subMap() methods allow you to specify both the start and end points for the subset collection you’re creating.

As you might expect, the question of whether the subsetted collection’s end points are inclusive or exclusive is a little tricky. The good news is that for the exam you have to remember only that when these methods are invoked with endpoint and boolean arguments, the boolean always means “is inclusive?”. A little more good news is that all you have to know for the exam is that unless specifically indicated by a boolean argument, a subset’s starting point will always be inclusive. Finally, you’ll notice when you study the API that all of the methods we’ve been discussing here have an overloaded version that’s new to Java 6. The older methods return either a SortedSet or a SortedMap, the new Java 6 methods return either a NavigableSet or a NavigableMap.

Let us summarize the details of the methods and their features using the table below:
Method Name Description/Purpose
headSet(e, b) Returns a subset ending at element e and exclusive of e
headMap(k, b) Returns a submap ending at key k and exclusive of key k
tailSet(e, b) Returns a subset starting at and inclusive of element e
tailMap(k, b) Returns a submap starting at and inclusive of key k
subSet(s, b, e, b) Returns a subset starting at element s and ending just before element e
subMap(s, b, e, b) Returns a submap starting at key s and ending just before key s
NOTE: These boolean arguments ‘b’ are optional. If they exist it’s a Java 6 method that lets you specify whether the endpoint is exclusive, and these methods return a NavigableXxx. If the boolean argument(s) don’t exist, the method returns either a SortedSet or a SortedMap.

Exam Tip: Let’s say that you’ve created a backed collection using either a tailXxx() or subXxx() method. Typically in these cases the original and copy collections have different “first” elements. For the exam it’s important that you remember that the pollFirstXxx() methods will always remove the first entry from the collection on which they’re invoked, but they will remove an element from the other collection only if it has same value. So it’s most likely that invoking pollFirstXxx() on the copy will remove an entry from both collections, but invoking pollFirstXxx() on the original will remove only the entry from the original.

Previous Chapter: Chapter 47 - Searching TreeSets and TreeMaps

Next Chapter: Chapter 49 - Priority Queue

No comments:

Post a Comment

© 2013 by All rights reserved. No part of this blog or its contents may be reproduced or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without prior written permission of the Author.


Google+ Followers