SortedMap Part I

1. Understanding SortedMap

The main characteristic of a SortedMap is that, it orders the keys by their natural ordering, or by a specified comparator. So consider using a TreeMap when you want a map that satisfies the following criteria:

  • null key or null value are not permitted.
  • The keys are sorted either by natural ordering or by a specified comparator.

The following example realizes the concept of a SortedMap:

1
2
3
4
5
6
7
8
9
SortedMap<String, String> mapDomains = new TreeMap<>();
mapDomains.put(".com", "International");
mapDomains.put(".us", "United States");
mapDomains.put(".uk", "United Kingdom");
mapDomains.put(".jp", "Japan");
mapDomains.put(".au", "Australia");
System.out.println(mapDomains);

Output:

1
{.au=Australia, .com=International, .jp=Japan, .uk=United Kingdom, .us=United States}

Here, this map contains mappings of domain=country, and as we see in the output, the domains (keys) are sorted by alphabetic order (natural ordering of Strings).

 

Besides the operations inherited from the Map interface, the SortedMap also defines the following operations:

  • Range view: returns a sub sorted map whose keys fall within a range of keys in the original map.
  • Endpoints: returns the first or last key in the sorted map.
  • Comparator access: returns the comparator (implements the Comparator interface), if any, used to sort the map.

Hence the following code is the definition of a SortedMap:

1
2
3
4
5
6
7
8
public interface SortedMap<K, V> extends Map<K, V>{
    Comparator<? super K> comparator();
    SortedMap<K, V> subMap(K fromKey, K toKey);
    SortedMap<K, V> headMap(K toKey);
    SortedMap<K, V> tailMap(K fromKey);
    K firstKey();
    K lastKey();
}

Let’s look at each type of operation in details. * Range View Operations:+ subMap(K fromKey, K toKey): returns a sorted map whose keys range from fromKey, inclusive, to toKey, exclusive.+ headMap(K toKey): returns a sorted map whose keys are strictly less than toKey.+ tailMap(K fromKey): returns a sorted map whose keys are greater than or equal to fromKey. * Endpoint operations:+ firstKey(): returns the first (lowest) key currently in the map.+ lastKey(): returns the last (highest) key currently in the map. * Comparator access:+ comparator(): returns the comparator used to order the keys in the map, or returns null if this map uses the natural ordering of its keys.

2. SortedMap and TreeMap Examples

The following code example demonstrates how to work with these operations on a TreeMap:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
SortedMap<Integer, String> mapHttpStatus = new TreeMap<>();
mapHttpStatus.put(100, "Continue");
mapHttpStatus.put(200, "OK");
mapHttpStatus.put(300, "Multiple Choices");
mapHttpStatus.put(400, "Bad Request");
mapHttpStatus.put(401, "Unauthorized");
mapHttpStatus.put(402, "Payment Required");
mapHttpStatus.put(403, "Forbidden");
mapHttpStatus.put(404, "Not Found");
mapHttpStatus.put(500, "Internal Server Error");
mapHttpStatus.put(501, "Not Implemented");
mapHttpStatus.put(502, "Bad Gateway");
System.out.println("All key-value pairs: ");
for (Integer code : mapHttpStatus.keySet()) {
    System.out.println(code + " -> " + mapHttpStatus.get(code));
}
System.out.println();
Integer firstKey = mapHttpStatus.firstKey();
String firstValue = mapHttpStatus.get(firstKey);
System.out.println("First status: " + firstKey + " -> " + firstValue);
System.out.println();
Integer lastKey = mapHttpStatus.lastKey();
String lastValue = mapHttpStatus.get(lastKey);
System.out.println("Last status: " + lastKey + " -> " + lastValue);
System.out.println();
SortedMap<Integer, String> map4xxStatus = mapHttpStatus.subMap(400, 500);
System.out.println("4xx Statuses: ");
for (Integer code : map4xxStatus.keySet()) {
    System.out.println(code + " -> " + map4xxStatus.get(code));
}
System.out.println();
SortedMap<Integer, String> mapUnder300Status = mapHttpStatus.headMap(300);
System.out.println("Statuses < 300: ");
for (Integer code : mapUnder300Status.keySet()) {
    System.out.println(code + " -> " + mapUnder300Status.get(code));
}
System.out.println();
SortedMap<Integer, String> mapAbove500Status = mapHttpStatus.tailMap(500);
System.out.println("Statuses > 500: ");
for (Integer code : mapAbove500Status.keySet()) {
    System.out.println(code + " -> " + mapAbove500Status.get(code));
}
Comparator comparator = mapHttpStatus.comparator();
System.out.println("Sorted by natural ordering? " + (comparator == null));

Output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
All key-value pairs:
100 -> Continue
200 -> OK
300 -> Multiple Choices
400 -> Bad Request
401 -> Unauthorized
402 -> Payment Required
403 -> Forbidden
404 -> Not Found
500 -> Internal Server Error
501 -> Not Implemented
502 -> Bad Gateway
First status: 100 -> Continue
Last status: 502 -> Bad Gateway
4xx Statuses:
400 -> Bad Request
401 -> Unauthorized
402 -> Payment Required
403 -> Forbidden
404 -> Not Found
Statuses < 300:
100 -> Continue
200 -> OK
Statuses > 500:
500 -> Internal Server Error
501 -> Not Implemented
502 -> Bad Gateway
Sorted by natural ordering? true   

And the following example shows how to use a comparator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
SortedMap<Integer, String> mapHttpStatus = new TreeMap<>(new ReverseComparator());
mapHttpStatus.put(100, "Continue");
mapHttpStatus.put(200, "OK");
mapHttpStatus.put(300, "Multiple Choices");
mapHttpStatus.put(400, "Bad Request");
mapHttpStatus.put(401, "Unauthorized");
mapHttpStatus.put(402, "Payment Required");
mapHttpStatus.put(403, "Forbidden");
mapHttpStatus.put(404, "Not Found");
mapHttpStatus.put(500, "Internal Server Error");
mapHttpStatus.put(501, "Not Implemented");
mapHttpStatus.put(502, "Bad Gateway");
for (Integer code : mapHttpStatus.keySet()) {
    System.out.println(code + " -> " + mapHttpStatus.get(code));
}

Here’s the code of the comparator class:

1
2
3
4
5
class ReverseComparator implements Comparator<Integer> {
    public int compare(Integer num1, Integer num2) {
        return num2.compareTo(num1);
    }
}

Output:

1
2
3
4
5
6
7
8
9
10
11
502 -> Bad Gateway
501 -> Not Implemented
500 -> Internal Server Error
404 -> Not Found
403 -> Forbidden
402 -> Payment Required
401 -> Unauthorized
400 -> Bad Request
300 -> Multiple Choices
200 -> OK
100 -> Continue

As you can see, this comparator sorts the map by the descending order of its keys.In case you are working on Java 8, use Lambda expressions to shorten the comparator code like this:

1
SortedMap<Integer, String> mapHttpStatus = new TreeMap<>((i1, i2) -> i2.compareTo(i1));
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: