Using Java Map for Range Searches

Using java map for range searches

I can think of a number of possible solutions for the more general problem where the ranges are not uniform and there are 'holes'. The simplest are:

1. Simply populate a Map for all valid key values, with multiple keys mapping to the same value. Assuming that you use HashMaps, this should be the most time efficient (O(1) lookups), though you have more work at setup time and you use more space.
2. Use a NavigableMap and use floorEntry(key) to do the lookups. This should be less time efficient (O(log(N) lookups) but more space efficient.

Here's a solution using NavigableMaps that allows for 'holes' in the mapping.

private static class Range {
   public int upper, value;
   ...
}

NavigableMap<Integer, Range> map = new TreeMap<Integer, Range>();
map.put(0, new Range(3, 0));       // 0..3     => 0
map.put(5, new Range(10, 1));      // 5..10    => 1
map.put(100, new Range(200, 2));   // 100..200 => 2

// To do a lookup for some value in 'key'
Map.Entry<Integer,Range> entry = map.floorEntry(key);
if (entry == null) {
    // too small
} else if (key <= entry.getValue().upper) {
    return entry.getValue().value;
} else {
    // too large or in a hole
}

On the other hand, if there are no 'holes' the solution is simpler:

NavigableMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
map.put(0, 0);    // 0..4     => 0
map.put(5, 1);    // 5..10    => 1
map.put(11, 2);   // 11..200  => 2

// To do a lookup for some value in 'key'
if (key < 0 || key > 200) {
    // out of range
} else {
   return map.floorEntry(key).getValue();
}

Data structures that can map a range of keys to a value

Are your ranges non-overlapping? If so you could use a TreeMap:

TreeMap<Double, Character> m = new TreeMap<Double, Character>();
m.put(1.0, 'A');
m.put(2.9, null);
m.put(4.0, 'B');
m.put(6.0, null);
m.put(6.5, 'C');
m.put(10.0, null);

The lookup logic is a bit complicated by the fact that you probably want an inclusive lookup (i.e. 2.9 maps to 'A', and not undefined):

private static <K, V> V mappedValue(TreeMap<K, V> map, K key) {
    Entry<K, V> e = map.floorEntry(key);
    if (e != null && e.getValue() == null) {
        e = map.lowerEntry(key);
    }
    return e == null ? null : e.getValue();
}

Example:

mappedValue(m, 5) == 'B'

More results include:

0.9 null
1.0 A
1.1 A
2.8 A
2.9 A
3.0 null
6.4 null
6.5 C
6.6 C
9.9 C
10.0 C
10.1 null

Get values for keys within a range in Java

It looks like you want more than a SortedMap; you want a NavigableMap! Specifically you can use the floorKey operation.

Here's an example:

    NavigableMap<Integer,String> map =
        new TreeMap<Integer, String>();

    map.put(0, "Kid");
    map.put(11, "Teens");
    map.put(20, "Twenties");
    map.put(30, "Thirties");
    map.put(40, "Forties");
    map.put(50, "Senior");
    map.put(100, "OMG OMG OMG!");

    System.out.println(map.get(map.floorKey(13)));     // Teens
    System.out.println(map.get(map.floorKey(29)));     // Twenties
    System.out.println(map.get(map.floorKey(30)));     // Thirties
    System.out.println(map.floorEntry(42).getValue()); // Forties
    System.out.println(map.get(map.floorKey(666)));    // OMG OMG OMG!

Note that there are also ceilingKey, lowerKey, higherKey, and also …Entry instead of …Key operations as well which returns a Map.Entry<K,V> instead of just the K.

Find number of elements in range from map object

You can do it like that:

public class MainClass {
    public static void main(String[] args) {
        Map<String, BigDecimal> aMap=new HashMap<>();

        aMap.put("A",new BigDecimal(12));
        aMap.put("B",new BigDecimal(23));
        aMap.put("C",new BigDecimal(67));
        aMap.put("D",new BigDecimal(99));
         Map<String, Long> o =  aMap.entrySet().stream().collect(Collectors.groupingBy( a ->{
             //Do the logic here to return the group by function
             if(a.getValue().compareTo(new BigDecimal(0))>0 &&
                     a.getValue().compareTo(new BigDecimal(25))<0)
                 return "0-25";

             if(a.getValue().compareTo(new BigDecimal(26))>0 &&
                     a.getValue().compareTo(new BigDecimal(50))<0)
                 return "26-50";

             if(a.getValue().compareTo(new BigDecimal(51))>0 &&
                     a.getValue().compareTo(new BigDecimal(75))<0)
                 return "51-75";
             if(a.getValue().compareTo(new BigDecimal(76))>0 &&
                     a.getValue().compareTo(new BigDecimal(100))<0)
                 return "76-100";

             return "not-found";
         }, Collectors.counting()));

         System.out.print("Result="+o);

    }

}

Result is : Result={0-25=2, 76-100=1, 51-75=1}

I couldn't find a better way to do that check for big decimals but you can think about how to improve it :) Maybe make an external method that does that trick

How to search within list of integer ranges efficiently - java

You can use Guava's RangeMap:

RangeMap<Integer, Character> rangeMap = TreeRangeMap.create();
rangeMap.put(Range.closed(10, 75), 'A');
rangeMap.put(Range.closed(95, 200), 'A');
rangeMap.put(Range.closed(300, 455), 'B');
rangeMap.put(Range.closed(570, 650), 'C');
rangeMap.put(Range.closed(201, 250), 'A');
rangeMap.put(Range.closed(255, 275), 'B');

Character character = rangeMap.get(61);
Character character2 = rangeMap.get(244);
Character character3 = rangeMap.get(270);

System.out.println(character);
System.out.println(character2);
System.out.println(character3);

Output:

A
A
B

Note: for some reason, it's marked with @Beta https://github.com/google/guava/issues/3376 so I would want to make sure it's OK if it's for production use.

Fetching range of values from Map in Java

You can use an implementation of NavigableMap (example TreeMap). This method in particular might interest you :

/**
 * Returns a view of the portion of this map whose keys range from
 * {@code fromKey} to {@code toKey}.  If {@code fromKey} and
 * {@code toKey} are equal, the returned map is empty unless
 * {@code fromExclusive} and {@code toExclusive} are both true.  The
 * returned map is backed by this map, so changes in the returned map are
 * reflected in this map, and vice-versa.  The returned map supports all
 * optional map operations that this map supports.
 *
 * <p>The returned map will throw an {@code IllegalArgumentException}
 * on an attempt to insert a key outside of its range, or to construct a
 * submap either of whose endpoints lie outside its range.
 *
 * @param fromKey low endpoint of the keys in the returned map
 * @param fromInclusive {@code true} if the low endpoint
 *        is to be included in the returned view
 * @param toKey high endpoint of the keys in the returned map
 * @param toInclusive {@code true} if the high endpoint
 *        is to be included in the returned view
 * @return a view of the portion of this map whose keys range from
 *         {@code fromKey} to {@code toKey}
 * @throws ClassCastException if {@code fromKey} and {@code toKey}
 *         cannot be compared to one another using this map's comparator
 *         (or, if the map has no comparator, using natural ordering).
 *         Implementations may, but are not required to, throw this
 *         exception if {@code fromKey} or {@code toKey}
 *         cannot be compared to keys currently in the map.
 * @throws NullPointerException if {@code fromKey} or {@code toKey}
 *         is null and this map does not permit null keys
 * @throws IllegalArgumentException if {@code fromKey} is greater than
 *         {@code toKey}; or if this map itself has a restricted
 *         range, and {@code fromKey} or {@code toKey} lies
 *         outside the bounds of the range
 */
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                         K toKey,   boolean toInclusive);

