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 ?

Holger · Accepted Answer · 2018-05-31 08:41:27Z

2

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

answered May 31, 2018 at 8:41

Holger

301k43 gold badges483 silver badges830 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

VitalyT Over a year ago

Hi @Holger , I have some issue that your suggestion isn't working , if u can have a look it will be great , thanks :)

Holger Over a year ago

@VitalyT When you use floorEntry, you request an entry equal or smaller, so floorEntry("var2#"+150L) can never end up at the entry of "var2#"+200L, as 200L is neither equal nor smaller than 150L. Since there is no smaller key with the "var2#" prefix, the closest key is "var1#"+200L. The prefix has precedence. But still, a comparator imposes a total order and floorEntry will invariably return an entry with an equal or smaller key according to that order. You can’t expect it to suddenly return an entry with a bigger key based on an additional condition.

VitalyT Over a year ago

thank's , I see what you're saying, but if I need to search first by "var2#" and after to map into backet range , how would you change the code , cause it works perfect until I got a bug with scenario like described :(

Holger Over a year ago

You could use String out1 = map.subMap("var2#0", true, "var3#0", false).get("var2#150"); to enforce the prefix, then, the result will be null as there’s no smaller key. Or resort to higher key if no smaller one with that prefix exists, like

Map.Entry<String, String> e = map.subMap("var2#0", true, "var2#150", true).lastEntry(); if(e == null) e = map.subMap("var2#0", true, "var3#0", false).firstEntry(); String out1 = e != null? e.getValue(): null;

. It may still result in null if no key with that prefix exists.

VitalyT Over a year ago

I mean inside your suggestion code snippet , 'int compareParts(String a, String b) ' ...

|

Hari Menon · Accepted Answer · 2018-05-31 05:02:36Z

1

The problem is that the TreeMap is using String for comparison. So it sorts alphabetically, and var2#2000 comes between var2#200 and var2#300. You should either specify a custom comparator, or use Long or Integer as the key for the TreeMap. So, this should work:

NavigableMap<Long, String> map = new TreeMap<>();
map.put(0L,   "out0");      // "var2#0..100        => out0
map.put(100L, "out1");    // "var2#100..200"     => out1
map.put(200L, "out2");    // "var2#200..300"     => out2
map.put(300L, "out3");    // "var2#300..+"       => out3

answered May 31, 2018 at 5:02

Hari Menon

35.7k15 gold badges90 silver badges111 bronze badges

4 Comments

Mincong Huang Over a year ago

Upvoted your answer because it makes sens to keep only the meaningful part as key. It's more readable and also avoid errors in the future.

AxelH Over a year ago

If "var2#" is constant in those keys, we can definitely use a numeric value. But if the idea is to provide a range for var1, var2, ... varN... this will need something like a Map<String, Map<Long, String>>

VitalyT Over a year ago

@ AxelH , var2 is not const , 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...."

AxelH Over a year ago

Please add this information in your questin @VitalyT, this is important.

Mincong Huang · Accepted Answer · 2018-05-31 05:15:16Z

1

You can extract the 2nd part of the key and use it as comparator for the navigable map:

Comparator.comparingLong(key -> Long.parseLong(key.split("#")[1]))

So:

NavigableMap<String, String> map =
    new TreeMap<>(Comparator.comparingLong(key -> Long.parseLong(key.split("#")[1])));

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

assertThat(map.floorEntry("var2#" + 150L).getValue()).isEqualTo("out1");
assertThat(map.floorEntry("var2#" + 2000L).getValue()).isEqualTo("out3");

edited May 31, 2018 at 5:15

answered May 31, 2018 at 5:03

Mincong Huang

5,5728 gold badges45 silver badges64 bronze badges

2 Comments

AxelH Over a year ago

That will be painful for a bigger Map !

Mincong Huang Over a year ago

@AxelH Yes, this comparator is not very efficient.

AxelH · Accepted Answer · 2018-05-31 05:30:45Z

I would split the key to get a Map of range per variable:

Map<String, Ranges> map;

Where we implementsRanges as we need to map the value and the result, like proposed by Hari Menon.

class Ranges {

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

    public String setFloor(long l, String s){
        return map.put(l, s);
    }

    public String getFloor(long l){
        return map.floorEntry(l).getValue();
    }
}

That will be simple to populate :

Map<String, Ranges> map = new HashMap<>();

Ranges r = new Ranges();
r.setFloor(0L, "out1");
r.setFloor(100L, "out2");   
map.put("var1", r);

r = new Ranges();
r.setFloor(0L, "out3");
r.setFloor(100L, "out4");
map.put("var2", r);

System.out.println(map.get("var1").getFloor(50L));
System.out.println(map.get("var2").getFloor(150L));

out1
out4

We can use a NavigableMap instead of the HashMap but I didn't see the point here.

Please note that this isn't NPE safe, this was not secured to keep the solution short and readable.

Collectives™ on Stack Overflow

How create range map in Java when the keys are strings

4 Answers 4

11 Comments

4 Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

11 Comments

4 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related