com.partnersoft.data

Class LinearSearch

java.lang.Object

com.partnersoft.data.LinearSearch

All Implemented Interfaces:

SearchingAlgorithm

public class LinearSearch
extends java.lang.Object
implements SearchingAlgorithm

A generic linear full-scan search.

This search method is generally used by other methods, or by sorting algorithms. It does not assume that the keys are in order. However, it is very slow for worst-case, so you should pre-sort your array and use BinarySearch or some other algorithm instead.

This isn't declared as a singleton, since it has no actual overhead (no state), so there's not strong reason to limit instantiation. However an standardInstance() method is provided that provides a shared instance.

You can also just use this via the handy convenience method SearchingLib.linearSearch(SearchingGopher, Object); that is actually the recommended method.

Copyright 2004-2006 Partner Software, Inc.

Author:

Paul Reavis

Constructor Summary

Constructors

Constructor and Description
LinearSearch() Creates a new LinearSearch algorithm object.

Method Summary

Methods

Modifier and Type	Method and Description
int	findClosest(SearchingGopher gopher, java.lang.Object key) Finds the slot where the given key would go if it were in there.
int	findClosest(SearchingGopher gopher, java.lang.Object key, int start, int end) Finds the slot where the given key would go if it were in there over the given inclusive range (start <= i <= end).
int	search(SearchingGopher gopher, java.lang.Object key) Searches for the given key using the given gopher.
int	search(SearchingGopher gopher, java.lang.Object key, int start, int end) Searches for the given key using the given gopher over the given range (start <= i < end).
static LinearSearch	standardInstance() Returns a singleton shared instance.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LinearSearch

public LinearSearch()

Creates a new LinearSearch algorithm object. Generally you don't need to do this; this constructor is provided to allow serialization and instantiation, but you can almost always just use the standardInstance() method.

Method Detail

standardInstance

public static LinearSearch standardInstance()

Returns a singleton shared instance.

Returns:

standard LinearSearch instance

search

public final int search(SearchingGopher gopher,
         java.lang.Object key)

Description copied from interface: SearchingAlgorithm

Searches for the given key using the given gopher. Returns -1 if the search fails.

Specified by:

search in interface SearchingAlgorithm

Parameters:

gopher - adapter to underlying array-like structure

key - value to search for

Returns:

index of found item, or -1 if search failed

search

public final int search(SearchingGopher gopher,
         java.lang.Object key,
         int start,
         int end)

Description copied from interface: SearchingAlgorithm

Searches for the given key using the given gopher over the given range (start <= i < end). Returns -1 if the search fails.

Specified by:

search in interface SearchingAlgorithm

Parameters:

gopher - adapter to underlying array-like structure

key - value to search for

start - start of index range, inclusive (start <= i)

end - end of index range, exclusive (i < end)

Returns:

index of found item, or -1 if search failed

findClosest

public final int findClosest(SearchingGopher gopher,
              java.lang.Object key)

Description copied from interface: SearchingAlgorithm

Finds the slot where the given key would go if it were in there. Always returns something. Useful for insertion-based structures, or for near-match searches.

Specified by:

findClosest in interface SearchingAlgorithm

Parameters:

gopher - adapter to underlying array-like structure

key - value to search for

Returns:

index of found item, or index where found item would be inserted if it were there

findClosest

public final int findClosest(SearchingGopher gopher,
              java.lang.Object key,
              int start,
              int end)

Description copied from interface: SearchingAlgorithm

Finds the slot where the given key would go if it were in there over the given inclusive range (start <= i <= end). Always returns something. Useful for insertion-based structures, or for near-match searches.

Specified by:

findClosest in interface SearchingAlgorithm

Parameters:

gopher - adapter to underlying array-like structure

key - value to search for

start - start of index range, inclusive (start <= i)

end - end of index range, exclusive (i < end)

Returns:

index of found item, or index where found item would be inserted if it were there