The underlying data structure for a TreeMap is red and black tree and all the complexity is abstracted by the NavigableMap interface thereby making it quite simple to use.

Efficient way to select a range of key-value pairs from a Java HashMap

You can't do anything that performs meaningfully better than an Iterator to do this with a HashMap.

If you use a TreeMap, however, this becomes easy: use subMap(0, 5) or the like.

Group the contents of a Map of LocalDates into a Map of Ranges of dates

Solution with custom Range class

To begin with, you need to define a class Range with two fields (start date and end date), and create a list of ranges. Since only three instance are required, it makes sense to declare this list as a public static final field within a utility class.

Below is an example of Range, for the purpose of conciseness I've implemented it as Java 16 record. It is given one utility method which is meant to check whether the given date is within this instance of range:

public record Range(LocalDate start, LocalDate end) {
    public boolean isWithinRange(LocalDate date) { // start inclusive, end exclusive
        return date.isBefore(start) || date.isBefore(end) && date.isAfter(start);
    }
}

A list of ranges:

public static final List<Range> RANGES =
    List.of(new Range(LocalDate.of(2020,1, 1), LocalDate.of(2020,3, 27)),
            new Range(LocalDate.of(2020,3, 27), LocalDate.of(2020,10, 31)),
            new Range(LocalDate.of(2020,10, 31), LocalDate.of(2021,1, 1)));

Utility method getRange() that is responsible for retrieving an instance of Range from the list of ranges based on the given date:

