Wednesday, November 24, 2010

How to fit a number in an array of numbers

The following code try to fit a number inside a list of numbers using the java language. 
  • The inputs to this program are the number to search: numberToSearch, and the List of numbers to fit the number in: targetList .
  •  The outputs are the lower bound: lowerBound , and the upper bound: upperBound , which are numbers from the list which encloses numberToSearch
The functions toArray and itemAt are taken from the OpenGTS (open source vehicle tracking system), whereas the function indexOfStable is based on the indexOf  function from the OpenGTS source code, and was modified by me in order to search the index of an object in an array by doing a comparison by reference not by value as the indexOf  function does.
..................................................................................................................................
..................................................................................................................................
  • Input: numberToSearch to fit into targetList.
  • Output: lowerBound <= numberToSearch <= upperBound where lowerBound and upperBound are conntained in targetList.


long numberToSearch= ....
List targetList= .....

Long lowerBound = targetList.get(0);
Long upperBound = targetList.get(targetList.size()-1);


Long numberToSearchByReference= new Long(numberToSearch);targetList.add(numberToSearchByReference);
Collections.sort(targetList);Long [] targetArray= ListTools.toArray(targetList, Long.class);
int index = ListTools.indexOfStable(targetArray, numberToSearchByReference);
       
if(index <= 0)
     return null;
else {
     lowerBound = ListTools.itemAt(targetArray, index -1, lowerBound);
     upperBound = ListTools.itemAt(targetArray, index +1, upperBound);               
}
 


...........................................................................................................................................................
...........................................................................................................................................................
The following function is based on the OpenGTS source code (ListTools.java) but was modified by me: 
public static <t> int indexOfStable(T list[], T item)
     {
         if (list == null) {

             /* no list */
             return -1;

         } else {

             /* constrain offset/length */
             int alen = (list != null)? list.length : 0;

             /* loop through array checking for item */
             for (int i = 0; i < alen; i++) {
                 if (list[i] == item) { // also takes care of 'null == null'
                     return i;
                 } 
             }

             /* still not found */
             return -1;

         }
     }
  
.......................................................................................................................
.......................................................................................................................
The following function is taked from the OpenGTS source code (ListTools.java)

public static <t> T itemAt(Collection<t> c, int ndx, T dft)
    {
        if ((c == null) || (ndx < 0) || (ndx >= c.size())) {
            return dft;
        } else
        if (c instanceof java.util.List) {
            // Randomly addressable list
            return ((java.util.List<t>)c).get(ndx);
        } else {
            // Serialized collection, iterate to item #ndx
            for (T obj : c) {
                if (ndx-- == 0) {
                    return obj;
                }
            }
            return dft;
        }
    }

.......................................................................................................................
.......................................................................................................................
The following function is taked from the OpenGTS source code (ListTools.java)

public static <t> T[] toArray(Collection list, Class<t> type)
    {
        if (type == null) { type = (Class<t>)Object.class; }
        if (list != null) {
            T array[] = (T[])Array.newInstance(type, list.size());  // "unchecked cast"
            return list.toArray(array);
        } else {
            return (T[])Array.newInstance(type, 0);  // "unchecked cast"
        }
    }