Solved

retrieve a scope of elements..

Posted on 2004-10-30
179 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
Question by:zollen
    9 Comments
     
    LVL 13

    Expert Comment

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

    Expert Comment

    by:CEHJ
    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
    Substitute

    map.values()

    for

    values()

    in the above
    0
     
    LVL 4

    Expert Comment

    by:lcwiding
    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
    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
    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
    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
    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:
    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

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    6 Surprising Benefits of Threat Intelligence

    All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

    Suggested Solutions

    Title # Comments Views Activity
    sum67 challenge 35 68
    has77  challenge 9 47
    wait notify demo infinite loop 3 54
    zeroMAx challenge 20 50
    1. Package the applet into a JAR file. The applet must be in a JAR file before a certificate can be attached to it. Use the jar JDK utility. If the applet was previously referenced with the help of a codebase attribute in  tag, replace the codebase …
    Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
    Video by: Michael
    Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
    Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:

    933 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

    Need Help in Real-Time?

    Connect with top rated Experts

    15 Experts available now in Live!

    Get 1:1 Help Now