How do you implement a custom Map in Java Collections that supports efficient range queries, and what are some use cases for doing so?

In Java Collections, a Map is an interface that maps keys to values. It provides several methods for manipulating the elements in the map. However, the built-in Map implementations in Java do not support efficient range queries, which can be useful in certain scenarios, such as searching for a range of values within a given range of keys. In such cases, a custom Map implementation may be required.

One approach for implementing a custom Map with efficient range queries is to use a data structure called a TreeMap. A TreeMap is a sorted map that is implemented as a red-black tree. The keys are sorted in ascending order, and each key is associated with a value. TreeMap provides efficient range queries using the subMap() method.

Here is an example implementation of a custom TreeMap-based map that supports range queries:

import java.util.TreeMap;

public class RangeMap<K extends Comparable<K>, V> {
    private final TreeMap<K, V> map;

    public RangeMap() {
        map = new TreeMap<>();
    }

    public void put(K key, V value) {
        map.put(key, value);
    }

    public V get(K key) {
        return map.get(key);
    }

    public V remove(K key) {
        return map.remove(key);
    }

    public RangeMap<K, V> subMap(K fromKey, K toKey) {
        RangeMap<K, V> rangeMap = new RangeMap<>();
        rangeMap.map.putAll(map.subMap(fromKey, toKey));
        return rangeMap;
    }
}

In this example, the custom RangeMap class is implemented using a TreeMap, and the subMap() method is overridden to return a new RangeMap containing a submap of the original TreeMap.

Here is an example usage of the RangeMap class:

RangeMap<Integer, String> map = new RangeMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
map.put(4, "four");
map.put(5, "five");
RangeMap<Integer, String> subMap = map.subMap(2, 5);
System.out.println(subMap.get(2)); // prints "two"
System.out.println(subMap.get(3)); // prints "three"
System.out.println(subMap.get(4)); // prints "four"

In this example, a RangeMap is created and populated with key-value pairs. The subMap() method is then used to create a submap containing the range of keys from 2 to 5. The get() method is then used to retrieve values from the submap.

A custom Map implementation like RangeMap can be useful in a variety of scenarios, such as indexing data in a database or performing range queries on sorted data.