Lower bound & Upper bound

Discussion in 'Java' started by sunil panda, Dec 25, 2003.

  1. sunil panda

    sunil panda Guest

    Hi Friends,

    I am new to java as well as to this group. I have a small question.
    I need to know as to how I can retrieve the lower bound
    and upper bound value from a container(TreeMap or HashMap)
    for a given key.

    Example: Map
    Key Value

    2 22
    3 33
    9 99
    7 77

    If the given key is 6, I need the lower bound as 2 and upperbound as 7.
    Are their any API's?. My container will store thousands of messages
    and I cannot go for a linear search in real time thread.
     
    sunil panda, Dec 25, 2003
    #1
    1. Advertising

  2. sunil panda wrote:
    > I am new to java as well as to this group. I have a small question.
    > I need to know as to how I can retrieve the lower bound
    > and upper bound value from a container(TreeMap or HashMap)
    > for a given key.
    >
    > Example: Map
    > Key Value
    >
    > 2 22
    > 3 33
    > 9 99
    > 7 77
    >
    > If the given key is 6, I need the lower bound as 2 and upperbound as 7.


    I do not understand the question, and I doubt anybody else does. What is the
    intended relationship between 6, 2 and 7 here?
     
    Michael Borgwardt, Dec 25, 2003
    #2
    1. Advertising

  3. "sunil panda" <> wrote in message
    news:...
    ....
    > ..how I can retrieve the lower bound
    > and upper bound value from a container(TreeMap or HashMap)
    > for a given key.
    >
    > Example: Map
    > Key Value
    >
    > 2 22
    > 3 33
    > 9 99
    > 7 77
    >
    > If the given key is 6, I need the lower bound as 2 and upperbound as 7.


    <pseudocode>
    int target = 6,
    lo = target,
    hi = taget;

    while ( !HashMap.containsKey(lo) ) lo--;
    while ( !HashMap.containsKey(hi) ) hi++;
    </pseudocode>

    HTH

    --
    Andrew Thompson
    * http://www.PhySci.org/ PhySci software suite
    * http://www.1point1C.org/ 1.1C - Superluminal!
    * http://www.AThompson.info/andrew/ personal site
     
    Andrew Thompson, Dec 25, 2003
    #3
  4. "Michael Borgwardt" <> wrote in message
    news:bseeem$c3ap2$-berlin.de...
    > sunil panda wrote:

    ....
    > > If the given key is 6, I need the lower bound as 2 and upperbound as 7.

    >
    > I do not understand the question, and I doubt anybody else does. What is

    the
    > intended relationship between 6, 2 and 7 here?


    Well, I _thought_ I did, ..when I
    mistook the two for a three. Now?
     
    Andrew Thompson, Dec 25, 2003
    #4
  5. sunil panda wrote:
    > Hi Friends,
    >
    > I am new to java as well as to this group. I have a small question.
    > I need to know as to how I can retrieve the lower bound
    > and upper bound value from a container(TreeMap or HashMap)
    > for a given key.
    >
    > Example: Map
    > Key Value
    >
    > 2 22
    > 3 33
    > 9 99
    > 7 77
    >
    > If the given key is 6, I need the lower bound as 2 and upperbound as 7.
    > Are their any API's?. My container will store thousands of messages
    > and I cannot go for a linear search in real time thread.


    Your question is a bit vague. I assume that by lower bound you mean the
    smallest key such that key <= given key, and by upper bound the smallest
    key >= given key. You need a SortedMap for this, like TreeMap which
    should give you O(log n) performance. It's not possible with HashMap.
    Code (untested):

    SortedMap m = new TreeMap(); // the map
    Object target = new Object(); // the given key
    Object lower = null, upper = null; // bounds

    if (!m.isEmpty())
    {

    Comparable first = (Comparable) m.firstKey();
    // lowest key in map

    if (first.compareTo(target) <= 0)
    {
    lower = first;
    }

    SortedMap tail = m.tailMap(target);
    // submap from target to end of map

    if (!tail.isEmpty())
    {
    upper = tail.firstKey();
    }
    }

    --
    Daniel Sjöblom
     
    =?ISO-8859-1?Q?Daniel_Sj=F6blom?=, Dec 25, 2003
    #5
  6. sunil panda

    sunil panda Guest

    Daniel Sjöblom <_NOSPAM> wrote in message news:<3feb2283$0$6037$>...
    > sunil panda wrote:
    > > Hi Friends,
    > >
    > > I am new to java as well as to this group. I have a small question.
    > > I need to know as to how I can retrieve the lower bound
    > > and upper bound value from a container(TreeMap or HashMap)
    > > for a given key.
    > >
    > > Example: Map
    > > Key Value
    > >
    > > 2 22
    > > 3 33
    > > 9 99
    > > 7 77
    > >
    > > If the given key is 6, I need the lower bound as 2 and upperbound as 7.
    > > Are their any API's?. My container will store thousands of messages
    > > and I cannot go for a linear search in real time thread.

    >
    > Your question is a bit vague. I assume that by lower bound you mean the
    > smallest key such that key <= given key, and by upper bound the smallest
    > key >= given key. You need a SortedMap for this, like TreeMap which
    > should give you O(log n) performance. It's not possible with HashMap.
    > Code (untested):
    >
    > SortedMap m = new TreeMap(); // the map
    > Object target = new Object(); // the given key
    > Object lower = null, upper = null; // bounds
    >
    > if (!m.isEmpty())
    > {
    >
    > Comparable first = (Comparable) m.firstKey();
    > // lowest key in map
    >
    > if (first.compareTo(target) <= 0)
    > {
    > lower = first;
    > }
    >
    > SortedMap tail = m.tailMap(target);
    > // submap from target to end of map
    >
    > if (!tail.isEmpty())
    > {
    > upper = tail.firstKey();
    > }
    > }


    Hi Andrew and Daniel,

    Thanks for the input. Infact both of you are correct but I
    have the following concerns.

    a) Andrew's suggestion is linear search and very time consuming.
    My container is going to hold thousands of messages and it
    needs to be iterated for every message I receive.

    b) Initially I thought of Daniel's idea but I had to stop because
    it involves large quantity of data transfer from one container
    to another that too in real time thread.

    What I am looking is for some container with STL map functionality
    of lower bound and upperbound.

    Thanks
    sunil
     
    sunil panda, Dec 26, 2003
    #6
  7. sunil panda wrote:
    > b) Initially I thought of Daniel's idea but I had to stop because
    > it involves large quantity of data transfer from one container
    > to another that too in real time thread.


    Whatever gave you that idea? Take a look at the implementation
    of TreeMap.tailMap(): in involves the copying of 4 references,
    that's all.
     
    Michael Borgwardt, Dec 26, 2003
    #7
  8. sunil panda wrote:

    > b) Initially I thought of Daniel's idea but I had to stop because
    > it involves large quantity of data transfer from one container
    > to another that too in real time thread.


    tailMap() is actually pretty cheap. Set up a test and see if it is fast
    enough!


    --
    Daniel Sjöblom
     
    =?ISO-8859-1?Q?Daniel_Sj=F6blom?=, Dec 26, 2003
    #8
  9. "Daniel Sjöblom" <_NOSPAM> wrote in message
    news:3fec856e$0$6029$...
    > sunil panda wrote:

    ....
    > > b) Initially I thought of Daniel's idea but I had to stop because
    > > it involves large quantity of data transfer from one container
    > > to another that too in real time thread.

    >
    > tailMap() is actually pretty cheap. Set up a test..


    Aaah. Those magic words.

    Come up with a self-contained piece of test code
    and I'm confident you could get a number of people
    using different VM's to test it for you (assuming
    your own test is any less than clear cut)

    --
    Andrew Thompson
    * http://www.PhySci.org/ PhySci software suite
    * http://www.1point1C.org/ 1.1C - Superluminal!
    * http://www.AThompson.info/andrew/ personal site
     
    Andrew Thompson, Dec 27, 2003
    #9
  10. sunil panda

    thushara wijeratna

    Joined:
    Oct 7, 2008
    Messages:
    1
    i believe the definition of lower_bound is "the first value in a sorted container that is greater than or equal to the given value"

    check here:
    http://www.cplusplus.com/reference/algorithm/lower_bound.html

    java tailmap will give the correct result.

    but upper_bound means : "the first value in a sorted container that is greater than the given value" and there is no such equivalent function in java TreeMap.
     
    thushara wijeratna, Oct 7, 2008
    #10
    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:
    4
    Views:
    711
    Jürgen Exner
    Dec 7, 2004
  2. ANM
    Replies:
    2
    Views:
    1,369
    Thomas Schodt
    Mar 7, 2004
  3. David
    Replies:
    10
    Views:
    783
    James Lothian
    May 7, 2004
  4. Rhiner Dan
    Replies:
    1
    Views:
    748
    Mike Wahler
    Mar 27, 2005
  5. BlackHelicopter
    Replies:
    0
    Views:
    528
    BlackHelicopter
    Jan 31, 2013
Loading...

Share This Page