icuSources/i18n/unicode/stsearch.h

   1 /*
   2 **********************************************************************
   3 *   Copyright (C) 2001-2004 IBM and others. All rights reserved.
   4 **********************************************************************
   5 *   Date        Name        Description
   6 *  03/22/2000   helena      Creation.
   7 **********************************************************************
   8 */
   9
  10 #ifndef STSEARCH_H
  11 #define STSEARCH_H
  12
  13 #include "unicode/utypes.h"
  14
  15 #if !UCONFIG_NO_COLLATION
  16
  17 #include "unicode/tblcoll.h"
  18 #include "unicode/coleitr.h"
  19 #include "unicode/search.h"
  20
  21 U_NAMESPACE_BEGIN
  22
  23 /**
  24  * <tt>StringSearch</tt> is a <tt>SearchIterator</tt> that provides
  25  * language-sensitive text searching based on the comparison rules defined
  26  * in a {@link RuleBasedCollator} object.
  27  * StringSearch ensures that language eccentricity can be
  28  * handled, e.g. for the German collator, characters ß and SS will be matched
  29  * if case is chosen to be ignored.
  30  * See the <a href="http://oss.software.ibm.com/cvs/icu/~checkout~/icuhtml/design/collation/ICU_collation_design.htm">
  31  * "ICU Collation Design Document"</a> for more information.
  32  * <p>
  33  * The algorithm implemented is a modified form of the Boyer Moore's search.
  34  * For more information  see
  35  * <a href=http://oss.software.ibm.com/icu/docs/papers/efficient_text_searching_in_java.html>
  36  * "Efficient Text Searching in Java"</a>, published in <i>Java Report</i>
  37  * in February, 1999, for further information on the algorithm.
  38  * <p>
  39  * There are 2 match options for selection:<br>
  40  * Let S' be the sub-string of a text string S between the offsets start and
  41  * end <start, end>.
  42  * <br>
  43  * A pattern string P matches a text string S at the offsets <start, end>
  44  * if
  45  * <pre>
  46  * option 1. Some canonical equivalent of P matches some canonical equivalent
  47  *           of S'
  48  * option 2. P matches S' and if P starts or ends with a combining mark,
  49  *           there exists no non-ignorable combining mark before or after S?
  50  *           in S respectively.
  51  * </pre>
  52  * Option 2. will be the default·
  53  * <p>
  54  * This search has APIs similar to that of other text iteration mechanisms
  55  * such as the break iterators in <tt>BreakIterator</tt>. Using these
  56  * APIs, it is easy to scan through text looking for all occurances of
  57  * a given pattern. This search iterator allows changing of direction by
  58  * calling a <tt>reset</tt> followed by a <tt>next</tt> or <tt>previous</tt>.
  59  * Though a direction change can occur without calling <tt>reset</tt> first,
  60  * this operation comes with some speed penalty.
  61  * Match results in the forward direction will match the result matches in
  62  * the backwards direction in the reverse order
  63  * <p>
  64  * <tt>SearchIterator</tt> provides APIs to specify the starting position
  65  * within the text string to be searched, e.g. <tt>setOffset</tt>,
  66  * <tt>preceding</tt> and <tt>following</tt>. Since the
  67  * starting position will be set as it is specified, please take note that
  68  * there are some danger points which the search may render incorrect
  69  * results:
  70  * <ul>
  71  * <li> The midst of a substring that requires normalization.
  72  * <li> If the following match is to be found, the position should not be the
  73  *      second character which requires to be swapped with the preceding
  74  *      character. Vice versa, if the preceding match is to be found,
  75  *      position to search from should not be the first character which
  76  *      requires to be swapped with the next character. E.g certain Thai and
  77  *      Lao characters require swapping.
  78  * <li> If a following pattern match is to be found, any position within a
  79  *      contracting sequence except the first will fail. Vice versa if a
  80  *      preceding pattern match is to be found, a invalid starting point
  81  *      would be any character within a contracting sequence except the last.
  82  * </ul>
  83  * <p>
  84  * A breakiterator can be used if only matches at logical breaks are desired.
  85  * Using a breakiterator will only give you results that exactly matches the
  86  * boundaries given by the breakiterator. For instance the pattern "e" will
  87  * not be found in the string "\u00e9" if a character break iterator is used.
  88  * <p>
  89  * Options are provided to handle overlapping matches.
  90  * E.g. In English, overlapping matches produces the result 0 and 2
  91  * for the pattern "abab" in the text "ababab", where else mutually
  92  * exclusive matches only produce the result of 0.
  93  * <p>
  94  * Though collator attributes will be taken into consideration while
  95  * performing matches, there are no APIs here for setting and getting the
  96  * attributes. These attributes can be set by getting the collator
  97  * from <tt>getCollator</tt> and using the APIs in <tt>coll.h</tt>.
  98  * Lastly to update StringSearch to the new collator attributes,
  99  * reset() has to be called.
 100  * <p>
 101  * Restriction: <br>
 102  * Currently there are no composite characters that consists of a
 103  * character with combining class > 0 before a character with combining
 104  * class == 0. However, if such a character exists in the future,
 105  * StringSearch does not guarantee the results for option 1.
 106  * <p>
 107  * Consult the <tt>SearchIterator</tt> documentation for information on
 108  * and examples of how to use instances of this class to implement text
 109  * searching.
 110  * <pre><code>
 111  * UnicodeString target("The quick brown fox jumped over the lazy fox");
 112  * UnicodeString pattern("fox");
 113  *
 114  * SearchIterator *iter  = new StringSearch(pattern, target);
 115  * UErrorCode      error = U_ZERO_ERROR;
 116  * for (int pos = iter->first(error); pos != USEARCH_DONE;
 117  *                               pos = iter->next(error)) {
 118  *     printf("Found match at %d pos, length is %d\n", pos,
 119  *                                             iter.getMatchLength());
 120  * }
 121  * </code></pre>
 122  * <p>
 123  * Note, StringSearch is not to be subclassed.
 124  * </p>
 125  * @see SearchIterator
 126  * @see RuleBasedCollator
 127  * @since ICU 2.0
 128  */
 129
 130 class U_I18N_API StringSearch : public SearchIterator
 131 {
 132 public:
 133
 134     // public constructors and destructors --------------------------------
 135
 136     /**
 137      * Creating a <tt>StringSearch</tt> instance using the argument locale
 138      * language rule set. A collator will be created in the process, which
 139      * will be owned by this instance and will be deleted during
 140      * destruction
 141      * @param pattern The text for which this object will search.
 142      * @param text    The text in which to search for the pattern.
 143      * @param locale  A locale which defines the language-sensitive
 144      *                comparison rules used to determine whether text in the
 145      *                pattern and target matches.
 146      * @param breakiter A <tt>BreakIterator</tt> object used to constrain
 147      *                the matches that are found. Matches whose start and end
 148      *                indices in the target text are not boundaries as
 149      *                determined by the <tt>BreakIterator</tt> are
 150      *                ignored. If this behavior is not desired,
 151      *                <tt>NULL</tt> can be passed in instead.
 152      * @param status  for errors if any. If pattern or text is NULL, or if
 153      *               either the length of pattern or text is 0 then an
 154      *               U_ILLEGAL_ARGUMENT_ERROR is returned.
 155      * @stable ICU 2.0
 156      */
 157     StringSearch(const UnicodeString &pattern, const UnicodeString &text,
 158                  const Locale        &locale,
 159                        BreakIterator *breakiter,
 160                        UErrorCode    &status);
 161
 162     /**
 163      * Creating a <tt>StringSearch</tt> instance using the argument collator
 164      * language rule set. Note, user retains the ownership of this collator,
 165      * it does not get destroyed during this instance's destruction.
 166      * @param pattern The text for which this object will search.
 167      * @param text    The text in which to search for the pattern.
 168      * @param coll    A <tt>RuleBasedCollator</tt> object which defines
 169      *                the language-sensitive comparison rules used to
 170      *                determine whether text in the pattern and target
 171      *                matches. User is responsible for the clearing of this
 172      *                object.
 173      * @param breakiter A <tt>BreakIterator</tt> object used to constrain
 174      *                the matches that are found. Matches whose start and end
 175      *                indices in the target text are not boundaries as
 176      *                determined by the <tt>BreakIterator</tt> are
 177      *                ignored. If this behavior is not desired,
 178      *                <tt>NULL</tt> can be passed in instead.
 179      * @param status for errors if any. If either the length of pattern or
 180      *               text is 0 then an U_ILLEGAL_ARGUMENT_ERROR is returned.
 181      * @stable ICU 2.0
 182      */
 183     StringSearch(const UnicodeString     &pattern,
 184                  const UnicodeString     &text,
 185                        RuleBasedCollator *coll,
 186                        BreakIterator     *breakiter,
 187                        UErrorCode        &status);
 188
 189     /**
 190      * Creating a <tt>StringSearch</tt> instance using the argument locale
 191      * language rule set. A collator will be created in the process, which
 192      * will be owned by this instance and will be deleted during
 193      * destruction
 194      * <p>
 195      * Note: No parsing of the text within the <tt>CharacterIterator</tt>
 196      * will be done during searching for this version. The block of text
 197      * in <tt>CharacterIterator</tt> will be used as it is.
 198      * @param pattern The text for which this object will search.
 199      * @param text    The text iterator in which to search for the pattern.
 200      * @param locale  A locale which defines the language-sensitive
 201      *                comparison rules used to determine whether text in the
 202      *                pattern and target matches. User is responsible for
 203      *                the clearing of this object.
 204      * @param breakiter A <tt>BreakIterator</tt> object used to constrain
 205      *                the matches that are found. Matches whose start and end
 206      *                indices in the target text are not boundaries as
 207      *                determined by the <tt>BreakIterator</tt> are
 208      *                ignored. If this behavior is not desired,
 209      *                <tt>NULL</tt> can be passed in instead.
 210      * @param status for errors if any. If either the length of pattern or
 211      *               text is 0 then an U_ILLEGAL_ARGUMENT_ERROR is returned.
 212      * @stable ICU 2.0
 213      */
 214     StringSearch(const UnicodeString &pattern, CharacterIterator &text,
 215                  const Locale        &locale,
 216                        BreakIterator *breakiter,
 217                        UErrorCode    &status);
 218
 219     /**
 220      * Creating a <tt>StringSearch</tt> instance using the argument collator
 221      * language rule set. Note, user retains the ownership of this collator,
 222      * it does not get destroyed during this instance's destruction.
 223      * <p>
 224      * Note: No parsing of the text within the <tt>CharacterIterator</tt>
 225      * will be done during searching for this version. The block of text
 226      * in <tt>CharacterIterator</tt> will be used as it is.
 227      * @param pattern The text for which this object will search.
 228      * @param text    The text in which to search for the pattern.
 229      * @param coll    A <tt>RuleBasedCollator</tt> object which defines
 230      *                the language-sensitive comparison rules used to
 231      *                determine whether text in the pattern and target
 232      *                matches. User is responsible for the clearing of this
 233      *                object.
 234      * @param breakiter A <tt>BreakIterator</tt> object used to constrain
 235      *                the matches that are found. Matches whose start and end
 236      *                indices in the target text are not boundaries as
 237      *                determined by the <tt>BreakIterator</tt> are
 238      *                ignored. If this behavior is not desired,
 239      *                <tt>NULL</tt> can be passed in instead.
 240      * @param status for errors if any. If either the length of pattern or
 241      *               text is 0 then an U_ILLEGAL_ARGUMENT_ERROR is returned.
 242      * @stable ICU 2.0
 243      */
 244     StringSearch(const UnicodeString     &pattern, CharacterIterator &text,
 245                        RuleBasedCollator *coll,
 246                        BreakIterator     *breakiter,
 247                        UErrorCode        &status);
 248
 249     /**
 250      * Copy constructor that creates a StringSearch instance with the same
 251      * behavior, and iterating over the same text.
 252      * @param that StringSearch instance to be copied.
 253      * @stable ICU 2.0
 254      */
 255     StringSearch(const StringSearch &that);
 256
 257     /**
 258     * Destructor. Cleans up the search iterator data struct.
 259     * If a collator is created in the constructor, it will be destroyed here.
 260     * @stable ICU 2.0
 261     */
 262     virtual ~StringSearch(void);
 263
 264     /**
 265      * Clone this object.
 266      * Clones can be used concurrently in multiple threads.
 267      * If an error occurs, then NULL is returned.
 268      * The caller must delete the clone.
 269      *
 270      * @return a clone of this object
 271      *
 272      * @see getDynamicClassID
 273      * @draft ICU 2.8
 274      */
 275     StringSearch *clone() const;
 276
 277     // operator overloading ---------------------------------------------
 278
 279     /**
 280      * Assignment operator. Sets this iterator to have the same behavior,
 281      * and iterate over the same text, as the one passed in.
 282      * @param that instance to be copied.
 283      * @stable ICU 2.0
 284      */
 285     StringSearch & operator=(const StringSearch &that);
 286
 287     /**
 288      * Equality operator.
 289      * @param that instance to be compared.
 290      * @return TRUE if both instances have the same attributes,
 291      *         breakiterators, collators and iterate over the same text
 292      *         while looking for the same pattern.
 293      * @stable ICU 2.0
 294      */
 295     virtual UBool operator==(const SearchIterator &that) const;
 296
 297     // public get and set methods ----------------------------------------
 298
 299     /**
 300      * Sets the index to point to the given position, and clears any state
 301      * that's affected.
 302      * <p>
 303      * This method takes the argument index and sets the position in the text
 304      * string accordingly without checking if the index is pointing to a
 305      * valid starting point to begin searching.
 306      * @param position within the text to be set. If position is less
 307      *          than or greater than the text range for searching,
 308      *          an U_INDEX_OUTOFBOUNDS_ERROR will be returned
 309      * @param status for errors if it occurs
 310      * @stable ICU 2.0
 311      */
 312     virtual void setOffset(int32_t position, UErrorCode &status);
 313
 314     /**
 315      * Return the current index in the text being searched.
 316      * If the iteration has gone past the end of the text
 317      * (or past the beginning for a backwards search), USEARCH_DONE
 318      * is returned.
 319      * @return current index in the text being searched.
 320      * @stable ICU 2.0
 321      */
 322     virtual int32_t getOffset(void) const;
 323
 324     /**
 325      * Set the target text to be searched.
 326      * Text iteration will hence begin at the start of the text string.
 327      * This method is
 328      * useful if you want to re-use an iterator to search for the same
 329      * pattern within a different body of text.
 330      * @param text text string to be searched
 331      * @param status for errors if any. If the text length is 0 then an
 332      *        U_ILLEGAL_ARGUMENT_ERROR is returned.
 333      * @stable ICU 2.0
 334      */
 335     virtual void setText(const UnicodeString &text, UErrorCode &status);
 336
 337     /**
 338      * Set the target text to be searched.
 339      * Text iteration will hence begin at the start of the text string.
 340      * This method is
 341      * useful if you want to re-use an iterator to search for the same
 342      * pattern within a different body of text.
 343      * Note: No parsing of the text within the <tt>CharacterIterator</tt>
 344      * will be done during searching for this version. The block of text
 345      * in <tt>CharacterIterator</tt> will be used as it is.
 346      * @param text text string to be searched
 347      * @param status for errors if any. If the text length is 0 then an
 348      *        U_ILLEGAL_ARGUMENT_ERROR is returned.
 349      * @stable ICU 2.0
 350      */
 351     virtual void setText(CharacterIterator &text, UErrorCode &status);
 352
 353     /**
 354      * Gets the collator used for the language rules.
 355      * <p>
 356      * Caller may modify but <b>must not</b> delete the <tt>RuleBasedCollator</tt>!
 357      * Modifications to this collator will affect the original collator passed in to
 358      * the <tt>StringSearch></tt> constructor or to setCollator, if any.
 359      * @return collator used for string search
 360      * @stable ICU 2.0
 361      */
 362     RuleBasedCollator * getCollator() const;
 363
 364     /**
 365      * Sets the collator used for the language rules. User retains the
 366      * ownership of this collator, thus the responsibility of deletion lies
 367      * with the user. This method causes internal data such as Boyer-Moore
 368      * shift tables to be recalculated, but the iterator's position is
 369      * unchanged.
 370      * @param coll    collator
 371      * @param status  for errors if any
 372      * @stable ICU 2.0
 373      */
 374     void setCollator(RuleBasedCollator *coll, UErrorCode &status);
 375
 376     /**
 377      * Sets the pattern used for matching.
 378      * Internal data like the Boyer Moore table will be recalculated, but
 379      * the iterator's position is unchanged.
 380      * @param pattern search pattern to be found
 381      * @param status for errors if any. If the pattern length is 0 then an
 382      *               U_ILLEGAL_ARGUMENT_ERROR is returned.
 383      * @stable ICU 2.0
 384      */
 385     void setPattern(const UnicodeString &pattern, UErrorCode &status);
 386
 387     /**
 388      * Gets the search pattern.
 389      * @return pattern used for matching
 390      * @stable ICU 2.0
 391      */
 392     const UnicodeString & getPattern() const;
 393
 394     // public methods ----------------------------------------------------
 395
 396     /**
 397      * Reset the iteration.
 398      * Search will begin at the start of the text string if a forward
 399      * iteration is initiated before a backwards iteration. Otherwise if
 400      * a backwards iteration is initiated before a forwards iteration, the
 401      * search will begin at the end of the text string.
 402      * @stable ICU 2.0
 403      */
 404     virtual void reset();
 405
 406     /**
 407      * Returns a copy of StringSearch with the same behavior, and
 408      * iterating over the same text, as this one. Note that all data will be
 409      * replicated, except for the user-specified collator and the
 410      * breakiterator.
 411      * @return cloned object
 412      * @stable ICU 2.0
 413      */
 414     virtual SearchIterator * safeClone(void) const;
 415
 416     /**
 417      * ICU "poor man's RTTI", returns a UClassID for the actual class.
 418      *
 419      * @stable ICU 2.2
 420      */
 421     virtual UClassID getDynamicClassID() const;
 422
 423     /**
 424      * ICU "poor man's RTTI", returns a UClassID for this class.
 425      *
 426      * @stable ICU 2.2
 427      */
 428     static UClassID U_EXPORT2 getStaticClassID();
 429
 430 protected:
 431
 432     // protected method -------------------------------------------------
 433
 434     /**
 435      * Search forward for matching text, starting at a given location.
 436      * Clients should not call this method directly; instead they should
 437      * call {@link SearchIterator#next }.
 438      * <p>
 439      * If a match is found, this method returns the index at which the match
 440      * starts and calls {@link SearchIterator#setMatchLength } with the number
 441      * of characters in the target text that make up the match. If no match
 442      * is found, the method returns <tt>USEARCH_DONE</tt>.
 443      * <p>
 444      * The <tt>StringSearch</tt> is adjusted so that its current index
 445      * (as returned by {@link #getOffset }) is the match position if one was
 446      * found.
 447      * If a match is not found, <tt>USEARCH_DONE</tt> will be returned and
 448      * the <tt>StringSearch</tt> will be adjusted to the index USEARCH_DONE.
 449      * @param position The index in the target text at which the search
 450      *                 starts
 451      * @param status for errors if any occurs
 452      * @return The index at which the matched text in the target starts, or
 453      *         USEARCH_DONE if no match was found.
 454      * @stable ICU 2.0
 455      */
 456     virtual int32_t handleNext(int32_t position, UErrorCode &status);
 457
 458     /**
 459      * Search backward for matching text, starting at a given location.
 460      * Clients should not call this method directly; instead they should call
 461      * <tt>SearchIterator.previous()</tt>, which this method overrides.
 462      * <p>
 463      * If a match is found, this method returns the index at which the match
 464      * starts and calls {@link SearchIterator#setMatchLength } with the number
 465      * of characters in the target text that make up the match. If no match
 466      * is found, the method returns <tt>USEARCH_DONE</tt>.
 467      * <p>
 468      * The <tt>StringSearch</tt> is adjusted so that its current index
 469      * (as returned by {@link #getOffset }) is the match position if one was
 470      * found.
 471      * If a match is not found, <tt>USEARCH_DONE</tt> will be returned and
 472      * the <tt>StringSearch</tt> will be adjusted to the index USEARCH_DONE.
 473      * @param position The index in the target text at which the search
 474      *                 starts.
 475      * @param status for errors if any occurs
 476      * @return The index at which the matched text in the target starts, or
 477      *         USEARCH_DONE if no match was found.
 478      * @stable ICU 2.0
 479      */
 480     virtual int32_t handlePrev(int32_t position, UErrorCode &status);
 481
 482 private :
 483     StringSearch(); // default constructor not implemented
 484
 485     // private data members ----------------------------------------------
 486
 487     /**
 488     * RuleBasedCollator, contains exactly the same UCollator * in m_strsrch_
 489     * @stable ICU 2.0
 490     */
 491     RuleBasedCollator  m_collator_;
 492     /**
 493     * Pattern text
 494     * @stable ICU 2.0
 495     */
 496     UnicodeString      m_pattern_;
 497     /**
 498     * Corresponding collation rules
 499     * @stable ICU 2.0
 500     */
 501     UnicodeString      m_collation_rules_;
 502     /**
 503     * String search struct data
 504     * @stable ICU 2.0
 505     */
 506     UStringSearch     *m_strsrch_;
 507
 508 };
 509
 510 U_NAMESPACE_END
 511
 512 #endif /* #if !UCONFIG_NO_COLLATION */
 513
 514 #endif
 515