Source/WTF/icu/unicode/edits.h - WebKit - Git at Google

 // © 2016 and later: Unicode, Inc. and others.
 // License & terms of use: http://www.unicode.org/copyright.html

 // edits.h
 // created: 2016dec30 Markus W. Scherer

 #ifndef __EDITS_H__
 #define __EDITS_H__

 #include "unicode/utypes.h"
 #include "unicode/uobject.h"

 /**
  * \file
  * \brief C++ API: C++ class Edits for low-level string transformations on styled text.
  */

 U_NAMESPACE_BEGIN

 class UnicodeString;

 /**
  * Records lengths of string edits but not replacement text. Supports replacements, insertions, deletions
  * in linear progression. Does not support moving/reordering of text.
  *
  * There are two types of edits: <em>change edits</em> and <em>no-change edits</em>. Add edits to
  * instances of this class using {@link #addReplace(int, int)} (for change edits) and
  * {@link #addUnchanged(int)} (for no-change edits). Change edits are retained with full granularity,
  * whereas adjacent no-change edits are always merged together. In no-change edits, there is a one-to-one
  * mapping between code points in the source and destination strings.
  *
  * After all edits have been added, instances of this class should be considered immutable, and an
  * {@link Edits::Iterator} can be used for queries.
  *
  * There are four flavors of Edits::Iterator:
  *
  * <ul>
  * <li>{@link #getFineIterator()} retains full granularity of change edits.
  * <li>{@link #getFineChangesIterator()} retains full granularity of change edits, and when calling
  * next() on the iterator, skips over no-change edits (unchanged regions).
  * <li>{@link #getCoarseIterator()} treats adjacent change edits as a single edit. (Adjacent no-change
  * edits are automatically merged during the construction phase.)
  * <li>{@link #getCoarseChangesIterator()} treats adjacent change edits as a single edit, and when
  * calling next() on the iterator, skips over no-change edits (unchanged regions).
  * </ul>
  *
  * For example, consider the string "abcßDeF", which case-folds to "abcssdef". This string has the
  * following fine edits:
  * <ul>
  * <li>abc ⇨ abc (no-change)
  * <li>ß ⇨ ss (change)
  * <li>D ⇨ d (change)
  * <li>e ⇨ e (no-change)
  * <li>F ⇨ f (change)
  * </ul>
  * and the following coarse edits (note how adjacent change edits get merged together):
  * <ul>
  * <li>abc ⇨ abc (no-change)
  * <li>ßD ⇨ ssd (change)
  * <li>e ⇨ e (no-change)
  * <li>F ⇨ f (change)
  * </ul>
  *
  * The "fine changes" and "coarse changes" iterators will step through only the change edits when their
  * {@link Edits::Iterator#next()} methods are called. They are identical to the non-change iterators when
  * their {@link Edits::Iterator#findSourceIndex(int)} or {@link Edits::Iterator#findDestinationIndex(int)}
  * methods are used to walk through the string.
  *
  * For examples of how to use this class, see the test <code>TestCaseMapEditsIteratorDocs</code> in
  * UCharacterCaseTest.java.
  *
  * An Edits object tracks a separate UErrorCode, but ICU string transformation functions
  * (e.g., case mapping functions) merge any such errors into their API's UErrorCode.
  *
  * @stable ICU 59
  */
 class U_COMMON_API Edits U_FINAL : public UMemory {
 public:
     /**
      * Constructs an empty object.
      * @stable ICU 59
      */
     Edits() :
             array(stackArray), capacity(STACK_CAPACITY), length(0), delta(0), numChanges(0),
             errorCode_(U_ZERO_ERROR) {}
     /**
      * Copy constructor.
      * @param other source edits
      * @draft ICU 60
      */
     Edits(const Edits &other) :
             array(stackArray), capacity(STACK_CAPACITY), length(other.length),
             delta(other.delta), numChanges(other.numChanges),
             errorCode_(other.errorCode_) {
         copyArray(other);
     }
     /**
      * Move constructor, might leave src empty.
      * This object will have the same contents that the source object had.
      * @param src source edits
      * @draft ICU 60
      */
     Edits(Edits &&src) U_NOEXCEPT :
             array(stackArray), capacity(STACK_CAPACITY), length(src.length),
             delta(src.delta), numChanges(src.numChanges),
             errorCode_(src.errorCode_) {
         moveArray(src);
     }

     /**
      * Destructor.
      * @stable ICU 59
      */
     ~Edits();

     /**
      * Assignment operator.
      * @param other source edits
      * @return *this
      * @draft ICU 60
      */
     Edits &operator=(const Edits &other);

     /**
      * Move assignment operator, might leave src empty.
      * This object will have the same contents that the source object had.
      * The behavior is undefined if *this and src are the same object.
      * @param src source edits
      * @return *this
      * @draft ICU 60
      */
     Edits &operator=(Edits &&src) U_NOEXCEPT;

     /**
      * Resets the data but may not release memory.
      * @stable ICU 59
      */
     void reset() U_NOEXCEPT;

     /**
      * Adds a no-change edit: a record for an unchanged segment of text.
      * Normally called from inside ICU string transformation functions, not user code.
      * @stable ICU 59
      */
     void addUnchanged(int32_t unchangedLength);
     /**
      * Adds a change edit: a record for a text replacement/insertion/deletion.
      * Normally called from inside ICU string transformation functions, not user code.
      * @stable ICU 59
      */
     void addReplace(int32_t oldLength, int32_t newLength);
     /**
      * Sets the UErrorCode if an error occurred while recording edits.
      * Preserves older error codes in the outErrorCode.
      * Normally called from inside ICU string transformation functions, not user code.
      * @param outErrorCode Set to an error code if it does not contain one already
      *                  and an error occurred while recording edits.
      *                  Otherwise unchanged.
      * @return TRUE if U_FAILURE(outErrorCode)
      * @stable ICU 59
      */
     UBool copyErrorTo(UErrorCode &outErrorCode);

     /**
      * How much longer is the new text compared with the old text?
      * @return new length minus old length
      * @stable ICU 59
      */
     int32_t lengthDelta() const { return delta; }
     /**
      * @return TRUE if there are any change edits
      * @stable ICU 59
      */
     UBool hasChanges() const { return numChanges != 0; }

 #ifndef U_HIDE_DRAFT_API
     /**
      * @return the number of change edits
      * @draft ICU 60
      */
     int32_t numberOfChanges() const { return numChanges; }
 #endif  // U_HIDE_DRAFT_API

     /**
      * Access to the list of edits.
      *
      * At any moment in time, an instance of this class points to a single edit: a "window" into a span
      * of the source string and the corresponding span of the destination string. The source string span
      * starts at {@link #sourceIndex()} and runs for {@link #oldLength()} chars; the destination string
      * span starts at {@link #destinationIndex()} and runs for {@link #newLength()} chars.
      *
      * The iterator can be moved between edits using the {@link #next()}, {@link #findSourceIndex(int)},
      * and {@link #findDestinationIndex(int)} methods. Calling any of these methods mutates the iterator
      * to make it point to the corresponding edit.
      *
      * For more information, see the documentation for {@link Edits}.
      *
      * @see getCoarseIterator
      * @see getFineIterator
      * @stable ICU 59
      */
     struct U_COMMON_API Iterator U_FINAL : public UMemory {
         /**
          * Default constructor, empty iterator.
          * @draft ICU 60
          */
         Iterator() :
                 array(nullptr), index(0), length(0),
                 remaining(0), onlyChanges_(FALSE), coarse(FALSE),
                 dir(0), changed(FALSE), oldLength_(0), newLength_(0),
                 srcIndex(0), replIndex(0), destIndex(0) {}
         /**
          * Copy constructor.
          * @stable ICU 59
          */
         Iterator(const Iterator &other) = default;
         /**
          * Assignment operator.
          * @stable ICU 59
          */
         Iterator &operator=(const Iterator &other) = default;

         /**
          * Advances the iterator to the next edit.
          * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
          *                  or else the function returns immediately. Check for U_FAILURE()
          *                  on output or use with function chaining. (See User Guide for details.)
          * @return TRUE if there is another edit
          * @stable ICU 59
          */
         UBool next(UErrorCode &errorCode) { return next(onlyChanges_, errorCode); }

         /**
          * Moves the iterator to the edit that contains the source index.
          * The source index may be found in a no-change edit
          * even if normal iteration would skip no-change edits.
          * Normal iteration can continue from a found edit.
          *
          * The iterator state before this search logically does not matter.
          * (It may affect the performance of the search.)
          *
          * The iterator state after this search is undefined
          * if the source index is out of bounds for the source string.
          *
          * @param i source index
          * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
          *                  or else the function returns immediately. Check for U_FAILURE()
          *                  on output or use with function chaining. (See User Guide for details.)
          * @return TRUE if the edit for the source index was found
          * @stable ICU 59
          */
         UBool findSourceIndex(int32_t i, UErrorCode &errorCode) {
             return findIndex(i, TRUE, errorCode) == 0;
         }

 #ifndef U_HIDE_DRAFT_API
         /**
          * Moves the iterator to the edit that contains the destination index.
          * The destination index may be found in a no-change edit
          * even if normal iteration would skip no-change edits.
          * Normal iteration can continue from a found edit.
          *
          * The iterator state before this search logically does not matter.
          * (It may affect the performance of the search.)
          *
          * The iterator state after this search is undefined
          * if the source index is out of bounds for the source string.
          *
          * @param i destination index
          * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
          *                  or else the function returns immediately. Check for U_FAILURE()
          *                  on output or use with function chaining. (See User Guide for details.)
          * @return TRUE if the edit for the destination index was found
          * @draft ICU 60
          */
         UBool findDestinationIndex(int32_t i, UErrorCode &errorCode) {
             return findIndex(i, FALSE, errorCode) == 0;
         }

         /**
          * Computes the destination index corresponding to the given source index.
          * If the source index is inside a change edit (not at its start),
          * then the destination index at the end of that edit is returned,
          * since there is no information about index mapping inside a change edit.
          *
          * (This means that indexes to the start and middle of an edit,
          * for example around a grapheme cluster, are mapped to indexes
          * encompassing the entire edit.
          * The alternative, mapping an interior index to the start,
          * would map such an interval to an empty one.)
          *
          * This operation will usually but not always modify this object.
          * The iterator state after this search is undefined.
          *
          * @param i source index
          * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
          *                  or else the function returns immediately. Check for U_FAILURE()
          *                  on output or use with function chaining. (See User Guide for details.)
          * @return destination index; undefined if i is not 0..string length
          * @draft ICU 60
          */
         int32_t destinationIndexFromSourceIndex(int32_t i, UErrorCode &errorCode);

         /**
          * Computes the source index corresponding to the given destination index.
          * If the destination index is inside a change edit (not at its start),
          * then the source index at the end of that edit is returned,
          * since there is no information about index mapping inside a change edit.
          *
          * (This means that indexes to the start and middle of an edit,
          * for example around a grapheme cluster, are mapped to indexes
          * encompassing the entire edit.
          * The alternative, mapping an interior index to the start,
          * would map such an interval to an empty one.)
          *
          * This operation will usually but not always modify this object.
          * The iterator state after this search is undefined.
          *
          * @param i destination index
          * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
          *                  or else the function returns immediately. Check for U_FAILURE()
          *                  on output or use with function chaining. (See User Guide for details.)
          * @return source index; undefined if i is not 0..string length
          * @draft ICU 60
          */
         int32_t sourceIndexFromDestinationIndex(int32_t i, UErrorCode &errorCode);
 #endif  // U_HIDE_DRAFT_API

         /**
          * Returns whether the edit currently represented by the iterator is a change edit.
          *
          * @return TRUE if this edit replaces oldLength() units with newLength() different ones.
          *         FALSE if oldLength units remain unchanged.
          * @stable ICU 59
          */
         UBool hasChange() const { return changed; }

         /**
          * The length of the current span in the source string, which starts at {@link #sourceIndex}.
          *
          * @return the number of units in the original string which are replaced or remain unchanged.
          * @stable ICU 59
          */
         int32_t oldLength() const { return oldLength_; }

         /**
          * The length of the current span in the destination string, which starts at
          * {@link #destinationIndex}, or in the replacement string, which starts at
          * {@link #replacementIndex}.
          *
          * @return the number of units in the modified string, if hasChange() is TRUE.
          *         Same as oldLength if hasChange() is FALSE.
          * @stable ICU 59
          */
         int32_t newLength() const { return newLength_; }

         /**
          * The start index of the current span in the source string; the span has length
          * {@link #oldLength}.
          *
          * @return the current index into the source string
          * @stable ICU 59
          */
         int32_t sourceIndex() const { return srcIndex; }

         /**
          * The start index of the current span in the replacement string; the span has length
          * {@link #newLength}. Well-defined only if the current edit is a change edit.
          * <p>
          * The <em>replacement string</em> is the concatenation of all substrings of the destination
          * string corresponding to change edits.
          * <p>
          * This method is intended to be used together with operations that write only replacement
          * characters (e.g., {@link CaseMap#omitUnchangedText()}). The source string can then be modified
          * in-place.
          *
          * @return the current index into the replacement-characters-only string,
          *         not counting unchanged spans
          * @stable ICU 59
          */
         int32_t replacementIndex() const {
             // TODO: Throw an exception if we aren't in a change edit?
             return replIndex;
         }

         /**
          * The start index of the current span in the destination string; the span has length
          * {@link #newLength}.
          *
          * @return the current index into the full destination string
          * @stable ICU 59
          */
         int32_t destinationIndex() const { return destIndex; }

 #ifndef U_HIDE_INTERNAL_API
         /**
          * A string representation of the current edit represented by the iterator for debugging. You
          * should not depend on the contents of the return string.
          * @internal
          */
         UnicodeString& toString(UnicodeString& appendTo) const;
 #endif  // U_HIDE_INTERNAL_API

     private:
         friend class Edits;

         Iterator(const uint16_t *a, int32_t len, UBool oc, UBool crs);

         int32_t readLength(int32_t head);
         void updateNextIndexes();
         void updatePreviousIndexes();
         UBool noNext();
         UBool next(UBool onlyChanges, UErrorCode &errorCode);
         UBool previous(UErrorCode &errorCode);
         /** @return -1: error or i<0; 0: found; 1: i>=string length */
         int32_t findIndex(int32_t i, UBool findSource, UErrorCode &errorCode);

         const uint16_t *array;
         int32_t index, length;
         // 0 if we are not within compressed equal-length changes.
         // Otherwise the number of remaining changes, including the current one.
         int32_t remaining;
         UBool onlyChanges_, coarse;

         int8_t dir;  // iteration direction: back(<0), initial(0), forward(>0)
         UBool changed;
         int32_t oldLength_, newLength_;
         int32_t srcIndex, replIndex, destIndex;
     };

     /**
      * Returns an Iterator for coarse-grained change edits
      * (adjacent change edits are treated as one).
      * Can be used to perform simple string updates.
      * Skips no-change edits.
      * @return an Iterator that merges adjacent changes.
      * @stable ICU 59
      */
     Iterator getCoarseChangesIterator() const {
         return Iterator(array, length, TRUE, TRUE);
     }

     /**
      * Returns an Iterator for coarse-grained change and no-change edits
      * (adjacent change edits are treated as one).
      * Can be used to perform simple string updates.
      * Adjacent change edits are treated as one edit.
      * @return an Iterator that merges adjacent changes.
      * @stable ICU 59
      */
     Iterator getCoarseIterator() const {
         return Iterator(array, length, FALSE, TRUE);
     }

     /**
      * Returns an Iterator for fine-grained change edits
      * (full granularity of change edits is retained).
      * Can be used for modifying styled text.
      * Skips no-change edits.
      * @return an Iterator that separates adjacent changes.
      * @stable ICU 59
      */
     Iterator getFineChangesIterator() const {
         return Iterator(array, length, TRUE, FALSE);
     }

     /**
      * Returns an Iterator for fine-grained change and no-change edits
      * (full granularity of change edits is retained).
      * Can be used for modifying styled text.
      * @return an Iterator that separates adjacent changes.
      * @stable ICU 59
      */
     Iterator getFineIterator() const {
         return Iterator(array, length, FALSE, FALSE);
     }

 #ifndef U_HIDE_DRAFT_API
     /**
      * Merges the two input Edits and appends the result to this object.
      *
      * Consider two string transformations (for example, normalization and case mapping)
      * where each records Edits in addition to writing an output string.<br>
      * Edits ab reflect how substrings of input string a
      * map to substrings of intermediate string b.<br>
      * Edits bc reflect how substrings of intermediate string b
      * map to substrings of output string c.<br>
      * This function merges ab and bc such that the additional edits
      * recorded in this object reflect how substrings of input string a
      * map to substrings of output string c.
      *
      * If unrelated Edits are passed in where the output string of the first
      * has a different length than the input string of the second,
      * then a U_ILLEGAL_ARGUMENT_ERROR is reported.
      *
      * @param ab reflects how substrings of input string a
      *     map to substrings of intermediate string b.
      * @param bc reflects how substrings of intermediate string b
      *     map to substrings of output string c.
      * @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
      *                  or else the function returns immediately. Check for U_FAILURE()
      *                  on output or use with function chaining. (See User Guide for details.)
      * @return *this, with the merged edits appended
      * @draft ICU 60
      */
     Edits &mergeAndAppend(const Edits &ab, const Edits &bc, UErrorCode &errorCode);
 #endif  // U_HIDE_DRAFT_API

 private:
     void releaseArray() U_NOEXCEPT;
     Edits &copyArray(const Edits &other);
     Edits &moveArray(Edits &src) U_NOEXCEPT;

     void setLastUnit(int32_t last) { array[length - 1] = (uint16_t)last; }
     int32_t lastUnit() const { return length > 0 ? array[length - 1] : 0xffff; }

     void append(int32_t r);
     UBool growArray();

     static const int32_t STACK_CAPACITY = 100;
     uint16_t *array;
     int32_t capacity;
     int32_t length;
     int32_t delta;
     int32_t numChanges;
     UErrorCode errorCode_;
     uint16_t stackArray[STACK_CAPACITY];
 };

 U_NAMESPACE_END

 #endif  // __EDITS_H__
	// © 2016 and later: Unicode, Inc. and others.
	// License & terms of use: http://www.unicode.org/copyright.html

	// edits.h
	// created: 2016dec30 Markus W. Scherer

	#ifndef __EDITS_H__
	#define __EDITS_H__

	#include "unicode/utypes.h"
	#include "unicode/uobject.h"

	/**
	* \file
	* \brief C++ API: C++ class Edits for low-level string transformations on styled text.
	*/

	U_NAMESPACE_BEGIN

	class UnicodeString;

	/**
	* Records lengths of string edits but not replacement text. Supports replacements, insertions, deletions
	* in linear progression. Does not support moving/reordering of text.
	*
	* There are two types of edits: <em>change edits</em> and <em>no-change edits</em>. Add edits to
	* instances of this class using {@link #addReplace(int, int)} (for change edits) and
	* {@link #addUnchanged(int)} (for no-change edits). Change edits are retained with full granularity,
	* whereas adjacent no-change edits are always merged together. In no-change edits, there is a one-to-one
	* mapping between code points in the source and destination strings.
	*
	* After all edits have been added, instances of this class should be considered immutable, and an
	* {@link Edits::Iterator} can be used for queries.
	*
	* There are four flavors of Edits::Iterator:
	*
	* <ul>
	* <li>{@link #getFineIterator()} retains full granularity of change edits.
	* <li>{@link #getFineChangesIterator()} retains full granularity of change edits, and when calling
	* next() on the iterator, skips over no-change edits (unchanged regions).
	* <li>{@link #getCoarseIterator()} treats adjacent change edits as a single edit. (Adjacent no-change
	* edits are automatically merged during the construction phase.)
	* <li>{@link #getCoarseChangesIterator()} treats adjacent change edits as a single edit, and when
	* calling next() on the iterator, skips over no-change edits (unchanged regions).
	* </ul>
	*
	* For example, consider the string "abcßDeF", which case-folds to "abcssdef". This string has the
	* following fine edits:
	* <ul>
	* <li>abc ⇨ abc (no-change)
	* <li>ß ⇨ ss (change)
	* <li>D ⇨ d (change)
	* <li>e ⇨ e (no-change)
	* <li>F ⇨ f (change)
	* </ul>
	* and the following coarse edits (note how adjacent change edits get merged together):
	* <ul>
	* <li>abc ⇨ abc (no-change)
	* <li>ßD ⇨ ssd (change)
	* <li>e ⇨ e (no-change)
	* <li>F ⇨ f (change)
	* </ul>
	*
	* The "fine changes" and "coarse changes" iterators will step through only the change edits when their
	* {@link Edits::Iterator#next()} methods are called. They are identical to the non-change iterators when
	* their {@link Edits::Iterator#findSourceIndex(int)} or {@link Edits::Iterator#findDestinationIndex(int)}
	* methods are used to walk through the string.
	*
	* For examples of how to use this class, see the test <code>TestCaseMapEditsIteratorDocs</code> in
	* UCharacterCaseTest.java.
	*
	* An Edits object tracks a separate UErrorCode, but ICU string transformation functions
	* (e.g., case mapping functions) merge any such errors into their API's UErrorCode.
	*
	* @stable ICU 59
	*/
	class U_COMMON_API Edits U_FINAL : public UMemory {
	public:
	/**
	* Constructs an empty object.
	* @stable ICU 59
	*/
	Edits() :
	array(stackArray), capacity(STACK_CAPACITY), length(0), delta(0), numChanges(0),
	errorCode_(U_ZERO_ERROR) {}
	/**
	* Copy constructor.
	* @param other source edits
	* @draft ICU 60
	*/
	Edits(const Edits &other) :
	array(stackArray), capacity(STACK_CAPACITY), length(other.length),
	delta(other.delta), numChanges(other.numChanges),
	errorCode_(other.errorCode_) {
	copyArray(other);
	}
	/**
	* Move constructor, might leave src empty.
	* This object will have the same contents that the source object had.
	* @param src source edits
	* @draft ICU 60
	*/
	Edits(Edits &&src) U_NOEXCEPT :
	array(stackArray), capacity(STACK_CAPACITY), length(src.length),
	delta(src.delta), numChanges(src.numChanges),
	errorCode_(src.errorCode_) {
	moveArray(src);
	}

	/**
	* Destructor.
	* @stable ICU 59
	*/
	~Edits();

	/**
	* Assignment operator.
	* @param other source edits
	* @return *this
	* @draft ICU 60
	*/
	Edits &operator=(const Edits &other);

	/**
	* Move assignment operator, might leave src empty.
	* This object will have the same contents that the source object had.
	* The behavior is undefined if *this and src are the same object.
	* @param src source edits
	* @return *this
	* @draft ICU 60
	*/
	Edits &operator=(Edits &&src) U_NOEXCEPT;

	/**
	* Resets the data but may not release memory.
	* @stable ICU 59
	*/
	void reset() U_NOEXCEPT;

	/**
	* Adds a no-change edit: a record for an unchanged segment of text.
	* Normally called from inside ICU string transformation functions, not user code.
	* @stable ICU 59
	*/
	void addUnchanged(int32_t unchangedLength);
	/**
	* Adds a change edit: a record for a text replacement/insertion/deletion.
	* Normally called from inside ICU string transformation functions, not user code.
	* @stable ICU 59
	*/
	void addReplace(int32_t oldLength, int32_t newLength);
	/**
	* Sets the UErrorCode if an error occurred while recording edits.
	* Preserves older error codes in the outErrorCode.
	* Normally called from inside ICU string transformation functions, not user code.
	* @param outErrorCode Set to an error code if it does not contain one already
	* and an error occurred while recording edits.
	* Otherwise unchanged.
	* @return TRUE if U_FAILURE(outErrorCode)
	* @stable ICU 59
	*/
	UBool copyErrorTo(UErrorCode &outErrorCode);

	/**
	* How much longer is the new text compared with the old text?
	* @return new length minus old length
	* @stable ICU 59
	*/
	int32_t lengthDelta() const { return delta; }
	/**
	* @return TRUE if there are any change edits
	* @stable ICU 59
	*/
	UBool hasChanges() const { return numChanges != 0; }

	#ifndef U_HIDE_DRAFT_API
	/**
	* @return the number of change edits
	* @draft ICU 60
	*/
	int32_t numberOfChanges() const { return numChanges; }
	#endif // U_HIDE_DRAFT_API

	/**
	* Access to the list of edits.
	*
	* At any moment in time, an instance of this class points to a single edit: a "window" into a span
	* of the source string and the corresponding span of the destination string. The source string span
	* starts at {@link #sourceIndex()} and runs for {@link #oldLength()} chars; the destination string
	* span starts at {@link #destinationIndex()} and runs for {@link #newLength()} chars.
	*
	* The iterator can be moved between edits using the {@link #next()}, {@link #findSourceIndex(int)},
	* and {@link #findDestinationIndex(int)} methods. Calling any of these methods mutates the iterator
	* to make it point to the corresponding edit.
	*
	* For more information, see the documentation for {@link Edits}.
	*
	* @see getCoarseIterator
	* @see getFineIterator
	* @stable ICU 59
	*/
	struct U_COMMON_API Iterator U_FINAL : public UMemory {
	/**
	* Default constructor, empty iterator.
	* @draft ICU 60
	*/
	Iterator() :
	array(nullptr), index(0), length(0),
	remaining(0), onlyChanges_(FALSE), coarse(FALSE),
	dir(0), changed(FALSE), oldLength_(0), newLength_(0),
	srcIndex(0), replIndex(0), destIndex(0) {}
	/**
	* Copy constructor.
	* @stable ICU 59
	*/
	Iterator(const Iterator &other) = default;
	/**
	* Assignment operator.
	* @stable ICU 59
	*/
	Iterator &operator=(const Iterator &other) = default;

	/**
	* Advances the iterator to the next edit.
	* @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
	* or else the function returns immediately. Check for U_FAILURE()
	* on output or use with function chaining. (See User Guide for details.)
	* @return TRUE if there is another edit
	* @stable ICU 59
	*/
	UBool next(UErrorCode &errorCode) { return next(onlyChanges_, errorCode); }

	/**
	* Moves the iterator to the edit that contains the source index.
	* The source index may be found in a no-change edit
	* even if normal iteration would skip no-change edits.
	* Normal iteration can continue from a found edit.
	*
	* The iterator state before this search logically does not matter.
	* (It may affect the performance of the search.)
	*
	* The iterator state after this search is undefined
	* if the source index is out of bounds for the source string.
	*
	* @param i source index
	* @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
	* or else the function returns immediately. Check for U_FAILURE()
	* on output or use with function chaining. (See User Guide for details.)
	* @return TRUE if the edit for the source index was found
	* @stable ICU 59
	*/
	UBool findSourceIndex(int32_t i, UErrorCode &errorCode) {
	return findIndex(i, TRUE, errorCode) == 0;
	}

	#ifndef U_HIDE_DRAFT_API
	/**
	* Moves the iterator to the edit that contains the destination index.
	* The destination index may be found in a no-change edit
	* even if normal iteration would skip no-change edits.
	* Normal iteration can continue from a found edit.
	*
	* The iterator state before this search logically does not matter.
	* (It may affect the performance of the search.)
	*
	* The iterator state after this search is undefined
	* if the source index is out of bounds for the source string.
	*
	* @param i destination index
	* @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
	* or else the function returns immediately. Check for U_FAILURE()
	* on output or use with function chaining. (See User Guide for details.)
	* @return TRUE if the edit for the destination index was found
	* @draft ICU 60
	*/
	UBool findDestinationIndex(int32_t i, UErrorCode &errorCode) {
	return findIndex(i, FALSE, errorCode) == 0;
	}

	/**
	* Computes the destination index corresponding to the given source index.
	* If the source index is inside a change edit (not at its start),
	* then the destination index at the end of that edit is returned,
	* since there is no information about index mapping inside a change edit.
	*
	* (This means that indexes to the start and middle of an edit,
	* for example around a grapheme cluster, are mapped to indexes
	* encompassing the entire edit.
	* The alternative, mapping an interior index to the start,
	* would map such an interval to an empty one.)
	*
	* This operation will usually but not always modify this object.
	* The iterator state after this search is undefined.
	*
	* @param i source index
	* @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
	* or else the function returns immediately. Check for U_FAILURE()
	* on output or use with function chaining. (See User Guide for details.)
	* @return destination index; undefined if i is not 0..string length
	* @draft ICU 60
	*/
	int32_t destinationIndexFromSourceIndex(int32_t i, UErrorCode &errorCode);

	/**
	* Computes the source index corresponding to the given destination index.
	* If the destination index is inside a change edit (not at its start),
	* then the source index at the end of that edit is returned,
	* since there is no information about index mapping inside a change edit.
	*
	* (This means that indexes to the start and middle of an edit,
	* for example around a grapheme cluster, are mapped to indexes
	* encompassing the entire edit.
	* The alternative, mapping an interior index to the start,
	* would map such an interval to an empty one.)
	*
	* This operation will usually but not always modify this object.
	* The iterator state after this search is undefined.
	*
	* @param i destination index
	* @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
	* or else the function returns immediately. Check for U_FAILURE()
	* on output or use with function chaining. (See User Guide for details.)
	* @return source index; undefined if i is not 0..string length
	* @draft ICU 60
	*/
	int32_t sourceIndexFromDestinationIndex(int32_t i, UErrorCode &errorCode);
	#endif // U_HIDE_DRAFT_API

	/**
	* Returns whether the edit currently represented by the iterator is a change edit.
	*
	* @return TRUE if this edit replaces oldLength() units with newLength() different ones.
	* FALSE if oldLength units remain unchanged.
	* @stable ICU 59
	*/
	UBool hasChange() const { return changed; }

	/**
	* The length of the current span in the source string, which starts at {@link #sourceIndex}.
	*
	* @return the number of units in the original string which are replaced or remain unchanged.
	* @stable ICU 59
	*/
	int32_t oldLength() const { return oldLength_; }

	/**
	* The length of the current span in the destination string, which starts at
	* {@link #destinationIndex}, or in the replacement string, which starts at
	* {@link #replacementIndex}.
	*
	* @return the number of units in the modified string, if hasChange() is TRUE.
	* Same as oldLength if hasChange() is FALSE.
	* @stable ICU 59
	*/
	int32_t newLength() const { return newLength_; }

	/**
	* The start index of the current span in the source string; the span has length
	* {@link #oldLength}.
	*
	* @return the current index into the source string
	* @stable ICU 59
	*/
	int32_t sourceIndex() const { return srcIndex; }

	/**
	* The start index of the current span in the replacement string; the span has length
	* {@link #newLength}. Well-defined only if the current edit is a change edit.
	* <p>
	* The <em>replacement string</em> is the concatenation of all substrings of the destination
	* string corresponding to change edits.
	* <p>
	* This method is intended to be used together with operations that write only replacement
	* characters (e.g., {@link CaseMap#omitUnchangedText()}). The source string can then be modified
	* in-place.
	*
	* @return the current index into the replacement-characters-only string,
	* not counting unchanged spans
	* @stable ICU 59
	*/
	int32_t replacementIndex() const {
	// TODO: Throw an exception if we aren't in a change edit?
	return replIndex;
	}

	/**
	* The start index of the current span in the destination string; the span has length
	* {@link #newLength}.
	*
	* @return the current index into the full destination string
	* @stable ICU 59
	*/
	int32_t destinationIndex() const { return destIndex; }

	#ifndef U_HIDE_INTERNAL_API
	/**
	* A string representation of the current edit represented by the iterator for debugging. You
	* should not depend on the contents of the return string.
	* @internal
	*/
	UnicodeString& toString(UnicodeString& appendTo) const;
	#endif // U_HIDE_INTERNAL_API

	private:
	friend class Edits;

	Iterator(const uint16_t *a, int32_t len, UBool oc, UBool crs);

	int32_t readLength(int32_t head);
	void updateNextIndexes();
	void updatePreviousIndexes();
	UBool noNext();
	UBool next(UBool onlyChanges, UErrorCode &errorCode);
	UBool previous(UErrorCode &errorCode);
	/** @return -1: error or i<0; 0: found; 1: i>=string length */
	int32_t findIndex(int32_t i, UBool findSource, UErrorCode &errorCode);

	const uint16_t *array;
	int32_t index, length;
	// 0 if we are not within compressed equal-length changes.
	// Otherwise the number of remaining changes, including the current one.
	int32_t remaining;
	UBool onlyChanges_, coarse;

	int8_t dir; // iteration direction: back(<0), initial(0), forward(>0)
	UBool changed;
	int32_t oldLength_, newLength_;
	int32_t srcIndex, replIndex, destIndex;
	};

	/**
	* Returns an Iterator for coarse-grained change edits
	* (adjacent change edits are treated as one).
	* Can be used to perform simple string updates.
	* Skips no-change edits.
	* @return an Iterator that merges adjacent changes.
	* @stable ICU 59
	*/
	Iterator getCoarseChangesIterator() const {
	return Iterator(array, length, TRUE, TRUE);
	}

	/**
	* Returns an Iterator for coarse-grained change and no-change edits
	* (adjacent change edits are treated as one).
	* Can be used to perform simple string updates.
	* Adjacent change edits are treated as one edit.
	* @return an Iterator that merges adjacent changes.
	* @stable ICU 59
	*/
	Iterator getCoarseIterator() const {
	return Iterator(array, length, FALSE, TRUE);
	}

	/**
	* Returns an Iterator for fine-grained change edits
	* (full granularity of change edits is retained).
	* Can be used for modifying styled text.
	* Skips no-change edits.
	* @return an Iterator that separates adjacent changes.
	* @stable ICU 59
	*/
	Iterator getFineChangesIterator() const {
	return Iterator(array, length, TRUE, FALSE);
	}

	/**
	* Returns an Iterator for fine-grained change and no-change edits
	* (full granularity of change edits is retained).
	* Can be used for modifying styled text.
	* @return an Iterator that separates adjacent changes.
	* @stable ICU 59
	*/
	Iterator getFineIterator() const {
	return Iterator(array, length, FALSE, FALSE);
	}

	#ifndef U_HIDE_DRAFT_API
	/**
	* Merges the two input Edits and appends the result to this object.
	*
	* Consider two string transformations (for example, normalization and case mapping)
	* where each records Edits in addition to writing an output string.<br>
	* Edits ab reflect how substrings of input string a
	* map to substrings of intermediate string b.<br>
	* Edits bc reflect how substrings of intermediate string b
	* map to substrings of output string c.<br>
	* This function merges ab and bc such that the additional edits
	* recorded in this object reflect how substrings of input string a
	* map to substrings of output string c.
	*
	* If unrelated Edits are passed in where the output string of the first
	* has a different length than the input string of the second,
	* then a U_ILLEGAL_ARGUMENT_ERROR is reported.
	*
	* @param ab reflects how substrings of input string a
	* map to substrings of intermediate string b.
	* @param bc reflects how substrings of intermediate string b
	* map to substrings of output string c.
	* @param errorCode ICU error code. Its input value must pass the U_SUCCESS() test,
	* or else the function returns immediately. Check for U_FAILURE()
	* on output or use with function chaining. (See User Guide for details.)
	* @return *this, with the merged edits appended
	* @draft ICU 60
	*/
	Edits &mergeAndAppend(const Edits &ab, const Edits &bc, UErrorCode &errorCode);
	#endif // U_HIDE_DRAFT_API

	private:
	void releaseArray() U_NOEXCEPT;
	Edits &copyArray(const Edits &other);
	Edits &moveArray(Edits &src) U_NOEXCEPT;

	void setLastUnit(int32_t last) { array[length - 1] = (uint16_t)last; }
	int32_t lastUnit() const { return length > 0 ? array[length - 1] : 0xffff; }

	void append(int32_t r);
	UBool growArray();

	static const int32_t STACK_CAPACITY = 100;
	uint16_t *array;
	int32_t capacity;
	int32_t length;
	int32_t delta;
	int32_t numChanges;
	UErrorCode errorCode_;
	uint16_t stackArray[STACK_CAPACITY];
	};

	U_NAMESPACE_END

	#endif // __EDITS_H__