SearchIterator.java
// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
*******************************************************************************
* Copyright (C) 1996-2015, International Business Machines Corporation and *
* others. All Rights Reserved. *
*******************************************************************************
*/
package com.ibm.icu.text;
import java.text.CharacterIterator;
/**
* {@code SearchIterator} is an abstract base class that provides methods to search for a pattern
* within a text string. Instances of {@code SearchIterator} maintain a current position and scan
* over the target text, returning the indices the pattern is matched and the length of each match.
*
* <p>{@code SearchIterator} defines a protocol for text searching. Subclasses provide concrete
* implementations of various search algorithms. For example, {@code StringSearch} implements
* language-sensitive pattern matching based on the comparison rules defined in a {@code
* RuleBasedCollator} object.
*
* <p>Other options for searching include using a BreakIterator to restrict the points at which
* matches are detected.
*
* <p>{@code SearchIterator} provides an API that is similar to that of other text iteration classes
* such as {@code BreakIterator}. Using this class, it is easy to scan through text looking for all
* occurrences of a given pattern. The following example uses a {@code StringSearch} object to find
* all instances of "fox" in the target string. Any other subclass of {@code SearchIterator} can be
* used in an identical manner.
*
* <pre><code>
* String target = "The quick brown fox jumped over the lazy fox";
* String pattern = "fox";
* SearchIterator iter = new StringSearch(pattern, target);
* for (int pos = iter.first(); pos != SearchIterator.DONE;
* pos = iter.next()) {
* System.out.println("Found match at " + pos +
* ", length is " + iter.getMatchLength());
* }
* </code></pre>
*
* @author Laura Werner, synwee
* @stable ICU 2.0
* @see BreakIterator
* @see RuleBasedCollator
*/
public abstract class SearchIterator {
/**
* The BreakIterator to define the boundaries of a logical match. This value can be a null. See
* class documentation for more information.
*
* @see #setBreakIterator(BreakIterator)
* @see #getBreakIterator
* @see BreakIterator
* @stable ICU 2.0
*/
protected BreakIterator breakIterator;
/**
* Target text for searching.
*
* @see #setTarget(CharacterIterator)
* @see #getTarget
* @stable ICU 2.0
*/
protected CharacterIterator targetText;
/**
* Length of the most current match in target text. Value 0 is the default value.
*
* @see #setMatchLength
* @see #getMatchLength
* @stable ICU 2.0
*/
protected int matchLength;
/**
* Java port of ICU4C struct USearch (usrchimp.h)
*
* <p>Note:
*
* <p>ICU4J already exposed some protected members such as targetText, breakIterator and
* matchedLength as a part of stable APIs. In ICU4C, they are exposed through USearch struct,
* although USearch struct itself is internal API.
*
* <p>This class was created for making ICU4J code parallel to ICU4C implementation. ICU4J
* implementation access member fields like C struct (e.g. search_.isOverlap_) mostly, except
* fields already exposed as protected member (e.g. search_.text()).
*/
final class Search {
CharacterIterator text() {
return SearchIterator.this.targetText;
}
void setTarget(CharacterIterator text) {
SearchIterator.this.targetText = text;
}
/**
* Flag to indicate if overlapping search is to be done. E.g. looking for "aa" in "aaa" will
* yield matches at offset 0 and 1.
*/
boolean isOverlap_;
boolean isCanonicalMatch_;
ElementComparisonType elementComparisonType_;
BreakIterator internalBreakIter_;
BreakIterator breakIter() {
return SearchIterator.this.breakIterator;
}
void setBreakIter(BreakIterator breakIter) {
SearchIterator.this.breakIterator = breakIter;
}
int matchedIndex_;
int matchedLength() {
return SearchIterator.this.matchLength;
}
void setMatchedLength(int matchedLength) {
SearchIterator.this.matchLength = matchedLength;
}
/** Flag indicates if we are doing a forwards search */
boolean isForwardSearching_;
/**
* Flag indicates if we are at the start of a string search. This indicates that we are in
* forward search and at the start of m_text.
*/
boolean reset_;
// Convenient methods for accessing begin/end index of the
// target text. These are ICU4J only and are not data fields.
int beginIndex() {
if (targetText == null) {
return 0;
}
return targetText.getBeginIndex();
}
int endIndex() {
if (targetText == null) {
return 0;
}
return targetText.getEndIndex();
}
}
Search search_ = new Search();
// public data members -------------------------------------------------
/**
* DONE is returned by previous() and next() after all valid matches have been returned, and by
* first() and last() if there are no matches at all.
*
* @see #previous
* @see #next
* @stable ICU 2.0
*/
public static final int DONE = -1;
// public methods -----------------------------------------------------
// public setters -----------------------------------------------------
/**
* Sets the position in the target text at which the next search will start. This method clears
* any previous match.
*
* @param position position from which to start the next search
* @exception IndexOutOfBoundsException thrown if argument position is out of the target text
* range.
* @see #getIndex
* @stable ICU 2.8
*/
public void setIndex(int position) {
if (position < search_.beginIndex() || position > search_.endIndex()) {
throw new IndexOutOfBoundsException(
"setIndex(int) expected position to be between "
+ search_.beginIndex()
+ " and "
+ search_.endIndex());
}
search_.reset_ = false;
search_.setMatchedLength(0);
search_.matchedIndex_ = DONE;
}
/**
* Determines whether overlapping matches are returned. See the class documentation for more
* information about overlapping matches.
*
* <p>The default setting of this property is false
*
* @param allowOverlap flag indicator if overlapping matches are allowed
* @see #isOverlapping
* @stable ICU 2.8
*/
public void setOverlapping(boolean allowOverlap) {
search_.isOverlap_ = allowOverlap;
}
/**
* Set the BreakIterator that will be used to restrict the points at which matches are detected.
*
* @param breakiter A BreakIterator that will be used to restrict the points at which matches
* are detected. If a match is found, but the match's start or end index is not a boundary
* as determined by the {@link BreakIterator}, the match will be rejected and another will
* be searched for. If this parameter is {@code null}, no break detection is attempted.
* @see BreakIterator
* @stable ICU 2.0
*/
public void setBreakIterator(BreakIterator breakiter) {
search_.setBreakIter(breakiter);
if (search_.breakIter() != null) {
// Create a clone of CharacterItearator, so it won't
// affect the position currently held by search_.text()
if (search_.text() != null) {
search_.breakIter().setText((CharacterIterator) search_.text().clone());
}
}
}
/**
* Set the target text to be searched. Text iteration will then begin at the start of the text
* string. This method is useful if you want to reuse an iterator to search within a different
* body of text.
*
* @param text new text iterator to look for match,
* @exception IllegalArgumentException thrown when text is null or has 0 length
* @see #getTarget
* @stable ICU 2.4
*/
public void setTarget(CharacterIterator text) {
if (text == null || text.getEndIndex() == text.getIndex()) {
throw new IllegalArgumentException("Illegal null or empty text");
}
text.setIndex(text.getBeginIndex());
search_.setTarget(text);
search_.matchedIndex_ = DONE;
search_.setMatchedLength(0);
search_.reset_ = true;
search_.isForwardSearching_ = true;
if (search_.breakIter() != null) {
// Create a clone of CharacterItearator, so it won't
// affect the position currently held by search_.text()
search_.breakIter().setText((CharacterIterator) text.clone());
}
if (search_.internalBreakIter_ != null) {
search_.internalBreakIter_.setText((CharacterIterator) text.clone());
}
}
// TODO: We may add APIs below to match ICU4C APIs
// setCanonicalMatch
// public getters ----------------------------------------------------
/**
* Returns the index to the match in the text string that was searched. This call returns a
* valid result only after a successful call to {@link #first}, {@link #next}, {@link
* #previous}, or {@link #last}. Just after construction, or after a searching method returns
* {@link #DONE}, this method will return {@link #DONE}.
*
* <p>Use {@link #getMatchLength} to get the matched string length.
*
* @return index of a substring within the text string that is being searched.
* @see #first
* @see #next
* @see #previous
* @see #last
* @stable ICU 2.0
*/
public int getMatchStart() {
return search_.matchedIndex_;
}
/**
* Return the current index in the text being searched. If the iteration has gone past the end
* of the text (or past the beginning for a backwards search), {@link #DONE} is returned.
*
* @return current index in the text being searched.
* @stable ICU 2.8
*/
public abstract int getIndex();
/**
* Returns the length of text in the string which matches the search pattern. This call returns
* a valid result only after a successful call to {@link #first}, {@link #next}, {@link
* #previous}, or {@link #last}. Just after construction, or after a searching method returns
* {@link #DONE}, this method will return 0.
*
* @return The length of the match in the target text, or 0 if there is no match currently.
* @see #first
* @see #next
* @see #previous
* @see #last
* @stable ICU 2.0
*/
public int getMatchLength() {
return search_.matchedLength();
}
/**
* Returns the BreakIterator that is used to restrict the indexes at which matches are detected.
* This will be the same object that was passed to the constructor or to {@link
* #setBreakIterator}. If the {@link BreakIterator} has not been set, {@code null} will be
* returned. See {@link #setBreakIterator} for more information.
*
* @return the BreakIterator set to restrict logic matches
* @see #setBreakIterator
* @see BreakIterator
* @stable ICU 2.0
*/
public BreakIterator getBreakIterator() {
return search_.breakIter();
}
/**
* Return the string text to be searched.
*
* @return text string to be searched.
* @stable ICU 2.0
*/
public CharacterIterator getTarget() {
return search_.text();
}
/**
* Returns the text that was matched by the most recent call to {@link #first}, {@link #next},
* {@link #previous}, or {@link #last}. If the iterator is not pointing at a valid match (e.g.
* just after construction or after {@link #DONE} has been returned, returns an empty string.
*
* @return the substring in the target test of the most recent match, or null if there is no
* match currently.
* @see #first
* @see #next
* @see #previous
* @see #last
* @stable ICU 2.0
*/
public String getMatchedText() {
if (search_.matchedLength() > 0) {
int limit = search_.matchedIndex_ + search_.matchedLength();
StringBuilder result = new StringBuilder(search_.matchedLength());
CharacterIterator it = search_.text();
it.setIndex(search_.matchedIndex_);
while (it.getIndex() < limit) {
result.append(it.current());
it.next();
}
it.setIndex(search_.matchedIndex_);
return result.toString();
}
return null;
}
// miscellaneous public methods -----------------------------------------
/**
* Returns the index of the next point at which the text matches the search pattern, starting
* from the current position The iterator is adjusted so that its current index (as returned by
* {@link #getIndex}) is the match position if one was found. If a match is not found, {@link
* #DONE} will be returned and the iterator will be adjusted to a position after the end of the
* text string.
*
* @return The index of the next match after the current position, or {@link #DONE} if there are
* no more matches.
* @see #getIndex
* @stable ICU 2.0
*/
public int next() {
int index = getIndex(); // offset = getOffset() in ICU4C
int matchindex = search_.matchedIndex_;
int matchlength = search_.matchedLength();
search_.reset_ = false;
if (search_.isForwardSearching_) {
int endIdx = search_.endIndex();
if (index == endIdx
|| matchindex == endIdx
|| (matchindex != DONE && matchindex + matchlength >= endIdx)) {
setMatchNotFound();
return DONE;
}
} else {
// switching direction.
// if matchedIndex == DONE, it means that either a
// setIndex (setOffset in C) has been called or that previous ran off the text
// string. the iterator would have been set to offset 0 if a
// match is not found.
search_.isForwardSearching_ = true;
if (search_.matchedIndex_ != DONE) {
// there's no need to set the collation element iterator
// the next call to next will set the offset.
return matchindex;
}
}
if (matchlength > 0) {
// if matchlength is 0 we are at the start of the iteration
if (search_.isOverlap_) {
index++;
} else {
index += matchlength;
}
}
return handleNext(index);
}
/**
* Returns the index of the previous point at which the string text matches the search pattern,
* starting at the current position. The iterator is adjusted so that its current index (as
* returned by {@link #getIndex}) is the match position if one was found. If a match is not
* found, {@link #DONE} will be returned and the iterator will be adjusted to the index {@link
* #DONE}.
*
* @return The index of the previous match before the current position, or {@link #DONE} if
* there are no more matches.
* @see #getIndex
* @stable ICU 2.0
*/
public int previous() {
int index; // offset in ICU4C
if (search_.reset_) {
index = search_.endIndex(); // m_search_->textLength in ICU4C
search_.isForwardSearching_ = false;
search_.reset_ = false;
setIndex(index);
} else {
index = getIndex();
}
int matchindex = search_.matchedIndex_;
if (search_.isForwardSearching_) {
// switching direction.
// if matchedIndex == DONE, it means that either a
// setIndex (setOffset in C) has been called or that next ran off the text
// string. the iterator would have been set to offset textLength if
// a match is not found.
search_.isForwardSearching_ = false;
if (matchindex != DONE) {
return matchindex;
}
} else {
int startIdx = search_.beginIndex();
if (index == startIdx || matchindex == startIdx) {
// not enough characters to match
setMatchNotFound();
return DONE;
}
}
if (matchindex != DONE) {
if (search_.isOverlap_) {
matchindex += search_.matchedLength() - 2;
}
return handlePrevious(matchindex);
}
return handlePrevious(index);
}
/**
* Return true if the overlapping property has been set. See {@link #setOverlapping(boolean)}
* for more information.
*
* @see #setOverlapping
* @return true if the overlapping property has been set, false otherwise
* @stable ICU 2.8
*/
public boolean isOverlapping() {
return search_.isOverlap_;
}
// TODO: We may add APIs below to match ICU4C APIs
// isCanonicalMatch
/**
* Resets the iteration. Search will begin at the start of the text string if a forward
* iteration is initiated before a backwards iteration. Otherwise if a backwards iteration is
* initiated before a forwards iteration, the search will begin at the end of the text string.
*
* @stable ICU 2.0
*/
public void reset() {
setMatchNotFound();
setIndex(search_.beginIndex());
search_.isOverlap_ = false;
search_.isCanonicalMatch_ = false;
search_.elementComparisonType_ = ElementComparisonType.STANDARD_ELEMENT_COMPARISON;
search_.isForwardSearching_ = true;
search_.reset_ = true;
}
/**
* Returns the first index at which the string text matches the search pattern. The iterator is
* adjusted so that its current index (as returned by {@link #getIndex()}) is the match position
* if one
*
* <p>was found. If a match is not found, {@link #DONE} will be returned and the iterator will
* be adjusted to the index {@link #DONE}.
*
* @return The character index of the first match, or {@link #DONE} if there are no matches.
* @see #getIndex
* @stable ICU 2.0
*/
public final int first() {
int startIdx = search_.beginIndex();
setIndex(startIdx);
return handleNext(startIdx);
}
/**
* Returns the first index equal or greater than {@code position} at which the string text
* matches the search pattern. The iterator is adjusted so that its current index (as returned
* by {@link #getIndex()}) is the match position if one was found. If a match is not found,
* {@link #DONE} will be returned and the iterator will be adjusted to the index {@link #DONE}.
*
* @param position where search if to start from.
* @return The character index of the first match following {@code position}, or {@link #DONE}
* if there are no matches.
* @throws IndexOutOfBoundsException If position is less than or greater than the text range for
* searching.
* @see #getIndex
* @stable ICU 2.0
*/
public final int following(int position) {
setIndex(position);
return handleNext(position);
}
/**
* Returns the last index in the target text at which it matches the search pattern. The
* iterator is adjusted so that its current index (as returned by {@link #getIndex}) is the
* match position if one was found. If a match is not found, {@link #DONE} will be returned and
* the iterator will be adjusted to the index {@link #DONE}.
*
* @return The index of the first match, or {@link #DONE} if there are no matches.
* @see #getIndex
* @stable ICU 2.0
*/
public final int last() {
int endIdx = search_.endIndex();
setIndex(endIdx);
return handlePrevious(endIdx);
}
/**
* Returns the first index less than {@code position} at which the string text matches the
* search pattern. The iterator is adjusted so that its current index (as returned by {@link
* #getIndex}) is the match position if one was found. If a match is not found, {@link #DONE}
* will be returned and the iterator will be adjusted to the index {@link #DONE}
*
* <p>When the overlapping option ({@link #isOverlapping}) is off, the last index of the result
* match is always less than {@code position}. When the overlapping option is on, the result
* match may span across {@code position}.
*
* @param position where search is to start from.
* @return The character index of the first match preceding {@code position}, or {@link #DONE}
* if there are no matches.
* @throws IndexOutOfBoundsException If position is less than or greater than the text range for
* searching
* @see #getIndex
* @stable ICU 2.0
*/
public final int preceding(int position) {
setIndex(position);
return handlePrevious(position);
}
// protected constructor ----------------------------------------------
/**
* Protected constructor for use by subclasses. Initializes the iterator with the argument
* target text for searching and sets the BreakIterator. See class documentation for more
* details on the use of the target text and {@link BreakIterator}.
*
* @param target The target text to be searched.
* @param breaker A {@link BreakIterator} that is used to determine the boundaries of a logical
* match. This argument can be null.
* @exception IllegalArgumentException thrown when argument target is null, or of length 0
* @see BreakIterator
* @stable ICU 2.0
*/
protected SearchIterator(CharacterIterator target, BreakIterator breaker) {
if (target == null || (target.getEndIndex() - target.getBeginIndex()) == 0) {
throw new IllegalArgumentException(
"Illegal argument target. " + " Argument can not be null or of length 0");
}
search_.setTarget(target);
search_.setBreakIter(breaker);
if (search_.breakIter() != null) {
search_.breakIter().setText((CharacterIterator) target.clone());
}
search_.isOverlap_ = false;
search_.isCanonicalMatch_ = false;
search_.elementComparisonType_ = ElementComparisonType.STANDARD_ELEMENT_COMPARISON;
search_.isForwardSearching_ = true;
search_.reset_ = true;
search_.matchedIndex_ = DONE;
search_.setMatchedLength(0);
}
// protected methods --------------------------------------------------
/**
* Sets the length of the most recent match in the target text. Subclasses' handleNext() and
* handlePrevious() methods should call this after they find a match in the target text.
*
* @param length new length to set
* @see #handleNext
* @see #handlePrevious
* @stable ICU 2.0
*/
protected void setMatchLength(int length) {
search_.setMatchedLength(length);
}
/**
* Abstract method which subclasses override to provide the mechanism for finding the next match
* in the target text. This allows different subclasses to provide different search algorithms.
*
* <p>If a match is found, the implementation should return the index at which the match starts
* and should call {@link #setMatchLength} with the number of characters in the target text that
* make up the match. If no match is found, the method should return {@link #DONE}.
*
* @param start The index in the target text at which the search should start.
* @return index at which the match starts, else if match is not found {@link #DONE} is returned
* @see #setMatchLength
* @stable ICU 2.0
*/
protected abstract int handleNext(int start);
/**
* Abstract method which subclasses override to provide the mechanism for finding the previous
* match in the target text. This allows different subclasses to provide different search
* algorithms.
*
* <p>If a match is found, the implementation should return the index at which the match starts
* and should call {@link #setMatchLength} with the number of characters in the target text that
* make up the match. If no match is found, the method should return {@link #DONE}.
*
* @param startAt The index in the target text at which the search should start.
* @return index at which the match starts, else if match is not found {@link #DONE} is returned
* @see #setMatchLength
* @stable ICU 2.0
*/
protected abstract int handlePrevious(int startAt);
/**
* @internal
* @deprecated This API is ICU internal only.
*/
@Deprecated
// TODO: This protected method is @stable 2.0 in ICU4C
protected void setMatchNotFound() {
search_.matchedIndex_ = DONE;
search_.setMatchedLength(0);
}
/**
* Option to control how collation elements are compared. The default value will be {@link
* #STANDARD_ELEMENT_COMPARISON}.
*
* <p>PATTERN_BASE_WEIGHT_IS_WILDCARD supports "asymmetric search" as described in <a
* href="http://www.unicode.org/reports/tr10/#Asymmetric_Search">UTS #10 Unicode Collation
* Algorithm</a>, while ANY_BASE_WEIGHT_IS_WILDCARD supports a related option in which
* "unmarked" characters in either the pattern or the searched text are treated as wildcards
* that match marked or unmarked versions of the same character.
*
* @see #setElementComparisonType(ElementComparisonType)
* @see #getElementComparisonType()
* @stable ICU 53
*/
public enum ElementComparisonType {
/**
* Standard collation element comparison at the specified collator strength.
*
* @stable ICU 53
*/
STANDARD_ELEMENT_COMPARISON,
/**
* Collation element comparison is modified to effectively provide behavior between the
* specified strength and strength - 1.
*
* <p>Collation elements in the pattern that have the base weight for the specified strength
* are treated as "wildcards" that match an element with any other weight at that collation
* level in the searched text. For example, with a secondary-strength English collator, a
* plain 'e' in the pattern will match a plain e or an e with any diacritic in the searched
* text, but an e with diacritic in the pattern will only match an e with the same diacritic
* in the searched text.
*
* @stable ICU 53
*/
PATTERN_BASE_WEIGHT_IS_WILDCARD,
/**
* Collation element comparison is modified to effectively provide behavior between the
* specified strength and strength - 1.
*
* <p>Collation elements in either the pattern or the searched text that have the base
* weight for the specified strength are treated as "wildcards" that match an element with
* any other weight at that collation level. For example, with a secondary-strength English
* collator, a plain 'e' in the pattern will match a plain e or an e with any diacritic in
* the searched text, but an e with diacritic in the pattern will only match an e with the
* same diacritic or a plain e in the searched text.
*
* @stable ICU 53
*/
ANY_BASE_WEIGHT_IS_WILDCARD
}
/**
* Sets the collation element comparison type.
*
* <p>The default comparison type is {@link ElementComparisonType#STANDARD_ELEMENT_COMPARISON}.
*
* @see ElementComparisonType
* @see #getElementComparisonType()
* @stable ICU 53
*/
public void setElementComparisonType(ElementComparisonType type) {
search_.elementComparisonType_ = type;
}
/**
* Returns the collation element comparison type.
*
* @see ElementComparisonType
* @see #setElementComparisonType(ElementComparisonType)
* @stable ICU 53
*/
public ElementComparisonType getElementComparisonType() {
return search_.elementComparisonType_;
}
}