SortedMap: getting value for largest key less or equal a given

[Andreas Leitgeb]

From: Andreas Leitgeb <[email protected]>

I've got an approach like the following, but I'm not entirely happy with it.
(see embedded comments) Error checking left out only for brevity-of-post's
sake.

<sscce>
class StepFunction<K,V> {
SortedMap<K,V> m_map = new TreeMap<K,V>();
public void put(K k,V v) { m_map.put(k,v); } // for demo-fill

/** @return the value for the largest key in the map
that is less OR equal to the given parameter. */

public V value(K k) {
// not really correct for generic use. In my usecase, K is
// actually Long, so I just add one to k to make it work.
return m_map.get(m_map.headMap(k).lastKey());

// I'm a bit unhappy about headMap's "open end",
// and also about the lack of some method like
// lastEntry() or lastKeysValue() in SortedMap,
// requiring one to look up the lastKey in the map,
// although the map had "its finger on it" just before.
// Did I miss something simple and obvious?
}
// demo-helper
void checkVal(K k, V v) {
System.out.println( map.value(k) + " should be " + v);
}
public static void main(String[] args) {
StepFunction<Integer,Double> sf = new StepFunction<>()
sf.put(Integer.MIN_VALUE, -1.0);
sf.put(0, 0.0); sf.put(2, 1.0);

sf.checkVal(-1 , -1.0);
sf.checkVal( 0 , 0.0);
sf.checkVal( 1 , 0.0);
sf.checkVal( 2 , 1.0);
sf.checkVal(Integer.MAX_VALUE , 1.0);
}
}
</sscce>

PS: No need to offer "solutions" involving linear search.
I could have come up with one, myself, if I wanted one.

--- BBBS/Li6 v4.10 Dada-1
* Origin: Prism bbs (1:261/38)
--- Synchronet 3.16a-Win32 NewsLink 1.98
Time Warp of the Future BBS - telnet://time.synchro.net:24

 

[Andreas Leitgeb]

To: Andreas Leitgeb
From: Andreas Leitgeb <[email protected]>

I've got an approach like the following, but I'm not entirely
happy with it...

It took me about an hour to compose that previous post, and not only did a bug
still hide in it ("map" instead of "m_map"), but also: only five minutes after
posting, it occurred to me that I could also look at TreeMap's methods, rather
than only at SortedMap's, and thereby stumbled over the (new in 1.6) interface
NavigableMap.

PS: return m_map.floorEntry(k).getValue(); // Case closed.

--- BBBS/Li6 v4.10 Dada-1
* Origin: Prism bbs (1:261/38)
--- Synchronet 3.16a-Win32 NewsLink 1.98
Time Warp of the Future BBS - telnet://time.synchro.net:24

 

[markspace]

To: Andreas Leitgeb
From: markspace <-@.>

It took me about an hour to compose that previous post, and not
only did a bug still hide in it ("map" instead of "m_map"), but
also: only five minutes after posting, it occurred to me that I
could also look at TreeMap's methods, rather than only at
SortedMap's, and thereby stumbled over the (new in 1.6) interface
NavigableMap.

PS: return m_map.floorEntry(k).getValue(); //
Case closed.

It is my contention that any requests for help should contain a careful
explanation of the problem and attempted solutions, plus an SSCCE. Then the
author should save the request on disc and go to lunch. If no solution was
discovered during lunch, then the request should be sent.

I think there's a Dilbert cartoon about this.

--- BBBS/Li6 v4.10 Dada-1
* Origin: Prism bbs (1:261/38)
--- Synchronet 3.16a-Win32 NewsLink 1.98
Time Warp of the Future BBS - telnet://time.synchro.net:24

 

[Roedy Green]

To: markspace
From: Roedy Green <[email protected]>

save the request on disc and go to lunch.

Bertrand Russell "told" me about this years ago. You have to get away from
your computer. He suggested even a week of "not" thinking about it for a
toughie. Then when you revisit the problem, the answer will be right under your
nose.

I just think about the problem while walking. The details are cleared away so
I have to think more abstractly. I ask myself , what could be failing that
created those symptoms. I am not looking for particular code, just thinking
about code that does some function. It is a different sort of thinking than
trying to decide if a line of code is faulty.

Of course Murphy's law says the most likely time for the answer to come to you
is one second after hitting submit.
--
Roedy Green Canadian Mind Products
http://mindprod.com
The greatest shortcoming of the human race is our inability to understand the
exponential function.
~ Dr. Albert A. Bartlett (born: 1923-03-21 age: 89)

--- BBBS/Li6 v4.10 Dada-1
* Origin: Prism bbs (1:261/38)
--- Synchronet 3.16a-Win32 NewsLink 1.98
Time Warp of the Future BBS - telnet://time.synchro.net:24

 

[Daniel Pitts]

To: Roedy Green
From: Daniel Pitts <[email protected]>

Bertrand Russell "told" me about this years ago. You have to get away
from your computer. He suggested even a week of "not" thinking about
it for a toughie. Then when you revisit the problem, the answer will
be right under your nose.

I just think about the problem while walking. The details are cleared
away so I have to think more abstractly. I ask myself , what could be
failing that created those symptoms. I am not looking for particular
code, just thinking about code that does some function. It is a
different sort of thinking than trying to decide if a line of code is
faulty.

Of course Murphy's law says the most likely time for the answer to
come to you is one second after hitting submit.

If we're talking about Murphy, then by submit you mean "deploy the hack
workaround fix to production after a month of QA".

;-)

--- BBBS/Li6 v4.10 Dada-1
* Origin: Prism bbs (1:261/38)
--- Synchronet 3.16a-Win32 NewsLink 1.98
Time Warp of the Future BBS - telnet://time.synchro.net:24

 

[Andreas Leitgeb]

To: Daniel Pitts
From: Andreas Leitgeb <[email protected]>


I hardly ever go to lunch at all. Typically have a bite at the workplace...

Away from the computer I couldn't have had a look at TreeMap's methods...

Within a week of this strategy, surely one of the coworkers would have noticed
my inactivity on the task and taken it over... maybe eventually asking me what
I think I'm being paid for... Nope, rather not let that happen ;-)
Good description of what kind of happened, btw.

If we're talking about Murphy, then by submit you mean "deploy the hack
workaround fix to production after a month of QA".
;-)

;-)

--- BBBS/Li6 v4.10 Dada-1
* Origin: Prism bbs (1:261/38)
--- Synchronet 3.16a-Win32 NewsLink 1.98
Time Warp of the Future BBS - telnet://time.synchro.net:24