How to get lower value in a TreeMap?-CodePudding

I use TreeMap to keep daily stocks of a product as shown below:

NavigableMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < stocks.size(); i  ) {
    map.put(i 1, stocks.get(i));
}

I use day as key and stock as value:

key  | value
------------
1    | 5 
2    | 6 
3    | 8 
4    | 4  <-- need to find lower of this value
5    | 9 
6    | 10 
7    | 8
8    | 3  <-- I need to obtain this
9    | 6 
10   | 4

I am trying to get the key of lower(4), which is 8. If there are multiple entries that match, such as in the case of lower(7), I want the key of the first entry, so lower(7) should produce 2, not 9.

However, I cannot go over values and need to use keys. So, how can I do this?

If it is not possible, should I also need to use a TreeSet to get lower?

CodePudding user response：

You should use the stock value as key, and the day as value. This makes it very easy to use lowerEntry(4).getValue() to find the day 8.

However, there can be duplicate values, and you want to find the earliest entry (i.e. with the lowest day number). The tree map obviously cannot have duplicate keys, so we work around this by only storing the earliest entry for each stock value.

NavigableMap<Integer, Integer> map = new TreeMap<>();
for (int i = stocks.size() - 1; i >= 0; i--) {
    map.put(stocks.get(i), i 1);
}

Notice that the arguments for put is reversed, and the for loop is also reversed. We start from the end of the list, so that the earliest stock values overwrite later ones if they happen to be the same.

Then you can do

map.lowerEntry(4).getValue()

to find 8.

CodePudding user response：

int key = 4;
Map.Entry<Integer, Integer> prior = map.lowerEntry(key); // map.floorEntry(key - 1);

If 3 would not be a map's key, 2 would be the resulting key.