/branches/v2_0_0_prep/libraries/libIverUtiles/src/com/iver/utiles/search/BinarySearchUsingFirstCharacters.java - Diff - | gvSIG desktop 1 - gvSIG

Revision 22508 branches/v2_0_0_prep/libraries/libIverUtiles/src/com/iver/utiles/search/BinarySearchUsingFirstCharacters.java

      * This class has static methods that return items that their beginning text value matches with a text pattern. <br>
      * It's necessary that items of the parameter array (Vector) were sort ordered according to their text value. <br>
      * Supports Vectors with and without repeated items.
+     *
+     *
      * There are four methods, that are a modification of a binary search algorithm of search, getting a rank of items:
      * <ul>
      * <li>Considering case sensitive in the search.</li>
-...
      * <li>Considering case sensitive in the search and an object which implements the Comparable interface</li>
      * <li>Ignoring case sensitive in the search, but yes an objecth which implements the Comparable interface</li>
      * </ul>
+     *
+     *
      * @author Pablo Piqueras Bartolom? (pablo.piqueras@iver.es)
      */
     public class BinarySearchUsingFirstCharacters {
     	/**
     	 * This method should be used when is wanted to distinguish small letters from capital letters during the search.
+    	 *
+    	 *
     	 * It's necessary that all items of the array implement the {@link Comparable} interface.<br>
     	 * And it's also necessary that the value returned by the <i>toString()</i> method of each item (supposing
     	 * And it's also necessary that the value returned by the <i>toString()</i> method of each item (supposing
     	 *   they inherit from Object) would be the expected value user saw (that would be used to compare the items).
+    	 *
+    	 *
     	 * @param text java.lang.String
     	 * @param sortOrderedItems java.util.Vector
     	 */
     	public synchronized static List<Object> doSearchConsideringCaseSensitive(String text, Vector<Object> sortOrderedItems) {
     	public synchronized static List doSearchConsideringCaseSensitive(String text, Vector sortOrderedItems) {
     		int currentIteration = 0;
     		int size = sortOrderedItems.size();
     		int maxNumberOfIterations = (int) MathExtension.log2(size);
     		int lowIndex = 0;
     		int highIndex = sortOrderedItems.size() - 1;
     		int mIndx;
     		while ((lowIndex <= highIndex) && (currentIteration <= maxNumberOfIterations)) {
     			mIndx = ( lowIndex + highIndex ) / 2;
     			if ( sortOrderedItems.get( mIndx ).toString().startsWith( text ) ) {
     				lowIndex = highIndex = mIndx;
     				highIndex ++;
-...
+    				}
     				// It's possible that items with different case, should be between the same case, then this item will be added individually:
     				List<Object> list = new Vector<Object>(sortOrderedItems.subList(lowIndex, highIndex));
     				List list = new Vector(sortOrderedItems.subList(lowIndex, highIndex));
     				// Expand to down
     				lowIndex --;
     				while ( ( lowIndex > -1 ) && ( sortOrderedItems.get( (lowIndex ) ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
     					if (sortOrderedItems.get( lowIndex ).toString().startsWith( text )) {
     						list.add(0, sortOrderedItems.get( lowIndex ));
+    					}
     					lowIndex --;
+    				}
     				// Expand to up
     				while ( ( highIndex < size ) && ( sortOrderedItems.get( highIndex ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
     					if (sortOrderedItems.get( highIndex ).toString().startsWith( text )) {
     					if (sortOrderedItems.get( highIndex ).toString().startsWith( text )) {
     						list.add(list.size(), sortOrderedItems.get( highIndex ));
+    					}
     					highIndex ++;
+    				}
     				// Returns all items in the rank
     				return list; // Breaks the loop
+    			}
-...
     					lowIndex = mIndx + 1;
+    				}
+    			}
     			currentIteration ++;
+    		}
     		// If no item has been found -> return null
     		return null;
+    	}
     	/**
     	 * This method should be used when is wanted not to distinguish small letters from capital letters during the search.
+    	 *
+    	 *
     	 * It's necessary that all items of the array implement the {@link Comparable} interface.<br>
     	 * And it's also necessary that the value returned by the <i>toString()</i> method of each item (supposing
     	 * And it's also necessary that the value returned by the <i>toString()</i> method of each item (supposing
     	 *   they inherit from Object) would be the expected value user saw (that would be used to compare the items).
+    	 *
     	 * In this particular situation, it's supposed that the vector is sort ordered according the default algorithm of Java; this has the problem that
-...
     	 * @param text java.lang.String
     	 * @param sortOrderedItems java.util.Vector
     	 */
     	public synchronized static List<Object> doSearchIgnoringCaseSensitive(String text, Vector<Object> sortOrderedItems) {
     	public synchronized static List doSearchIgnoringCaseSensitive(String text, Vector sortOrderedItems) {
     		int currentIteration = 0;
     		int size = sortOrderedItems.size();
     		int maxNumberOfIterations = (int) MathExtension.log2(size);
     		int lowIndex = 0;
     		int highIndex = sortOrderedItems.size() - 1;
     		int mIndx;
     		List<Object> list = null;
     		List<Object> list2 = null;
     		List list = null;
     		List list2 = null;
     		// FIRST RANK
     		while ((lowIndex <= highIndex) && (currentIteration <= maxNumberOfIterations)) {
     			mIndx = ( lowIndex + highIndex ) / 2;
     			if ( sortOrderedItems.get( mIndx ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) {
     				lowIndex = highIndex = mIndx;
     				highIndex ++;
     				// Expand the rank to up
     				while ( ( highIndex < size ) && ( sortOrderedItems.get( highIndex ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
     					highIndex ++;
-...
     				while ( ( (lowIndex - 1) > -1 ) && ( sortOrderedItems.get( (lowIndex - 1) ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
     					lowIndex --;
+    				}
     				// Returns all items in the rank
     				list = Arrays.asList((sortOrderedItems.subList(lowIndex, highIndex)).toArray());
     				break;
-...
     					lowIndex = mIndx + 1;
+    				}
+    			}
     			currentIteration ++;
+    		}
-...
     		while ((lowIndex <= highIndex) && (currentIteration <= maxNumberOfIterations)) {
     			mIndx = ( lowIndex + highIndex ) / 2;
     			if ( sortOrderedItems.get( mIndx ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) {
     				lowIndex = highIndex = mIndx;
     				highIndex ++;
     				// Expand the rank to up
     				while ( ( highIndex < size ) && ( sortOrderedItems.get( highIndex ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
     					highIndex ++;
-...
     				while ( ( (lowIndex - 1) > -1 ) && ( sortOrderedItems.get( (lowIndex - 1) ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
     					lowIndex --;
+    				}
     				// Returns all items in the rank
     				// Returns all items in the rank
     				list2 = Arrays.asList((sortOrderedItems.subList(lowIndex, highIndex)).toArray()); // Breaks the loop
     				if (list == null)
     					return list2;
     				else {
-...
     					Object obj;
     					int j;
     					list = new ArrayList<Object>(list.subList(0, list.size()));
     					list = new ArrayList(list.subList(0, list.size()));
     					for (int i = 0; i < list2.size(); i ++) {
     						obj = list2.get(i);
     						// Don't add items which are already in the list
     						if (!list.contains(obj)) {
     						if (!list.contains(obj)) {
     							// Adds in sort order the new item:
     							for (j = 0; j < list.size(); j ++) {
     								if (list.get(j).toString().compareTo(obj.toString()) > 0)
     									break;
+    							}
     							list.add(j, obj);
+    						}
+    					}
     					// It's possible that some elements at the end wouldn't be found -> another small search
     					size = list.size();
     					if (size == 0) {
-...
     					else {
     						j = sortOrderedItems.indexOf(list.get(size - 1));
+    					}
     					j++;
     					if (j < sortOrderedItems.size()) {
     						do {
     							obj = sortOrderedItems.get( j );
     							if (obj.toString().toLowerCase().startsWith( text.toLowerCase())) {
     								list.add(size, obj);
+    							}
     							j++;
+    						}
     						while (j < sortOrderedItems.size());
+    					}
     					return list;
+    				}
+    			}
-...
     					lowIndex = mIndx + 1;
+    				}
+    			}
     			currentIteration ++;
+    		}
     		return null;
+    	}
     //	/** THIS VERSION FAILURES IN SOME PARTICULAR SITUATIONS
     //	 * This method should be used when is wanted distinguish small letters from capital letters during the search, and the comparation of items
     //	 *   done according an algorithm we define.
     //	 *
     //	 * And it's also necessary that the value returned by the <i>toString()</i> method of each item (supposing
     //	 *
     //	 * And it's also necessary that the value returned by the <i>toString()</i> method of each item (supposing
     //	 *   they inherit from Object) would be the expected value user saw (that would be used to compare the items).
     //	 *
     //	 *
     //	 * @param text java.lang.String
     //	 * @param sortOrderedItems java.util.Vector
     //	 * @param comp An Comparator object which implements the <i><b>compareTo()</b><i>  method.
-...
     //
     //				// It's possible that items with different case, should be between the same case, then this item will be added individually:
     //				List list = new Vector(sortOrderedItems.subList(lowIndex, highIndex));
     //
     //
     //
     //				// Expand to down
     //				lowIndex --;
     //				while ( ( lowIndex > -1 ) && ( sortOrderedItems.get( (lowIndex ) ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
     //					if (sortOrderedItems.get( lowIndex ).toString().startsWith( text )) {
     //						list.add(0, sortOrderedItems.get( lowIndex ));
     //					}
     //
     //
     //					lowIndex --;
     //				}
     //
     //
     //				// Expand to up
     //				while ( ( highIndex < size ) && ( sortOrderedItems.get( highIndex ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
     //					if (sortOrderedItems.get( highIndex ).toString().startsWith( text )) {
     //					if (sortOrderedItems.get( highIndex ).toString().startsWith( text )) {
     //						list.add(list.size(), sortOrderedItems.get( highIndex ));
     //					}
     //
     //
     //					highIndex ++;
     //				}
     //
     //
     //				// Returns all items in the rank
     //				return list; // Breaks the loop
     //			}
-...
     //		// If no item has been found -> return null
     //		return null;
     //	}
     	/**
     	 * This method should be used when is wanted distinguish small letters from capital letters during the search, and the comparation of items
     	 *   done according an algorithm we define.
+    	 *
     	 * And it's also necessary that the value returned by the <i>toString()</i> method of each item (supposing
+    	 *
     	 * And it's also necessary that the value returned by the <i>toString()</i> method of each item (supposing
     	 *   they inherit from Object) would be the expected value user saw (that would be used to compare the items).
+    	 *
+    	 *
     	 * @param text java.lang.String
     	 * @param sortOrderedItems java.util.Vector
     	 * @param comp An Comparator object which implements the <i><b>compareTo()</b><i>  method.
     	 */
     	public synchronized static List<Object> doSearchConsideringCaseSensitive(String text, Vector<Object> sortOrderedItems, Comparator<Object> comp) {
     		List<Object> results_list = doSearchIgnoringCaseSensitive(text, sortOrderedItems, comp);
     	public synchronized static List doSearchConsideringCaseSensitive(String text, Vector sortOrderedItems, Comparator comp) {
     		List results_list = doSearchIgnoringCaseSensitive(text, sortOrderedItems, comp);
     		if (results_list == null)
     			return null;
     		List<Object> results = new ArrayList<Object>();
     		List results = new ArrayList();
     		for (int i = 0; i < (results_list.size()); i++) {
     			if (results_list.get(i).toString().startsWith(text)) {
-...
     		return results;
+    	}
     	/**
     	 * This method should be used when is wanted not to distinguish small letters from capital letters during the search, and the comparation of items
     	 *   done according an algorithm we define.
+    	 *
     	 * And it's also necessary that the value returned by the <i>toString()</i> method of each item (supposing
+    	 *
     	 * And it's also necessary that the value returned by the <i>toString()</i> method of each item (supposing
     	 *   they inherit from Object) would be the expected value user saw (that would be used to compare the items).
+    	 *
     	 * @param text java.lang.String
     	 * @param sortOrderedItems java.util.Vector
     	 * @param comp An Comparator object which implements the <i><b>compareTo()</b><i>  method.
     	 */
     	public synchronized static List<Object> doSearchIgnoringCaseSensitive(String text, Vector<Object> sortOrderedItems, Comparator<Object> comp) {
     	public synchronized static List doSearchIgnoringCaseSensitive(String text, Vector sortOrderedItems, Comparator comp) {
     		int currentIteration = 0;
     		int size = sortOrderedItems.size();
     		int maxNumberOfIterations = (int) MathExtension.log2(size);
     		int lowIndex = 0;
     		int highIndex = sortOrderedItems.size() - 1;
     		int mIndx;
     		while ((lowIndex <= highIndex) && (currentIteration <= maxNumberOfIterations)) {
     			mIndx = ( lowIndex + highIndex ) / 2;
     			if ( sortOrderedItems.get( mIndx ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) {
     				lowIndex = highIndex = mIndx;
     				highIndex ++;
     				// Expand the rank to up
     				while ( ( highIndex < size ) && ( sortOrderedItems.get( highIndex ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
     					highIndex ++;
-...
     				while ( ( (lowIndex - 1) > -1 ) && ( sortOrderedItems.get( (lowIndex - 1) ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
     					lowIndex --;
+    				}
     				// Returns all items in the rank
     				// Returns all items in the rank
     				return Arrays.asList((sortOrderedItems.subList(lowIndex, highIndex)).toArray()); // Breaks the loop
+    			}
     			else {
-...
     					lowIndex = mIndx + 1;
+    				}
+    			}
     			currentIteration ++;
+    		}
     		return null;
+    	}
+    }

Also available in: Unified diff