Lower bound & Upper bound

S

sunil panda

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.
 
M

Michael Borgwardt

sunil said:
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?
 
A

Andrew Thompson

....
..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
 
A

Andrew Thompson

Michael Borgwardt said:
sunil panda wrote: ....

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

=?ISO-8859-1?Q?Daniel_Sj=F6blom?=

sunil said:
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();
}
}
 
S

sunil panda

Daniel Sjöblom said:
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
 
M

Michael Borgwardt

sunil said:
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.
 
?

=?ISO-8859-1?Q?Daniel_Sj=F6blom?=

sunil said:
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!
 
A

Andrew Thompson

Daniel Sjöblom said:
sunil panda wrote: ....

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)
 
Joined
Oct 7, 2008
Messages
1
Reaction score
0
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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Staff online

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,832
Latest member
GlennSmall

Latest Threads

Top