Source code
Revision control
Copy as Markdown
Other Tools
// © 2016 and later: Unicode, Inc. and others.
// edits.h
// created: 2016dec30 Markus W. Scherer
#ifndef __EDITS_H__
#define __EDITS_H__
#include "unicode/utypes.h"
#if U_SHOW_CPLUSPLUS_API
#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(int32_t, int32_t)} (for change edits) and
* {@link #addUnchanged(int32_t)} (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
* `Edits::Iterator::next()` methods are called. They are identical to the non-change iterators when
* their `Edits::Iterator::findSourceIndex()` or `Edits::Iterator::findDestinationIndex()`
* methods are used to walk through the string.
*
* For examples of how to use this class, see the test `TestCaseMapEditsIteratorDocs` 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 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
* @stable 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
* @stable ICU 60
*/
Edits(Edits &&src) 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
* @stable 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
* @stable ICU 60
*/
Edits &operator=(Edits &&src) noexcept;
/**
* Resets the data but may not release memory.
* @stable ICU 59
*/
void reset() 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) const;
/**
* 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; }
/**
* @return the number of change edits
* @stable ICU 60
*/
int32_t numberOfChanges() const { return numChanges; }
/**
* 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 `next()`, `findSourceIndex(int32_t, UErrorCode &)`,
* and `findDestinationIndex(int32_t, UErrorCode &)` 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 final : public UMemory {
/**
* Default constructor, empty iterator.
* @stable 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;
}
/**
* 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
* @stable 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
* @stable 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
* @stable ICU 60
*/
int32_t sourceIndexFromDestinationIndex(int32_t i, UErrorCode &errorCode);
/**
* 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.
*
* The *replacement string* is the concatenation of all substrings of the destination
* string corresponding to change edits.
*
* This method is intended to be used together with operations that write only replacement
* characters (e.g. operations specifying the \ref U_OMIT_UNCHANGED_TEXT option).
* 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);
}
/**
* 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
* @stable ICU 60
*/
Edits &mergeAndAppend(const Edits &ab, const Edits &bc, UErrorCode &errorCode);
private:
void releaseArray() noexcept;
Edits ©Array(const Edits &other);
Edits &moveArray(Edits &src) 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 /* U_SHOW_CPLUSPLUS_API */
#endif // __EDITS_H__