icuSources/i18n/unicode/stsearch.h

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