How create range map in Java when the keys are strings

Question

I want to create a large range map that will map the keys accoriding their numbers to buckets , for instance :

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

            map.put("var2#" + 0L,   "out0");      // "var2#0..100        => out0
            map.put("var2#" + 100L, "out1");    // "var2#100..200"     => out1
            map.put("var2#" + 200L, "out2");    // "var2#200..300"     => out2
            map.put("var2#" + 300L, "out3");    // "var2#300..+"       => out3

That means if a new key will arrive with value res should be "var2#150" ==> "out1"

What I tried to do , is to use sorted map , everything is working with range of the numbers inside the map

something like :

String out1 = map.floorEntry("var2#" + 150L).getValue(); //out1 , works!

, but if send var2#2000 , instead to get res "out3" , I got "out2" , and so on...

String res = map.floorEntry("var2#" + 2000L).getValue(); 
Syso(res)  ==> out2 , BUT I expected result => "out3"
// because it is bigger that the range.

P.S:

It is very large map with prefix of some "string" and comes after typed
 long number . Eg. "var1#100, var1#200 , ...bla1#1000 , bla5#2000....

Another issue - when I have same long value on different keys I expect to do 1st match on the string and then on the number ...

    map.put("var1#" + 200L, "out0");
    map.put("var2#" + 200L, "out1");
    map.put("var3#" + 200L, "out2");
    map.put("var4#" + 200L, "out3");

    String out1 = map.floorEntry("var2#" + 150L).getValue();
    System.out.println("====> " + out1); //expected  out1 , because only match of "var2
    String out3 = map.floorEntry("var2#" + 250L).getValue(); //expected  out1 , because only match of "var2
    System.out.println("====> " + out3);" ....

Any suggestions please , maybe some algorithm ?

Answer 1

One way to compare the prefix string-wise, followed by comparing the suffix numerically, would be:

public static int compareParts(String a, String b) {
    String[] aa = a.split("#", 2), ba = b.split("#", 2);
    int c = aa[0].compareTo(ba[0]);
    return c != 0? c: Integer.compare(Integer.parseInt(aa[1]), Integer.parseInt(ba[1]));
}

But since comparison methods might get called very often, even a single lookup may involve multiple comparisons, it is worth investigating some time to improve the performance, even if the code will look more complicated:

public static int compareParts(String a, String b) {
    final int aLen = a.length(), bLen = b.length(), l = Math.min(aLen, bLen);
    int ix = 0;
    stringPart: {
        for(; ix < l; ix++) {
            char aCh = a.charAt(ix), bCh = b.charAt(ix);
            int cmp = Character.compare(aCh, bCh);
            if(cmp != 0)
                return aCh == '#'? -1: bCh == '#'? +1: cmp;
            if(aCh == '#') break stringPart;
        }
        return 0;
    }
    // number part
    int aIx = ix+1, bIx = aIx;
    while(aIx < aLen && a.charAt(aIx)=='0') aIx++;
    while(bIx < bLen && b.charAt(bIx)=='0') bIx++;
    int cmp = Integer.compare(aLen-aIx, bLen-bIx);
    for(; cmp == 0 && aIx < aLen; aIx++, bIx++) {
        cmp = Character.compare(a.charAt(aIx), b.charAt(bIx));
    }
    return cmp;
}

This does only a single pass over the string. First, it iterates over the first characters of the string like String.compareTo would do, stopping at the first mismatching character or the '#' character. If only one string encountered the '#' the other has a longer prefix and we have to consider that for the result.

Only when both strings have the same prefix, the numerical part after the '#' gets processed. Instead of a doing a full integer parsing, we skip all leading zeros, if there are some. Then, if the length of the remaining significant part differs, it already indicates which number is larger. Only if the significant parts have the same length, we need to iterate them. But we can compare the digits literally without needing to interpret them as numbers in that case, as the iteration order is already from most significant digit to lowest significant digit.

Either method can be used like

NavigableMap<String, String> map = new TreeMap<>(MyClass::compareParts);

map.put("var2#" + 0L,   "out0");
map.put("var2#" + 100L, "out1");
map.put("var2#" + 200L, "out2");
map.put("var2#" + 300L, "out3");

String out1 = map.floorEntry("var2#" + 150L).getValue();
System.out.println("out1 = "+out1);
String out3 = map.floorEntry("var2#" + 2000L).getValue();
System.out.println("res = "+out3);