[Webinar] Streamline your web hosting managementRegister Today

x
?
Solved

retrieve a scope of elements..

Posted on 2004-10-30
9
Medium Priority
?
184 Views
Last Modified: 2010-03-31
I have a TreeMap container holding following elements:

1 1 2 2 2 4 4 5 7 7 7 7 10 13 13 14 14 14 14 14 16 16 17...

Image this is a very long list(5000+ elements)
I need a function that requires input of begin value and end value, and it returns all elements between the begin value and the end value.
For example:
function1(7, 13) =>  7 7 7 7 10 13 13
function1(2, 4) => 2 2 2 4 4
function1(2, 3) => 2 2 2
function1(14, 16) => 14 14 14 14 14 16 16

I need another function that always return the first element between the begin value and the end value.
function2(7, 13) => 7 (the first element of 7)
function2(2, 4) => 2 (the first element of 2)
function2(14, 16) => 14 (the first element of 14)


Is it possible??

0
Comment
Question by:zollen
9 Comments
 
LVL 13

Expert Comment

by:petmagdy
ID: 12453409
could u please explain in this tree map what is the key and what is value?
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 12453412
The routines should be pretty similar. Something like:

List getValueRange(Object startVal, Object endVal) {
      List foundList = new ArrayList();
      Iterator iter = values.iterator();
      while (iter.hasNext()) {
            Comparable n = (Comparable)iter.next();
            if (n.compareTo(startVal) >= 0 && n.compareTo(endVal) <=0) {
                  found.add(n);
            }
            // do a break clause too for efficiency
      }
      return foundList;
}



Object getFirstValue(Object startVal) {
      Iterator iter = values.iterator();
      while (iter.hasNext()) {
            Comparable n = (Comparable)iter.next();
            if (n.compareTo(startVal) == 0) {
                  return n;
            }
      }
}
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 12453417
Substitute

map.values()

for

values()

in the above
0
Never miss a deadline with monday.com

The revolutionary project management tool is here!   Plan visually with a single glance and make sure your projects get done.

 
LVL 4

Expert Comment

by:lcwiding
ID: 12453435
With a TreeMap, the most straight forward approach would be as follows:

class X
{
   TreeMap map;

   Collection function1(int first, int last)
   {
      Vector found = new Vector();
      Iterator itr = map.values().iterator();
      int num;
      Object obj;
      while (itr.hasNext())
      {
         obj = itr.next();
         num = ((Integer)obj).valueOf();
         if (num >= first && num <= last)
            found.add(obj);
         else if (num > last)
            break;
      }
      return found;
   }

   Collection function2(int first, int last)
   {
      Collection col = function1(first, last);
      return ((Integer)col.toArray()[0]).valueOf();
   }
}

You should add additional bounds and error checking as well.
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 12453553
Couple of other inaccuracies in my example. This one's tested ;-)

static java.util.List getValueRange(Map m, Object startVal, Object endVal) {
    java.util.List foundList = new ArrayList();
    Iterator iter = m.values().iterator();
    while (iter.hasNext()) {
         Comparable n = (Comparable)iter.next();
         if (n.compareTo(startVal) >= 0 && n.compareTo(endVal) <=0) {
              foundList.add(n);
         }
         if (n.compareTo(endVal) > 0) {
           break;
         }
    }
    return foundList;
}
0
 

Author Comment

by:zollen
ID: 12457428
All elements (5000+) in the TreeMap container are already sorted. Is there a way to take advantage of these sorted elements (i.e. binary search..etc), instead of using linear search? Imagine that searching is being performed 100+ times per second. Performance is important.

0
 
LVL 4

Expert Comment

by:lcwiding
ID: 12458389
These methods will take advantage of the presorting. Though, actually, the code in the examples does take advantage of the fact that the lsits are sorted, in that they will not run through the entire list, unless what youa re looking for is at the end of the list.

That said, these are my revised methods:

   Collection function1(Object first, Object last)
   {
      SortedMap found = map.tailMap(first);
      if (found != null)
         return found.headMap(last);
      else
         return found;
   }

   Object function2(Object first, Object last)
   {
      SortedMap found = map.tailMap(first);
      if (found == null)
         return null;
      else
         return found.firstKey();
   }

0
 
LVL 86

Expert Comment

by:CEHJ
ID: 12462638
You should definitely test any profferred solutions. Don't forget that operations involving re-containment of the values (e.g. in a List) will have to balance the cost of the container copy operation against a potentially faster lookup operation
0
 
LVL 4

Accepted Solution

by:
lcwiding earned 200 total points
ID: 12464165
CEHJ is correct. If performance is critical on this, you will probably want to look at keeping the values in a simple, sorted array, and performing your own binary search on the array to locate the values you want.

One performance problem I see is that you are using a generic container (TreeMap) when the data you present in your example is made up of integers. While coding can be faster with generic classes from prebuilt libraries, because of their being generic, they will not offer the kind of performance that you can get with code written for the data you are using. Using the assumption of integer values, as in your example, for best performance, the following would be my recommendation:

import java.util.*;
public class ScopeTest
{
      TreeMap map;
      int [] array = null;

      public void ScopeTest(TreeMap m)
      {
            map = m;
            array = new int[m.size()];
            Iterator itr = map.values().iterator();
            int index = 0;
            Object obj;
            while (itr.hasNext())
            {
                  obj = itr.next();
                  array[index++] = ((Integer)obj).intValue();
            }
      }

      private int findFirst(int value)
      {
            int low = 0;
            int high = array.length-1;
            int mid = (low + high) / 2;
            
            while (low <= high)
            {
                  if (array[mid] == value)
                  {
                        while (mid > 0 && array[mid] == value)
                        {
                              --mid;
                        }
                        if (mid < 0 || array[mid] < value)
                              ++mid;
                        
                        return mid;
                  }
                  
                  if (array[mid] < value)
                  {
                        low = mid + 1;
                  }
                  else
                  {
                        high = mid - 1;
                  }
                  mid = (low + high) / 2;
            }
            //
            // return the next highest value
            //
            while (mid < array.length && array[mid] < value)
            {
                  ++mid;
            }
            if (mid < array.length)
            {
                  --mid;
                  value = array[mid];
            }
            
            return mid;
      }
      
      Collection function1(int first, int last)
      {
            Vector found = new Vector();
            int start = this.findFirst(first);
            
            while (start < array.length && array[start] <= last)
            {
                  found.add(new Integer(array[start]));
                  ++start;
            }
            
            return found;
      }

      int function2(int first, int last)
      {
            int start = this.findFirst(first);
            if (start < array.length)
                  return array[start];
            else
                  return -1;
      }

}
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
Suggested Courses
Course of the Month8 days, 15 hours left to enroll

590 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question