Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

retrieve a scope of elements..

Posted on 2004-10-30
9
Medium Priority
?
182 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
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: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say 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

After being asked a question last year, I went into one of my moods where I did some research and code just for the fun and learning of it all.  Subsequently, from this journey, I put together this article on "Range Searching Using Visual Basic.NET …
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
Suggested Courses

636 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