Transilvania JUG

Sponsors

20
Mar
2011
0

Navigating (Searching) Collections

The Java collections framework includes the concept of NavigableSets / NavigableMaps. The principle behind these interfaces is that taking a SortedSet/SortedMap you can use a subset of it. Some examples:

Given the following set:

1
2
3
4
5
@Before
public void setUp() {
  set = new TreeSet();
  set.addAll(Arrays.asList(1, 2, 3, 4, 6, 7, 8));
}

The following is true:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Returns the least element in this set greater than or equal to the given element
assertEquals(Integer.valueOf(6), set.ceiling(5)); 
// Returns the greatest element in this set less than or equal to the given element
assertEquals(Integer.valueOf(4), set.floor(5));
// Returns the least element in this set strictly greater than the given element
assertEquals(Integer.valueOf(7), set.higher(6));
// Returns the greatest element in this set strictly less than the given element
assertEquals(Integer.valueOf(3), set.lower(4));
 
// Returns a view of the portion of this set whose elements are strictly less than toElement.
assertTrue(set.headSet(4).containsAll(Arrays.asList(1, 2, 3)));
assertEquals(3, set.headSet(4).size());
// Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
assertTrue(set.tailSet(4).containsAll(Arrays.asList(4, 6, 7, 8)));
assertEquals(4, set.tailSet(4).size());
// Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.
assertTrue(set.subSet(4, 8).containsAll(Arrays.asList(4, 6, 7)));
assertEquals(3, set.subSet(4, 8).size());

Also, the subsets / submaps / “views” remain connected to the parent collection, so adding / removing to/from the parent collection updates them:

1
2
3
4
5
6
7
8
9
10
11
12
13
SortedSet headSet = set.headSet(4);
assertTrue(headSet.containsAll(Arrays.asList(1, 2, 3)));
assertEquals(3, headSet.size());
 
// subsets remain connected
set.removeAll(Arrays.asList(1, 2));
assertTrue(headSet.containsAll(Arrays.asList(3)));
assertEquals(1, headSet.size());
 
// subsets remain connected
set.addAll(Arrays.asList(-1, 1, 2, 3, 4, 5));
assertTrue(headSet.containsAll(Arrays.asList(-1, 1, 2, 3)));
assertEquals(4, headSet.size());

Finally, you manipulate the subsets and the result will be reflected in the original set (however if you try to add an out-of-range element, you will get an exception):

1
2
3
4
5
6
SortedSet headSet = set.headSet(4);
headSet.add(-1);
assertTrue(headSet.containsAll(Arrays.asList(-1, 1, 2, 3)));
assertEquals(4, headSet.size());
assertTrue(set.containsAll(Arrays.asList(-1, 1, 2, 3, 4, 6, 7, 8)));
assertEquals(8, set.size());

The implementation is very memory efficient, there is no copying of elements going on. One thing to consider is that by default these operations are not thread safe! Ie. if you generate two subsets of the same set and process them on two different threads, you must take care to properly synchronize the processing.

Standard postscript: this is a guest-post by Attila Balazs (aka Cd-MaN). The text of the article is available under the CC-BY-SA license. The associated source code is available under public domain, CC0 or the MIT/X License, depending on your preference. See Checking out the samples for a more detailed description about how to get the associate source code.

Leave a Reply

Your email address will not be published. Required fields are marked *

df