de.caff.generics.algorithm

Class FastIntSequenceSearch

java.lang.Object

de.caff.generics.algorithm.FastIntSequenceSearch

public class FastIntSequenceSearch
extends java.lang.Object

Fast search algorithm in sequences of random-accessible integer values.

Currently only forward search is implemented, but basically both the search indexable and the searched indexable can be reversed before searching.

It also allows for case-insensitive search in integer indexables representing UTF-32 character codes, as this is simple and fast to implement. Note that in this case the allowed character values in the search term are checked to be in the Unicode range of 0x00 to 0x00_10_ff_ff. The indexable in which the search term is searched is not checked for this restriction, and there are no guarantees given to whatever happens in cases where it violates it.

Since:

July 07, 2020

Author:

Rammi

Field Summary

Fields

Modifier and Type	Field and Description
static int	UNICODE_MAX_VALUE Maximum allowed character code value in the Unicode range.

Constructor Summary

Constructors

Constructor and Description
FastIntSequenceSearch(boolean caseInsensitive, int... searchTerm) Convenience constructor.
FastIntSequenceSearch(int... searchTerm) Convenience constructor.
FastIntSequenceSearch(IntIndexable searchTerm) Constructor.
FastIntSequenceSearch(IntIndexable searchTerm, boolean caseInsensitive) Constructor.
FastIntSequenceSearch(java.lang.String searchTerm) Convenience constructor.
FastIntSequenceSearch(java.lang.String searchTerm, boolean caseInsensitive) Convenience constructor.

Method Summary

Modifier and Type	Method and Description
IntIndexable	findAllMatches(IntIndexable data, boolean allowOverlaps) Find all matches.
int	findFirst(IntIndexable data) Find the first appearance of the search term in the given data.
int	findNext(IntIndexable data, int pos) Find the next appearance of the search term after the given position in the given data.
int	findNext(IntIndexable data, int pos, int end) Find the next appearance of the search term after the given start position and before the given end position in the given data.
IntIndexable	getSearchTerm() Get the search term.
boolean	isCaseInsensitive() Is this search done case-insensitive?

Methods inherited from class java.lang.Object

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

Field Detail

UNICODE_MAX_VALUE

public static final int UNICODE_MAX_VALUE

Maximum allowed character code value in the Unicode range.

See Also:

Constant Field Values

Constructor Detail

FastIntSequenceSearch

public FastIntSequenceSearch(@NotNull
                             IntIndexable searchTerm)

Constructor. This will match exactly.

Parameters:

searchTerm - term to search for

FastIntSequenceSearch

public FastIntSequenceSearch(@NotNull
                             IntIndexable searchTerm,
                             boolean caseInsensitive)

Constructor.

Parameters:

searchTerm - term to search for (not empty)

caseInsensitive - true: searching is done in a case-insensitive way (assuming UTF-32 encoding for all values)
false: values have to match exactly

FastIntSequenceSearch

public FastIntSequenceSearch(@NotNull
                             java.lang.String searchTerm)

Convenience constructor. This will look for the code points of the given string.

Parameters:

searchTerm - search term

FastIntSequenceSearch

public FastIntSequenceSearch(@NotNull
                             java.lang.String searchTerm,
                             boolean caseInsensitive)

Convenience constructor. This will look for the code points of the given string, possibly in a case-insensitive way.

Parameters:

searchTerm - search term

caseInsensitive - true: searching is done in a case-insensitive way (assuming UTF-32 encoding for all values)
false: values have to match exactly

FastIntSequenceSearch

public FastIntSequenceSearch(@NotNull
                             int... searchTerm)

Convenience constructor.

Parameters:

searchTerm - search term

FastIntSequenceSearch

public FastIntSequenceSearch(boolean caseInsensitive,
                             @NotNull
                             int... searchTerm)

Convenience constructor. When called with caseInsensitive == true this will handle the values as code points.

Parameters:

searchTerm - search term

caseInsensitive - true: searching is done in a case-insensitive way (assuming UTF-32 encoding for all values)
false: values have to match exactly

Method Detail

getSearchTerm

@NotNull
public IntIndexable getSearchTerm()

Get the search term.

Returns:

search term

isCaseInsensitive

public boolean isCaseInsensitive()

Is this search done case-insensitive?

Returns:

true: if case is not cared for
false: if values have to match exactly

findFirst

public int findFirst(@NotNull
                     IntIndexable data)

Find the first appearance of the search term in the given data.

Parameters:

data - data to search through

Returns:

index of first appearance of the search term in the given data, or -1 if there was nothing found

findNext

public int findNext(@NotNull
                    IntIndexable data,
                    int pos)

Find the next appearance of the search term after the given position in the given data.

Parameters:

data - data to search through

pos - position to start the search

Returns:

position of next appearance of the search term in the given data after the given position, or -1 if there was nothing found between the position and the end of data

findNext

public int findNext(@NotNull
                    IntIndexable data,
                    int pos,
                    int end)

Find the next appearance of the search term after the given start position and before the given end position in the given data.

Parameters:

data - data to search through

pos - position to start the search

end - position to end the search, the whole search term has to fit before this position to be found

Returns:

position of next appearance of the search term in the given data after the given start position and before the given end position, or -1 if there was nothing found between the position and the end of data

findAllMatches

@NotNull
public IntIndexable findAllMatches(@NotNull
                                            IntIndexable data,
                                            boolean allowOverlaps)

Find all matches.

Parameters:

data - data to search

allowOverlaps - allow overlapping sequences in the matches?

Returns:

start position of all matches