go

[Dictionary.git] / jars / icu4j-4_4_2-src / main / classes / collate / src / com / ibm / icu / text / StringSearch.java

/*\r
 *******************************************************************************\r
 * Copyright (C) 1996-2010, International Business Machines Corporation and    *\r
 * others. All Rights Reserved.                                                *\r
 *******************************************************************************\r
 */\r
\r
package com.ibm.icu.text;\r
\r
import java.text.CharacterIterator;\r
import java.text.StringCharacterIterator;\r
import java.util.Locale;\r
\r
import com.ibm.icu.impl.CharacterIteratorWrapper;\r
import com.ibm.icu.impl.Norm2AllModes;\r
import com.ibm.icu.impl.Normalizer2Impl;\r
import com.ibm.icu.lang.UCharacter;\r
import com.ibm.icu.util.ULocale;\r
\r
/**\r
 * <p>\r
 * <code>StringSearch</code> is the concrete subclass of \r
 * <code>SearchIterator</code> that provides language-sensitive text searching \r
 * based on the comparison rules defined in a {@link RuleBasedCollator} object.\r
 * </p>\r
 * <p>\r
 * <code>StringSearch</code> uses a version of the fast Boyer-Moore search\r
 * algorithm that has been adapted to work with the large character set of\r
 * Unicode. Refer to \r
 * <a href="http://www.icu-project.org/docs/papers/efficient_text_searching_in_java.html">\r
 * "Efficient Text Searching in Java"</a>, published in the \r
 * <i>Java Report</i> on February, 1999, for further information on the \r
 * algorithm.\r
 * </p>\r
 * <p>\r
 * Users are also strongly encouraged to read the section on \r
 * <a href="http://www.icu-project.org/userguide/searchString.html">\r
 * String Search</a> and \r
 * <a href="http://www.icu-project.org/userguide/Collate_Intro.html">\r
 * Collation</a> in the user guide before attempting to use this class.\r
 * </p>\r
 * <p>\r
 * String searching becomes a little complicated when accents are encountered at\r
 * match boundaries. If a match is found and it has preceding or trailing \r
 * accents not part of the match, the result returned will include the \r
 * preceding accents up to the first base character, if the pattern searched \r
 * for starts an accent. Likewise, \r
 * if the pattern ends with an accent, all trailing accents up to the first\r
 * base character will be included in the result.\r
 * </p>\r
 * <p>\r
 * For example, if a match is found in target text "a&#92;u0325&#92;u0300" for \r
 * the pattern\r
 * "a&#92;u0325", the result returned by StringSearch will be the index 0 and\r
 * length 3 &lt;0, 3&gt;. If a match is found in the target \r
 * "a&#92;u0325&#92;u0300" \r
 * for the pattern "&#92;u0300", then the result will be index 1 and length 2 \r
 * <1, 2>.\r
 * </p>\r
 * <p>\r
 * In the case where the decomposition mode is on for the RuleBasedCollator,\r
 * all matches that starts or ends with an accent will have its results include \r
 * preceding or following accents respectively. For example, if pattern "a" is\r
 * looked for in the target text "&aacute;&#92;u0325", the result will be\r
 * index 0 and length 2 &lt;0, 2&gt;.\r
 * </p>\r
 * <p>\r
 * The StringSearch class provides two options to handle accent matching \r
 * described below:\r
 * </p>\r
 * <p>\r
 * Let S' be the sub-string of a text string S between the offsets start and \r
 * end &lt;start, end&gt;.\r
 * <br>\r
 * A pattern string P matches a text string S at the offsets &lt;start, \r
 * length&gt; \r
 * <br>\r
 * if\r
 * <pre> \r
 * option 1. P matches some canonical equivalent string of S'. Suppose the \r
 *           RuleBasedCollator used for searching has a collation strength of \r
 *           TERTIARY, all accents are non-ignorable. If the pattern \r
 *           "a&#92;u0300" is searched in the target text \r
 *           "a&#92;u0325&#92;u0300", \r
 *           a match will be found, since the target text is canonically \r
 *           equivalent to "a&#92;u0300&#92;u0325"\r
 * option 2. P matches S' and if P starts or ends with a combining mark, \r
 *           there exists no non-ignorable combining mark before or after S' \r
 *           in S respectively. Following the example above, the pattern \r
 *           "a&#92;u0300" will not find a match in "a&#92;u0325&#92;u0300", \r
 *           since\r
 *           there exists a non-ignorable accent '&#92;u0325' in the middle of \r
 *           'a' and '&#92;u0300'. Even with a target text of \r
 *           "a&#92;u0300&#92;u0325" a match will not be found because of the \r
 *           non-ignorable trailing accent &#92;u0325.\r
 * </pre>\r
 * Option 2. will be the default mode for dealing with boundary accents unless\r
 * specified via the API setCanonical(boolean).\r
 * One restriction is to be noted for option 1. Currently there are no \r
 * composite characters that consists of a character with combining class > 0 \r
 * before a character with combining class == 0. However, if such a character \r
 * exists in the future, the StringSearch may not work correctly with option 1\r
 * when such characters are encountered.\r
 * </p>\r
 * <p>\r
 * <tt>SearchIterator</tt> provides APIs to specify the starting position \r
 * within the text string to be searched, e.g. <tt>setIndex</tt>,\r
 * <tt>preceding</tt> and <tt>following</tt>. Since the starting position will \r
 * be set as it is specified, please take note that there are some dangerous \r
 * positions which the search may render incorrect results:\r
 * <ul>\r
 * <li> The midst of a substring that requires decomposition.\r
 * <li> If the following match is to be found, the position should not be the\r
 *      second character which requires to be swapped with the preceding \r
 *      character. Vice versa, if the preceding match is to be found, \r
 *      position to search from should not be the first character which \r
 *      requires to be swapped with the next character. E.g certain Thai and\r
 *      Lao characters require swapping.\r
 * <li> If a following pattern match is to be found, any position within a \r
 *      contracting sequence except the first will fail. Vice versa if a \r
 *      preceding pattern match is to be found, a invalid starting point \r
 *      would be any character within a contracting sequence except the last.\r
 * </ul>\r
 * </p>\r
 * <p>\r
 * Though collator attributes will be taken into consideration while \r
 * performing matches, there are no APIs provided in StringSearch for setting \r
 * and getting the attributes. These attributes can be set by getting the \r
 * collator from <tt>getCollator</tt> and using the APIs in \r
 * <tt>com.ibm.icu.text.Collator</tt>. To update StringSearch to the new \r
 * collator attributes, <tt>reset()</tt> or \r
 * <tt>setCollator(RuleBasedCollator)</tt> has to be called.\r
 * </p>\r
 * <p>\r
 * Consult the \r
 * <a href="http://www.icu-project.org/userguide/searchString.html">\r
 * String Search</a> user guide and the <code>SearchIterator</code> \r
 * documentation for more information and examples of use.\r
 * </p>\r
 * <p>\r
 * This class is not subclassable\r
 * </p>\r
 * @see SearchIterator\r
 * @see RuleBasedCollator\r
 * @author Laura Werner, synwee\r
 * @stable ICU 2.0\r
 */\r
