Revision 11858 trunk/libraries/libUI/src/org/gvsig/gui/beans/swing/jComboBoxItemsSeeker/BinarySearchUsingFirstCharacters.java
| BinarySearchUsingFirstCharacters.java | ||
|---|---|---|
| 187 | 187 |
|
| 188 | 188 |
// Returns all items in the rank |
| 189 | 189 |
list = Arrays.asList((sortOrderedItems.subList(lowIndex, highIndex)).toArray()); |
| 190 |
|
|
| 191 |
// list = new ArrayList(Arrays.asList((sortOrderedItems.subList(lowIndex, highIndex)).toArray())); // Breaks the loop |
|
| 192 |
// break; |
|
| 190 |
break; |
|
| 193 | 191 |
} |
| 194 | 192 |
else {
|
| 195 | 193 |
if ( sortOrderedItems.get( mIndx ).toString().compareTo( text ) > 0 ) {
|
| ... | ... | |
| 243 | 241 |
obj = list2.get(i); |
| 244 | 242 |
|
| 245 | 243 |
// Don't add items which are already in the list |
| 246 |
if (!list.contains(obj)) {
|
|
| 244 |
if (!list.contains(obj)) {
|
|
| 247 | 245 |
// Adds in sort order the new item: |
| 248 | 246 |
for (j = 0; j < list.size(); j ++) {
|
| 249 | 247 |
if (list.get(j).toString().compareTo(obj.toString()) > 0) |
| ... | ... | |
| 251 | 249 |
} |
| 252 | 250 |
|
| 253 | 251 |
list.add(j, obj); |
| 254 |
System.out.println("A?ade: " + obj);
|
|
| 255 | 252 |
} |
| 256 | 253 |
} |
| 257 | 254 |
|
| 255 |
// It's possible that some elements at the end wouldn't be found -> another small search |
|
| 256 |
size = list.size(); |
|
| 257 |
if (size == 0) {
|
|
| 258 |
j = 0; |
|
| 259 |
} |
|
| 260 |
else {
|
|
| 261 |
j = sortOrderedItems.indexOf(list.get(size - 1)); |
|
| 262 |
} |
|
| 263 |
|
|
| 264 |
j++; |
|
| 265 |
|
|
| 266 |
if (j < sortOrderedItems.size()) {
|
|
| 267 |
do {
|
|
| 268 |
obj = sortOrderedItems.get( j ); |
|
| 269 |
|
|
| 270 |
if (obj.toString().toLowerCase().startsWith( text.toLowerCase())) {
|
|
| 271 |
list.add(size, obj); |
|
| 272 |
} |
|
| 273 |
|
|
| 274 |
j++; |
|
| 275 |
} |
|
| 276 |
while (j < sortOrderedItems.size()); |
|
| 277 |
} |
|
| 278 |
|
|
| 258 | 279 |
return list; |
| 259 | 280 |
} |
| 260 | 281 |
} |
| ... | ... | |
| 273 | 294 |
return null; |
| 274 | 295 |
} |
| 275 | 296 |
|
| 297 |
// /** THIS VERSION FAILURES IN SOME PARTICULAR SITUATIONS |
|
| 298 |
// * This method should be used when is wanted distinguish small letters from capital letters during the search, and the comparation of items |
|
| 299 |
// * done according an algorithm we define. |
|
| 300 |
// * |
|
| 301 |
// * And it's also necessary that the value returned by the <i>toString()</i> method of each item (supposing |
|
| 302 |
// * they inherit from Object) would be the expected value user saw (that would be used to compare the items). |
|
| 303 |
// * |
|
| 304 |
// * @param text java.lang.String |
|
| 305 |
// * @param sortOrderedItems java.util.Vector |
|
| 306 |
// * @param comp An Comparator object which implements the <i><b>compareTo()</b><i> method. |
|
| 307 |
// */ |
|
| 308 |
// public synchronized static List doSearchConsideringCaseSensitive(String text, Vector sortOrderedItems, Comparator comp) {
|
|
| 309 |
// int currentIteration = 0; |
|
| 310 |
// int size = sortOrderedItems.size(); |
|
| 311 |
// int maxNumberOfIterations = (int) MathExtension.log2(size); |
|
| 312 |
// int lowIndex = 0; |
|
| 313 |
// int highIndex = sortOrderedItems.size() - 1; |
|
| 314 |
// int mIndx; |
|
| 315 |
// |
|
| 316 |
// |
|
| 317 |
// while ((lowIndex <= highIndex) && (currentIteration <= maxNumberOfIterations)) {
|
|
| 318 |
// mIndx = ( lowIndex + highIndex ) / 2; |
|
| 319 |
// |
|
| 320 |
// if ( sortOrderedItems.get( mIndx ).toString().startsWith( text ) ) {
|
|
| 321 |
// lowIndex = highIndex = mIndx; |
|
| 322 |
// highIndex ++; |
|
| 323 |
// |
|
| 324 |
// // Expand the rank to up |
|
| 325 |
// while ( ( highIndex < size ) && ( sortOrderedItems.get( highIndex ).toString().startsWith( text ) ) ) {
|
|
| 326 |
// highIndex ++; |
|
| 327 |
// } |
|
| 328 |
// |
|
| 329 |
// // Expand the rank to down |
|
| 330 |
// while ( ( (lowIndex - 1) > -1 ) && ( sortOrderedItems.get( (lowIndex - 1) ).toString().startsWith( text ) ) ) {
|
|
| 331 |
// lowIndex --; |
|
| 332 |
// } |
|
| 333 |
// |
|
| 334 |
// // It's possible that items with different case, should be between the same case, then this item will be added individually: |
|
| 335 |
// List list = new Vector(sortOrderedItems.subList(lowIndex, highIndex)); |
|
| 336 |
// |
|
| 337 |
// |
|
| 338 |
// // Expand to down |
|
| 339 |
// lowIndex --; |
|
| 340 |
// while ( ( lowIndex > -1 ) && ( sortOrderedItems.get( (lowIndex ) ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
|
|
| 341 |
// if (sortOrderedItems.get( lowIndex ).toString().startsWith( text )) {
|
|
| 342 |
// list.add(0, sortOrderedItems.get( lowIndex )); |
|
| 343 |
// } |
|
| 344 |
// |
|
| 345 |
// lowIndex --; |
|
| 346 |
// } |
|
| 347 |
// |
|
| 348 |
// // Expand to up |
|
| 349 |
// while ( ( highIndex < size ) && ( sortOrderedItems.get( highIndex ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
|
|
| 350 |
// if (sortOrderedItems.get( highIndex ).toString().startsWith( text )) {
|
|
| 351 |
// list.add(list.size(), sortOrderedItems.get( highIndex )); |
|
| 352 |
// } |
|
| 353 |
// |
|
| 354 |
// highIndex ++; |
|
| 355 |
// } |
|
| 356 |
// |
|
| 357 |
// // Returns all items in the rank |
|
| 358 |
// return list; // Breaks the loop |
|
| 359 |
// } |
|
| 360 |
// else {
|
|
| 361 |
// if ( comp.compare(sortOrderedItems.get( mIndx ), text ) > 0 ) {
|
|
| 362 |
// highIndex = mIndx - 1; |
|
| 363 |
// } |
|
| 364 |
// else {
|
|
| 365 |
// lowIndex = mIndx + 1; |
|
| 366 |
// } |
|
| 367 |
// } |
|
| 368 |
// |
|
| 369 |
// currentIteration ++; |
|
| 370 |
// } |
|
| 371 |
// |
|
| 372 |
// // If no item has been found -> return null |
|
| 373 |
// return null; |
|
| 374 |
// } |
|
| 375 |
|
|
| 276 | 376 |
/** |
| 277 | 377 |
* This method should be used when is wanted distinguish small letters from capital letters during the search, and the comparation of items |
| 278 | 378 |
* done according an algorithm we define. |
| ... | ... | |
| 285 | 385 |
* @param comp An Comparator object which implements the <i><b>compareTo()</b><i> method. |
| 286 | 386 |
*/ |
| 287 | 387 |
public synchronized static List doSearchConsideringCaseSensitive(String text, Vector sortOrderedItems, Comparator comp) {
|
| 288 |
int currentIteration = 0; |
|
| 289 |
int size = sortOrderedItems.size(); |
|
| 290 |
int maxNumberOfIterations = (int) MathExtensionReduced.log2(size); |
|
| 291 |
int lowIndex = 0; |
|
| 292 |
int highIndex = sortOrderedItems.size() - 1; |
|
| 293 |
int mIndx; |
|
| 388 |
List results_list = doSearchIgnoringCaseSensitive(text, sortOrderedItems, comp); |
|
| 294 | 389 |
|
| 390 |
if (results_list == null) |
|
| 391 |
return null; |
|
| 295 | 392 |
|
| 296 |
while ((lowIndex <= highIndex) && (currentIteration <= maxNumberOfIterations)) {
|
|
| 297 |
mIndx = ( lowIndex + highIndex ) / 2; |
|
| 393 |
List results = new ArrayList(); |
|
| 298 | 394 |
|
| 299 |
if ( sortOrderedItems.get( mIndx ).toString().startsWith( text ) ) {
|
|
| 300 |
lowIndex = highIndex = mIndx; |
|
| 301 |
highIndex ++; |
|
| 302 |
|
|
| 303 |
// Expand the rank to up |
|
| 304 |
while ( ( highIndex < size ) && ( sortOrderedItems.get( highIndex ).toString().startsWith( text ) ) ) {
|
|
| 305 |
highIndex ++; |
|
| 306 |
} |
|
| 307 |
|
|
| 308 |
// Expand the rank to down |
|
| 309 |
while ( ( (lowIndex - 1) > -1 ) && ( sortOrderedItems.get( (lowIndex - 1) ).toString().startsWith( text ) ) ) {
|
|
| 310 |
lowIndex --; |
|
| 311 |
} |
|
| 312 |
|
|
| 313 |
// It's possible that items with different case, should be between the same case, then this item will be added individually: |
|
| 314 |
List list = new Vector(sortOrderedItems.subList(lowIndex, highIndex)); |
|
| 315 |
|
|
| 316 |
|
|
| 317 |
// Expand to down |
|
| 318 |
lowIndex --; |
|
| 319 |
while ( ( lowIndex > -1 ) && ( sortOrderedItems.get( (lowIndex ) ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
|
|
| 320 |
if (sortOrderedItems.get( lowIndex ).toString().startsWith( text )) {
|
|
| 321 |
list.add(0, sortOrderedItems.get( lowIndex )); |
|
| 322 |
} |
|
| 323 |
|
|
| 324 |
lowIndex --; |
|
| 325 |
} |
|
| 326 |
|
|
| 327 |
// Expand to up |
|
| 328 |
while ( ( highIndex < size ) && ( sortOrderedItems.get( highIndex ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) ) {
|
|
| 329 |
if (sortOrderedItems.get( highIndex ).toString().startsWith( text )) {
|
|
| 330 |
list.add(list.size(), sortOrderedItems.get( highIndex )); |
|
| 331 |
} |
|
| 332 |
|
|
| 333 |
highIndex ++; |
|
| 334 |
} |
|
| 335 |
|
|
| 336 |
// Returns all items in the rank |
|
| 337 |
return list; // Breaks the loop |
|
| 395 |
for (int i = 0; i < (results_list.size()); i++) {
|
|
| 396 |
if (results_list.get(i).toString().startsWith(text)) {
|
|
| 397 |
results.add(results_list.get(i)); |
|
| 338 | 398 |
} |
| 339 |
else {
|
|
| 340 |
if ( comp.compare(sortOrderedItems.get( mIndx ), text ) > 0 ) {
|
|
| 341 |
highIndex = mIndx - 1; |
|
| 342 |
} |
|
| 343 |
else {
|
|
| 344 |
lowIndex = mIndx + 1; |
|
| 345 |
} |
|
| 346 |
} |
|
| 347 |
|
|
| 348 |
currentIteration ++; |
|
| 349 | 399 |
} |
| 350 | 400 |
|
| 351 |
// If no item has been found -> return null |
|
| 352 |
return null; |
|
| 401 |
return results; |
|
| 353 | 402 |
} |
| 354 | 403 |
|
| 355 | 404 |
/** |
| ... | ... | |
| 373 | 422 |
|
| 374 | 423 |
while ((lowIndex <= highIndex) && (currentIteration <= maxNumberOfIterations)) {
|
| 375 | 424 |
mIndx = ( lowIndex + highIndex ) / 2; |
| 376 |
|
|
| 425 |
|
|
| 377 | 426 |
if ( sortOrderedItems.get( mIndx ).toString().toLowerCase().startsWith( text.toLowerCase() ) ) {
|
| 378 | 427 |
lowIndex = highIndex = mIndx; |
| 379 | 428 |
highIndex ++; |
Also available in: Unified diff