+++ /dev/null
-/*
-**********************************************************************
-* Copyright (C) 1999-2004 IBM Corp. All rights reserved.
-**********************************************************************
-* Date Name Description
-* 12/1/99 rgillam Complete port from Java.
-* 01/13/2000 helena Added UErrorCode to ctors.
-**********************************************************************
-*/
-
-#include "unicode/utypes.h"
-
-#if !UCONFIG_NO_BREAK_ITERATION
-
-#include "unicode/dbbi.h"
-#include "unicode/schriter.h"
-#include "dbbi_tbl.h"
-#include "uvector.h"
-#include "cmemory.h"
-#include "uassert.h"
-
-U_NAMESPACE_BEGIN
-
-UOBJECT_DEFINE_RTTI_IMPLEMENTATION(DictionaryBasedBreakIterator)
-
-
-//------------------------------------------------------------------------------
-//
-// constructors
-//
-//------------------------------------------------------------------------------
-
-DictionaryBasedBreakIterator::DictionaryBasedBreakIterator() :
-RuleBasedBreakIterator() {
- init();
-}
-
-
-DictionaryBasedBreakIterator::DictionaryBasedBreakIterator(UDataMemory* rbbiData,
- const char* dictionaryFilename,
- UErrorCode& status)
-: RuleBasedBreakIterator(rbbiData, status)
-{
- init();
- if (U_FAILURE(status)) {return;};
- fTables = new DictionaryBasedBreakIteratorTables(dictionaryFilename, status);
- if (U_FAILURE(status)) {
- if (fTables != NULL) {
- fTables->removeReference();
- fTables = NULL;
- }
- return;
- }
- /* test for NULL */
- if(fTables == 0) {
- status = U_MEMORY_ALLOCATION_ERROR;
- return;
- }
-}
-
-
-DictionaryBasedBreakIterator::DictionaryBasedBreakIterator(const DictionaryBasedBreakIterator &other) :
-RuleBasedBreakIterator(other)
-{
- init();
- if (other.fTables != NULL) {
- fTables = other.fTables;
- fTables->addReference();
- }
-}
-
-
-
-
-//------------------------------------------------------------------------------
-//
-// Destructor
-//
-//------------------------------------------------------------------------------
-DictionaryBasedBreakIterator::~DictionaryBasedBreakIterator()
-{
- uprv_free(cachedBreakPositions);
- cachedBreakPositions = NULL;
- if (fTables != NULL) {fTables->removeReference();};
-}
-
-//------------------------------------------------------------------------------
-//
-// Assignment operator. Sets this iterator to have the same behavior,
-// and iterate over the same text, as the one passed in.
-//
-//------------------------------------------------------------------------------
-DictionaryBasedBreakIterator&
-DictionaryBasedBreakIterator::operator=(const DictionaryBasedBreakIterator& that) {
- if (this == &that) {
- return *this;
- }
- reset(); // clears out cached break positions.
- RuleBasedBreakIterator::operator=(that);
- if (this->fTables != that.fTables) {
- if (this->fTables != NULL) {this->fTables->removeReference();};
- this->fTables = that.fTables;
- if (this->fTables != NULL) {this->fTables->addReference();};
- }
- return *this;
-}
-
-//------------------------------------------------------------------------------
-//
-// Clone() Returns a newly-constructed RuleBasedBreakIterator with the same
-// behavior, and iterating over the same text, as this one.
-//
-//------------------------------------------------------------------------------
-BreakIterator*
-DictionaryBasedBreakIterator::clone() const {
- return new DictionaryBasedBreakIterator(*this);
-}
-
-//=======================================================================
-// BreakIterator overrides
-//=======================================================================
-
-/**
- * Advances the iterator one step backwards.
- * @return The position of the last boundary position before the
- * current iteration position
- */
-int32_t
-DictionaryBasedBreakIterator::previous()
-{
- // if we have cached break positions and we're still in the range
- // covered by them, just move one step backward in the cache
- if (cachedBreakPositions != NULL && positionInCache > 0) {
- --positionInCache;
- fText->setIndex(cachedBreakPositions[positionInCache]);
- return cachedBreakPositions[positionInCache];
- }
-
- // otherwise, dump the cache and use the inherited previous() method to move
- // backward. This may fill up the cache with new break positions, in which
- // case we have to mark our position in the cache
- else {
- reset();
- int32_t result = RuleBasedBreakIterator::previous();
- if (cachedBreakPositions != NULL) {
- for (positionInCache=0;
- cachedBreakPositions[positionInCache] != result;
- positionInCache++);
- U_ASSERT(positionInCache < numCachedBreakPositions);
- if (positionInCache >= numCachedBreakPositions) {
- // Something has gone wrong. Dump the cache.
- reset();
- }
- }
- return result;
- }
-}
-
-/**
- * Sets the current iteration position to the last boundary position
- * before the specified position.
- * @param offset The position to begin searching from
- * @return The position of the last boundary before "offset"
- */
-int32_t
-DictionaryBasedBreakIterator::preceding(int32_t offset)
-{
- // if the offset passed in is already past the end of the text,
- // just return DONE; if it's before the beginning, return the
- // text's starting offset
- if (fText == NULL || offset > fText->endIndex()) {
- return BreakIterator::DONE;
- }
- else if (offset < fText->startIndex()) {
- return fText->startIndex();
- }
-
- // if we have no cached break positions, or "offset" is outside the
- // range covered by the cache, we can just call the inherited routine
- // (which will eventually call other routines in this class that may
- // refresh the cache)
- if (cachedBreakPositions == NULL || offset <= cachedBreakPositions[0] ||
- offset > cachedBreakPositions[numCachedBreakPositions - 1]) {
- reset();
- return RuleBasedBreakIterator::preceding(offset);
- }
-
- // on the other hand, if "offset" is within the range covered by the cache,
- // then all we have to do is search the cache for the last break position
- // before "offset"
- else {
- positionInCache = 0;
- while (positionInCache < numCachedBreakPositions
- && offset > cachedBreakPositions[positionInCache])
- ++positionInCache;
- --positionInCache;
- fText->setIndex(cachedBreakPositions[positionInCache]);
- return fText->getIndex();
- }
-}
-
-/**
- * Sets the current iteration position to the first boundary position after
- * the specified position.
- * @param offset The position to begin searching forward from
- * @return The position of the first boundary after "offset"
- */
-int32_t
-DictionaryBasedBreakIterator::following(int32_t offset)
-{
- // if the offset passed in is already past the end of the text,
- // just return DONE; if it's before the beginning, return the
- // text's starting offset
- if (fText == NULL || offset > fText->endIndex()) {
- return BreakIterator::DONE;
- }
- else if (offset < fText->startIndex()) {
- return fText->startIndex();
- }
-
- // if we have no cached break positions, or if "offset" is outside the
- // range covered by the cache, then dump the cache and call our
- // inherited following() method. This will call other methods in this
- // class that may refresh the cache.
- if (cachedBreakPositions == NULL || offset < cachedBreakPositions[0] ||
- offset >= cachedBreakPositions[numCachedBreakPositions - 1]) {
- reset();
- return RuleBasedBreakIterator::following(offset);
- }
-
- // on the other hand, if "offset" is within the range covered by the
- // cache, then just search the cache for the first break position
- // after "offset"
- else {
- positionInCache = 0;
- while (positionInCache < numCachedBreakPositions
- && offset >= cachedBreakPositions[positionInCache])
- ++positionInCache;
- fText->setIndex(cachedBreakPositions[positionInCache]);
- return fText->getIndex();
- }
-}
-
-/**
- * This is the implementation function for next().
- */
-int32_t
-DictionaryBasedBreakIterator::handleNext()
-{
- UErrorCode status = U_ZERO_ERROR;
- // if there are no cached break positions, or if we've just moved
- // off the end of the range covered by the cache, we have to dump
- // and possibly regenerate the cache
- if (cachedBreakPositions == NULL || positionInCache == numCachedBreakPositions - 1) {
-
- // start by using the inherited handleNext() to find a tentative return
- // value. dictionaryCharCount tells us how many dictionary characters
- // we passed over on our way to the tentative return value
- int32_t startPos = fText->getIndex();
- fDictionaryCharCount = 0;
- int32_t result = RuleBasedBreakIterator::handleNext();
-
- // if we passed over more than one dictionary character, then we use
- // divideUpDictionaryRange() to regenerate the cached break positions
- // for the new range
- if (fDictionaryCharCount > 1 && result - startPos > 1) {
- divideUpDictionaryRange(startPos, result, status);
- U_ASSERT(U_SUCCESS(status));
- if (U_FAILURE(status)) {
- // Something went badly wrong, an internal error.
- // We have no way from here to report it to caller.
- // Treat as if this is if the dictionary did not apply to range.
- reset();
- return result;
- }
- }
-
- // otherwise, the value we got back from the inherited fuction
- // is our return value, and we can dump the cache
- else {
- reset();
- return result;
- }
- }
-
- // if the cache of break positions has been regenerated (or existed all
- // along), then just advance to the next break position in the cache
- // and return it
- if (cachedBreakPositions != NULL) {
- ++positionInCache;
- fText->setIndex(cachedBreakPositions[positionInCache]);
- return cachedBreakPositions[positionInCache];
- }
- return -9999; // SHOULD NEVER GET HERE!
-}
-
-void
-DictionaryBasedBreakIterator::reset()
-{
- uprv_free(cachedBreakPositions);
- cachedBreakPositions = NULL;
- numCachedBreakPositions = 0;
- fDictionaryCharCount = 0;
- positionInCache = 0;
-}
-
-
-
-//------------------------------------------------------------------------------
-//
-// init() Common initialization routine, for use by constructors, etc.
-//
-//------------------------------------------------------------------------------
-void DictionaryBasedBreakIterator::init() {
- cachedBreakPositions = NULL;
- fTables = NULL;
- numCachedBreakPositions = 0;
- fDictionaryCharCount = 0;
- positionInCache = 0;
-}
-
-
-//------------------------------------------------------------------------------
-//
-// BufferClone
-//
-//------------------------------------------------------------------------------
-BreakIterator * DictionaryBasedBreakIterator::createBufferClone(void *stackBuffer,
- int32_t &bufferSize,
- UErrorCode &status)
-{
- if (U_FAILURE(status)){
- return NULL;
- }
-
- //
- // If user buffer size is zero this is a preflight operation to
- // obtain the needed buffer size, allowing for worst case misalignment.
- //
- if (bufferSize == 0) {
- bufferSize = sizeof(DictionaryBasedBreakIterator) + U_ALIGNMENT_OFFSET_UP(0);
- return NULL;
- }
-
- //
- // Check the alignment and size of the user supplied buffer.
- // Allocate heap memory if the user supplied memory is insufficient.
- //
- char *buf = (char *)stackBuffer;
- uint32_t s = bufferSize;
-
- if (stackBuffer == NULL) {
- s = 0; // Ignore size, force allocation if user didn't give us a buffer.
- }
- if (U_ALIGNMENT_OFFSET(stackBuffer) != 0) {
- int32_t offsetUp = (int32_t)U_ALIGNMENT_OFFSET_UP(buf);
- s -= offsetUp;
- buf += offsetUp;
- }
- if (s < sizeof(DictionaryBasedBreakIterator)) {
- buf = (char *) new DictionaryBasedBreakIterator();
- if (buf == 0) {
- status = U_MEMORY_ALLOCATION_ERROR;
- return NULL;
- }
- status = U_SAFECLONE_ALLOCATED_WARNING;
- }
-
- //
- // Initialize the clone object.
- // TODO: using an overloaded C++ "operator new" to directly initialize the
- // copy in the user's buffer would be better, but it doesn't seem
- // to get along with namespaces. Investigate why.
- //
- // The memcpy is only safe with an empty (default constructed)
- // break iterator. Use on others can screw up reference counts
- // to data. memcpy-ing objects is not really a good idea...
- //
- DictionaryBasedBreakIterator localIter; // Empty break iterator, source for memcpy
- DictionaryBasedBreakIterator *clone = (DictionaryBasedBreakIterator *)buf;
- uprv_memcpy(clone, &localIter, sizeof(DictionaryBasedBreakIterator)); // clone = empty, but initialized, iterator.
- *clone = *this; // clone = the real one we want.
- if (status != U_SAFECLONE_ALLOCATED_WARNING) {
- clone->fBufferClone = TRUE;
- }
- return clone;
-}
-
-
-
-
-/**
- * This is the function that actually implements the dictionary-based
- * algorithm. Given the endpoints of a range of text, it uses the
- * dictionary to determine the positions of any boundaries in this
- * range. It stores all the boundary positions it discovers in
- * cachedBreakPositions so that we only have to do this work once
- * for each time we enter the range.
- */
-void
-DictionaryBasedBreakIterator::divideUpDictionaryRange(int32_t startPos, int32_t endPos, UErrorCode &status)
-{
- // the range we're dividing may begin or end with non-dictionary characters
- // (i.e., for line breaking, we may have leading or trailing punctuation
- // that needs to be kept with the word). Seek from the beginning of the
- // range to the first dictionary character
- fText->setIndex(startPos);
- UChar c = fText->current();
- while (isDictionaryChar(c) == FALSE) {
- c = fText->next();
- }
-
- if (U_FAILURE(status)) {
- return; // UStack below overwrites the status error codes
- }
-
- // initialize. We maintain two stacks: currentBreakPositions contains
- // the list of break positions that will be returned if we successfully
- // finish traversing the whole range now. possibleBreakPositions lists
- // all other possible word ends we've passed along the way. (Whenever
- // we reach an error [a sequence of characters that can't begin any word
- // in the dictionary], we back up, possibly delete some breaks from
- // currentBreakPositions, move a break from possibleBreakPositions
- // to currentBreakPositions, and start over from there. This process
- // continues in this way until we either successfully make it all the way
- // across the range, or exhaust all of our combinations of break
- // positions.) wrongBreakPositions is used to keep track of paths we've
- // tried on previous iterations. As the iterator backs up further and
- // further, this saves us from having to follow each possible path
- // through the text all the way to the error (hopefully avoiding many
- // future recursive calls as well).
- // there can be only one kind of error in UStack and UVector, so we'll
- // just let the error fall through
- UStack currentBreakPositions(status);
- UStack possibleBreakPositions(status);
- UVector wrongBreakPositions(status);
-
- // the dictionary is implemented as a trie, which is treated as a state
- // machine. -1 represents the end of a legal word. Every word in the
- // dictionary is represented by a path from the root node to -1. A path
- // that ends in state 0 is an illegal combination of characters.
- int16_t state = 0;
-
- // these two variables are used for error handling. We keep track of the
- // farthest we've gotten through the range being divided, and the combination
- // of breaks that got us that far. If we use up all possible break
- // combinations, the text contains an error or a word that's not in the
- // dictionary. In this case, we "bless" the break positions that got us the
- // farthest as real break positions, and then start over from scratch with
- // the character where the error occurred.
- int32_t farthestEndPoint = fText->getIndex();
- UStack bestBreakPositions(status);
- UBool bestBreakPositionsInitialized = FALSE;
-
- if (U_FAILURE(status)) {
- return;
- }
- // initialize (we always exit the loop with a break statement)
- c = fText->current();
- for (;;) {
-
- // if we can transition to state "-1" from our current state, we're
- // on the last character of a legal word. Push that position onto
- // the possible-break-positions stack
- if (fTables->fDictionary->at(state, (int32_t)0) == -1) {
- possibleBreakPositions.push(fText->getIndex(), status);
- if (U_FAILURE(status)) {
- return;
- }
- }
-
- // look up the new state to transition to in the dictionary
- state = fTables->fDictionary->at(state, c);
-
- // if the character we're sitting on causes us to transition to
- // the "end of word" state, then it was a non-dictionary character
- // and we've successfully traversed the whole range. Drop out
- // of the loop.
- if (state == -1) {
- currentBreakPositions.push(fText->getIndex(), status);
- if (U_FAILURE(status)) {
- return;
- }
- break;
- }
-
- // if the character we're sitting on causes us to transition to
- // the error state, or if we've gone off the end of the range
- // without transitioning to the "end of word" state, we've hit
- // an error...
- else if (state == 0 || fText->getIndex() >= endPos) {
-
- // if this is the farthest we've gotten, take note of it in
- // case there's an error in the text
- if (fText->getIndex() > farthestEndPoint) {
- farthestEndPoint = fText->getIndex();
- bestBreakPositions.removeAllElements();
- bestBreakPositionsInitialized = TRUE;
- for (int32_t i = 0; i < currentBreakPositions.size(); i++) {
- bestBreakPositions.push(currentBreakPositions.elementAti(i), status);
- }
- }
-
- // wrongBreakPositions is a list of all break positions we've tried starting
- // that didn't allow us to traverse all the way through the text. Every time
- // we pop a break position off of currentBreakPositions, we put it into
- // wrongBreakPositions to avoid trying it again later. If we make it to this
- // spot, we're either going to back up to a break in possibleBreakPositions
- // and try starting over from there, or we've exhausted all possible break
- // positions and are going to do the fallback procedure. This loop prevents
- // us from messing with anything in possibleBreakPositions that didn't work as
- // a starting point the last time we tried it (this is to prevent a bunch of
- // repetitive checks from slowing down some extreme cases)
- while (!possibleBreakPositions.isEmpty() && wrongBreakPositions.contains(
- possibleBreakPositions.peeki())) {
- possibleBreakPositions.popi();
- }
-
- // if we've used up all possible break-position combinations, there's
- // an error or an unknown word in the text. In this case, we start
- // over, treating the farthest character we've reached as the beginning
- // of the range, and "blessing" the break positions that got us that
- // far as real break positions
- if (possibleBreakPositions.isEmpty()) {
- if (bestBreakPositionsInitialized) {
- currentBreakPositions.removeAllElements();
- for (int32_t i = 0; i < bestBreakPositions.size(); i++) {
- currentBreakPositions.push(bestBreakPositions.elementAti(i), status);
- if (U_FAILURE(status)) {
- return;
- }
- }
- bestBreakPositions.removeAllElements();
- if (farthestEndPoint < endPos) {
- fText->setIndex(farthestEndPoint + 1);
- }
- else {
- break;
- }
- }
- else {
- if ((currentBreakPositions.isEmpty()
- || currentBreakPositions.peeki() != fText->getIndex())
- && fText->getIndex() != startPos) {
- currentBreakPositions.push(fText->getIndex(), status);
- if (U_FAILURE(status)) {
- return;
- }
- }
- fText->next();
- currentBreakPositions.push(fText->getIndex(), status);
- if (U_FAILURE(status)) {
- return;
- }
- }
- }
-
- // if we still have more break positions we can try, then promote the
- // last break in possibleBreakPositions into currentBreakPositions,
- // and get rid of all entries in currentBreakPositions that come after
- // it. Then back up to that position and start over from there (i.e.,
- // treat that position as the beginning of a new word)
- else {
- int32_t temp = possibleBreakPositions.popi();
- int32_t temp2 = 0;
- while (!currentBreakPositions.isEmpty() && temp <
- currentBreakPositions.peeki()) {
- temp2 = currentBreakPositions.popi();
- wrongBreakPositions.addElement(temp2, status);
- }
- currentBreakPositions.push(temp, status);
- fText->setIndex(currentBreakPositions.peeki());
- }
-
- // re-sync "c" for the next go-round, and drop out of the loop if
- // we've made it off the end of the range
- c = fText->current();
- if (fText->getIndex() >= endPos) {
- break;
- }
- }
-
- // if we didn't hit any exceptional conditions on this last iteration,
- // just advance to the next character and loop
- else {
- c = fText->next();
- }
- }
-
- // dump the last break position in the list, and replace it with the actual
- // end of the range (which may be the same character, or may be further on
- // because the range actually ended with non-dictionary characters we want to
- // keep with the word)
- if (!currentBreakPositions.isEmpty()) {
- currentBreakPositions.popi();
- }
- currentBreakPositions.push(endPos, status);
- if (U_FAILURE(status)) {
- return;
- }
-
- // create a regular array to hold the break positions and copy
- // the break positions from the stack to the array (in addition,
- // our starting position goes into this array as a break position).
- // This array becomes the cache of break positions used by next()
- // and previous(), so this is where we actually refresh the cache.
- if (cachedBreakPositions != NULL) {
- uprv_free(cachedBreakPositions);
- }
- cachedBreakPositions = (int32_t *)uprv_malloc((currentBreakPositions.size() + 1) * sizeof(int32_t));
- /* Test for NULL */
- if(cachedBreakPositions == NULL) {
- status = U_MEMORY_ALLOCATION_ERROR;
- return;
- }
- numCachedBreakPositions = currentBreakPositions.size() + 1;
- cachedBreakPositions[0] = startPos;
-
- for (int32_t i = 0; i < currentBreakPositions.size(); i++) {
- cachedBreakPositions[i + 1] = currentBreakPositions.elementAti(i);
- }
- positionInCache = 0;
-}
-
-U_NAMESPACE_END
-
-#endif /* #if !UCONFIG_NO_BREAK_ITERATION */
-
-/* eof */
projects / apple / icu.git / blobdiff