jpayne@69: // © 2016 and later: Unicode, Inc. and others. jpayne@69: // License & terms of use: http://www.unicode.org/copyright.html jpayne@69: jpayne@69: // edits.h jpayne@69: // created: 2016dec30 Markus W. Scherer jpayne@69: jpayne@69: #ifndef __EDITS_H__ jpayne@69: #define __EDITS_H__ jpayne@69: jpayne@69: #include "unicode/utypes.h" jpayne@69: jpayne@69: #if U_SHOW_CPLUSPLUS_API jpayne@69: jpayne@69: #include "unicode/uobject.h" jpayne@69: jpayne@69: /** jpayne@69: * \file jpayne@69: * \brief C++ API: C++ class Edits for low-level string transformations on styled text. jpayne@69: */ jpayne@69: jpayne@69: U_NAMESPACE_BEGIN jpayne@69: jpayne@69: class UnicodeString; jpayne@69: jpayne@69: /** jpayne@69: * Records lengths of string edits but not replacement text. Supports replacements, insertions, deletions jpayne@69: * in linear progression. Does not support moving/reordering of text. jpayne@69: * jpayne@69: * There are two types of edits: change edits and no-change edits. Add edits to jpayne@69: * instances of this class using {@link #addReplace(int32_t, int32_t)} (for change edits) and jpayne@69: * {@link #addUnchanged(int32_t)} (for no-change edits). Change edits are retained with full granularity, jpayne@69: * whereas adjacent no-change edits are always merged together. In no-change edits, there is a one-to-one jpayne@69: * mapping between code points in the source and destination strings. jpayne@69: * jpayne@69: * After all edits have been added, instances of this class should be considered immutable, and an jpayne@69: * {@link Edits::Iterator} can be used for queries. jpayne@69: * jpayne@69: * There are four flavors of Edits::Iterator: jpayne@69: * jpayne@69: * jpayne@69: * jpayne@69: * For example, consider the string "abcßDeF", which case-folds to "abcssdef". This string has the jpayne@69: * following fine edits: jpayne@69: * jpayne@69: * and the following coarse edits (note how adjacent change edits get merged together): jpayne@69: * jpayne@69: * jpayne@69: * The "fine changes" and "coarse changes" iterators will step through only the change edits when their jpayne@69: * `Edits::Iterator::next()` methods are called. They are identical to the non-change iterators when jpayne@69: * their `Edits::Iterator::findSourceIndex()` or `Edits::Iterator::findDestinationIndex()` jpayne@69: * methods are used to walk through the string. jpayne@69: * jpayne@69: * For examples of how to use this class, see the test `TestCaseMapEditsIteratorDocs` in jpayne@69: * UCharacterCaseTest.java. jpayne@69: * jpayne@69: * An Edits object tracks a separate UErrorCode, but ICU string transformation functions jpayne@69: * (e.g., case mapping functions) merge any such errors into their API's UErrorCode. jpayne@69: * jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: class U_COMMON_API Edits U_FINAL : public UMemory { jpayne@69: public: jpayne@69: /** jpayne@69: * Constructs an empty object. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: Edits() : jpayne@69: array(stackArray), capacity(STACK_CAPACITY), length(0), delta(0), numChanges(0), jpayne@69: errorCode_(U_ZERO_ERROR) {} jpayne@69: /** jpayne@69: * Copy constructor. jpayne@69: * @param other source edits jpayne@69: * @stable ICU 60 jpayne@69: */ jpayne@69: Edits(const Edits &other) : jpayne@69: array(stackArray), capacity(STACK_CAPACITY), length(other.length), jpayne@69: delta(other.delta), numChanges(other.numChanges), jpayne@69: errorCode_(other.errorCode_) { jpayne@69: copyArray(other); jpayne@69: } jpayne@69: /** jpayne@69: * Move constructor, might leave src empty. jpayne@69: * This object will have the same contents that the source object had. jpayne@69: * @param src source edits jpayne@69: * @stable ICU 60 jpayne@69: */ jpayne@69: Edits(Edits &&src) U_NOEXCEPT : jpayne@69: array(stackArray), capacity(STACK_CAPACITY), length(src.length), jpayne@69: delta(src.delta), numChanges(src.numChanges), jpayne@69: errorCode_(src.errorCode_) { jpayne@69: moveArray(src); jpayne@69: } jpayne@69: jpayne@69: /** jpayne@69: * Destructor. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: ~Edits(); jpayne@69: jpayne@69: /** jpayne@69: * Assignment operator. jpayne@69: * @param other source edits jpayne@69: * @return *this jpayne@69: * @stable ICU 60 jpayne@69: */ jpayne@69: Edits &operator=(const Edits &other); jpayne@69: jpayne@69: /** jpayne@69: * Move assignment operator, might leave src empty. jpayne@69: * This object will have the same contents that the source object had. jpayne@69: * The behavior is undefined if *this and src are the same object. jpayne@69: * @param src source edits jpayne@69: * @return *this jpayne@69: * @stable ICU 60 jpayne@69: */ jpayne@69: Edits &operator=(Edits &&src) U_NOEXCEPT; jpayne@69: jpayne@69: /** jpayne@69: * Resets the data but may not release memory. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: void reset() U_NOEXCEPT; jpayne@69: jpayne@69: /** jpayne@69: * Adds a no-change edit: a record for an unchanged segment of text. jpayne@69: * Normally called from inside ICU string transformation functions, not user code. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: void addUnchanged(int32_t unchangedLength); jpayne@69: /** jpayne@69: * Adds a change edit: a record for a text replacement/insertion/deletion. jpayne@69: * Normally called from inside ICU string transformation functions, not user code. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: void addReplace(int32_t oldLength, int32_t newLength); jpayne@69: /** jpayne@69: * Sets the UErrorCode if an error occurred while recording edits. jpayne@69: * Preserves older error codes in the outErrorCode. jpayne@69: * Normally called from inside ICU string transformation functions, not user code. jpayne@69: * @param outErrorCode Set to an error code if it does not contain one already jpayne@69: * and an error occurred while recording edits. jpayne@69: * Otherwise unchanged. jpayne@69: * @return TRUE if U_FAILURE(outErrorCode) jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: UBool copyErrorTo(UErrorCode &outErrorCode) const; jpayne@69: jpayne@69: /** jpayne@69: * How much longer is the new text compared with the old text? jpayne@69: * @return new length minus old length jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: int32_t lengthDelta() const { return delta; } jpayne@69: /** jpayne@69: * @return TRUE if there are any change edits jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: UBool hasChanges() const { return numChanges != 0; } jpayne@69: jpayne@69: /** jpayne@69: * @return the number of change edits jpayne@69: * @stable ICU 60 jpayne@69: */ jpayne@69: int32_t numberOfChanges() const { return numChanges; } jpayne@69: jpayne@69: /** jpayne@69: * Access to the list of edits. jpayne@69: * jpayne@69: * At any moment in time, an instance of this class points to a single edit: a "window" into a span jpayne@69: * of the source string and the corresponding span of the destination string. The source string span jpayne@69: * starts at {@link #sourceIndex()} and runs for {@link #oldLength()} chars; the destination string jpayne@69: * span starts at {@link #destinationIndex()} and runs for {@link #newLength()} chars. jpayne@69: * jpayne@69: * The iterator can be moved between edits using the `next()`, `findSourceIndex(int32_t, UErrorCode &)`, jpayne@69: * and `findDestinationIndex(int32_t, UErrorCode &)` methods. jpayne@69: * Calling any of these methods mutates the iterator to make it point to the corresponding edit. jpayne@69: * jpayne@69: * For more information, see the documentation for {@link Edits}. jpayne@69: * jpayne@69: * @see getCoarseIterator jpayne@69: * @see getFineIterator jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: struct U_COMMON_API Iterator U_FINAL : public UMemory { jpayne@69: /** jpayne@69: * Default constructor, empty iterator. jpayne@69: * @stable ICU 60 jpayne@69: */ jpayne@69: Iterator() : jpayne@69: array(nullptr), index(0), length(0), jpayne@69: remaining(0), onlyChanges_(FALSE), coarse(FALSE), jpayne@69: dir(0), changed(FALSE), oldLength_(0), newLength_(0), jpayne@69: srcIndex(0), replIndex(0), destIndex(0) {} jpayne@69: /** jpayne@69: * Copy constructor. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: Iterator(const Iterator &other) = default; jpayne@69: /** jpayne@69: * Assignment operator. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: Iterator &operator=(const Iterator &other) = default; jpayne@69: jpayne@69: /** jpayne@69: * Advances the iterator to the next edit. jpayne@69: * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test, jpayne@69: * or else the function returns immediately. Check for U_FAILURE() jpayne@69: * on output or use with function chaining. (See User Guide for details.) jpayne@69: * @return TRUE if there is another edit jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: UBool next(UErrorCode &errorCode) { return next(onlyChanges_, errorCode); } jpayne@69: jpayne@69: /** jpayne@69: * Moves the iterator to the edit that contains the source index. jpayne@69: * The source index may be found in a no-change edit jpayne@69: * even if normal iteration would skip no-change edits. jpayne@69: * Normal iteration can continue from a found edit. jpayne@69: * jpayne@69: * The iterator state before this search logically does not matter. jpayne@69: * (It may affect the performance of the search.) jpayne@69: * jpayne@69: * The iterator state after this search is undefined jpayne@69: * if the source index is out of bounds for the source string. jpayne@69: * jpayne@69: * @param i source index jpayne@69: * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test, jpayne@69: * or else the function returns immediately. Check for U_FAILURE() jpayne@69: * on output or use with function chaining. (See User Guide for details.) jpayne@69: * @return TRUE if the edit for the source index was found jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: UBool findSourceIndex(int32_t i, UErrorCode &errorCode) { jpayne@69: return findIndex(i, TRUE, errorCode) == 0; jpayne@69: } jpayne@69: jpayne@69: /** jpayne@69: * Moves the iterator to the edit that contains the destination index. jpayne@69: * The destination index may be found in a no-change edit jpayne@69: * even if normal iteration would skip no-change edits. jpayne@69: * Normal iteration can continue from a found edit. jpayne@69: * jpayne@69: * The iterator state before this search logically does not matter. jpayne@69: * (It may affect the performance of the search.) jpayne@69: * jpayne@69: * The iterator state after this search is undefined jpayne@69: * if the source index is out of bounds for the source string. jpayne@69: * jpayne@69: * @param i destination index jpayne@69: * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test, jpayne@69: * or else the function returns immediately. Check for U_FAILURE() jpayne@69: * on output or use with function chaining. (See User Guide for details.) jpayne@69: * @return TRUE if the edit for the destination index was found jpayne@69: * @stable ICU 60 jpayne@69: */ jpayne@69: UBool findDestinationIndex(int32_t i, UErrorCode &errorCode) { jpayne@69: return findIndex(i, FALSE, errorCode) == 0; jpayne@69: } jpayne@69: jpayne@69: /** jpayne@69: * Computes the destination index corresponding to the given source index. jpayne@69: * If the source index is inside a change edit (not at its start), jpayne@69: * then the destination index at the end of that edit is returned, jpayne@69: * since there is no information about index mapping inside a change edit. jpayne@69: * jpayne@69: * (This means that indexes to the start and middle of an edit, jpayne@69: * for example around a grapheme cluster, are mapped to indexes jpayne@69: * encompassing the entire edit. jpayne@69: * The alternative, mapping an interior index to the start, jpayne@69: * would map such an interval to an empty one.) jpayne@69: * jpayne@69: * This operation will usually but not always modify this object. jpayne@69: * The iterator state after this search is undefined. jpayne@69: * jpayne@69: * @param i source index jpayne@69: * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test, jpayne@69: * or else the function returns immediately. Check for U_FAILURE() jpayne@69: * on output or use with function chaining. (See User Guide for details.) jpayne@69: * @return destination index; undefined if i is not 0..string length jpayne@69: * @stable ICU 60 jpayne@69: */ jpayne@69: int32_t destinationIndexFromSourceIndex(int32_t i, UErrorCode &errorCode); jpayne@69: jpayne@69: /** jpayne@69: * Computes the source index corresponding to the given destination index. jpayne@69: * If the destination index is inside a change edit (not at its start), jpayne@69: * then the source index at the end of that edit is returned, jpayne@69: * since there is no information about index mapping inside a change edit. jpayne@69: * jpayne@69: * (This means that indexes to the start and middle of an edit, jpayne@69: * for example around a grapheme cluster, are mapped to indexes jpayne@69: * encompassing the entire edit. jpayne@69: * The alternative, mapping an interior index to the start, jpayne@69: * would map such an interval to an empty one.) jpayne@69: * jpayne@69: * This operation will usually but not always modify this object. jpayne@69: * The iterator state after this search is undefined. jpayne@69: * jpayne@69: * @param i destination index jpayne@69: * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test, jpayne@69: * or else the function returns immediately. Check for U_FAILURE() jpayne@69: * on output or use with function chaining. (See User Guide for details.) jpayne@69: * @return source index; undefined if i is not 0..string length jpayne@69: * @stable ICU 60 jpayne@69: */ jpayne@69: int32_t sourceIndexFromDestinationIndex(int32_t i, UErrorCode &errorCode); jpayne@69: jpayne@69: /** jpayne@69: * Returns whether the edit currently represented by the iterator is a change edit. jpayne@69: * jpayne@69: * @return TRUE if this edit replaces oldLength() units with newLength() different ones. jpayne@69: * FALSE if oldLength units remain unchanged. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: UBool hasChange() const { return changed; } jpayne@69: jpayne@69: /** jpayne@69: * The length of the current span in the source string, which starts at {@link #sourceIndex}. jpayne@69: * jpayne@69: * @return the number of units in the original string which are replaced or remain unchanged. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: int32_t oldLength() const { return oldLength_; } jpayne@69: jpayne@69: /** jpayne@69: * The length of the current span in the destination string, which starts at jpayne@69: * {@link #destinationIndex}, or in the replacement string, which starts at jpayne@69: * {@link #replacementIndex}. jpayne@69: * jpayne@69: * @return the number of units in the modified string, if hasChange() is TRUE. jpayne@69: * Same as oldLength if hasChange() is FALSE. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: int32_t newLength() const { return newLength_; } jpayne@69: jpayne@69: /** jpayne@69: * The start index of the current span in the source string; the span has length jpayne@69: * {@link #oldLength}. jpayne@69: * jpayne@69: * @return the current index into the source string jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: int32_t sourceIndex() const { return srcIndex; } jpayne@69: jpayne@69: /** jpayne@69: * The start index of the current span in the replacement string; the span has length jpayne@69: * {@link #newLength}. Well-defined only if the current edit is a change edit. jpayne@69: * jpayne@69: * The *replacement string* is the concatenation of all substrings of the destination jpayne@69: * string corresponding to change edits. jpayne@69: * jpayne@69: * This method is intended to be used together with operations that write only replacement jpayne@69: * characters (e.g. operations specifying the \ref U_OMIT_UNCHANGED_TEXT option). jpayne@69: * The source string can then be modified in-place. jpayne@69: * jpayne@69: * @return the current index into the replacement-characters-only string, jpayne@69: * not counting unchanged spans jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: int32_t replacementIndex() const { jpayne@69: // TODO: Throw an exception if we aren't in a change edit? jpayne@69: return replIndex; jpayne@69: } jpayne@69: jpayne@69: /** jpayne@69: * The start index of the current span in the destination string; the span has length jpayne@69: * {@link #newLength}. jpayne@69: * jpayne@69: * @return the current index into the full destination string jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: int32_t destinationIndex() const { return destIndex; } jpayne@69: jpayne@69: #ifndef U_HIDE_INTERNAL_API jpayne@69: /** jpayne@69: * A string representation of the current edit represented by the iterator for debugging. You jpayne@69: * should not depend on the contents of the return string. jpayne@69: * @internal jpayne@69: */ jpayne@69: UnicodeString& toString(UnicodeString& appendTo) const; jpayne@69: #endif // U_HIDE_INTERNAL_API jpayne@69: jpayne@69: private: jpayne@69: friend class Edits; jpayne@69: jpayne@69: Iterator(const uint16_t *a, int32_t len, UBool oc, UBool crs); jpayne@69: jpayne@69: int32_t readLength(int32_t head); jpayne@69: void updateNextIndexes(); jpayne@69: void updatePreviousIndexes(); jpayne@69: UBool noNext(); jpayne@69: UBool next(UBool onlyChanges, UErrorCode &errorCode); jpayne@69: UBool previous(UErrorCode &errorCode); jpayne@69: /** @return -1: error or i<0; 0: found; 1: i>=string length */ jpayne@69: int32_t findIndex(int32_t i, UBool findSource, UErrorCode &errorCode); jpayne@69: jpayne@69: const uint16_t *array; jpayne@69: int32_t index, length; jpayne@69: // 0 if we are not within compressed equal-length changes. jpayne@69: // Otherwise the number of remaining changes, including the current one. jpayne@69: int32_t remaining; jpayne@69: UBool onlyChanges_, coarse; jpayne@69: jpayne@69: int8_t dir; // iteration direction: back(<0), initial(0), forward(>0) jpayne@69: UBool changed; jpayne@69: int32_t oldLength_, newLength_; jpayne@69: int32_t srcIndex, replIndex, destIndex; jpayne@69: }; jpayne@69: jpayne@69: /** jpayne@69: * Returns an Iterator for coarse-grained change edits jpayne@69: * (adjacent change edits are treated as one). jpayne@69: * Can be used to perform simple string updates. jpayne@69: * Skips no-change edits. jpayne@69: * @return an Iterator that merges adjacent changes. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: Iterator getCoarseChangesIterator() const { jpayne@69: return Iterator(array, length, TRUE, TRUE); jpayne@69: } jpayne@69: jpayne@69: /** jpayne@69: * Returns an Iterator for coarse-grained change and no-change edits jpayne@69: * (adjacent change edits are treated as one). jpayne@69: * Can be used to perform simple string updates. jpayne@69: * Adjacent change edits are treated as one edit. jpayne@69: * @return an Iterator that merges adjacent changes. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: Iterator getCoarseIterator() const { jpayne@69: return Iterator(array, length, FALSE, TRUE); jpayne@69: } jpayne@69: jpayne@69: /** jpayne@69: * Returns an Iterator for fine-grained change edits jpayne@69: * (full granularity of change edits is retained). jpayne@69: * Can be used for modifying styled text. jpayne@69: * Skips no-change edits. jpayne@69: * @return an Iterator that separates adjacent changes. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: Iterator getFineChangesIterator() const { jpayne@69: return Iterator(array, length, TRUE, FALSE); jpayne@69: } jpayne@69: jpayne@69: /** jpayne@69: * Returns an Iterator for fine-grained change and no-change edits jpayne@69: * (full granularity of change edits is retained). jpayne@69: * Can be used for modifying styled text. jpayne@69: * @return an Iterator that separates adjacent changes. jpayne@69: * @stable ICU 59 jpayne@69: */ jpayne@69: Iterator getFineIterator() const { jpayne@69: return Iterator(array, length, FALSE, FALSE); jpayne@69: } jpayne@69: jpayne@69: /** jpayne@69: * Merges the two input Edits and appends the result to this object. jpayne@69: * jpayne@69: * Consider two string transformations (for example, normalization and case mapping) jpayne@69: * where each records Edits in addition to writing an output string.
jpayne@69: * Edits ab reflect how substrings of input string a jpayne@69: * map to substrings of intermediate string b.
jpayne@69: * Edits bc reflect how substrings of intermediate string b jpayne@69: * map to substrings of output string c.
jpayne@69: * This function merges ab and bc such that the additional edits jpayne@69: * recorded in this object reflect how substrings of input string a jpayne@69: * map to substrings of output string c. jpayne@69: * jpayne@69: * If unrelated Edits are passed in where the output string of the first jpayne@69: * has a different length than the input string of the second, jpayne@69: * then a U_ILLEGAL_ARGUMENT_ERROR is reported. jpayne@69: * jpayne@69: * @param ab reflects how substrings of input string a jpayne@69: * map to substrings of intermediate string b. jpayne@69: * @param bc reflects how substrings of intermediate string b jpayne@69: * map to substrings of output string c. jpayne@69: * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test, jpayne@69: * or else the function returns immediately. Check for U_FAILURE() jpayne@69: * on output or use with function chaining. (See User Guide for details.) jpayne@69: * @return *this, with the merged edits appended jpayne@69: * @stable ICU 60 jpayne@69: */ jpayne@69: Edits &mergeAndAppend(const Edits &ab, const Edits &bc, UErrorCode &errorCode); jpayne@69: jpayne@69: private: jpayne@69: void releaseArray() U_NOEXCEPT; jpayne@69: Edits ©Array(const Edits &other); jpayne@69: Edits &moveArray(Edits &src) U_NOEXCEPT; jpayne@69: jpayne@69: void setLastUnit(int32_t last) { array[length - 1] = (uint16_t)last; } jpayne@69: int32_t lastUnit() const { return length > 0 ? array[length - 1] : 0xffff; } jpayne@69: jpayne@69: void append(int32_t r); jpayne@69: UBool growArray(); jpayne@69: jpayne@69: static const int32_t STACK_CAPACITY = 100; jpayne@69: uint16_t *array; jpayne@69: int32_t capacity; jpayne@69: int32_t length; jpayne@69: int32_t delta; jpayne@69: int32_t numChanges; jpayne@69: UErrorCode errorCode_; jpayne@69: uint16_t stackArray[STACK_CAPACITY]; jpayne@69: }; jpayne@69: jpayne@69: U_NAMESPACE_END jpayne@69: jpayne@69: #endif /* U_SHOW_CPLUSPLUS_API */ jpayne@69: jpayne@69: #endif // __EDITS_H__