Lookups on range of dates

Question

I have a table that I want to lookup on 1 or more columns

say

|Caller         | Receiver       |  Classification |
| 0060          |   001          |    International|
| 006017        |   001          |    Maxis-US     |
| 0060175559138 |   001323212232 |    Free         |

so say i want to have exact matches only then I can store the lookup keys in a hashmap

Map<String, String> map = new HashMap<>();
//key = caller, value = classification
map.set("0060","International");
map.set("0060175559138 ","001323212232");

I will do the same with the other column
//key =receiver, value = classification
map.set("001","International");
map.set("001","Maxis-US");
map.set("001323212232","Free");

so to get the correct classification on a lookup of caller = 0060175559138 and receiver = 001323212232 I do an intersection 

String classfication1 = map.get("0060175559138") 
Set result1 = new HashSet(1);
result1.add(classfication1);


String classfication2 = map.get("001323212232") 
Set result2 = new HashSet(1);
result2.add(classfication1 );


Set<String> finalResult = intersection(result1,result2);


public Set<V> intersection(Set<V> s1, Set<V> s2) {
    Set<V> set;
    set = new HashSet<>(s1);
    set.retainAll(s2);
    if (set.isEmpty()) {
       throw new NoMatchException("No match found");
    }

    return set;
}

Best Matches will work the same , expect I don't use a hashmap but a trie

so any call from Malaysia to USA (unless it is 0060175559138 calling 001323212232) will return a classification of International

e.g 0060124538738 to 00134646547

My problem now is I have a set of data than can only be valid at certain times

|Caller         | Receiver |  Classification |Valid From    | Valid To     |
| 0060          |   001          |    International|              |              |
| 006017        |   001          |    Maxis-US     |              |              |
| 0060175559138 |   001323212232 |    Free         |20170101000000|20180101000000|

so if 0060175559138 makes a call this within 2017 say at 20170102150000 , its classification is Free instead of International.

I can't use Valid From and Valid To as indexes with hashmap or trie.

Is there any type of data structures that help on doing range checking?

Have you considered an [IntervalTree](https://en.wikipedia.org/wiki/Interval_tree). There's an implementation [here](https://stackoverflow.com/a/11189080/823393). — OldCurmudgeon, Nov 22 '17 at 13:41
Exactly the data structure I have looking to solve my problem. Thanks — spakai, Dec 26 '17 at 10:11

score 0 · Answer 1 · answered Nov 22 '17 at 13:53

0

TreeMap is your friend. It has subMap, headMap and tailMap methods which will return ranges.

It's implemented as a red-black tree under the hood.

answered Nov 22 '17 at 13:53

Gorazd Rebolj

803
6
10

I am writing a interval tree in C++, once i get that done, will check TreeMap. – spakai Dec 26 '17 at 10:11

Lookups on range of dates

1 Answers1