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

Discussion in 'Java' started by Andreas Leitgeb, Aug 4, 2012.

  1. From: "Andreas Leitgeb" <andreas.leitgeb@1:261/38.remove-5qr-this>

    From: "Andreas Leitgeb" <andreas.leitgeb@1:261/38.remove-yy0-this>

    From: "Andreas Leitgeb" <andreas.leitgeb@1:261/38.remove-s5y-this>

    From: Andreas Leitgeb <>

    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

    -+- 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

    -+- 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

    --- 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, Aug 4, 2012
    #1
    1. Advertising

  2. To: Andreas Leitgeb
    From: "Andreas Leitgeb" <andreas.leitgeb@1:261/38.remove-5qr-this>

    To: Andreas Leitgeb
    From: "Andreas Leitgeb" <andreas.leitgeb@1:261/38.remove-yy0-this>

    To: Andreas Leitgeb
    From: "Andreas Leitgeb" <andreas.leitgeb@1:261/38.remove-s5y-this>

    To: Andreas Leitgeb
    From: Andreas Leitgeb <>

    Andreas Leitgeb <> wrote:
    > 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

    -+- 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

    -+- 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

    --- 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, Aug 4, 2012
    #2
    1. Advertising

  3. Andreas Leitgeb

    markspace Guest

    To: Andreas Leitgeb
    From: "markspace" <markspace@1:261/38.remove-5qr-this>

    To: Andreas Leitgeb
    From: "markspace" <markspace@1:261/38.remove-yy0-this>

    To: Andreas Leitgeb
    From: "markspace" <markspace@1:261/38.remove-s5y-this>

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

    On 8/1/2012 1:19 PM, Andreas Leitgeb wrote:
    > Andreas Leitgeb <> wrote:
    >> 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.



    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

    -+- 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

    -+- 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

    --- 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, Aug 4, 2012
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    727
    Thomas Hawtin
    Mar 27, 2006
  2. Andreas Leitgeb
    Replies:
    5
    Views:
    204
    Andreas Leitgeb
    Aug 3, 2012
  3. Andreas Leitgeb
    Replies:
    5
    Views:
    185
    Andreas Leitgeb
    Aug 3, 2012
  4. Andreas Leitgeb
    Replies:
    2
    Views:
    117
    markspace
    Aug 3, 2012
  5. Andreas Leitgeb
    Replies:
    2
    Views:
    140
    markspace
    Aug 4, 2012
Loading...

Share This Page