retrieve a scope of elements..

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

zollenAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

petmagdyCommented:
could u please explain in this tree map what is the key and what is value?
0
CEHJCommented:
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
CEHJCommented:
Substitute

map.values()

for

values()

in the above
0
Cloud Class® Course: Microsoft Azure 2017

Azure has a changed a lot since it was originally introduce by adding new services and features. Do you know everything you need to about Azure? This course will teach you about the Azure App Service, monitoring and application insights, DevOps, and Team Services.

lcwidingCommented:
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
CEHJCommented:
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
zollenAuthor Commented:
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
lcwidingCommented:
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
CEHJCommented:
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
lcwidingCommented:
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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.