// internal notes: all methods do not guarantee the correct status of the \r
// characteriterator. the caller has to maintain the original index position\r
// if necessary. methods could change the index position as it deems fit\r
public final class StringSearch extends SearchIterator\r
{\r
    \r
    // public constructors --------------------------------------------------\r
    \r
    /**\r
     * Initializes the iterator to use the language-specific rules defined in \r
     * the argument collator to search for argument pattern in the argument \r
     * target text. The argument breakiter is used to define logical matches.\r
     * See super class documentation for more details on the use of the target \r
     * text and BreakIterator.\r
     * @param pattern text to look for.\r
     * @param target target text to search for pattern. \r
     * @param collator RuleBasedCollator that defines the language rules\r
     * @param breakiter A {@link BreakIterator} that is used to determine the \r
     *                boundaries of a logical match. This argument can be null.\r
     * @exception IllegalArgumentException thrown when argument target is null,\r
     *            or of length 0\r
     * @see BreakIterator\r
     * @see RuleBasedCollator\r
     * @see SearchIterator\r
     * @stable ICU 2.0\r
     */\r
    public StringSearch(String pattern, CharacterIterator target,\r
                        RuleBasedCollator collator, BreakIterator breakiter) \r
    {\r
        super(target, breakiter);\r
        m_textBeginOffset_ = targetText.getBeginIndex();\r
        m_textLimitOffset_ = targetText.getEndIndex();\r
        m_collator_ = collator;\r
        m_colEIter_ = m_collator_.getCollationElementIterator(target);\r
        m_utilColEIter_ = collator.getCollationElementIterator("");\r
        m_ceMask_ = getMask(m_collator_.getStrength());\r
        m_isCanonicalMatch_ = false;\r
        m_pattern_ = new Pattern(pattern);\r
        m_matchedIndex_ = DONE;\r
        m_charBreakIter_ = BreakIterator.getCharacterInstance(/*m_collator_.getLocale(ULocale.ACTUAL_LOCALE)*/);\r
        m_charBreakIter_.setText(target);\r
        initialize();\r
    }\r
\r
    /**\r
     * Initializes the iterator to use the language-specific rules defined in \r
     * the argument collator to search for argument pattern in the argument \r
     * target text. No BreakIterators are set to test for logical matches.\r
     * @param pattern text to look for.\r
     * @param target target text to search for pattern. \r
     * @param collator RuleBasedCollator that defines the language rules\r
     * @exception IllegalArgumentException thrown when argument target is null,\r
     *            or of length 0\r
     * @see RuleBasedCollator\r
     * @see SearchIterator\r
     * @stable ICU 2.0\r
     */\r
    public StringSearch(String pattern, CharacterIterator target,\r
                        RuleBasedCollator collator) \r
    {\r
        this(pattern, target, collator, null/*BreakIterator.getCharacterInstance()*/);\r
    }\r
\r
    /**\r
     * Initializes the iterator to use the language-specific rules and \r
     * break iterator rules defined in the argument locale to search for \r
     * argument pattern in the argument target text. \r
     * See super class documentation for more details on the use of the target \r
     * text and BreakIterator.\r
     * @param pattern text to look for.\r
     * @param target target text to search for pattern. \r
     * @param locale locale to use for language and break iterator rules\r
     * @exception IllegalArgumentException thrown when argument target is null,\r
     *            or of length 0. ClassCastException thrown if the collator for \r
     *            the specified locale is not a RuleBasedCollator.\r
     * @see BreakIterator\r
     * @see RuleBasedCollator\r
     * @see SearchIterator\r
     * @stable ICU 2.0\r
     */\r
    public StringSearch(String pattern, CharacterIterator target, Locale locale)\r
    {\r
        this(pattern, target, ULocale.forLocale(locale));\r
    }\r
\r
    /**\r
     * Initializes the iterator to use the language-specific rules and \r
     * break iterator rules defined in the argument locale to search for \r
     * argument pattern in the argument target text. \r
     * See super class documentation for more details on the use of the target \r
     * text and BreakIterator.\r
     * @param pattern text to look for.\r
     * @param target target text to search for pattern. \r
     * @param locale ulocale to use for language and break iterator rules\r
     * @exception IllegalArgumentException thrown when argument target is null,\r
     *            or of length 0. ClassCastException thrown if the collator for \r
     *            the specified locale is not a RuleBasedCollator.\r
     * @see BreakIterator\r
     * @see RuleBasedCollator\r
     * @see SearchIterator\r
     * @stable ICU 3.2\r
     */\r
    public StringSearch(String pattern, CharacterIterator target, ULocale locale)\r
    {\r
        this(pattern, target, (RuleBasedCollator)Collator.getInstance(locale),\r
             null/*BreakIterator.getCharacterInstance(locale)*/);\r
    }\r
\r
    /**\r
     * Initializes the iterator to use the language-specific rules and \r
     * break iterator rules defined in the default locale to search for \r
     * argument pattern in the argument target text. \r
     * See super class documentation for more details on the use of the target \r
     * text and BreakIterator.\r
     * @param pattern text to look for.\r
     * @param target target text to search for pattern. \r
     * @exception IllegalArgumentException thrown when argument target is null,\r
     *            or of length 0. ClassCastException thrown if the collator for \r
     *            the default locale is not a RuleBasedCollator.\r
     * @see BreakIterator\r
     * @see RuleBasedCollator\r
     * @see SearchIterator\r
     * @stable ICU 2.0\r
     */\r
    public StringSearch(String pattern, String target) \r
    {\r
        this(pattern, new StringCharacterIterator(target),\r
             (RuleBasedCollator)Collator.getInstance(),\r
             null/*BreakIterator.getCharacterInstance()*/);\r
    }\r
\r
    // public getters -----------------------------------------------------\r
    \r
    /**\r
     * <p>\r
     * Gets the RuleBasedCollator used for the language rules.\r
     * </p>\r
     * <p>\r
     * Since StringSearch depends on the returned RuleBasedCollator, any \r
     * changes to the RuleBasedCollator result should follow with a call to \r
     * either StringSearch.reset() or \r
     * StringSearch.setCollator(RuleBasedCollator) to ensure the correct \r
     * search behaviour.\r
     * </p>\r
     * @return RuleBasedCollator used by this StringSearch\r
     * @see RuleBasedCollator\r
     * @see #setCollator\r
     * @stable ICU 2.0\r
     */\r
    public RuleBasedCollator getCollator() \r
    {\r
        return m_collator_;\r
    }\r
    \r
    /**\r
     * Returns the pattern for which StringSearch is searching for.\r
     * @return the pattern searched for\r
     * @stable ICU 2.0\r
     */\r
    public String getPattern() \r
    {\r
        return m_pattern_.targetText;\r
    }\r
    \r
    /**\r
     * Return the index in the target text where the iterator is currently \r
     * positioned at. \r
     * If the iteration has gone past the end of the target text or past \r
     * the beginning for a backwards search, {@link #DONE} is returned.\r
     * @return index in the target text where the iterator is currently \r
     *         positioned at\r
     * @stable ICU 2.8\r
     */\r
    public int getIndex() \r
    {\r
        int result = m_colEIter_.getOffset();\r
        if (isOutOfBounds(m_textBeginOffset_, m_textLimitOffset_, result)) {\r
            return DONE;\r
        }\r
        return result;\r
    }\r
    \r
    /**\r
     * Determines whether canonical matches (option 1, as described in the \r
     * class documentation) is set.\r
     * See setCanonical(boolean) for more information.\r
     * @see #setCanonical\r
     * @return true if canonical matches is set, false otherwise\r
     * @stable ICU 2.8\r
     */\r
    public boolean isCanonical() \r
    {\r
        return m_isCanonicalMatch_;\r
    }\r
    \r
    // public setters -----------------------------------------------------\r
    \r
    /**\r
     * <p>\r
     * Sets the RuleBasedCollator to be used for language-specific searching.\r
     * </p>\r
     * <p>\r
     * This method causes internal data such as Boyer-Moore shift tables\r
     * to be recalculated, but the iterator's position is unchanged.\r
     * </p>\r
     * @param collator to use for this StringSearch\r
     * @exception IllegalArgumentException thrown when collator is null\r
     * @see #getCollator\r
     * @stable ICU 2.0\r
     */\r
    public void setCollator(RuleBasedCollator collator) \r
    {\r
        if (collator == null) {\r
            throw new IllegalArgumentException("Collator can not be null");\r
        }\r
        m_collator_ = collator;\r
        m_ceMask_ = getMask(m_collator_.getStrength());\r
        // if status is a failure, ucol_getAttribute returns UCOL_DEFAULT\r
        initialize();\r
        m_colEIter_.setCollator(m_collator_);\r
        m_utilColEIter_.setCollator(m_collator_);\r
        m_charBreakIter_ = BreakIterator.getCharacterInstance(/*collator.getLocale(ULocale.VALID_LOCALE)*/);\r
        m_charBreakIter_.setText(targetText);\r
    }\r
    \r
    /**\r
     * <p>\r
     * Set the pattern to search for.  \r
     * </p>\r
     * <p>\r
     * This method causes internal data such as Boyer-Moore shift tables\r
     * to be recalculated, but the iterator's position is unchanged.\r
     * </p>\r
     * @param pattern for searching\r
     * @see #getPattern\r
     * @exception IllegalArgumentException thrown if pattern is null or of\r
     *               length 0\r
     * @stable ICU 2.0\r
     */\r
    public void setPattern(String pattern) \r
    {\r
        if (pattern == null || pattern.length() <= 0) {\r
            throw new IllegalArgumentException(\r
                    "Pattern to search for can not be null or of length 0");\r
        }\r
        m_pattern_.targetText = pattern;\r
        initialize();\r
    }\r
    \r
    /**\r
      * Set the target text to be searched. Text iteration will hence begin at \r
     * the start of the text string. This method is useful if you want to \r
     * re-use an iterator to search within a different body of text.\r
     * @param text new text iterator to look for match, \r
     * @exception IllegalArgumentException thrown when text is null or has\r
     *            0 length\r
     * @see #getTarget\r
     * @stable ICU 2.8\r
     */\r
    public void setTarget(CharacterIterator text)\r
    {\r
        super.setTarget(text);\r
        m_textBeginOffset_ = targetText.getBeginIndex();\r
        m_textLimitOffset_ = targetText.getEndIndex();\r
        m_colEIter_.setText(targetText);\r
        m_charBreakIter_.setText(targetText);\r
    }\r
    \r
    /**\r
     * <p>\r
     * Sets the position in the target text which the next search will start \r
     * from to the argument. This method clears all previous states.\r
     * </p>\r
     * <p>\r
     * This method takes the argument position and sets the position in the \r
     * target text accordingly, without checking if position is pointing to a \r
     * valid starting point to begin searching.\r
     * </p>\r
     * <p>\r
     * Search positions that may render incorrect results are highlighted in \r
     * the class documentation.\r
     * </p>\r
     * @param position index to start next search from.\r
     * @exception IndexOutOfBoundsException thrown if argument position is out\r
     *            of the target text range.\r
     * @see #getIndex\r
     * @stable ICU 2.8\r
     */\r
    public void setIndex(int position)\r
    {\r
        super.setIndex(position);\r
        m_matchedIndex_ = DONE;\r
        m_colEIter_.setExactOffset(position);\r
    }\r
    \r
    /**\r
     * <p>\r
     * Set the canonical match mode. See class documentation for details.\r
     * The default setting for this property is false.\r
     * </p>\r
     * @param allowCanonical flag indicator if canonical matches are allowed\r
     * @see #isCanonical\r
     * @stable ICU 2.8\r
     */\r
    public void setCanonical(boolean allowCanonical)\r
    {\r
        m_isCanonicalMatch_ = allowCanonical;\r
        if (m_isCanonicalMatch_ == true) {\r
            if (m_canonicalPrefixAccents_ == null) {\r
                m_canonicalPrefixAccents_ = new StringBuilder();\r
            }\r
            else {\r
                m_canonicalPrefixAccents_.delete(0, \r
                                            m_canonicalPrefixAccents_.length());\r
            }\r
            if (m_canonicalSuffixAccents_ == null) {\r
                m_canonicalSuffixAccents_ = new StringBuilder();\r
            }\r
            else {\r
                m_canonicalSuffixAccents_.delete(0, \r
                                            m_canonicalSuffixAccents_.length());\r
            }\r
        }\r
    }\r
    \r
    // public miscellaneous methods -----------------------------------------\r
    \r
    /** \r
     * <p>\r
     * Resets the search iteration. All properties will be reset to the \r
     * default value.\r
     * </p>\r
     * <p>\r
     * Search will begin at the start of the target text if a forward iteration \r
     * is initiated before a backwards iteration. Otherwise if a \r
     * backwards iteration is initiated before a forwards iteration, the search \r
     * will begin at the end of the target text.\r
     * </p>\r
     * <p>\r
     * Canonical match option will be reset to false, ie an exact match.\r
     * </p>\r
     * @stable ICU 2.8\r
     */\r
    public void reset()\r
    {\r
        // reset is setting the attributes that are already in string search, \r
        // hence all attributes in the collator should be retrieved without any \r
        // problems\r
        super.reset();\r
        m_isCanonicalMatch_ = false;\r
        m_ceMask_ = getMask(m_collator_.getStrength());\r
        // if status is a failure, ucol_getAttribute returns UCOL_DEFAULT\r
        initialize();\r
        m_colEIter_.setCollator(m_collator_);\r
        m_colEIter_.reset();\r
        m_utilColEIter_.setCollator(m_collator_);\r
    }\r
\r
    // protected methods -----------------------------------------------------\r
    \r
    /**\r
     * <p>\r
     * Concrete method to provide the mechanism \r
     * for finding the next <b>forwards</b> match in the target text.\r
     * See super class documentation for its use.\r
     * </p>  \r
     * @param start index in the target text at which the forwards search \r
     *        should begin.\r
     * @return the starting index of the next forwards match if found, DONE \r
     *         otherwise\r
     * @see #handlePrevious(int)\r
     * @see #DONE\r
     * @stable ICU 2.8\r
     */\r
    protected int handleNext(int start)\r
    {\r
        if (m_pattern_.m_CELength_ == 0) {\r
            matchLength = 0;\r
            if (m_matchedIndex_ == DONE && start == m_textBeginOffset_) {\r
                m_matchedIndex_ = start;\r
                return m_matchedIndex_;\r
            }\r
            \r
            targetText.setIndex(start);\r
            char ch = targetText.current();\r
            // ch can never be done, it is handled by next()\r
            char ch2 = targetText.next();\r
            if (ch2 == CharacterIterator.DONE) {\r
                m_matchedIndex_ = DONE;    \r
            }\r
            else {\r
                m_matchedIndex_ = targetText.getIndex();\r
            }\r
            if (UTF16.isLeadSurrogate(ch) && UTF16.isTrailSurrogate(ch2)) {\r
                targetText.next();\r
                m_matchedIndex_ = targetText.getIndex();\r
            }\r
        }\r
        else {\r
            if (matchLength <= 0) {\r
                // we must have reversed direction after we reached the start\r
                // of the target text\r
                // see SearchIterator next(), it checks the bounds and returns\r
                // if it exceeds the range. It does not allow setting of\r
                // m_matchedIndex\r
                if (start == m_textBeginOffset_) {\r
                    m_matchedIndex_ = DONE;\r
                }\r
                else {\r
                    // for boundary check purposes. this will ensure that the\r
                    // next match will not preceed the current offset\r
                    // note search->matchedIndex will always be set to something\r
                    // in the code\r
                    m_matchedIndex_ = start - 1;\r
                }\r
            }\r
    \r
            // status checked below\r
            if (m_isCanonicalMatch_) {\r
                // can't use exact here since extra accents are allowed.\r
                handleNextCanonical(start);\r
            }\r
            else {\r
                handleNextExact(start);\r
            }\r
        }\r
        if (m_matchedIndex_ == DONE) {\r
            targetText.setIndex(m_textLimitOffset_);\r
        }\r
        else {\r
            targetText.setIndex(m_matchedIndex_);\r
        }\r
        return m_matchedIndex_;\r
    }\r
    \r
    /**\r
     * <p>\r
     * Concrete method to provide the mechanism \r
     * for finding the next <b>backwards</b> match in the target text.\r
     * See super class documentation for its use.\r
     * </p>  \r
     * @param start index in the target text at which the backwards search \r
     *        should begin.\r
     * @return the starting index of the next backwards match if found, DONE \r
     *         otherwise\r
     * @see #handleNext(int)\r
     * @see #DONE\r
     * @stable ICU 2.8\r
     */\r
    protected int handlePrevious(int start)\r
    {\r
        if (m_pattern_.m_CELength_ == 0) {\r
            matchLength = 0;\r
            // start can never be DONE or 0, it is handled in previous\r
            targetText.setIndex(start);\r
            char ch = targetText.previous();\r
            if (ch == CharacterIterator.DONE) {\r
                m_matchedIndex_ = DONE;\r
            }\r
            else {\r
                m_matchedIndex_ = targetText.getIndex();\r
                if (UTF16.isTrailSurrogate(ch)) {\r
                    if (UTF16.isLeadSurrogate(targetText.previous())) {\r
                        m_matchedIndex_ = targetText.getIndex();\r
                    }\r
                }\r
            }            \r
        }\r
        else {\r
            if (matchLength == 0) {\r
                // we must have reversed direction after we reached the end\r
                // of the target text\r
                // see SearchIterator next(), it checks the bounds and returns\r
                // if it exceeds the range. It does not allow setting of\r
                // m_matchedIndex\r
                m_matchedIndex_ = DONE;\r
            }\r
            if (m_isCanonicalMatch_) {\r
                // can't use exact here since extra accents are allowed.\r
                handlePreviousCanonical(start);\r
            }\r
            else {\r
                handlePreviousExact(start);\r
            }\r
        }\r
\r
        if (m_matchedIndex_ == DONE) {\r
            targetText.setIndex(m_textBeginOffset_);\r
        }\r
        else {\r
            targetText.setIndex(m_matchedIndex_);\r
        }\r
        return m_matchedIndex_;\r
    }\r
\r
    // private static inner classes ----------------------------------------\r
    \r
    private static class Pattern \r
    {\r
        // protected methods -----------------------------------------------\r
        \r
        /**\r
         * Pattern string\r
         */\r
        protected String targetText;\r
        /**\r
         * Array containing the collation elements of targetText\r
         */\r
        protected int m_CE_[];\r
        /**\r
         * Number of collation elements in m_CE_\r
         */\r
        protected int m_CELength_; \r
        /**\r
         * Flag indicator if targetText starts with an accent\r
         */\r
        protected boolean m_hasPrefixAccents_;\r
        /**\r
         * Flag indicator if targetText ends with an accent\r
         */\r
        protected boolean m_hasSuffixAccents_;\r
        /**\r
         * Default number of characters to shift for Boyer Moore\r
         */\r
        protected int m_defaultShiftSize_;\r
        /**\r
         * Number of characters to shift for Boyer Moore, depending on the\r
         * source text to search\r
         */\r
        protected char m_shift_[];\r
        /**\r
         * Number of characters to shift backwards for Boyer Moore, depending \r
         * on the source text to search\r
         */\r
        protected char m_backShift_[];\r
        \r
        // protected constructors ------------------------------------------\r
        \r
        /**\r
         * Empty constructor \r
         */\r
        protected Pattern(String pattern) \r
        {\r
            targetText = pattern;\r
            m_CE_ = new int[INITIAL_ARRAY_SIZE_];    \r
            m_CELength_ = 0;\r
            m_hasPrefixAccents_ = false;\r
            m_hasSuffixAccents_ = false;\r
            m_defaultShiftSize_ = 1;        \r
            m_shift_ = new char[MAX_TABLE_SIZE_];\r
            m_backShift_ = new char[MAX_TABLE_SIZE_];\r
        }\r
    }\r
\r
\r
    // private data members ------------------------------------------------\r
    \r
    /**\r
     * target text begin offset. Each targetText has a valid contiguous region \r
     * to iterate and this data member is the offset to the first such\r
     * character in the region.\r
     */\r
    private int m_textBeginOffset_;\r
    /**\r
     * target text limit offset. Each targetText has a valid contiguous region \r
     * to iterate and this data member is the offset to 1 after the last such\r
     * character in the region.\r
     */\r
    private int m_textLimitOffset_;\r
    /**\r
     * Upon completion of a search, m_matchIndex_ will store starting offset in\r
     * m_text for the match. The Value DONE is the default value. \r
     * If we are not at the start of the text or the end of the text and \r
     * m_matchedIndex_ is DONE it means that we can find any more matches in \r
     * that particular direction\r
     */\r
    private int m_matchedIndex_; \r
    /**\r
     * Current pattern to search for\r
     */\r
    private Pattern m_pattern_;\r
    /**\r
     * Collator whose rules are used to perform the search\r
     */\r
    private RuleBasedCollator m_collator_;\r
    /** \r
     * The collation element iterator for the text source.\r
     */\r
    private CollationElementIterator m_colEIter_;\r
    /** \r
     * Utility collation element, used throughout program for temporary \r
     * iteration.\r
     */\r
    private CollationElementIterator m_utilColEIter_;\r
    /**\r
     * The mask used on the collation elements to retrieve the valid strength\r
     * weight \r
     */\r
    private int m_ceMask_;\r
    /**\r
     * Buffer storing accents during a canonical search\r
     */\r
    private StringBuilder m_canonicalPrefixAccents_;\r
    /**\r
     * Buffer storing accents during a canonical search\r
     */\r
    private StringBuilder m_canonicalSuffixAccents_;\r
    /**\r
     * Flag to indicate if canonical search is to be done.\r
     * E.g looking for "a\u0300" in "a\u0318\u0300" will yield the match at 0.\r
     */\r
    private boolean m_isCanonicalMatch_;\r
    /**\r
     * Character break iterator for boundary checking.\r
     */\r
    private BreakIterator m_charBreakIter_;\r
    private final Normalizer2Impl m_nfcImpl_ = Norm2AllModes.getNFCInstance().impl;\r
    /**\r
     * Size of the shift tables\r
     */\r
    private static final int MAX_TABLE_SIZE_ = 257; \r
    /**\r
     * Initial array size\r
     */\r
    private static final int INITIAL_ARRAY_SIZE_ = 256;\r
    /**\r
     * Utility mask\r
     */\r
    private static final int SECOND_LAST_BYTE_SHIFT_ = 8;\r
    /**\r
     * Utility mask\r
     */\r
    private static final int LAST_BYTE_MASK_ = 0xff;\r
    /**\r
     * Utility buffer for return values and temporary storage\r
     */\r
    private int m_utilBuffer_[] = new int[2];\r
    /**\r
     *  Unsigned 32-Bit Integer Mask\r
     */\r
    private static final long UNSIGNED_32BIT_MASK = 0xffffffffL;\r
\r
    // private methods -------------------------------------------------------\r
\r
    /**\r
     * Hash a collation element from its full size (32 bits) down into a\r
     * value that can be used as an index into the shift tables.  Right\r
     * now we do a modulus by the size of the hash table.\r
     * @param ce collation element\r
     * @return collapsed version of the collation element\r
     */\r
    private static final int hash(int ce) \r
    {\r
        // the old value UCOL_PRIMARYORDER(ce) % MAX_TABLE_SIZE_ does not work\r
        // well with the new collation where most of the latin 1 characters\r
        // are of the value xx000xxx. their hashes will most of the time be 0\r
        // to be discussed on the hash algo.\r
        return CollationElementIterator.primaryOrder(ce) % MAX_TABLE_SIZE_;\r
    }\r
\r
    private final char getFCD(int c) {\r
        return (char)m_nfcImpl_.getFCD16(c);\r
    }\r
    /**\r
     * Gets the fcd value for a character at the argument index.\r
     * This method takes into accounts of the supplementary characters.\r
     * Note this method changes the offset in the character iterator.\r
     * @param str UTF16 string where character for fcd retrieval resides\r
     * @param offset position of the character whose fcd is to be retrieved\r
     * @return fcd value\r
     */\r
    private final char getFCD(CharacterIterator str, int offset)\r
    {\r
        char ch = str.setIndex(offset);\r
        int result = m_nfcImpl_.getFCD16FromSingleLead(ch);\r
        if (result != 0 && Character.isHighSurrogate(ch)) {\r
            char c2 = str.next();\r
            if (Character.isLowSurrogate(c2)) {\r
                result = m_nfcImpl_.getFCD16(Character.toCodePoint(ch, c2));\r
            } else {\r
                result = 0;\r
            }\r
        }\r
        return (char)result;\r
    }\r
    /**\r
     * Gets the FCD value for the code point before the input offset.\r
     * Modifies the iterator's index.\r
     * @param iter text iterator\r
     * @param offset index after the character to test\r
     * @return FCD value for the character before offset\r
     */\r
    private final int getFCDBefore(CharacterIterator iter, int offset) {\r
        int result;\r
        iter.setIndex(offset);\r
        char c = iter.previous();\r
        if (UTF16.isSurrogate(c)) {\r
            if (Normalizer2Impl.UTF16Plus.isSurrogateLead(c)) {\r
                result = 0;\r
            } else {\r
                char lead = iter.previous();\r
                if (Character.isHighSurrogate(lead)) {\r
                    result = m_nfcImpl_.getFCD16(Character.toCodePoint(lead, c));\r
                } else {\r
                    result = 0;\r
                }\r
            }\r
        } else {\r
            result = m_nfcImpl_.getFCD16FromSingleLead(c);\r
        }\r
        return result;\r
    }\r
    /**\r
     * Gets the fcd value for a character at the argument index.\r
     * This method takes into accounts of the supplementary characters.\r
     * @param str UTF16 string where character for fcd retrieval resides\r
     * @param offset position of the character whose fcd is to be retrieved\r
     * @return fcd value\r
     */\r
    private final char getFCD(String str, int offset)\r
    {\r
        char ch = str.charAt(offset);\r
        int result = m_nfcImpl_.getFCD16FromSingleLead(ch);\r
        if (result != 0 && Character.isHighSurrogate(ch)) {\r
            char c2;\r
            if (++offset < str.length() && Character.isLowSurrogate(c2 = str.charAt(offset))) {\r
                result = m_nfcImpl_.getFCD16(Character.toCodePoint(ch, c2));\r
            } else {\r
                result = 0;\r
            }\r
        }\r
        return (char)result;\r
    }\r
\r
    /**\r
    * Getting the modified collation elements taking into account the collation \r
    * attributes\r
    * @param ce \r
    * @return the modified collation element\r
    */\r
    private final int getCE(int ce)\r
    {\r
        // note for tertiary we can't use the collator->tertiaryMask, that\r
        // is a preprocessed mask that takes into account case options. since\r
        // we are only concerned with exact matches, we don't need that.\r
        ce &= m_ceMask_;\r
        \r
        if (m_collator_.isAlternateHandlingShifted()) {\r
            // alternate handling here, since only the 16 most significant \r
            // digits is only used, we can safely do a compare without masking\r
            // if the ce is a variable, we mask and get only the primary values\r
            // no shifting to quartenary is required since all primary values\r
            // less than variabletop will need to be masked off anyway.\r
            if (((m_collator_.m_variableTopValue_  << 16) & UNSIGNED_32BIT_MASK) > (ce & UNSIGNED_32BIT_MASK)) {\r
                if (m_collator_.getStrength() == Collator.QUATERNARY) {\r
                    ce = CollationElementIterator.primaryOrder(ce);\r
                }\r
                else { \r
                    ce = CollationElementIterator.IGNORABLE;\r
                }\r
            }\r
        }\r
    \r
        return ce;\r
    }\r
    \r
    /**\r
     * Appends a int to a int array, increasing the size of the array when \r
     * we are out of space.\r
     * @param offset in array to append to\r
     * @param value to append\r
     * @param array to append to\r
     * @return the array appended to, this could be a new and bigger array\r
     */\r
    private static final int[] append(int offset, int value, int array[])\r
    {\r
        if (offset >= array.length) {\r
            int temp[] = new int[offset + INITIAL_ARRAY_SIZE_];\r
            System.arraycopy(array, 0, temp, 0, array.length);\r
            array = temp;\r
        }\r
        array[offset] = value;\r
        return array;\r
    }\r
    \r
    /**\r
     * Initializing the ce table for a pattern. Stores non-ignorable collation \r
     * keys. Table size will be estimated by the size of the pattern text. \r
     * Table expansion will be perform as we go along. Adding 1 to ensure that \r
     * the table size definitely increases.\r
     * Internal method, status assumed to be a success.\r
     * @return total number of expansions \r
     */\r
    private final int initializePatternCETable()\r
    {\r
        m_utilColEIter_.setText(m_pattern_.targetText);\r
        \r
        int offset = 0;\r
        int result = 0;\r
        int ce = m_utilColEIter_.next();\r
    \r
        while (ce != CollationElementIterator.NULLORDER) {\r
            int newce = getCE(ce);\r
            if (newce != CollationElementIterator.IGNORABLE) {\r
                m_pattern_.m_CE_ = append(offset, newce, m_pattern_.m_CE_);\r
                offset ++;            \r
            }\r
            result += m_utilColEIter_.getMaxExpansion(ce) - 1;\r
            ce = m_utilColEIter_.next();\r
        }\r
    \r
        m_pattern_.m_CE_ = append(offset, 0, m_pattern_.m_CE_);\r
        m_pattern_.m_CELength_ = offset;\r
    \r
        return result;\r
    }\r
    \r
    /**\r
     * Initializes the pattern struct.\r
     * Internal method, status assumed to be success.\r
     * @return expansionsize the total expansion size of the pattern\r
     */ \r
    private final int initializePattern()\r
    {\r
        if (m_collator_.getStrength() == Collator.PRIMARY) {\r
            m_pattern_.m_hasPrefixAccents_ = false;\r
            m_pattern_.m_hasSuffixAccents_ = false;\r
        } else {\r
            m_pattern_.m_hasPrefixAccents_ = (getFCD(m_pattern_.targetText, 0) \r
                                                 >> SECOND_LAST_BYTE_SHIFT_) != 0;\r
            m_pattern_.m_hasSuffixAccents_ = (getFCD(m_pattern_.targetText.codePointBefore(\r
                                                        m_pattern_.targetText.length()))\r
                                                & LAST_BYTE_MASK_) != 0;\r
        }\r
        // since intializePattern is an internal method status is a success.\r
        return initializePatternCETable();   \r
    }\r
    \r
    /**\r
     * Initializing shift tables, with the default values.\r
     * If a corresponding default value is 0, the shift table is not set.\r
     * @param shift table for forwards shift \r
     * @param backshift table for backwards shift\r
     * @param cetable table containing pattern ce\r
     * @param cesize size of the pattern ces\r
     * @param expansionsize total size of the expansions\r
     * @param defaultforward the default forward value\r
     * @param defaultbackward the default backward value\r
     */\r
     private final void setShiftTable(char shift[], \r
                                                    char backshift[], \r
                                                    int cetable[], int cesize, \r
                                                      int expansionsize,\r
                                                    char defaultforward,\r
                                                      char defaultbackward)\r
    {\r
        // estimate the value to shift. to do that we estimate the smallest \r
        // number of characters to give the relevant ces, ie approximately\r
        // the number of ces minus their expansion, since expansions can come \r
        // from a character.\r
        for (int count = 0; count < MAX_TABLE_SIZE_; count ++) {\r
            shift[count] = defaultforward;\r
        }\r
        cesize --; // down to the last index\r
        for (int count = 0; count < cesize; count ++) {\r
            // number of ces from right of array to the count\r
            int temp = defaultforward - count - 1;\r
            shift[hash(cetable[count])] = temp > 1 ? ((char)temp) : 1;\r
        }\r
        shift[hash(cetable[cesize])] = 1;\r
        // for ignorables we just shift by one. see test examples.\r
        shift[hash(0)] = 1;\r
        \r
        for (int count = 0; count < MAX_TABLE_SIZE_; count ++) {\r
            backshift[count] = defaultbackward;\r
        }\r
        for (int count = cesize; count > 0; count --) {\r
            // the original value count does not seem to work\r
            backshift[hash(cetable[count])] = (char)(count > expansionsize ? \r
                                                      count - expansionsize : 1);\r
        }\r
        backshift[hash(cetable[0])] = 1;\r
        backshift[hash(0)] = 1;\r
    }\r
    \r
    /**\r
     * <p>Building of the pattern collation element list and the Boyer Moore \r
     * StringSearch table.</p>\r
     * <p>The canonical match will only be performed after the default match \r
     * fails.</p>\r
     * <p>For both cases we need to remember the size of the composed and \r
     * decomposed versions of the string. Since the Boyer-Moore shift \r
     * calculations shifts by a number of characters in the text and tries to \r
     * match the pattern from that offset, the shift value can not be too large \r
     * in case we miss some characters. To choose a right shift size, we \r
     * estimate the NFC form of the and use its size as a shift guide. The NFC \r
     * form should be the small possible representation of the pattern. Anyways, \r
     * we'll err on the smaller shift size. Hence the calculation for \r
     * minlength. Canonical match will be performed slightly differently. We'll \r
     * split the pattern into 3 parts, the prefix accents (PA), the middle \r
     * string bounded by the first and last base character (MS), the ending \r
     * accents (EA). Matches will be done on MS first, and only when we match \r
     * MS then some processing will be required for the prefix and end accents \r
     * in order to determine if they match PA and EA. Hence the default shift \r
     * values for the canonical match will take the size of either end's accent \r
     * into consideration. Forwards search will take the end accents into \r
     * consideration for the default shift values and the backwards search will \r
     * take the prefix accents into consideration.</p>\r
     * <p>If pattern has no non-ignorable ce, we return a illegal argument \r
     * error.</p>\r
     */ \r
    private final void initialize()\r
    {\r
        int expandlength  = initializePattern();   \r
        if (m_pattern_.m_CELength_ > 0) {\r
            char minlength = (char)(m_pattern_.m_CELength_ > expandlength \r
                                ? m_pattern_.m_CELength_ - expandlength : 1);\r
            m_pattern_.m_defaultShiftSize_ = minlength;\r
            setShiftTable(m_pattern_.m_shift_, m_pattern_.m_backShift_, \r
                          m_pattern_.m_CE_, m_pattern_.m_CELength_, \r
                          expandlength, minlength, minlength);\r
        }\r
        else {\r
            m_pattern_.m_defaultShiftSize_ = 0;\r
        }\r
    }\r
    \r
    /**\r
     * Determine whether the search text bounded by the offset start and end is \r
     * one or more whole units of text as determined by the breakiterator in \r
     * StringSearch.\r
     * @param start target text start offset\r
     * @param end target text end offset\r
     */\r
    private final boolean isBreakUnit(int start, int end) \r
    {\r
        if (breakIterator != null) {\r
            int startindex = breakIterator.first();\r
            int endindex   = breakIterator.last();\r
            \r
            // out-of-range indexes are never boundary positions\r
            if (start < startindex || start > endindex || end < startindex \r
                || end > endindex) {\r
                return false;\r
            }\r
            // otherwise, we can use following() on the position before the \r
            // specified one and return true of the position we get back is the \r
            // one the user specified\r
            boolean result = (start == startindex \r
                              || breakIterator.following(start - 1) == start) \r
                             && (end == endindex \r
                                  || breakIterator.following(end - 1) == end);\r
            if (result) {\r
                // iterates the individual ces\r
                m_utilColEIter_.setText(\r
                    new CharacterIteratorWrapper(targetText), start);\r
                for (int count = 0; count < m_pattern_.m_CELength_;\r
                     count ++) {\r
                    int ce = getCE(m_utilColEIter_.next());\r
                    if (ce == CollationElementIterator.IGNORABLE) {\r
                        count --;\r
                        continue;\r
                    }\r
                    if (ce != m_pattern_.m_CE_[count]) {\r
                        return false;\r
                    }\r
                }\r
                int nextce = m_utilColEIter_.next();\r
                while (m_utilColEIter_.getOffset() == end \r
                       && getCE(nextce) == CollationElementIterator.IGNORABLE) {\r
                    nextce = m_utilColEIter_.next();       \r
                }\r
                if (nextce != CollationElementIterator.NULLORDER \r
                    && m_utilColEIter_.getOffset() == end) {\r
                    // extra collation elements at the end of the match\r
                    return false;\r
                }\r
            }\r
            return result;\r
        }\r
        return true;\r
    }\r
\r
    /**\r
     * Getting the next base character offset if current offset is an accent, \r
     * or the current offset if the current character contains a base character. \r
     * accents the following base character will be returned\r
     * @param text string\r
     * @param textoffset current offset\r
     * @param textlength length of text string\r
     * @return the next base character or the current offset\r
     *         if the current character is contains a base character.\r
     */\r
    private final int getNextBaseOffset(CharacterIterator text, int textoffset)\r
    {\r
        if (textoffset >= text.getEndIndex()) {\r
            return textoffset;\r
        }\r
        // iteration ends with reading CharacterIterator.DONE which has fcd==0\r
        char c = text.setIndex(textoffset);\r
        for (;;) {\r
            if ((m_nfcImpl_.getFCD16FromSingleLead(c) >> SECOND_LAST_BYTE_SHIFT_) == 0) {\r
                return textoffset;\r
            }\r
            char next = text.next();\r
            if (Character.isSurrogatePair(c, next)) {\r
                int fcd = m_nfcImpl_.getFCD16(Character.toCodePoint(c, next));\r
                if ((fcd >> SECOND_LAST_BYTE_SHIFT_) == 0) {\r
                    return textoffset;\r
                }\r
                next = text.next();\r
                textoffset += 2;\r
            } else {\r
                ++textoffset;\r
            }\r
            c = next;\r
        }\r
    }\r
\r
    /**\r
     * Gets the next base character offset depending on the string search \r
     * pattern data\r
     * @param textoffset one offset away from the last character\r
     *                   to search for.\r
     * @return start index of the next base character or the current offset\r
     *         if the current character is contains a base character.\r
     */\r
    private final int getNextBaseOffset(int textoffset)\r
    {\r
        if (m_pattern_.m_hasSuffixAccents_ && textoffset < m_textLimitOffset_) {\r
            if ((getFCDBefore(targetText, textoffset) & LAST_BYTE_MASK_) != 0) {\r
                return getNextBaseOffset(targetText, textoffset);\r
            }\r
        }\r
        return textoffset;\r
    }\r
\r
    /**\r
     * Shifting the collation element iterator position forward to prepare for\r
     * a following match. If the last character is a unsafe character, we'll \r
     * only shift by 1 to capture contractions, normalization etc.\r
     * Internal method, status assumed to be success.\r
     * @param textoffset start text position to do search\r
     * @param ce the text ce which failed the match.\r
     * @param patternceindex index of the ce within the pattern ce buffer which\r
     *        failed the match\r
     * @return final offset\r
     */\r
    private int shiftForward(int textoffset, int ce, int patternceindex)\r
                                    \r
    {\r
        if (ce != CollationElementIterator.NULLORDER) {\r
            int shift = m_pattern_.m_shift_[hash(ce)];\r
            // this is to adjust for characters in the middle of the \r
            // substring for matching that failed.\r
            int adjust = m_pattern_.m_CELength_ - patternceindex;\r
            if (adjust > 1 && shift >= adjust) {\r
                shift -= adjust - 1;\r
            }\r
            textoffset += shift;\r
        }\r
        else {\r
            textoffset += m_pattern_.m_defaultShiftSize_;\r
        }\r
         \r
        textoffset = getNextBaseOffset(textoffset);\r
        // check for unsafe characters\r
        // * if it is the start or middle of a contraction: to be done after \r
        //   a initial match is found\r
        // * thai or lao base consonant character: similar to contraction\r
        // * high surrogate character: similar to contraction\r
        // * next character is a accent: shift to the next base character\r
        return textoffset;\r
    }\r
    \r
    /**\r
     * Gets the offset to the next safe point in text.\r
     * ie. not the middle of a contraction, swappable characters or \r
     * supplementary characters.\r
     * @param textoffset offset in string\r
     * @param end offset in string\r
     * @return offset to the next safe character\r
     */\r
    private final int getNextSafeOffset(int textoffset, int end)\r
    {\r
        int result = textoffset; // first contraction character\r
        targetText.setIndex(result);\r
        while (result != end && \r
            m_collator_.isUnsafe(targetText.current())) {\r
               result ++;\r
               targetText.setIndex(result);\r
        }\r
        return result; \r
    }\r
    \r
    /** \r
     * This checks for accents in the potential match started with a composite \r
     * character.\r
     * This is really painful... we have to check that composite character do \r
     * not have any extra accents. We have to normalize the potential match and \r
     * find the immediate decomposed character before the match.\r
     * The first composite character would have been taken care of by the fcd \r
     * checks in checkForwardExactMatch.\r
     * This is the slow path after the fcd of the first character and \r
     * the last character has been checked by checkForwardExactMatch and we \r
     * determine that the potential match has extra non-ignorable preceding\r
     * ces.\r
     * E.g. looking for \u0301 acute in \u01FA A ring above and acute, \r
     * checkExtraMatchAccent should fail since there is a middle ring in \r
     * \u01FA Note here that accents checking are slow and cautioned in the API \r
     * docs.\r
     * Internal method, status assumed to be a success, caller should check \r
     * status before calling this method\r
     * @param start index of the potential unfriendly composite character\r
     * @param end index of the potential unfriendly composite character\r
     * @return true if there is non-ignorable accents before at the beginning\r
     *              of the match, false otherwise.\r
     */\r
    private final boolean checkExtraMatchAccents(int start, int end)\r
    {\r
        boolean result = false;\r
        if (m_pattern_.m_hasPrefixAccents_) {\r
            targetText.setIndex(start);\r
            \r
            if (UTF16.isLeadSurrogate(targetText.next())) {\r
                if (!UTF16.isTrailSurrogate(targetText.next())) {\r
                    targetText.previous();\r
                }\r
            }\r
            // we are only concerned with the first composite character\r
            String str = getString(targetText, start, end);\r
            if (Normalizer.quickCheck(str, Normalizer.NFD,0) \r
                                                    == Normalizer.NO) {\r
                int safeoffset = getNextSafeOffset(start, end);\r
                if (safeoffset != end) {\r
                    safeoffset ++;\r
                }\r
                String decomp = Normalizer.decompose(\r
                                str.substring(0, safeoffset - start), false);\r
                m_utilColEIter_.setText(decomp);\r
                int firstce = m_pattern_.m_CE_[0];\r
                boolean ignorable = true;\r
                int ce = CollationElementIterator.IGNORABLE;\r
                int offset = 0;\r
                while (ce != firstce) {\r
                    offset = m_utilColEIter_.getOffset();\r
                    if (ce != firstce \r
                        && ce != CollationElementIterator.IGNORABLE) {\r
                        ignorable = false;\r
                    }\r
                    ce = m_utilColEIter_.next();\r
                }\r
                m_utilColEIter_.setExactOffset(offset); // back up 1 to the \r
                m_utilColEIter_.previous();             // right offset\r
                offset = m_utilColEIter_.getOffset();\r
                result = !ignorable && (UCharacter.getCombiningClass(\r
                                            UTF16.charAt(decomp, offset)) != 0);\r
            }\r
        }\r
    \r
        return result;\r
    }\r
    \r
    /**\r
    * Used by exact matches, checks if there are accents before the match. \r
    * This is really painful... we have to check that composite characters at\r
    * the start of the matches have to not have any extra accents. \r
    * We check the FCD of the character first, if it starts with an accent and \r
    * the first pattern ce does not match the first ce of the character, we \r
    * bail.\r
    * Otherwise we try normalizing the first composite \r
    * character and find the immediate decomposed character before the match to \r
    * see if it is an non-ignorable accent.\r
    * Now normalizing the first composite character is enough because we ensure \r
    * that when the match is passed in here with extra beginning ces, the \r
    * first or last ce that match has to occur within the first character.\r
    * E.g. looking for \u0301 acute in \u01FA A ring above and acute, \r
    * checkExtraMatchAccent should fail since there is a middle ring in \u01FA\r
    * Note here that accents checking are slow and cautioned in the API docs.\r
    * @param start offset \r
    * @param end offset\r
    * @return true if there are accents on either side of the match, \r
    *         false otherwise\r
    */\r
    private final boolean hasAccentsBeforeMatch(int start, int end) \r
    {\r
        if (m_pattern_.m_hasPrefixAccents_) {\r
            // we have been iterating forwards previously\r
            boolean ignorable = true;\r
            int firstce = m_pattern_.m_CE_[0];\r
            m_colEIter_.setExactOffset(start);\r
            int ce  = getCE(m_colEIter_.next());\r
            while (ce != firstce) {\r
                if (ce != CollationElementIterator.IGNORABLE) {\r
                    ignorable = false;\r
                }\r
                ce = getCE(m_colEIter_.next());\r
            }\r
            if (!ignorable && m_colEIter_.isInBuffer()) {\r
                // within normalization buffer, discontiguous handled here\r
                return true;\r
            }\r
    \r
            // within text\r
            boolean accent = (getFCD(targetText, start) >> SECOND_LAST_BYTE_SHIFT_)\r
                                                        != 0; \r
            if (!accent) {\r
                return checkExtraMatchAccents(start, end);\r
            }\r
            if (!ignorable) {\r
                return true;\r
            }\r
            if (start > m_textBeginOffset_) {\r
                targetText.setIndex(start);\r
                targetText.previous();\r
                if ((getFCD(targetText, targetText.getIndex()) & LAST_BYTE_MASK_) \r
                                                                        != 0) {\r
                    m_colEIter_.setExactOffset(start);\r
                    ce = m_colEIter_.previous();\r
                    if (ce != CollationElementIterator.NULLORDER \r
                        && ce != CollationElementIterator.IGNORABLE) {\r
                        return true;\r
                    }\r
                }\r
            }\r
        }\r
      \r
        return false;\r
    }\r
    \r
    /**\r
     * Used by exact matches, checks if there are accents bounding the match.\r
     * Note this is the initial boundary check. If the potential match\r
     * starts or ends with composite characters, the accents in those\r
     * characters will be determined later.\r
     * Not doing backwards iteration here, since discontiguos contraction for \r
     * backwards collation element iterator, use up too many characters.\r
     * E.g. looking for \u030A ring in \u01FA A ring above and acute, \r
     * should fail since there is a acute at the end of \u01FA\r
     * Note here that accents checking are slow and cautioned in the API docs.\r
     * @param start offset of match\r
     * @param end end offset of the match\r
     * @return true if there are accents on either side of the match, \r
     *         false otherwise\r
     */\r
    private final boolean hasAccentsAfterMatch(int start, int end) \r
    {\r
        if (m_pattern_.m_hasSuffixAccents_) {\r
            targetText.setIndex(end);\r
            if (end > m_textBeginOffset_ \r
                && UTF16.isTrailSurrogate(targetText.previous())) {\r
                if (targetText.getIndex() > m_textBeginOffset_ &&\r
                    !UTF16.isLeadSurrogate(targetText.previous())) {\r
                    targetText.next();\r
                }\r
            }\r
            if ((getFCD(targetText, targetText.getIndex()) & LAST_BYTE_MASK_) != 0) {\r
                int firstce  = m_pattern_.m_CE_[0];\r
                m_colEIter_.setExactOffset(start);\r
                while (getCE(m_colEIter_.next()) != firstce) {\r
                }\r
                int count = 1;\r
                while (count < m_pattern_.m_CELength_) {\r
                    if (getCE(m_colEIter_.next()) \r
                        == CollationElementIterator.IGNORABLE) {\r
                        count --;\r
                    }\r
                    count ++;\r
                }\r
                //int ce = getCE(m_colEIter_.next());\r
                int ce = m_colEIter_.next();\r
                if (ce != CollationElementIterator.NULLORDER \r
                        && ce != CollationElementIterator.IGNORABLE) {\r
                    ce = getCE(ce);\r
                }\r
                if (ce != CollationElementIterator.NULLORDER \r
                            && ce != CollationElementIterator.IGNORABLE) {\r
                    if (m_colEIter_.getOffset() <= end) {\r
                        return true;\r
                    }\r
                    if ((getFCD(targetText, end) >> SECOND_LAST_BYTE_SHIFT_) \r
                        != 0) {\r
                        return true;\r
                    }\r
                }\r
            }\r
        }\r
        return false;\r
    }\r
    \r
    /**\r
    * Checks if the offset runs out of the text string range\r
    * @param textstart offset of the first character in the range\r
    * @param textlimit limit offset of the text string range\r
    * @param offset to test\r
    * @return true if offset is out of bounds, false otherwise\r
    */\r
    private static final boolean isOutOfBounds(int textstart, int textlimit, \r
                                                int offset)\r
    {\r
        return offset < textstart || offset > textlimit;\r
    }\r
    \r
    /**\r
     * Checks for identical match\r
     * @param strsrch string search data\r
     * @param start offset of possible match\r
     * @param end offset of possible match\r
     * @return true if identical match is found\r
     */\r
    private final boolean checkIdentical(int start, int end) \r
    {\r
        if (m_collator_.getStrength() != Collator.IDENTICAL) {\r
            return true;\r
        }\r
    \r
        String textstr = getString(targetText, start, end - start);\r
        if (Normalizer.quickCheck(textstr, Normalizer.NFD,0) \r
                                                    == Normalizer.NO) {\r
            textstr = Normalizer.decompose(textstr, false);\r
        }\r
        String patternstr = m_pattern_.targetText;\r
        if (Normalizer.quickCheck(patternstr, Normalizer.NFD,0) \r
                                                    == Normalizer.NO) {\r
            patternstr = Normalizer.decompose(patternstr, false);\r
        }\r
        return textstr.equals(patternstr);\r
    }\r
    \r
    /**\r
     * Checks to see if the match is repeated\r
     * @param start new match start index\r
     * @param limit new match limit index\r
     * @return true if the the match is repeated, false otherwise\r
     */\r
    private final boolean checkRepeatedMatch(int start, int limit)\r
    {\r
        if (m_matchedIndex_ == DONE) {\r
            return false;\r
        }\r
        int end = limit - 1; // last character in the match\r
        int lastmatchend = m_matchedIndex_ + matchLength - 1; \r
        if (!isOverlapping()) {\r
            return (start >= m_matchedIndex_ && start <= lastmatchend) \r
                    || (end >= m_matchedIndex_ && end <= lastmatchend)\r
                    || (start <= m_matchedIndex_ && end >= lastmatchend);\r
                      \r
        }\r
        return start <= m_matchedIndex_ && end >= lastmatchend;\r
    }\r
    \r
    /**\r
     * Checks match for contraction. \r
     * If the match ends with a partial contraction we fail.\r
     * If the match starts too far off (because of backwards iteration) we try \r
     * to chip off the extra characters depending on whether a breakiterator \r
     * has been used.\r
     * Temporary utility buffer used to return modified start and end.\r
     * @param start offset of potential match, to be modified if necessary\r
     * @param end offset of potential match, to be modified if necessary\r
     * @return true if match passes the contraction test, false otherwise.\r
     */\r
    private final boolean checkNextExactContractionMatch(int start, int end) \r
    {\r
        // This part checks if either ends of the match contains potential \r
        // contraction. If so we'll have to iterate through them\r
        char endchar = 0;\r
        if (end < m_textLimitOffset_) {\r
            targetText.setIndex(end);\r
            endchar = targetText.current();\r
        }\r
        char poststartchar = 0;\r
        if (start + 1 < m_textLimitOffset_) {\r
            targetText.setIndex(start + 1);\r
            poststartchar = targetText.current();\r
        }\r
        if (m_collator_.isUnsafe(endchar) \r
            || m_collator_.isUnsafe(poststartchar)) {\r
            // expansion prefix, what's left to iterate\r
            int bufferedCEOffset = m_colEIter_.m_CEBufferOffset_;\r
            boolean hasBufferedCE = bufferedCEOffset > 0;\r
            m_colEIter_.setExactOffset(start);\r
            int temp = start;\r
            while (bufferedCEOffset > 0) {\r
                // getting rid of the redundant ce, caused by setOffset.\r
                // since backward contraction/expansion may have extra ces if \r
                // we are in the normalization buffer, hasAccentsBeforeMatch \r
                // would have taken care of it.\r
                // E.g. the character \u01FA will have an expansion of 3, but \r
                // if we are only looking for acute and ring \u030A and \u0301, \r
                // we'll have to skip the first ce in the expansion buffer.\r
                m_colEIter_.next();\r
                if (m_colEIter_.getOffset() != temp) {\r
                    start = temp;\r
                    temp  = m_colEIter_.getOffset();\r
                }\r
                bufferedCEOffset --;\r
            }\r
    \r
            int count = 0;\r
            while (count < m_pattern_.m_CELength_) {\r
                int ce = getCE(m_colEIter_.next());\r
                if (ce == CollationElementIterator.IGNORABLE) {\r
                    continue;\r
                }\r
                if (hasBufferedCE && count == 0 \r
                    && m_colEIter_.getOffset() != temp) {\r
                    start = temp;\r
                    temp   = m_colEIter_.getOffset();\r
                }\r
                if (ce != m_pattern_.m_CE_[count]) {\r
                    end ++;\r
                    end = getNextBaseOffset(end);  \r
                    m_utilBuffer_[0] = start;\r
                    m_utilBuffer_[1] = end;\r
                    return false;\r
                }\r
                count ++;\r
            }\r
        } \r
        m_utilBuffer_[0] = start;\r
        m_utilBuffer_[1] = end;\r
        return true;\r
    }\r
    \r
    \r
    /**\r
     * Checks and sets the match information if found.\r
     * Checks \r
     * <ul>\r
     * <li> the potential match does not repeat the previous match\r
     * <li> boundaries are correct\r
     * <li> exact matches has no extra accents\r
     * <li> identical matchesb\r
     * <li> potential match does not end in the middle of a contraction\r
     * </ul>\r
     * Otherwise the offset will be shifted to the next character.\r
     * The result m_matchIndex_ and m_matchLength_ will be set to the truncated\r
     * more fitting result value.\r
     * Uses the temporary utility buffer for storing the modified textoffset.\r
     * @param textoffset offset in the collation element text.\r
     * @return true if the match is valid, false otherwise\r
     */\r
    private final boolean checkNextExactMatch(int textoffset)\r
    {\r
        int start = m_colEIter_.getOffset();        \r
        if (!checkNextExactContractionMatch(start, textoffset)) {\r
            // returns the modified textoffset\r
            m_utilBuffer_[0] = m_utilBuffer_[1];\r
            return false;\r
        }\r
    \r
        start = m_utilBuffer_[0];\r
        textoffset = m_utilBuffer_[1];\r
        // this totally matches, however we need to check if it is repeating\r
        if (!isBreakUnit(start, textoffset) \r
            || checkRepeatedMatch(start, textoffset) \r
            || hasAccentsBeforeMatch(start, textoffset) \r
            || !checkIdentical(start, textoffset) \r
            || hasAccentsAfterMatch(start, textoffset)) {\r
            textoffset ++;\r
            textoffset = getNextBaseOffset(textoffset);  \r
            m_utilBuffer_[0] = textoffset;\r
            return false;\r
        }\r
        \r
        if (m_collator_.getStrength() == Collator.PRIMARY) {\r
            textoffset = checkBreakBoundary(textoffset);\r
        }\r
            \r
        // totally match, we will get rid of the ending ignorables.\r
        m_matchedIndex_  = start;\r
        matchLength = textoffset - start;\r
        return true;\r
    }\r
    \r
    /**\r
    * Getting the previous base character offset, or the current offset if the \r
    * current character is a base character\r
    * @param text the source text to work on\r
    * @param textoffset one offset after the current character\r
    * @return the offset of the next character after the base character or the \r
    *             first composed character with accents\r
    */\r
    private final int getPreviousBaseOffset(CharacterIterator text, \r
                                            int textoffset)\r
    {\r
        if (textoffset > m_textBeginOffset_) {\r
            while (true) {\r
                int result = textoffset;\r
                text.setIndex(result);\r
                if (UTF16.isTrailSurrogate(text.previous())) {\r
                    if (text.getIndex() != text.getBeginIndex() &&\r
                        !UTF16.isLeadSurrogate(text.previous())) {\r
                        text.next();\r
                    }\r
                }\r
                textoffset = text.getIndex();\r
                char fcd = getFCD(text, textoffset);\r
                if ((fcd >> SECOND_LAST_BYTE_SHIFT_) == 0) {\r
                    if ((fcd & LAST_BYTE_MASK_) != 0) {\r
                        return textoffset;\r
                    }\r
                    return result;\r
                }\r
                if (textoffset == m_textBeginOffset_) {\r
                    return m_textBeginOffset_;\r
                }\r
            }\r
        }\r
        return textoffset;\r
    }\r
    \r
    /**\r
    * Getting the indexes of the accents that are not blocked in the argument\r
    * accent array\r
    * @param accents accents in nfd.\r
    * @param accentsindex array to store the indexes of accents in accents that \r
    *         are not blocked\r
    * @return the length of populated accentsindex\r
    */\r
    private int getUnblockedAccentIndex(StringBuilder accents, \r
                                        int accentsindex[])\r
    {\r
        int index = 0;\r
        int length = accents.length();\r
        int cclass = 0;\r
        int result = 0;\r
        while (index < length) {\r
            int codepoint = UTF16.charAt(accents, index);\r
            int tempclass = UCharacter.getCombiningClass(codepoint);\r
            if (tempclass != cclass) {\r
                cclass = tempclass;\r
                accentsindex[result] = index;\r
                result ++;\r
            }\r
            if (UCharacter.isSupplementary(codepoint)) {\r
                index += 2;\r
            }\r
            else {\r
                index ++;\r
            }\r
        }\r
        accentsindex[result] = length;\r
        return result;\r
    }\r
\r
    /**\r
     * Appends 3 StringBuilder/CharacterIterator together into a destination \r
     * string buffer.\r
     * @param source1 string buffer\r
     * @param source2 character iterator\r
     * @param start2 start of the character iterator to merge\r
     * @param end2 end of the character iterator to merge\r
     * @param source3 string buffer\r
     * @return appended string buffer\r
     */\r
    private static final StringBuilder merge(StringBuilder source1, \r
                                             CharacterIterator source2,\r
                                             int start2, int end2,\r
                                             StringBuilder source3) \r
    {\r
        StringBuilder result = new StringBuilder();    \r
        if (source1 != null && source1.length() != 0) {\r
            result.append(source1);\r
        }\r
        source2.setIndex(start2);\r
        while (source2.getIndex() < end2) {\r
            result.append(source2.current());\r
            source2.next();\r
        }\r
        if (source3 != null && source3.length() != 0) {\r
            result.append(source3);\r
        }\r
        return result;\r
    }\r
    \r
    /**\r
    * Running through a collation element iterator to see if the contents \r
    * matches pattern in string search data\r
    * @param coleiter collation element iterator to test\r
    * @return true if a match if found, false otherwise\r
    */\r
    private final boolean checkCollationMatch(CollationElementIterator coleiter)\r
    {\r
        int patternceindex = m_pattern_.m_CELength_;\r
        int offset = 0;\r
        while (patternceindex > 0) {\r
            int ce = getCE(coleiter.next());\r
            if (ce == CollationElementIterator.IGNORABLE) {\r
                continue;\r
            }\r
            if (ce != m_pattern_.m_CE_[offset]) {\r
                return false;\r
            }\r
            offset ++;\r
            patternceindex --;\r
        }\r
        return true;\r
    }\r
    \r
    /**\r
     * Rearranges the front accents to try matching.\r
     * Prefix accents in the text will be grouped according to their combining \r
     * class and the groups will be mixed and matched to try find the perfect \r
     * match with the pattern.\r
     * So for instance looking for "\u0301" in "\u030A\u0301\u0325"\r
     * step 1: split "\u030A\u0301" into 6 other type of potential accent \r
     *            substrings "\u030A", "\u0301", "\u0325", "\u030A\u0301", \r
     *            "\u030A\u0325", "\u0301\u0325".\r
     * step 2: check if any of the generated substrings matches the pattern.\r
     * Internal method, status is assumed to be success, caller has to check \r
     * status before calling this method.\r
     * @param start first offset of the accents to start searching\r
     * @param end start of the last accent set\r
     * @return DONE if a match is not found, otherwise return the starting\r
     *         offset of the match. Note this start includes all preceding \r
     *            accents.\r
     */\r
    private int doNextCanonicalPrefixMatch(int start, int end)\r
    {\r
        if ((getFCD(targetText, start) & LAST_BYTE_MASK_) == 0) {\r
            // die... failed at a base character\r
            return DONE;\r
        }\r
    \r
        start = targetText.getIndex(); // index changed by fcd\r
        int offset = getNextBaseOffset(targetText, start);\r
        start = getPreviousBaseOffset(start);\r
    \r
        StringBuilder accents = new StringBuilder();\r
        String accentstr = getString(targetText, start, offset - start);\r
        // normalizing the offensive string\r
        if (Normalizer.quickCheck(accentstr, Normalizer.NFD,0) \r
                                                    == Normalizer.NO) {\r
            accentstr = Normalizer.decompose(accentstr, false);\r
        }\r
        accents.append(accentstr);\r
            \r
        int accentsindex[] = new int[INITIAL_ARRAY_SIZE_];      \r
        int accentsize = getUnblockedAccentIndex(accents, accentsindex);\r
        int count = (2 << (accentsize - 1)) - 1;  \r
        while (count > 0) {\r
            // copy the base characters\r
            m_canonicalPrefixAccents_.delete(0, \r
                                        m_canonicalPrefixAccents_.length());\r
            int k = 0;\r
            for (; k < accentsindex[0]; k ++) {\r
                m_canonicalPrefixAccents_.append(accents.charAt(k));\r
            }\r
            // forming all possible canonical rearrangement by dropping\r
            // sets of accents\r
            for (int i = 0; i <= accentsize - 1; i ++) {\r
                int mask = 1 << (accentsize - i - 1);\r
                if ((count & mask) != 0) {\r
                    for (int j = accentsindex[i]; j < accentsindex[i + 1]; \r
                                                                        j ++) {\r
                        m_canonicalPrefixAccents_.append(accents.charAt(j));\r
                    }\r
                }\r
            }\r
            StringBuilder match = merge(m_canonicalPrefixAccents_,\r
                                       targetText, offset, end,\r
                                       m_canonicalSuffixAccents_);\r
                \r
            // if status is a failure, ucol_setText does nothing.\r
            // run the collator iterator through this match\r
            m_utilColEIter_.setText(match.toString());\r
            if (checkCollationMatch(m_utilColEIter_)) {\r
                 return start;\r
            }\r
            count --;\r
        }\r
        return DONE;\r
    }\r
\r
    /**\r
    * Gets the offset to the safe point in text before textoffset.\r
    * ie. not the middle of a contraction, swappable characters or \r
    * supplementary characters.\r
    * @param start offset in string\r
    * @param textoffset offset in string\r
    * @return offset to the previous safe character\r
    */\r
    private final int getPreviousSafeOffset(int start, int textoffset)\r
    {\r
        int result = textoffset; // first contraction character\r
        targetText.setIndex(textoffset);\r
        while (result >= start && m_collator_.isUnsafe(targetText.previous())) {\r
            result = targetText.getIndex();\r
        }\r
        if (result != start) {\r
            // the first contraction character is consider unsafe here\r
            result = targetText.getIndex(); // originally result --;\r
        }\r
        return result; \r
    }\r
\r
    /**\r
     * Take the rearranged end accents and tries matching. If match failed at\r
     * a seperate preceding set of accents (seperated from the rearranged on by\r
     * at least a base character) then we rearrange the preceding accents and \r
     * tries matching again.\r
     * We allow skipping of the ends of the accent set if the ces do not match. \r
     * However if the failure is found before the accent set, it fails.\r
     * Internal method, status assumed to be success, caller has to check \r
     * status before calling this method.\r
     * @param textoffset of the start of the rearranged accent\r
     * @return DONE if a match is not found, otherwise return the starting\r
     *         offset of the match. Note this start includes all preceding \r
     *         accents.\r
     */\r
    private int doNextCanonicalSuffixMatch(int textoffset)\r
    {\r
        int safelength = 0;\r
        StringBuilder safetext;\r
        int safeoffset = m_textBeginOffset_; \r
        \r
        if (textoffset != m_textBeginOffset_ \r
            && m_canonicalSuffixAccents_.length() > 0\r
            && m_collator_.isUnsafe(m_canonicalSuffixAccents_.charAt(0))) {\r
            safeoffset     = getPreviousSafeOffset(m_textBeginOffset_, \r
                                                    textoffset);\r
            safelength     = textoffset - safeoffset;\r
            safetext       = merge(null, targetText, safeoffset, textoffset, \r
                                   m_canonicalSuffixAccents_);\r
        }\r
        else {\r
            safetext = m_canonicalSuffixAccents_;\r
        }\r
    \r
        // if status is a failure, ucol_setText does nothing\r
        CollationElementIterator coleiter = m_utilColEIter_;\r
        coleiter.setText(safetext.toString());\r
        // status checked in loop below\r
    \r
        int ceindex = m_pattern_.m_CELength_ - 1;\r
        boolean isSafe = true; // indication flag for position in safe zone\r
        \r
        while (ceindex >= 0) {\r
            int textce = coleiter.previous();\r
            if (textce == CollationElementIterator.NULLORDER) {\r
                // check if we have passed the safe buffer\r
                if (coleiter == m_colEIter_) {\r
                    return DONE;\r
                }\r
                coleiter = m_colEIter_;\r
                if (safetext != m_canonicalSuffixAccents_) {\r
                    safetext.delete(0, safetext.length());\r
                }\r
                coleiter.setExactOffset(safeoffset);\r
                // status checked at the start of the loop\r
                isSafe = false;\r
                continue;\r
            }\r
            textce = getCE(textce);\r
            if (textce != CollationElementIterator.IGNORABLE \r
                && textce != m_pattern_.m_CE_[ceindex]) {\r
                // do the beginning stuff\r
                int failedoffset = coleiter.getOffset();\r
                if (isSafe && failedoffset >= safelength) {\r
                    // alas... no hope. failed at rearranged accent set\r
                    return DONE;\r
                }\r
                else {\r
                    if (isSafe) {\r
                        failedoffset += safeoffset;\r
                    }\r
                    \r
                    // try rearranging the front accents\r
                    int result = doNextCanonicalPrefixMatch(failedoffset, \r
                                                            textoffset);\r
                    if (result != DONE) {\r
                        // if status is a failure, ucol_setOffset does nothing\r
                        m_colEIter_.setExactOffset(result);\r
                    }\r
                    return result;\r
                }\r
            }\r
            if (textce == m_pattern_.m_CE_[ceindex]) {\r
                ceindex --;\r
            }\r
        }\r
        // set offset here\r
        if (isSafe) {\r
            int result = coleiter.getOffset();\r
            // sets the text iterator with the correct expansion and offset\r
            int leftoverces = coleiter.m_CEBufferOffset_;\r
            if (result >= safelength) { \r
                result = textoffset;\r
            }\r
            else {\r
                result += safeoffset;\r
            }\r
            m_colEIter_.setExactOffset(result);\r
            m_colEIter_.m_CEBufferOffset_ = leftoverces;\r
            return result;\r
        }\r
        \r
        return coleiter.getOffset();              \r
    }\r
    \r
    /**\r
     * Trying out the substring and sees if it can be a canonical match.\r
     * This will try normalizing the end accents and arranging them into \r
     * canonical equivalents and check their corresponding ces with the pattern \r
     * ce.\r
     * Suffix accents in the text will be grouped according to their combining \r
     * class and the groups will be mixed and matched to try find the perfect \r
     * match with the pattern.\r
     * So for instance looking for "\u0301" in "\u030A\u0301\u0325"\r
     * step 1: split "\u030A\u0301" into 6 other type of potential accent \r
     *         substrings\r
     *         "\u030A", "\u0301", "\u0325", "\u030A\u0301", "\u030A\u0325", \r
     *         "\u0301\u0325".\r
     * step 2: check if any of the generated substrings matches the pattern.\r
     * @param textoffset end offset in the collation element text that ends with \r
     *                   the accents to be rearranged\r
     * @return true if the match is valid, false otherwise\r
     */\r
    private boolean doNextCanonicalMatch(int textoffset)\r
    {\r
        int offset = m_colEIter_.getOffset();\r
        targetText.setIndex(textoffset);\r
        if (UTF16.isTrailSurrogate(targetText.previous()) \r
            && targetText.getIndex() > m_textBeginOffset_) { \r
            if (!UTF16.isLeadSurrogate(targetText.previous())) {\r
                targetText.next();\r
            }\r
        }\r
        if ((getFCD(targetText, targetText.getIndex()) & LAST_BYTE_MASK_) == 0) {\r
            if (m_pattern_.m_hasPrefixAccents_) {\r
                offset = doNextCanonicalPrefixMatch(offset, textoffset);\r
                if (offset != DONE) {\r
                    m_colEIter_.setExactOffset(offset);\r
                    return true;\r
                }\r
            }\r
            return false;\r
        }\r
    \r
        if (!m_pattern_.m_hasSuffixAccents_) {\r
            return false;\r
        }\r
    \r
        StringBuilder accents = new StringBuilder();\r
        // offset to the last base character in substring to search\r
        int baseoffset = getPreviousBaseOffset(targetText, textoffset);\r
        // normalizing the offensive string\r
        String accentstr = getString(targetText, baseoffset, \r
                                     textoffset - baseoffset);\r
        if (Normalizer.quickCheck(accentstr, Normalizer.NFD,0) \r
                                                    == Normalizer.NO) {\r
            accentstr = Normalizer.decompose(accentstr, false);\r
        }\r
        accents.append(accentstr);\r
        // status checked in loop below\r
            \r
        int accentsindex[] = new int[INITIAL_ARRAY_SIZE_];\r
        int size = getUnblockedAccentIndex(accents, accentsindex);\r
    \r
        // 2 power n - 1 plus the full set of accents\r
        int  count = (2 << (size - 1)) - 1;  \r
        while (count > 0) {\r
            m_canonicalSuffixAccents_.delete(0, \r
                                           m_canonicalSuffixAccents_.length());\r
            // copy the base characters\r
            for (int k = 0; k < accentsindex[0]; k ++) {\r
                m_canonicalSuffixAccents_.append(accents.charAt(k));\r
            }\r
            // forming all possible canonical rearrangement by dropping\r
            // sets of accents\r
            for (int i = 0; i <= size - 1; i ++) {\r
                int mask = 1 << (size - i - 1);\r
                if ((count & mask) != 0) {\r
                    for (int j = accentsindex[i]; j < accentsindex[i + 1]; \r
                        j ++) {\r
                        m_canonicalSuffixAccents_.append(accents.charAt(j));\r
                    }\r
                }\r
            }\r
            offset = doNextCanonicalSuffixMatch(baseoffset);\r
            if (offset != DONE) {\r
                return true; // match found\r
            }\r
            count --;\r
        }\r
        return false;\r
    }\r
    \r
    /**\r
     * Gets the previous base character offset depending on the string search \r
     * pattern data\r
     * @param strsrch string search data\r
     * @param textoffset current offset, current character\r
     * @return the offset of the next character after this base character or \r
     *             itself if it is a composed character with accents\r
     */\r
    private final int getPreviousBaseOffset(int textoffset)\r
    {\r
        if (m_pattern_.m_hasPrefixAccents_ && textoffset > m_textBeginOffset_) {\r
            int offset = textoffset;\r
            if ((getFCD(targetText, offset) >> SECOND_LAST_BYTE_SHIFT_) != 0) {\r
                return getPreviousBaseOffset(targetText, textoffset);\r
            }\r
        }\r
        return textoffset;\r
    }\r
    \r
    /**\r
     * Checks match for contraction. \r
     * If the match ends with a partial contraction we fail.\r
     * If the match starts too far off (because of backwards iteration) we try \r
     * to chip off the extra characters.\r
     * Uses the temporary util buffer for return values of the modified start\r
     * and end.\r
     * @param start offset of potential match, to be modified if necessary\r
     * @param end offset of potential match, to be modified if necessary\r
     * @return true if match passes the contraction test, false otherwise. \r
     */\r
    private boolean checkNextCanonicalContractionMatch(int start, int end) \r
    {\r
        // This part checks if either ends of the match contains potential \r
        // contraction. If so we'll have to iterate through them\r
        char schar = 0;\r
        char echar = 0;\r
        if (end < m_textLimitOffset_) {\r
            targetText.setIndex(end);\r
            echar = targetText.current();\r
        }\r
        if (start < m_textLimitOffset_) {\r
            targetText.setIndex(start + 1);\r
            schar = targetText.current();\r
        }\r
        if (m_collator_.isUnsafe(echar) || m_collator_.isUnsafe(schar)) {\r
            int expansion  = m_colEIter_.m_CEBufferOffset_;\r
            boolean hasExpansion = expansion > 0;\r
            m_colEIter_.setExactOffset(start);\r
            int temp = start;\r
            while (expansion > 0) {\r
                // getting rid of the redundant ce, caused by setOffset.\r
                // since backward contraction/expansion may have extra ces if \r
                // we are in the normalization buffer, hasAccentsBeforeMatch \r
                // would have taken care of it.\r
                // E.g. the character \u01FA will have an expansion of 3, but \r
                // if we are only looking for acute and ring \u030A and \u0301, \r
                // we'll have to skip the first ce in the expansion buffer.\r
                m_colEIter_.next();\r
                if (m_colEIter_.getOffset() != temp) {\r
                    start = temp;\r
                    temp  = m_colEIter_.getOffset();\r
                }\r
                expansion --;\r
            }\r
    \r
            int count = 0;\r
            while (count < m_pattern_.m_CELength_) {\r
                int ce = getCE(m_colEIter_.next());\r
                // status checked below, note that if status is a failure\r
                // ucol_next returns UCOL_NULLORDER\r
                if (ce == CollationElementIterator.IGNORABLE) {\r
                    continue;\r
                }\r
                if (hasExpansion && count == 0 \r
                    && m_colEIter_.getOffset() != temp) {\r
                    start = temp;\r
                    temp = m_colEIter_.getOffset();\r
                }\r
    \r
                if (count == 0 && ce != m_pattern_.m_CE_[0]) {\r
                    // accents may have extra starting ces, this occurs when a \r
                    // pure accent pattern is matched without rearrangement\r
                    // text \u0325\u0300 and looking for \u0300\r
                    int expected = m_pattern_.m_CE_[0]; \r
                    if ((getFCD(targetText, start) & LAST_BYTE_MASK_) != 0) {\r
                        ce = getCE(m_colEIter_.next());\r
                        while (ce != expected \r
                               && ce != CollationElementIterator.NULLORDER \r
                               && m_colEIter_.getOffset() <= end) {\r
                            ce = getCE(m_colEIter_.next());\r
                        }\r
                    }\r
                }\r
                if (ce != m_pattern_.m_CE_[count]) {\r
                    end ++;\r
                    end = getNextBaseOffset(end);  \r
                    m_utilBuffer_[0] = start;\r
                    m_utilBuffer_[1] = end;\r
                    return false;\r
                }\r
                count ++;\r
            }\r
        } \r
        m_utilBuffer_[0] = start;\r
        m_utilBuffer_[1] = end;\r
        return true;\r
    }\r
\r
    /**\r
     * Checks and sets the match information if found.\r
     * Checks \r
     * <ul>\r
     * <li> the potential match does not repeat the previous match\r
     * <li> boundaries are correct\r
     * <li> potential match does not end in the middle of a contraction\r
     * <li> identical matches\r
     * </ul>\r
     * Otherwise the offset will be shifted to the next character.\r
     * The result m_matchIndex_ and m_matchLength_ will be set to the truncated\r
     * more fitting result value.\r
     * Uses the temporary utility buffer for storing the modified textoffset.\r
     * @param textoffset offset in the collation element text.\r
     * @return true if the match is valid, false otherwise\r
     */\r
    private boolean checkNextCanonicalMatch(int textoffset)\r
    {\r
        // to ensure that the start and ends are not composite characters\r
        // if we have a canonical accent match\r
        if ((m_pattern_.m_hasSuffixAccents_ \r
                && m_canonicalSuffixAccents_.length() != 0) || \r
            (m_pattern_.m_hasPrefixAccents_ \r
                && m_canonicalPrefixAccents_.length() != 0)) {\r
            m_matchedIndex_ = getPreviousBaseOffset(m_colEIter_.getOffset());\r
            matchLength = textoffset - m_matchedIndex_;\r
            return true;\r
        }\r
    \r
        int start = m_colEIter_.getOffset();\r
        if (!checkNextCanonicalContractionMatch(start, textoffset)) {\r
            // return the modified textoffset\r
            m_utilBuffer_[0] = m_utilBuffer_[1]; \r
            return false;\r
        }\r
        start = m_utilBuffer_[0];\r
        textoffset = m_utilBuffer_[1];\r
        start = getPreviousBaseOffset(start);\r
        // this totally matches, however we need to check if it is repeating\r
        if (checkRepeatedMatch(start, textoffset) \r
            || !isBreakUnit(start, textoffset) \r
            || !checkIdentical(start, textoffset)) {\r
            textoffset ++;\r
            textoffset = getNextBaseOffset(targetText, textoffset);\r
            m_utilBuffer_[0] = textoffset;\r
            return false;\r
        }\r
        \r
        m_matchedIndex_  = start;\r
        matchLength = textoffset - start;\r
        return true;\r
    }\r
    \r
    /**\r
     * Shifting the collation element iterator position forward to prepare for\r
     * a preceding match. If the first character is a unsafe character, we'll \r
     * only shift by 1 to capture contractions, normalization etc.\r
     * @param textoffset start text position to do search\r
     * @param ce the text ce which failed the match.\r
     * @param patternceindex index of the ce within the pattern ce buffer which\r
     *        failed the match\r
     * @return final offset\r
     */\r
    private int reverseShift(int textoffset, int ce, int patternceindex)\r
    {         \r
        if (isOverlapping()) {\r
            if (textoffset != m_textLimitOffset_) {\r
                textoffset --;\r
            }\r
            else {\r
                textoffset -= m_pattern_.m_defaultShiftSize_;\r
            }\r
        }\r
        else {\r
            if (ce != CollationElementIterator.NULLORDER) {\r
                int shift = m_pattern_.m_backShift_[hash(ce)];\r
                \r
                // this is to adjust for characters in the middle of the substring \r
                // for matching that failed.\r
                int adjust = patternceindex;\r
                if (adjust > 1 && shift > adjust) {\r
                    shift -= adjust - 1;\r
                }\r
                textoffset -= shift;\r
            }\r
            else {\r
                textoffset -= m_pattern_.m_defaultShiftSize_;\r
            }\r
        }    \r
        \r
        textoffset = getPreviousBaseOffset(textoffset);\r
        return textoffset;\r
    }\r
\r
    /**\r
     * Checks match for contraction. \r
     * If the match starts with a partial contraction we fail.\r
     * Uses the temporary utility buffer to return the modified start and end.\r
     * @param start offset of potential match, to be modified if necessary\r
     * @param end offset of potential match, to be modified if necessary\r
     * @return true if match passes the contraction test, false otherwise.\r
     */\r
    private boolean checkPreviousExactContractionMatch(int start, int end) \r
    {\r
        // This part checks if either ends of the match contains potential \r
        // contraction. If so we'll have to iterate through them\r
        char echar = 0;\r
        if (end < m_textLimitOffset_) {\r
            targetText.setIndex(end);\r
            echar = targetText.current();\r
        }\r
        char schar = 0;\r
        if (start + 1 < m_textLimitOffset_) {\r
            targetText.setIndex(start + 1);\r
            schar = targetText.current();\r
        }\r
        if (m_collator_.isUnsafe(echar) || m_collator_.isUnsafe(schar)) {\r
            // expansion suffix, what's left to iterate\r
            int expansion = m_colEIter_.m_CEBufferSize_ \r
                                            - m_colEIter_.m_CEBufferOffset_;\r
            boolean hasExpansion = expansion > 0;\r
            m_colEIter_.setExactOffset(end);\r
            int temp = end;\r
            while (expansion > 0) {\r
                // getting rid of the redundant ce\r
                // since forward contraction/expansion may have extra ces\r
                // if we are in the normalization buffer, hasAccentsBeforeMatch\r
                // would have taken care of it.\r
                // E.g. the character \u01FA will have an expansion of 3, but if\r
                // we are only looking for A ring A\u030A, we'll have to skip the \r
                // last ce in the expansion buffer\r
                m_colEIter_.previous();\r
                if (m_colEIter_.getOffset() != temp) {\r
                    end = temp;\r
                    temp = m_colEIter_.getOffset();\r
                }\r
                expansion --;\r
            }\r
    \r
            int count = m_pattern_.m_CELength_;\r
            while (count > 0) {\r
                int ce = getCE(m_colEIter_.previous());\r
                // status checked below, note that if status is a failure\r
                // ucol_previous returns UCOL_NULLORDER\r
                if (ce == CollationElementIterator.IGNORABLE) {\r
                    continue;\r
                }\r
                if (hasExpansion && count == 0 \r
                    && m_colEIter_.getOffset() != temp) {\r
                    end = temp;\r
                    temp = m_colEIter_.getOffset();\r
                }\r
                if (ce != m_pattern_.m_CE_[count - 1]) {\r
                    start --;\r
                    start = getPreviousBaseOffset(targetText, start);\r
                    m_utilBuffer_[0] = start;\r
                    m_utilBuffer_[1] = end;\r
                    return false;\r
                }\r
                count --;\r
            }\r
        } \r
        m_utilBuffer_[0] = start;\r
        m_utilBuffer_[1] = end;\r
        return true;\r
    }\r
    \r
    /**\r
     * Checks and sets the match information if found.\r
     * Checks \r
     * <ul>\r
     * <li> the current match does not repeat the last match\r
     * <li> boundaries are correct\r
     * <li> exact matches has no extra accents\r
     * <li> identical matches\r
     * </ul>\r
     * Otherwise the offset will be shifted to the preceding character.\r
     * Uses the temporary utility buffer to store the modified textoffset.\r
     * @param textoffset offset in the collation element text. the returned value\r
     *        will be the truncated start offset of the match or the new start \r
     *        search offset.\r
     * @return true if the match is valid, false otherwise\r
     */\r
    private final boolean checkPreviousExactMatch(int textoffset)\r
    {\r
        // to ensure that the start and ends are not composite characters\r
        int end = m_colEIter_.getOffset();        \r
        if (!checkPreviousExactContractionMatch(textoffset, end)) {\r
            return false;\r
        }\r
        textoffset = m_utilBuffer_[0];\r
        end = m_utilBuffer_[1];\r
            \r
        // this totally matches, however we need to check if it is repeating\r
        // the old match\r
        if (checkRepeatedMatch(textoffset, end) \r
            || !isBreakUnit(textoffset, end) \r
            || hasAccentsBeforeMatch(textoffset, end) \r
            || !checkIdentical(textoffset, end) \r
            || hasAccentsAfterMatch(textoffset, end)) {\r
            textoffset --;\r
            textoffset = getPreviousBaseOffset(targetText, textoffset);\r
            m_utilBuffer_[0] = textoffset;\r
            return false;\r
        }\r
        \r
        if (m_collator_.getStrength() == Collator.PRIMARY) {\r
            end = checkBreakBoundary(end);\r
        }\r
        \r
        m_matchedIndex_ = textoffset;\r
        matchLength = end - textoffset;\r
        return true;\r
    }\r
\r
    /**\r
     * Rearranges the end accents to try matching.\r
     * Suffix accents in the text will be grouped according to their combining \r
     * class and the groups will be mixed and matched to try find the perfect \r
     * match with the pattern.\r
     * So for instance looking for "\u0301" in "\u030A\u0301\u0325"\r
     * step 1: split "\u030A\u0301" into 6 other type of potential accent \r
     *             substrings\r
     *         "\u030A", "\u0301", "\u0325", "\u030A\u0301", "\u030A\u0325", \r
     *         "\u0301\u0325".\r
     * step 2: check if any of the generated substrings matches the pattern.\r
     * @param start offset of the first base character\r
     * @param end start of the last accent set\r
     * @return DONE if a match is not found, otherwise return the ending\r
     *         offset of the match. Note this start includes all following \r
     *         accents.\r
     */\r
    private int doPreviousCanonicalSuffixMatch(int start, int end)\r
    {\r
        targetText.setIndex(end);\r
        if (UTF16.isTrailSurrogate(targetText.previous()) \r
            && targetText.getIndex() > m_textBeginOffset_) {\r
            if (!UTF16.isLeadSurrogate(targetText.previous())) {\r
                targetText.next();\r
            } \r
        }\r
        if ((getFCD(targetText, targetText.getIndex()) & LAST_BYTE_MASK_) == 0) {\r
            // die... failed at a base character\r
            return DONE;\r
        }\r
        end = getNextBaseOffset(targetText, end);\r
    \r
        StringBuilder accents = new StringBuilder();\r
        int offset = getPreviousBaseOffset(targetText, end);\r
        // normalizing the offensive string\r
        String accentstr = getString(targetText, offset, end - offset);\r
        if (Normalizer.quickCheck(accentstr, Normalizer.NFD,0) \r
                                                    == Normalizer.NO) {\r
            accentstr = Normalizer.decompose(accentstr, false);\r
        }\r
        accents.append(accentstr);    \r
            \r
        int accentsindex[] = new int[INITIAL_ARRAY_SIZE_];      \r
        int accentsize = getUnblockedAccentIndex(accents, accentsindex);\r
        int count = (2 << (accentsize - 1)) - 1;  \r
        while (count > 0) {\r
            m_canonicalSuffixAccents_.delete(0, \r
                                           m_canonicalSuffixAccents_.length());\r
            // copy the base characters\r
            for (int k = 0; k < accentsindex[0]; k ++) {\r
                 m_canonicalSuffixAccents_.append(accents.charAt(k));\r
            }\r
            // forming all possible canonical rearrangement by dropping\r
            // sets of accents\r
            for (int i = 0; i <= accentsize - 1; i ++) {\r
                int mask = 1 << (accentsize - i - 1);\r
                if ((count & mask) != 0) {\r
                    for (int j = accentsindex[i]; j < accentsindex[i + 1]; \r
                                                                        j ++) {\r
                        m_canonicalSuffixAccents_.append(accents.charAt(j));\r
                    }\r
                }\r
            }\r
            StringBuilder match = merge(m_canonicalPrefixAccents_, targetText,\r
                                        start, offset, \r
                                        m_canonicalSuffixAccents_);\r
            // run the collator iterator through this match\r
            // if status is a failure ucol_setText does nothing\r
            m_utilColEIter_.setText(match.toString());\r
            if (checkCollationMatch(m_utilColEIter_)) {\r
                return end;\r
            }\r
            count --;\r
        }\r
        return DONE;\r
    }\r
    \r
    /**\r
     * Take the rearranged start accents and tries matching. If match failed at\r
     * a seperate following set of accents (seperated from the rearranged on by\r
     * at least a base character) then we rearrange the preceding accents and \r
     * tries matching again.\r
     * We allow skipping of the ends of the accent set if the ces do not match. \r
     * However if the failure is found before the accent set, it fails.\r
     * Internal method, status assumed to be success, caller has to check \r
     * status before calling this method.\r
     * @param textoffset of the ends of the rearranged accent\r
     * @return DONE if a match is not found, otherwise return the ending offset \r
     *             of the match. Note this start includes all following accents.\r
     */\r
    private int doPreviousCanonicalPrefixMatch(int textoffset)\r
    {\r
       // int safelength = 0;\r
        StringBuilder safetext;\r
        int safeoffset = textoffset;\r
    \r
        if (textoffset > m_textBeginOffset_\r
            && m_collator_.isUnsafe(m_canonicalPrefixAccents_.charAt(\r
                                    m_canonicalPrefixAccents_.length() - 1))) {\r
            safeoffset = getNextSafeOffset(textoffset, m_textLimitOffset_);\r
            //safelength = safeoffset - textoffset;\r
            safetext = merge(m_canonicalPrefixAccents_, targetText, textoffset, \r
                             safeoffset, null);\r
        }\r
        else {\r
            safetext = m_canonicalPrefixAccents_;\r
        }\r
    \r
        // if status is a failure, ucol_setText does nothing\r
        CollationElementIterator coleiter = m_utilColEIter_;\r
        coleiter.setText(safetext.toString());\r
        // status checked in loop below\r
        \r
        int ceindex = 0;\r
        boolean isSafe = true; // safe zone indication flag for position\r
        int prefixlength = m_canonicalPrefixAccents_.length();\r
        \r
        while (ceindex < m_pattern_.m_CELength_) {\r
            int textce = coleiter.next();\r
            if (textce == CollationElementIterator.NULLORDER) {\r
                // check if we have passed the safe buffer\r
                if (coleiter == m_colEIter_) {\r
                    return DONE;\r
                }\r
                if (safetext != m_canonicalPrefixAccents_) {\r
                    safetext.delete(0, safetext.length());\r
                }\r
                coleiter = m_colEIter_;\r
                coleiter.setExactOffset(safeoffset);\r
                // status checked at the start of the loop\r
                isSafe = false;\r
                continue;\r
            }\r
            textce = getCE(textce);\r
            if (textce != CollationElementIterator.IGNORABLE \r
                && textce != m_pattern_.m_CE_[ceindex]) {\r
                // do the beginning stuff\r
                int failedoffset = coleiter.getOffset();\r
                if (isSafe && failedoffset <= prefixlength) {\r
                    // alas... no hope. failed at rearranged accent set\r
                    return DONE;\r
                }\r
                else {\r
                    if (isSafe) {\r
                        failedoffset = safeoffset - failedoffset;\r
                        if (safetext != m_canonicalPrefixAccents_) {\r
                            safetext.delete(0, safetext.length());\r
                        }\r
                    }\r
                    \r
                    // try rearranging the end accents\r
                    int result = doPreviousCanonicalSuffixMatch(textoffset, \r
                                                                failedoffset);\r
                    if (result != DONE) {\r
                        // if status is a failure, ucol_setOffset does nothing\r
                        m_colEIter_.setExactOffset(result);\r
                    }\r
                    return result;\r
                }\r
            }\r
            if (textce == m_pattern_.m_CE_[ceindex]) {\r
                ceindex ++;\r
            }\r
        }\r
        // set offset here\r
        if (isSafe) {\r
            int result = coleiter.getOffset();\r
            // sets the text iterator here with the correct expansion and offset\r
            int leftoverces = coleiter.m_CEBufferSize_ \r
                                                - coleiter.m_CEBufferOffset_;\r
            if (result <= prefixlength) { \r
                result = textoffset;\r
            }\r
            else {\r
                result = textoffset + (safeoffset - result);\r
            }\r
            m_colEIter_.setExactOffset(result);\r
            m_colEIter_.m_CEBufferOffset_ = m_colEIter_.m_CEBufferSize_ \r
                                                                - leftoverces;\r
            return result;\r
        }\r
        \r
        return coleiter.getOffset();              \r
    }\r
    \r
    /**\r
     * Trying out the substring and sees if it can be a canonical match.\r
     * This will try normalizing the starting accents and arranging them into \r
     * canonical equivalents and check their corresponding ces with the pattern \r
     * ce.\r
     * Prefix accents in the text will be grouped according to their combining \r
     * class and the groups will be mixed and matched to try find the perfect \r
     * match with the pattern.\r
     * So for instance looking for "\u0301" in "\u030A\u0301\u0325"\r
     * step 1: split "\u030A\u0301" into 6 other type of potential accent \r
     *            substrings\r
     *         "\u030A", "\u0301", "\u0325", "\u030A\u0301", "\u030A\u0325", \r
     *         "\u0301\u0325".\r
     * step 2: check if any of the generated substrings matches the pattern.\r
     * @param textoffset start offset in the collation element text that starts \r
     *                   with the accents to be rearranged\r
     * @return true if the match is valid, false otherwise\r
     */\r
    private boolean doPreviousCanonicalMatch(int textoffset)\r
    {\r
        int offset = m_colEIter_.getOffset();\r
        if ((getFCD(targetText, textoffset) >> SECOND_LAST_BYTE_SHIFT_) == 0) {\r
            if (m_pattern_.m_hasSuffixAccents_) {\r
                offset = doPreviousCanonicalSuffixMatch(textoffset, offset);\r
                if (offset != DONE) {\r
                    m_colEIter_.setExactOffset(offset);\r
                    return true;\r
                }\r
            }\r
            return false;\r
        }\r
    \r
        if (!m_pattern_.m_hasPrefixAccents_) {\r
            return false;\r
        }\r
    \r
        StringBuilder accents = new StringBuilder();\r
        // offset to the last base character in substring to search\r
        int baseoffset = getNextBaseOffset(targetText, textoffset);\r
        // normalizing the offensive string\r
        String textstr = getString(targetText, textoffset, \r
                                                    baseoffset - textoffset);\r
        if (Normalizer.quickCheck(textstr, Normalizer.NFD,0) \r
                                                    == Normalizer.NO) {\r
            textstr = Normalizer.decompose(textstr, false);\r
        }\r
        accents.append(textstr);\r
        // status checked in loop\r
            \r
        int accentsindex[] = new int[INITIAL_ARRAY_SIZE_];\r
        int size = getUnblockedAccentIndex(accents, accentsindex);\r
    \r
        // 2 power n - 1 plus the full set of accents\r
        int count = (2 << (size - 1)) - 1;  \r
        while (count > 0) {\r
            m_canonicalPrefixAccents_.delete(0, \r
                                        m_canonicalPrefixAccents_.length());\r
            // copy the base characters\r
            for (int k = 0; k < accentsindex[0]; k ++) {\r
                m_canonicalPrefixAccents_.append(accents.charAt(k));\r
            }\r
            // forming all possible canonical rearrangement by dropping\r
            // sets of accents\r
            for (int i = 0; i <= size - 1; i ++) {\r
                int mask = 1 << (size - i - 1);\r
                if ((count & mask) != 0) {\r
                    for (int j = accentsindex[i]; j < accentsindex[i + 1]; \r
                         j ++) {\r
                        m_canonicalPrefixAccents_.append(accents.charAt(j));\r
                    }\r
                }\r
            }\r
            offset = doPreviousCanonicalPrefixMatch(baseoffset);\r
            if (offset != DONE) {\r
                return true; // match found\r
            }\r
            count --;\r
        }\r
        return false;\r
    }\r
    \r
    /**\r
     * Checks match for contraction. \r
     * If the match starts with a partial contraction we fail.\r
     * Uses the temporary utility buffer to return the modified start and end.\r
     * @param start offset of potential match, to be modified if necessary\r
     * @param end offset of potential match, to be modified if necessary\r
     * @return true if match passes the contraction test, false otherwise.\r
     */\r
    private boolean checkPreviousCanonicalContractionMatch(int start, int end) \r
    {\r
        int temp = end;\r
        // This part checks if either ends of the match contains potential \r
        // contraction. If so we'll have to iterate through them\r
        char echar = 0;\r
        char schar = 0;\r
        if (end < m_textLimitOffset_) {\r
            targetText.setIndex(end);\r
            echar = targetText.current();\r
        }\r
        if (start + 1 < m_textLimitOffset_) {\r
            targetText.setIndex(start + 1);\r
            schar = targetText.current();\r
        }\r
        if (m_collator_.isUnsafe(echar) || m_collator_.isUnsafe(schar)) {\r
            int expansion = m_colEIter_.m_CEBufferSize_ \r
                                            - m_colEIter_.m_CEBufferOffset_;\r
            boolean hasExpansion = expansion > 0;\r
            m_colEIter_.setExactOffset(end);\r
            while (expansion > 0) {\r
                // getting rid of the redundant ce\r
                // since forward contraction/expansion may have extra ces\r
                // if we are in the normalization buffer, hasAccentsBeforeMatch\r
                // would have taken care of it.\r
                // E.g. the character \u01FA will have an expansion of 3, but \r
                // if we are only looking for A ring A\u030A, we'll have to \r
                // skip the last ce in the expansion buffer\r
                m_colEIter_.previous();\r
                if (m_colEIter_.getOffset() != temp) {\r
                    end = temp;\r
                    temp = m_colEIter_.getOffset();\r
                }\r
                expansion --;\r
            }\r
    \r
            int count = m_pattern_.m_CELength_;\r
            while (count > 0) {\r
                int ce = getCE(m_colEIter_.previous());\r
                // status checked below, note that if status is a failure\r
                // previous() returns NULLORDER\r
                if (ce == CollationElementIterator.IGNORABLE) {\r
                    continue;\r
                }\r
                if (hasExpansion && count == 0 \r
                    && m_colEIter_.getOffset() != temp) {\r
                    end = temp;\r
                    temp = m_colEIter_.getOffset();\r
                }\r
                if (count == m_pattern_.m_CELength_ \r
                    && ce != m_pattern_.m_CE_[m_pattern_.m_CELength_ - 1]) {\r
                    // accents may have extra starting ces, this occurs when a \r
                    // pure accent pattern is matched without rearrangement\r
                    int expected = m_pattern_.m_CE_[m_pattern_.m_CELength_ - 1];\r
                    targetText.setIndex(end);\r
                    if (UTF16.isTrailSurrogate(targetText.previous())) {\r
                        if (targetText.getIndex() > m_textBeginOffset_ &&\r
                            !UTF16.isLeadSurrogate(targetText.previous())) {\r
                            targetText.next();\r
                        }\r
                    }\r
                    end = targetText.getIndex();\r
                    if ((getFCD(targetText, end) & LAST_BYTE_MASK_) != 0) {\r
                        ce = getCE(m_colEIter_.previous());\r
                        while (ce != expected \r
                                && ce != CollationElementIterator.NULLORDER \r
                                && m_colEIter_.getOffset() <= start) {\r
                            ce = getCE(m_colEIter_.previous());\r
                        }\r
                    }\r
                }\r
                if (ce != m_pattern_.m_CE_[count - 1]) {\r
                    start --;\r
                    start = getPreviousBaseOffset(start);\r
                    m_utilBuffer_[0] = start;\r
                    m_utilBuffer_[1] = end;\r
                    return false;\r
                }\r
                count --;\r
            }\r
        } \r
        m_utilBuffer_[0] = start;\r
        m_utilBuffer_[1] = end;\r
        return true;\r
    }\r
    \r
    /**\r
     * Checks and sets the match information if found.\r
     * Checks \r
     * <ul>\r
     * <li> the potential match does not repeat the previous match\r
     * <li> boundaries are correct\r
     * <li> potential match does not end in the middle of a contraction\r
     * <li> identical matches\r
     * </ul>\r
     * Otherwise the offset will be shifted to the next character.\r
     * Uses the temporary utility buffer for storing the modified textoffset.\r
     * @param textoffset offset in the collation element text. the returned \r
     *             value will be the truncated start offset of the match or the \r
     *             new start search offset.\r
     * @return true if the match is valid, false otherwise\r
     */\r
    private boolean checkPreviousCanonicalMatch(int textoffset)\r
    {\r
        // to ensure that the start and ends are not composite characters\r
        // if we have a canonical accent match\r
        if (m_pattern_.m_hasSuffixAccents_ \r
            && m_canonicalSuffixAccents_.length() != 0 \r
            || m_pattern_.m_hasPrefixAccents_ \r
            && m_canonicalPrefixAccents_.length() != 0) {\r
            m_matchedIndex_ = textoffset;\r
            matchLength = getNextBaseOffset(m_colEIter_.getOffset()) \r
                                                                - textoffset;\r
            return true;\r
        }\r
    \r
        int end = m_colEIter_.getOffset();\r
        if (!checkPreviousCanonicalContractionMatch(textoffset, end)) {\r
            // storing the modified textoffset\r
            return false;\r
        }\r
        textoffset = m_utilBuffer_[0];\r
        end = m_utilBuffer_[1];\r
        end = getNextBaseOffset(end);\r
        // this totally matches, however we need to check if it is repeating\r
        if (checkRepeatedMatch(textoffset, end) \r
            || !isBreakUnit(textoffset, end) \r
            || !checkIdentical(textoffset, end)) {\r
            textoffset --;\r
            textoffset = getPreviousBaseOffset(textoffset);\r
            m_utilBuffer_[0] = textoffset;\r
            return false;\r
        }\r
        \r
        m_matchedIndex_ = textoffset;\r
        matchLength = end - textoffset;\r
        return true;\r
    }\r
    \r
    /**\r
     * Method that does the next exact match\r
     * @param start the offset to start shifting from and performing the \r
     *        next exact match\r
     */\r
    private void handleNextExact(int start)\r
    {\r
        int textoffset = shiftForward(start, \r
                                         CollationElementIterator.NULLORDER,\r
                                         m_pattern_.m_CELength_);\r
        int targetce = CollationElementIterator.IGNORABLE;\r
        while (textoffset <= m_textLimitOffset_) {\r
            m_colEIter_.setExactOffset(textoffset);\r
            int patternceindex = m_pattern_.m_CELength_ - 1;\r
            boolean found = false;\r
            int lastce = CollationElementIterator.NULLORDER;\r
            \r
            while (true) {\r
                // finding the last pattern ce match, imagine composite \r
                // characters. for example: search for pattern A in text \u00C0\r
                // we'll have to skip \u0300 the grave first before we get to A\r
                targetce = m_colEIter_.previous();\r
                if (targetce == CollationElementIterator.NULLORDER) {\r
                    found = false;\r
                    break;\r
                }\r
                targetce = getCE(targetce);\r
                if (targetce == CollationElementIterator.IGNORABLE && \r
                    m_colEIter_.isInBuffer()) { \r
                    // this is for the text \u0315\u0300 that requires \r
                    // normalization and pattern \u0300, where \u0315 is ignorable\r
                    continue;\r
                }\r
                if (lastce == CollationElementIterator.NULLORDER \r
                    || lastce == CollationElementIterator.IGNORABLE) {\r
                    lastce = targetce;\r
                }\r
                if (targetce == m_pattern_.m_CE_[patternceindex]) {\r
                    // the first ce can be a contraction\r
                    found = true;\r
                    break;\r
                }\r
                if (m_colEIter_.m_CEBufferOffset_ <= 0) {\r
                    found = false;\r
                    break;\r
                }\r
            }\r
    \r
            while (found && patternceindex > 0) {\r
                lastce = targetce;\r
                targetce = m_colEIter_.previous();\r
                if (targetce == CollationElementIterator.NULLORDER) {\r
                    found = false;\r
                    break;\r
                }\r
                targetce = getCE(targetce);\r
                if (targetce == CollationElementIterator.IGNORABLE) {\r
                    continue;\r
                }\r
    \r
                patternceindex --;\r
                found = found && targetce == m_pattern_.m_CE_[patternceindex]; \r
            }\r
            \r
            targetce = lastce;\r
    \r
            if (!found) {\r
                textoffset = shiftForward(textoffset, lastce, patternceindex);\r
                // status checked at loop.\r
                patternceindex = m_pattern_.m_CELength_;\r
                continue;\r
            }\r
            \r
            if (checkNextExactMatch(textoffset)) {\r
                // status checked in ucol_setOffset\r
                return;\r
            }\r
            textoffset = m_utilBuffer_[0];\r
        }\r
        setMatchNotFound();\r
    }\r
\r
    /**\r
     * Method that does the next canonical match\r
     * @param start the offset to start shifting from and performing the \r
     *        next canonical match\r
     */\r
    private void handleNextCanonical(int start)\r
    {\r
        boolean hasPatternAccents = \r
           m_pattern_.m_hasSuffixAccents_ || m_pattern_.m_hasPrefixAccents_;\r
              \r
        // shifting it check for setting offset\r
        // if setOffset is called previously or there was no previous match, we\r
        // leave the offset as it is.\r
        int textoffset = shiftForward(start, CollationElementIterator.NULLORDER, \r
                                        m_pattern_.m_CELength_);\r
        m_canonicalPrefixAccents_.delete(0, m_canonicalPrefixAccents_.length());\r
        m_canonicalSuffixAccents_.delete(0, m_canonicalSuffixAccents_.length());\r
        int targetce = CollationElementIterator.IGNORABLE;\r
        \r
        while (textoffset <= m_textLimitOffset_)\r
        {\r
            m_colEIter_.setExactOffset(textoffset);\r
            int patternceindex = m_pattern_.m_CELength_ - 1;\r
            boolean found = false;\r
            int lastce = CollationElementIterator.NULLORDER;\r
            \r
            while (true) {\r
                // finding the last pattern ce match, imagine composite characters\r
                // for example: search for pattern A in text \u00C0\r
                // we'll have to skip \u0300 the grave first before we get to A\r
                targetce = m_colEIter_.previous();\r
                if (targetce == CollationElementIterator.NULLORDER) {\r
                    found = false;\r
                    break;\r
                }\r
                targetce = getCE(targetce);\r
                if (lastce == CollationElementIterator.NULLORDER \r
                            || lastce == CollationElementIterator.IGNORABLE) {\r
                    lastce = targetce;\r
                }\r
                if (targetce == m_pattern_.m_CE_[patternceindex]) {\r
                    // the first ce can be a contraction\r
                    found = true;\r
                    break;\r
                }\r
                if (m_colEIter_.m_CEBufferOffset_ <= 0) {\r
                    found = false;\r
                    break;\r
                }\r
            }\r
            \r
            while (found && patternceindex > 0) {\r
                targetce    = m_colEIter_.previous();\r
                if (targetce == CollationElementIterator.NULLORDER) {\r
                    found = false;\r
                    break;\r
                }\r
                targetce    = getCE(targetce);\r
                if (targetce == CollationElementIterator.IGNORABLE) {\r
                    continue;\r
                }\r
    \r
                patternceindex --;\r
                found = found && targetce == m_pattern_.m_CE_[patternceindex]; \r
            }\r
    \r
            // initializing the rearranged accent array\r
            if (hasPatternAccents && !found) {\r
                found = doNextCanonicalMatch(textoffset);\r
            }\r
    \r
            if (!found) {\r
                textoffset = shiftForward(textoffset, lastce, patternceindex);\r
                // status checked at loop\r
                patternceindex = m_pattern_.m_CELength_;\r
                continue;\r
            }\r
            \r
            if (checkNextCanonicalMatch(textoffset)) {\r
                return;\r
            }\r
            textoffset = m_utilBuffer_[0];\r
        }\r
        setMatchNotFound();\r
    }\r
    \r
    /**\r
     * Method that does the previous exact match\r
     * @param start the offset to start shifting from and performing the \r
     *        previous exact match\r
     */\r
    private void handlePreviousExact(int start)\r
    {\r
        int textoffset = reverseShift(start, CollationElementIterator.NULLORDER, \r
                                      m_pattern_.m_CELength_);\r
        while (textoffset >= m_textBeginOffset_)\r
        {\r
            m_colEIter_.setExactOffset(textoffset);\r
            int patternceindex = 1;\r
            int targetce = CollationElementIterator.IGNORABLE;\r
            boolean found = false;\r
            int firstce = CollationElementIterator.NULLORDER;\r
            \r
            while (true) {\r
                // finding the first pattern ce match, imagine composite \r
                // characters. for example: search for pattern \u0300 in text \r
                // \u00C0, we'll have to skip A first before we get to \r
                // \u0300 the grave accent\r
                targetce = m_colEIter_.next();\r
                if (targetce == CollationElementIterator.NULLORDER) {\r
                    found = false;\r
                    break;\r
                }\r
                targetce = getCE(targetce);\r
                if (firstce == CollationElementIterator.NULLORDER \r
                    || firstce == CollationElementIterator.IGNORABLE) {\r
                    firstce = targetce;\r
                }\r
                if (targetce == CollationElementIterator.IGNORABLE && m_collator_.getStrength() != Collator.PRIMARY) {\r
                    continue;\r
                }         \r
                if (targetce == m_pattern_.m_CE_[0]) {\r
                    found = true;\r
                    break;\r
                }\r
                if (m_colEIter_.m_CEBufferOffset_ == -1 \r
                    || m_colEIter_.m_CEBufferOffset_ \r
                                            == m_colEIter_.m_CEBufferSize_) {\r
                    // checking for accents in composite character\r
                    found = false;\r
                    break;\r
                }\r
            }\r
    \r
            //targetce = firstce;\r
            \r
            while (found && patternceindex < m_pattern_.m_CELength_) {\r
                firstce = targetce;\r
                targetce = m_colEIter_.next();\r
                if (targetce == CollationElementIterator.NULLORDER) {\r
                    found = false;\r
                    break;\r
                }\r
                targetce = getCE(targetce);\r
                if (targetce == CollationElementIterator.IGNORABLE) {\r
                    continue;\r
                }\r
    \r
                found = found && targetce == m_pattern_.m_CE_[patternceindex]; \r
                patternceindex ++;\r
            }\r
            \r
            targetce = firstce;\r
    \r
            if (!found) {\r
                textoffset = reverseShift(textoffset, targetce, patternceindex);\r
                patternceindex = 0;\r
                continue;\r
            }\r
            \r
            if (checkPreviousExactMatch(textoffset)) {\r
                return;\r
            }\r
            textoffset = m_utilBuffer_[0];\r
        }\r
        setMatchNotFound();\r
    }\r
    \r
    /**\r
     * Method that does the previous canonical match\r
     * @param start the offset to start shifting from and performing the \r
     *        previous canonical match\r
     */\r
    private void handlePreviousCanonical(int start)\r
    {\r
        boolean hasPatternAccents = \r
           m_pattern_.m_hasSuffixAccents_ || m_pattern_.m_hasPrefixAccents_;\r
              \r
        // shifting it check for setting offset\r
        // if setOffset is called previously or there was no previous match, we\r
        // leave the offset as it is.\r
        int textoffset = reverseShift(start, CollationElementIterator.NULLORDER, \r
                                          m_pattern_.m_CELength_);\r
        m_canonicalPrefixAccents_.delete(0, m_canonicalPrefixAccents_.length());\r
        m_canonicalSuffixAccents_.delete(0, m_canonicalSuffixAccents_.length());\r
        \r
        while (textoffset >= m_textBeginOffset_)\r
        {\r
            m_colEIter_.setExactOffset(textoffset);\r
            int patternceindex = 1;\r
            int targetce = CollationElementIterator.IGNORABLE;\r
            boolean found = false;\r
            int firstce = CollationElementIterator.NULLORDER;\r
            \r
            while (true) {\r
                // finding the first pattern ce match, imagine composite \r
                // characters. for example: search for pattern \u0300 in text \r
                // \u00C0, we'll have to skip A first before we get to \r
                // \u0300 the grave accent\r
                targetce = m_colEIter_.next();\r
                if (targetce == CollationElementIterator.NULLORDER) {\r
                    found = false;\r
                    break;\r
                }\r
                targetce = getCE(targetce);\r
                if (firstce == CollationElementIterator.NULLORDER \r
                    || firstce == CollationElementIterator.IGNORABLE) {\r
                    firstce = targetce;\r
                }\r
                \r
                if (targetce == m_pattern_.m_CE_[0]) {\r
                    // the first ce can be a contraction\r
                    found = true;\r
                    break;\r
                }\r
                if (m_colEIter_.m_CEBufferOffset_ == -1 \r
                    || m_colEIter_.m_CEBufferOffset_ \r
                                            == m_colEIter_.m_CEBufferSize_) {\r
                    // checking for accents in composite character\r
                    found = false;\r
                    break;\r
                }\r
            }\r
    \r
            targetce = firstce;\r
            \r
            while (found && patternceindex < m_pattern_.m_CELength_) {\r
                targetce = m_colEIter_.next();\r
                if (targetce == CollationElementIterator.NULLORDER) {\r
                    found = false;\r
                    break;\r
                }\r
                targetce = getCE(targetce);\r
                if (targetce == CollationElementIterator.IGNORABLE) {\r
                    continue;\r
                }\r
    \r
                found = found && targetce == m_pattern_.m_CE_[patternceindex]; \r
                patternceindex ++;\r
            }\r
    \r
            // initializing the rearranged accent array\r
            if (hasPatternAccents && !found) {\r
                found = doPreviousCanonicalMatch(textoffset);\r
            }\r
    \r
            if (!found) {\r
                textoffset = reverseShift(textoffset, targetce, patternceindex);\r
                patternceindex = 0;\r
                continue;\r
            }\r
    \r
            if (checkPreviousCanonicalMatch(textoffset)) {\r
                return;\r
            }\r
            textoffset = m_utilBuffer_[0];\r
        }\r
        setMatchNotFound();\r
    }\r
    \r
    /**\r
     * Gets a substring out of a CharacterIterator\r
     * @param text CharacterIterator\r
     * @param start start offset\r
     * @param length of substring\r
     * @return substring from text starting at start and length length\r
     */\r
    private static final String getString(CharacterIterator text, int start,\r
                                            int length)\r
    {\r
        StringBuilder result = new StringBuilder(length);\r
        int offset = text.getIndex();\r
        text.setIndex(start);\r
        for (int i = 0; i < length; i ++) {\r
            result.append(text.current());\r
            text.next();\r
        }\r
        text.setIndex(offset);\r
        return result.toString();\r
    }\r
    \r
    /**\r
     * Getting the mask for collation strength\r
     * @param strength collation strength\r
      * @return collation element mask\r
     */\r
    private static final int getMask(int strength) \r
    {\r
        switch (strength) \r
        {\r
            case Collator.PRIMARY:\r
                return RuleBasedCollator.CE_PRIMARY_MASK_;\r
            case Collator.SECONDARY:\r
                return RuleBasedCollator.CE_SECONDARY_MASK_ \r
                       | RuleBasedCollator.CE_PRIMARY_MASK_;\r
            default:\r
                return RuleBasedCollator.CE_TERTIARY_MASK_ \r
                       | RuleBasedCollator.CE_SECONDARY_MASK_ \r
                       | RuleBasedCollator.CE_PRIMARY_MASK_;\r
        }\r
    }\r
    \r
    /**\r
     * Sets match not found \r
     */\r
    private void setMatchNotFound() \r
    {\r
        // this method resets the match result regardless of the error status.\r
        m_matchedIndex_ = DONE;\r
        setMatchLength(0);\r
    }\r
    \r
    /**\r
     * Check the boundaries of the match.\r
     */\r
    private int checkBreakBoundary(int end) {\r
        if (!m_charBreakIter_.isBoundary(end)) {\r
            end = m_charBreakIter_.following(end);\r
        }\r
        return end;\r
    }\r
}\r