public static Range getRange(LocalDate data) {
    return RANGES.stream()
        .filter(range -> range.isWithinRange(data))
        .findFirst()
        .orElseThrow();
}

Dummy record Shift (used for testing purposes):

public record Shift(int id, LocalTime startTime) {}

In order to approach the conversion of a Map<LocalDate, Collection<Shift>> into a Map<Range, List<Shift>> with streams, we need to create a stream of map entries. Than make use of collector groupingBy() in order to group the data by range. As the downstream collector of groupingBy() we have to provide flatMapping() in order to flatten the data associated with a particular data (so that all Shift objects that will be mapped to the same range would be placed in the same collection). And a downstream of flatMapping() we need to provide a collector which defines how store (or how to perform reduction) flattened elements. In the data collector toList() is used to store the data mapped to the same key in a list.

main() - demo

public static void main(String[] args) {
    Map<LocalDate, Collection<Shift>> shiftsByDate =
        Map.of(LocalDate.of(2020,3, 26),
                   List.of(new Shift(4, LocalTime.of(21, 0, 0)), new Shift(5, LocalTime.of(9, 0, 0))),
               LocalDate.of(2020,3, 27),
                   List.of(new Shift(4, LocalTime.of(22, 0, 0)), new Shift(5, LocalTime.of(10, 0, 0)))
            );
    
    Map<Range, List<Shift>> shiftsByRange = shiftsByDate.entrySet().stream()
        .collect(Collectors.groupingBy(entry -> getRange(entry.getKey()),
            Collectors.flatMapping(entry -> entry.getValue().stream(),
                Collectors.toList())));
    
    shiftsByRange.forEach((k, v) -> System.out.println(k + " : " + v));
}

Output

Range[start=2020-10-31, end=2021-01-01] : [Shift[id=4, startTime=22:00], Shift[id=5, startTime=10:00]]
Range[start=2020-01-01, end=2020-03-27] : [Shift[id=4, startTime=21:00], Shift[id=5, startTime=09:00]]

Solution with Range from the Spring Data

The previous version required moderate only changes in order to use Range<T> from the Spring Data project. We need to fix the list RANGES where these objects are instantiated, and replace the type Range with the Range<T>.

There's caveat: if you expect generic type parameter <T> to be LocalDate - it's not correct and wouldn't work.

Range<T> class expects its generic type to be comparable, i.e. T extends Comparable<T> and LocalDate doesn't extend comparable directly, it implements ChronoLocalDate interface which in turn implements Comparable interface and LocalDate inherits its default implementation of compareTo().

In other words:

• it's incorrect to say that LocalDate extends Comparable<LocalDate>
• because in fact LocalDate extends Comparable<ChronoLocalDate>.

Therefore, we have to use ChronoLocalDate as a generic type.

The RANGES list will look like that:

public static final List<Range<ChronoLocalDate>> RANGES =
    List.of(Range.rightOpen(LocalDate.of(2020,1, 1), LocalDate.of(2020,3, 27)),
            Range.rightOpen(LocalDate.of(2020,3, 27), LocalDate.of(2020,10, 31)),
            Range.rightOpen(LocalDate.of(2020,10, 31), LocalDate.of(2021,1, 1)));

Method getRange() which is responsible for retrieving an instance of Range from the list of ranges based on the given date:

public static Range<ChronoLocalDate> getRange(LocalDate data) {
    return RANGES.stream()
        .filter(range -> range.contains(data))
        .findFirst()
        .orElseThrow();
}

main() - demo

public static void main(String[] args) {
    Map<LocalDate, Collection<Shift>> shiftsByDate =
        Map.of(LocalDate.of(2020,3, 26),
                   List.of(new Shift(4, LocalTime.of(21, 0, 0)), new Shift(5, LocalTime.of(9, 0, 0))),
               LocalDate.of(2020,3, 27),
                   List.of(new Shift(4, LocalTime.of(22, 0, 0)), new Shift(5, LocalTime.of(10, 0, 0)))
        );
    
    Map<Range<ChronoLocalDate>, List<Shift>> shiftsByRange = shiftsByDate.entrySet().stream()
        .collect(Collectors.groupingBy(entry -> getRange(entry.getKey()),
            Collectors.flatMapping(entry -> entry.getValue().stream(),
                Collectors.toList())));
    
    shiftsByRange.forEach((k, v) -> System.out.println(k + " : " + v));
}

Output:

[2020-03-27-2020-10-31) : [Shift[id=4, startTime=22:00], Shift[id=5, startTime=10:00]]
[2020-01-01-2020-03-27) : [Shift[id=4, startTime=21:00], Shift[id=5, startTime=09:00]]

---

Related Topics