michael@0: * The algorithm implemented is a modified form of the Boyer Moore's search. michael@0: * For more information see michael@0: * michael@0: * "Efficient Text Searching in Java", published in Java Report michael@0: * in February, 1999, for further information on the algorithm. michael@0: *
michael@0: * There are 2 match options for selection:
michael@0: * This search has APIs similar to that of other text iteration mechanisms
michael@0: * such as the break iterators in BreakIterator. Using these
michael@0: * APIs, it is easy to scan through text looking for all occurances of
michael@0: * a given pattern. This search iterator allows changing of direction by
michael@0: * calling a reset followed by a next or previous.
michael@0: * Though a direction change can occur without calling reset first,
michael@0: * this operation comes with some speed penalty.
michael@0: * Match results in the forward direction will match the result matches in
michael@0: * the backwards direction in the reverse order
michael@0: *
michael@0: * SearchIterator provides APIs to specify the starting position
michael@0: * within the text string to be searched, e.g. setOffset,
michael@0: * preceding and following. Since the
michael@0: * starting position will be set as it is specified, please take note that
michael@0: * there are some danger points which the search may render incorrect
michael@0: * results:
michael@0: *
michael@0: * A breakiterator can be used if only matches at logical breaks are desired.
michael@0: * Using a breakiterator will only give you results that exactly matches the
michael@0: * boundaries given by the breakiterator. For instance the pattern "e" will
michael@0: * not be found in the string "\u00e9" if a character break iterator is used.
michael@0: *
michael@0: * Options are provided to handle overlapping matches.
michael@0: * E.g. In English, overlapping matches produces the result 0 and 2
michael@0: * for the pattern "abab" in the text "ababab", where else mutually
michael@0: * exclusive matches only produce the result of 0.
michael@0: *
michael@0: * Though collator attributes will be taken into consideration while
michael@0: * performing matches, there are no APIs here for setting and getting the
michael@0: * attributes. These attributes can be set by getting the collator
michael@0: * from getCollator and using the APIs in coll.h.
michael@0: * Lastly to update StringSearch to the new collator attributes,
michael@0: * reset() has to be called.
michael@0: *
michael@0: * Restriction:
michael@0: * Consult the SearchIterator documentation for information on
michael@0: * and examples of how to use instances of this class to implement text
michael@0: * searching.
michael@0: *
michael@0: * Note, StringSearch is not to be subclassed.
michael@0: *
michael@0: * Note: No parsing of the text within the CharacterIterator
michael@0: * will be done during searching for this version. The block of text
michael@0: * in CharacterIterator will be used as it is.
michael@0: * @param pattern The text for which this object will search.
michael@0: * @param text The text iterator in which to search for the pattern.
michael@0: * @param locale A locale which defines the language-sensitive
michael@0: * comparison rules used to determine whether text in the
michael@0: * pattern and target matches. User is responsible for
michael@0: * the clearing of this object.
michael@0: * @param breakiter A BreakIterator object used to constrain
michael@0: * the matches that are found. Matches whose start and end
michael@0: * indices in the target text are not boundaries as
michael@0: * determined by the BreakIterator are
michael@0: * ignored. If this behavior is not desired,
michael@0: * NULL can be passed in instead.
michael@0: * @param status for errors if any. If either the length of pattern or
michael@0: * text is 0 then an U_ILLEGAL_ARGUMENT_ERROR is returned.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: StringSearch(const UnicodeString &pattern, CharacterIterator &text,
michael@0: const Locale &locale,
michael@0: BreakIterator *breakiter,
michael@0: UErrorCode &status);
michael@0:
michael@0: /**
michael@0: * Creating a StringSearch instance using the argument collator
michael@0: * language rule set. Note, user retains the ownership of this collator,
michael@0: * it does not get destroyed during this instance's destruction.
michael@0: *
michael@0: * Note: No parsing of the text within the CharacterIterator
michael@0: * will be done during searching for this version. The block of text
michael@0: * in CharacterIterator will be used as it is.
michael@0: * @param pattern The text for which this object will search.
michael@0: * @param text The text in which to search for the pattern.
michael@0: * @param coll A RuleBasedCollator object which defines
michael@0: * the language-sensitive comparison rules used to
michael@0: * determine whether text in the pattern and target
michael@0: * matches. User is responsible for the clearing of this
michael@0: * object.
michael@0: * @param breakiter A BreakIterator object used to constrain
michael@0: * the matches that are found. Matches whose start and end
michael@0: * indices in the target text are not boundaries as
michael@0: * determined by the BreakIterator are
michael@0: * ignored. If this behavior is not desired,
michael@0: * NULL can be passed in instead.
michael@0: * @param status for errors if any. If either the length of pattern or
michael@0: * text is 0 then an U_ILLEGAL_ARGUMENT_ERROR is returned.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: StringSearch(const UnicodeString &pattern, CharacterIterator &text,
michael@0: RuleBasedCollator *coll,
michael@0: BreakIterator *breakiter,
michael@0: UErrorCode &status);
michael@0:
michael@0: /**
michael@0: * Copy constructor that creates a StringSearch instance with the same
michael@0: * behavior, and iterating over the same text.
michael@0: * @param that StringSearch instance to be copied.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: StringSearch(const StringSearch &that);
michael@0:
michael@0: /**
michael@0: * Destructor. Cleans up the search iterator data struct.
michael@0: * If a collator is created in the constructor, it will be destroyed here.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: virtual ~StringSearch(void);
michael@0:
michael@0: /**
michael@0: * Clone this object.
michael@0: * Clones can be used concurrently in multiple threads.
michael@0: * If an error occurs, then NULL is returned.
michael@0: * The caller must delete the clone.
michael@0: *
michael@0: * @return a clone of this object
michael@0: *
michael@0: * @see getDynamicClassID
michael@0: * @stable ICU 2.8
michael@0: */
michael@0: StringSearch *clone() const;
michael@0:
michael@0: // operator overloading ---------------------------------------------
michael@0:
michael@0: /**
michael@0: * Assignment operator. Sets this iterator to have the same behavior,
michael@0: * and iterate over the same text, as the one passed in.
michael@0: * @param that instance to be copied.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: StringSearch & operator=(const StringSearch &that);
michael@0:
michael@0: /**
michael@0: * Equality operator.
michael@0: * @param that instance to be compared.
michael@0: * @return TRUE if both instances have the same attributes,
michael@0: * breakiterators, collators and iterate over the same text
michael@0: * while looking for the same pattern.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: virtual UBool operator==(const SearchIterator &that) const;
michael@0:
michael@0: // public get and set methods ----------------------------------------
michael@0:
michael@0: /**
michael@0: * Sets the index to point to the given position, and clears any state
michael@0: * that's affected.
michael@0: *
michael@0: * This method takes the argument index and sets the position in the text
michael@0: * string accordingly without checking if the index is pointing to a
michael@0: * valid starting point to begin searching.
michael@0: * @param position within the text to be set. If position is less
michael@0: * than or greater than the text range for searching,
michael@0: * an U_INDEX_OUTOFBOUNDS_ERROR will be returned
michael@0: * @param status for errors if it occurs
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: virtual void setOffset(int32_t position, UErrorCode &status);
michael@0:
michael@0: /**
michael@0: * Return the current index in the text being searched.
michael@0: * If the iteration has gone past the end of the text
michael@0: * (or past the beginning for a backwards search), USEARCH_DONE
michael@0: * is returned.
michael@0: * @return current index in the text being searched.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: virtual int32_t getOffset(void) const;
michael@0:
michael@0: /**
michael@0: * Set the target text to be searched.
michael@0: * Text iteration will hence begin at the start of the text string.
michael@0: * This method is
michael@0: * useful if you want to re-use an iterator to search for the same
michael@0: * pattern within a different body of text.
michael@0: * @param text text string to be searched
michael@0: * @param status for errors if any. If the text length is 0 then an
michael@0: * U_ILLEGAL_ARGUMENT_ERROR is returned.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: virtual void setText(const UnicodeString &text, UErrorCode &status);
michael@0:
michael@0: /**
michael@0: * Set the target text to be searched.
michael@0: * Text iteration will hence begin at the start of the text string.
michael@0: * This method is
michael@0: * useful if you want to re-use an iterator to search for the same
michael@0: * pattern within a different body of text.
michael@0: * Note: No parsing of the text within the CharacterIterator
michael@0: * will be done during searching for this version. The block of text
michael@0: * in CharacterIterator will be used as it is.
michael@0: * @param text text string to be searched
michael@0: * @param status for errors if any. If the text length is 0 then an
michael@0: * U_ILLEGAL_ARGUMENT_ERROR is returned.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: virtual void setText(CharacterIterator &text, UErrorCode &status);
michael@0:
michael@0: /**
michael@0: * Gets the collator used for the language rules.
michael@0: *
michael@0: * Caller may modify but must not delete the RuleBasedCollator!
michael@0: * Modifications to this collator will affect the original collator passed in to
michael@0: * the StringSearch> constructor or to setCollator, if any.
michael@0: * @return collator used for string search
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: RuleBasedCollator * getCollator() const;
michael@0:
michael@0: /**
michael@0: * Sets the collator used for the language rules. User retains the
michael@0: * ownership of this collator, thus the responsibility of deletion lies
michael@0: * with the user. This method causes internal data such as Boyer-Moore
michael@0: * shift tables to be recalculated, but the iterator's position is
michael@0: * unchanged.
michael@0: * @param coll collator
michael@0: * @param status for errors if any
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: void setCollator(RuleBasedCollator *coll, UErrorCode &status);
michael@0:
michael@0: /**
michael@0: * Sets the pattern used for matching.
michael@0: * Internal data like the Boyer Moore table will be recalculated, but
michael@0: * the iterator's position is unchanged.
michael@0: * @param pattern search pattern to be found
michael@0: * @param status for errors if any. If the pattern length is 0 then an
michael@0: * U_ILLEGAL_ARGUMENT_ERROR is returned.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: void setPattern(const UnicodeString &pattern, UErrorCode &status);
michael@0:
michael@0: /**
michael@0: * Gets the search pattern.
michael@0: * @return pattern used for matching
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: const UnicodeString & getPattern() const;
michael@0:
michael@0: // public methods ----------------------------------------------------
michael@0:
michael@0: /**
michael@0: * Reset the iteration.
michael@0: * Search will begin at the start of the text string if a forward
michael@0: * iteration is initiated before a backwards iteration. Otherwise if
michael@0: * a backwards iteration is initiated before a forwards iteration, the
michael@0: * search will begin at the end of the text string.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: virtual void reset();
michael@0:
michael@0: /**
michael@0: * Returns a copy of StringSearch with the same behavior, and
michael@0: * iterating over the same text, as this one. Note that all data will be
michael@0: * replicated, except for the user-specified collator and the
michael@0: * breakiterator.
michael@0: * @return cloned object
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: virtual SearchIterator * safeClone(void) const;
michael@0:
michael@0: /**
michael@0: * ICU "poor man's RTTI", returns a UClassID for the actual class.
michael@0: *
michael@0: * @stable ICU 2.2
michael@0: */
michael@0: virtual UClassID getDynamicClassID() const;
michael@0:
michael@0: /**
michael@0: * ICU "poor man's RTTI", returns a UClassID for this class.
michael@0: *
michael@0: * @stable ICU 2.2
michael@0: */
michael@0: static UClassID U_EXPORT2 getStaticClassID();
michael@0:
michael@0: protected:
michael@0:
michael@0: // protected method -------------------------------------------------
michael@0:
michael@0: /**
michael@0: * Search forward for matching text, starting at a given location.
michael@0: * Clients should not call this method directly; instead they should
michael@0: * call {@link SearchIterator#next }.
michael@0: *
michael@0: * If a match is found, this method returns the index at which the match
michael@0: * starts and calls {@link SearchIterator#setMatchLength } with the number
michael@0: * of characters in the target text that make up the match. If no match
michael@0: * is found, the method returns USEARCH_DONE.
michael@0: *
michael@0: * The StringSearch is adjusted so that its current index
michael@0: * (as returned by {@link #getOffset }) is the match position if one was
michael@0: * found.
michael@0: * If a match is not found, USEARCH_DONE will be returned and
michael@0: * the StringSearch will be adjusted to the index USEARCH_DONE.
michael@0: * @param position The index in the target text at which the search
michael@0: * starts
michael@0: * @param status for errors if any occurs
michael@0: * @return The index at which the matched text in the target starts, or
michael@0: * USEARCH_DONE if no match was found.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: virtual int32_t handleNext(int32_t position, UErrorCode &status);
michael@0:
michael@0: /**
michael@0: * Search backward for matching text, starting at a given location.
michael@0: * Clients should not call this method directly; instead they should call
michael@0: * SearchIterator.previous(), which this method overrides.
michael@0: *
michael@0: * If a match is found, this method returns the index at which the match
michael@0: * starts and calls {@link SearchIterator#setMatchLength } with the number
michael@0: * of characters in the target text that make up the match. If no match
michael@0: * is found, the method returns USEARCH_DONE.
michael@0: *
michael@0: * The StringSearch is adjusted so that its current index
michael@0: * (as returned by {@link #getOffset }) is the match position if one was
michael@0: * found.
michael@0: * If a match is not found, USEARCH_DONE will be returned and
michael@0: * the StringSearch will be adjusted to the index USEARCH_DONE.
michael@0: * @param position The index in the target text at which the search
michael@0: * starts.
michael@0: * @param status for errors if any occurs
michael@0: * @return The index at which the matched text in the target starts, or
michael@0: * USEARCH_DONE if no match was found.
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: virtual int32_t handlePrev(int32_t position, UErrorCode &status);
michael@0:
michael@0: private :
michael@0: StringSearch(); // default constructor not implemented
michael@0:
michael@0: // private data members ----------------------------------------------
michael@0:
michael@0: /**
michael@0: * RuleBasedCollator, contains exactly the same UCollator * in m_strsrch_
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: RuleBasedCollator m_collator_;
michael@0: /**
michael@0: * Pattern text
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: UnicodeString m_pattern_;
michael@0: /**
michael@0: * String search struct data
michael@0: * @stable ICU 2.0
michael@0: */
michael@0: UStringSearch *m_strsrch_;
michael@0:
michael@0: };
michael@0:
michael@0: U_NAMESPACE_END
michael@0:
michael@0: #endif /* #if !UCONFIG_NO_COLLATION */
michael@0:
michael@0: #endif
michael@0:
michael@0: * Let S' be the sub-string of a text string S between the offsets start and
michael@0: * end
michael@0: * A pattern string P matches a text string S at the offsets
michael@0: * option 1. Some canonical equivalent of P matches some canonical equivalent
michael@0: * of S'
michael@0: * option 2. P matches S' and if P starts or ends with a combining mark,
michael@0: * there exists no non-ignorable combining mark before or after S?
michael@0: * in S respectively.
michael@0: *
michael@0: * Option 2. will be the default.
michael@0: *
michael@0: *
michael@0: *
michael@0: * Currently there are no composite characters that consists of a
michael@0: * character with combining class > 0 before a character with combining
michael@0: * class == 0. However, if such a character exists in the future,
michael@0: * StringSearch does not guarantee the results for option 1.
michael@0: *
michael@0: *
michael@0: * UnicodeString target("The quick brown fox jumps over the lazy dog.");
michael@0: * UnicodeString pattern("fox");
michael@0: *
michael@0: * UErrorCode error = U_ZERO_ERROR;
michael@0: * StringSearch iter(pattern, target, Locale::getUS(), NULL, status);
michael@0: * for (int pos = iter.first(error);
michael@0: * pos != USEARCH_DONE;
michael@0: * pos = iter.next(error))
michael@0: * {
michael@0: * printf("Found match at %d pos, length is %d\n", pos,
michael@0: * iter.getMatchLength());
michael@0: * }
michael@0: *