Using java map for range searches

Question

I have a use case where if a number lies between 0-10 it should return 0 and if it lies between 11-20 it should return 1 etc

0 => 0-3, (0 and 3 are inclusive)
1 => 4-15, (4 and 15 are inclusive)
2 => 16-40, (16 and 40 are inclusive)
3 => 41-88, (41 and 88 are inclusive)
5 => 89-300 (89 and 300 are inclusive)

I was thinking how could I implement and was thinking java maps, but it does not allow range searching

I am interested in something like this , I have a function

int foo() {

}

if foo returns 5 , since it lies between 0 to 10 I would use 0, if foo return 25 it would use 2.

Any ideas

Edit : Actually the ranges are not as simple as 0-10, 11-20. I want to be able to do range searches. Sorry about the confusion. Based on the queries I have added the correct example, the numbers are continous

Antinomy

Please provide a real example of what you want to do. – Stash

The ranges given in the example are not continuous. If one searches for 4, or 50, do you want a null result, the range above, below, or nearest, or what? – Siegel

@mkal: the way you keep on changing the requirements, you could be the manager from hell :-) – Jejune

Apologies if this is adding so much confusion :) – Antinomy

Possible duplicate of Data structures that can map a range of keys to a value – Kootenay

Answer 1

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();
}

Jejune

This is very good use of the existing TreeMap to do a simple range search. Note that if there are overlapping intervals, then the approach will return that interval with the closest lower key to the lookup key. Similarly, this approach does not support a search for all overlapping intervals containing a given search key, as discussed in #1580685 – Misbehave

If there are overlapping ranges, then the ranges are (most likely) incorrectly specified. At least, that is my reading of THIS question. – Jejune

Answer 2

Pseudo-code:

1. Store the range bounds in a flat array: new int[] {0, 3, 5, 15, 100, 300}.
2. Binary search through the array as if inserting a number into the array. See Arrays.binarySearch().
3. If the insertion point is even, the number does not fit into any range.
4. If the insertion point is odd, it fits into the corresponding range. For example, the insertion point for 10 in the above array would be 3, placing it between 5 and 15, so it belongs in the second range.

Freddafreddi

Note: this only works if we are mapping to the integers {0, 1, 2, ...}. For more general cases, a Map of some kind should be used. – Jejune

Answer 3

In a more general case that can't be solved with arithmetic, you can create a TreeMap with an appropriate Comparator. Add mappings for the boundary values, and then use ceilingEntry or floorEntry to find the appropriate match.

Hohenlinden

Answer 4

I think what you want is something along the lines of foo()/10, but that will give you ranges slightly off from what you requested. You can always just do comparisons with the two endpoints for each item in your "map" if they don't follow an easy pattern.

Cowpea

Answer 5

I think the easiest solution would be to add mappings from the upper boundaries of your ranges to the value that range maps to, and just keep incrementing your number (key in the map) until you reach a mapping (which is the upper boundary for the range your number is in).

Another way would be to populate the map with all entries in a range, and add a mapping for each.

Which one is more efficient depends on whether it's likely you need to request all numbers in a range repeatedly (use the latter solution), or just some of the numbers a few times (use the first)

Nagual

Answer 6

Based on John Kugelman's answer I needed something similar for a date range search that had data associated to the date range... Here is an example of how I applied it. "dates" would be your keys and "rangeData" would be the data associated.

  long[] dates = new long[] {
    Instant.parse("1900-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1950-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1960-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1970-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1980-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("1990-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("2000-01-01T00:00:00Z").toEpochMilli(),
    Instant.parse("2010-01-01T00:00:00Z").toEpochMilli()
  };
  String[] rangeData = new String[] {
    "Before 1900 data", "Before 1950 data", "Before 1960 data", 
    "Before 1970 data", "Before 1980 data", "Before 1990 data", 
    "Before 2000 data", "Before 2010 data"
  };
  
  long searchDate = Instant.parse("1949-02-15T00:00:00Z").toEpochMilli();
  int result = Arrays.binarySearch(dates, searchDate);
  
  System.out.println("Result: " + result); 
  if (result == dates.length) {
      System.out.println("Date is after all ranges");
      System.out.println("Data: none");
  }
  else if (result >= 0) {
      System.out.println("Date is an exact match of " + Instant.ofEpochMilli(dates[result]));
      System.out.println("Data: " + rangeData[result]);
  }
  else {
      int resultIndex = Math.abs(result) - 1;
      System.out.println("Date is before idx: "+ resultIndex + " date " + Instant.ofEpochMilli(dates[resultIndex]));
      System.out.println("Data: " + rangeData[resultIndex]);
  }

Result

Result: -2
Date is before idx: 1 date 1950-01-01T00:00:00Z
Data: Before 1950 data

Kitchenmaid