source/i18n/rbt_set.cpp - external/github.com/unicode-org/icu - Git at Google

 /*
 **********************************************************************
 *   Copyright (C) 1999, International Business Machines
 *   Corporation and others.  All Rights Reserved.
 **********************************************************************
 *   Date        Name        Description
 *   11/17/99    aliu        Creation.
 **********************************************************************
 */
 #include "rbt_set.h"
 #include "rbt_rule.h"
 #include "unicode/unistr.h"
 #include "cmemory.h"

 static void _deleteRule(void *rule) {
     delete (TransliterationRule *)rule;
 }

 /**
  * Construct a new empty rule set.
  */
 TransliterationRuleSet::TransliterationRuleSet() {
     maxContextLength = 0;
     ruleVector = new UVector();
     ruleVector->setDeleter(&_deleteRule);
     rules = NULL;
 }

 /**
  * Copy constructor.  We assume that the ruleset being copied
  * has already been frozen.
  */
 TransliterationRuleSet::TransliterationRuleSet(const TransliterationRuleSet& other) :
     ruleVector(0),
     maxContextLength(other.maxContextLength) {

     uprv_memcpy(index, other.index, sizeof(index));
     int32_t len = index[256]; // see freeze()
     rules = new TransliterationRule*[len];
     for (int32_t i=0; i<len; ++i) {
         rules[i] = new TransliterationRule(*other.rules[i]);
     }
 }

 /**
  * Destructor.
  */
 TransliterationRuleSet::~TransliterationRuleSet() {
     delete ruleVector;
     delete[] rules;
 }

 /**
  * Return the maximum context length.
  * @return the length of the longest preceding context.
  */
 int32_t TransliterationRuleSet::getMaximumContextLength(void) const {
     return maxContextLength;
 }

 /**
  * Add a rule to this set.  Rules are added in order, and order is
  * significant.  The last call to this method must be followed by
  * a call to <code>freeze()</code> before the rule set is used.
  *
  * @param adoptedRule the rule to add
  */
 void TransliterationRuleSet::addRule(TransliterationRule* adoptedRule,
                                      UErrorCode& status) {
     if (U_FAILURE(status)) {
         delete adoptedRule;
         return;
     }
     ruleVector->addElement(adoptedRule);

     int32_t len;
     if ((len = adoptedRule->getAnteContextLength()) > maxContextLength) {
         maxContextLength = len;
     }

     delete[] rules; // Contains alias pointers
     rules = 0;
 }

 /**
  * Check this for masked rules and index it to optimize performance.
  * The sequence of operations is: (1) add rules to a set using
  * <code>addRule()</code>; (2) freeze the set using
  * <code>freeze()</code>; (3) use the rule set.  If
  * <code>addRule()</code> is called after calling this method, it
  * invalidates this object, and this method must be called again.
  * That is, <code>freeze()</code> may be called multiple times,
  * although for optimal performance it shouldn't be.
  */
 void TransliterationRuleSet::freeze(const TransliterationRuleData& data,
                                     UErrorCode& status) {
     if (U_FAILURE(status)) {
         return;
     }

     /* Construct the rule array and index table.  We reorder the
      * rules by sorting them into 256 bins.  Each bin contains all
      * rules matching the index value for that bin.  A rule
      * matches an index value if string whose first key character
      * has a low byte equal to the index value can match the rule.
      *
      * Each bin contains zero or more rules, in the same order
      * they were found originally.  However, the total rules in
      * the bins may exceed the number in the original vector,
      * since rules that have a variable as their first key
      * character will generally fall into more than one bin.
      *
      * That is, each bin contains all rules that either have that
      * first index value as their first key character, or have
      * a set containing the index value as their first character.
      */
     int32_t n = ruleVector->size();
     int32_t j;
     int16_t x;
     UVector v(2*n); // heuristic; adjust as needed

     /* Precompute the index values.  This saves a LOT of time.
      */
     int16_t* indexValue = new int16_t[n];
     for (j=0; j<n; ++j) {
         TransliterationRule* r = (TransliterationRule*) ruleVector->elementAt(j);
         indexValue[j] = r->getIndexValue(data);
     }
     for (x=0; x<256; ++x) {
         index[x] = v.size();
         for (j=0; j<n; ++j) {
             if (indexValue[j] >= 0) {
                 if (indexValue[j] == x) {
                     v.addElement(ruleVector->elementAt(j));
                 }
             } else {
                 // If the indexValue is < 0, then the first key character is
                 // a set, and we must use the more time-consuming
                 // matchesIndexValue check.  In practice this happens
                 // rarely, so we seldom tread this code path.
                 TransliterationRule* r = (TransliterationRule*) ruleVector->elementAt(j);
                 if (r->matchesIndexValue((uint8_t)x, data)) {
                     v.addElement(r);
                 }
             }
         }
     }
     delete[] indexValue;
     index[256] = v.size();

     /* Freeze things into an array.
      */
     delete[] rules; // Contains alias pointers
     rules = new TransliterationRule*[v.size()];
     for (j=0; j<v.size(); ++j) {
         rules[j] = (TransliterationRule*) v.elementAt(j);
     }

     // TODO Add error reporting that indicates the rules that
     //      are being masked.
     //UnicodeString errors;

     /* Check for masking.  This is MUCH faster than our old check,
      * which was each rule against each following rule, since we
      * only have to check for masking within each bin now.  It's
      * 256*O(n2^2) instead of O(n1^2), where n1 is the total rule
      * count, and n2 is the per-bin rule count.  But n2<<n1, so
      * it's a big win.
      */
     for (x=0; x<256; ++x) {
         for (j=index[x]; j<index[x+1]-1; ++j) {
             TransliterationRule* r1 = rules[j];
             for (int32_t k=j+1; k<index[x+1]; ++k) {
                 TransliterationRule* r2 = rules[k];
                 if (r1->masks(*r2)) {
 //|                 if (errors == null) {
 //|                     errors = new StringBuffer();
 //|                 } else {
 //|                     errors.append("\n");
 //|                 }
 //|                 errors.append("Rule " + r1 + " masks " + r2);
                     status = U_ILLEGAL_ARGUMENT_ERROR;
                     return;
                 }
             }
         }
     }

     //if (errors != null) {
     //    throw new IllegalArgumentException(errors.toString());
     //}
 }

 /**
  * Attempt to find a matching rule at the specified point in the text.
  * @param text the text, both translated and untranslated
  * @param start the beginning index, inclusive; <code>0 <= start
  * <= limit</code>.
  * @param limit the ending index, exclusive; <code>start <= limit
  * <= text.length()</code>.
  * @param cursor position at which to translate next, representing offset
  * into text.  This value must be between <code>start</code> and
  * <code>limit</code>.
  * @param data a dictionary mapping variables to the sets they
  * represent (maps <code>Character</code> to <code>UnicodeSet</code>)
  * @param filter the filter.  Any character for which
  * <tt>filter.contains()</tt> returns <tt>false</tt> will not be
  * altered by this transliterator.  If <tt>filter</tt> is
  * <tt>null</tt> then no filtering is applied.
  * @return the matching rule, or null if none found.
  */
 TransliterationRule*
 TransliterationRuleSet::findMatch(const Replaceable& text,
                                   const UTransPosition& pos,
                                   const TransliterationRuleData& data,
                                   const UnicodeFilter* filter) const {
     /* We only need to check our indexed bin of the rule table,
      * based on the low byte of the first key character.
      */
     int16_t x = (int16_t) (text.charAt(pos.start) & 0xFF);
     for (int32_t i=index[x]; i<index[x+1]; ++i) {
         if (rules[i]->matches(text, pos, data, filter)) {
             return rules[i];
         }
     }
     return NULL;
 }

 /**
  * Attempt to find a matching rule at the specified point in the text.
  * Unlike <code>findMatch()</code>, this method does an incremental match.
  * An incremental match requires that there be no partial matches that might
  * pre-empt the full match that is found.  If there are partial matches,
  * then null is returned.  A non-null result indicates that a full match has
  * been found, and that it cannot be pre-empted by a partial match
  * regardless of what additional text is added to the translation buffer.
  * @param text the text, both translated and untranslated
  * @param start the beginning index, inclusive; <code>0 <= start
  * <= limit</code>.
  * @param limit the ending index, exclusive; <code>start <= limit
  * <= text.length()</code>.
  * @param cursor position at which to translate next, representing offset
  * into text.  This value must be between <code>start</code> and
  * <code>limit</code>.
  * @param data a dictionary mapping variables to the sets they
  * represent (maps <code>Character</code> to <code>UnicodeSet</code>)
  * @param partial output parameter.  <code>partial[0]</code> is set to
  * true if a partial match is returned.
  * @param filter the filter.  Any character for which
  * <tt>filter.contains()</tt> returns <tt>false</tt> will not be
  * altered by this transliterator.  If <tt>filter</tt> is
  * <tt>null</tt> then no filtering is applied.
  * @return the matching rule, or null if none found, or if the text buffer
  * does not have enough text yet to unambiguously match a rule.
  */
 TransliterationRule*
 TransliterationRuleSet::findIncrementalMatch(const Replaceable& text,
                                              const UTransPosition& pos,
                                              const TransliterationRuleData& data,
                                              UBool& isPartial,
                                              const UnicodeFilter* filter) const {

     /* We only need to check our indexed bin of the rule table,
      * based on the low byte of the first key character.
      */
     isPartial = FALSE;
     int16_t x = (int16_t) (text.charAt(pos.start) & 0xFF);
     for (int32_t i=index[x]; i<index[x+1]; ++i) {
         int32_t match = rules[i]->getMatchDegree(text, pos, data, filter);
         switch (match) {
         case TransliterationRule::FULL_MATCH:
             return rules[i];
         case TransliterationRule::PARTIAL_MATCH:
             isPartial = TRUE;
             return NULL;
         }
     }
     return NULL;
 }
	/*
	**********************************************************************
	* Copyright (C) 1999, International Business Machines
	* Corporation and others. All Rights Reserved.
	**********************************************************************
	* Date Name Description
	* 11/17/99 aliu Creation.
	**********************************************************************
	*/
	#include "rbt_set.h"
	#include "rbt_rule.h"
	#include "unicode/unistr.h"
	#include "cmemory.h"

	static void _deleteRule(void *rule) {
	delete (TransliterationRule *)rule;
	}

	/**
	* Construct a new empty rule set.
	*/
	TransliterationRuleSet::TransliterationRuleSet() {
	maxContextLength = 0;
	ruleVector = new UVector();
	ruleVector->setDeleter(&_deleteRule);
	rules = NULL;
	}

	/**
	* Copy constructor. We assume that the ruleset being copied
	* has already been frozen.
	*/
	TransliterationRuleSet::TransliterationRuleSet(const TransliterationRuleSet& other) :
	ruleVector(0),
	maxContextLength(other.maxContextLength) {

	uprv_memcpy(index, other.index, sizeof(index));
	int32_t len = index[256]; // see freeze()
	rules = new TransliterationRule*[len];
	for (int32_t i=0; i<len; ++i) {
	rules[i] = new TransliterationRule(*other.rules[i]);
	}
	}

	/**
	* Destructor.
	*/
	TransliterationRuleSet::~TransliterationRuleSet() {
	delete ruleVector;
	delete[] rules;
	}

	/**
	* Return the maximum context length.
	* @return the length of the longest preceding context.
	*/
	int32_t TransliterationRuleSet::getMaximumContextLength(void) const {
	return maxContextLength;
	}

	/**
	* Add a rule to this set. Rules are added in order, and order is
	* significant. The last call to this method must be followed by
	* a call to <code>freeze()</code> before the rule set is used.
	*
	* @param adoptedRule the rule to add
	*/
	void TransliterationRuleSet::addRule(TransliterationRule* adoptedRule,
	UErrorCode& status) {
	if (U_FAILURE(status)) {
	delete adoptedRule;
	return;
	}
	ruleVector->addElement(adoptedRule);

	int32_t len;
	if ((len = adoptedRule->getAnteContextLength()) > maxContextLength) {
	maxContextLength = len;
	}

	delete[] rules; // Contains alias pointers
	rules = 0;
	}

	/**
	* Check this for masked rules and index it to optimize performance.
	* The sequence of operations is: (1) add rules to a set using
	* <code>addRule()</code>; (2) freeze the set using
	* <code>freeze()</code>; (3) use the rule set. If
	* <code>addRule()</code> is called after calling this method, it
	* invalidates this object, and this method must be called again.
	* That is, <code>freeze()</code> may be called multiple times,
	* although for optimal performance it shouldn't be.
	*/
	void TransliterationRuleSet::freeze(const TransliterationRuleData& data,
	UErrorCode& status) {
	if (U_FAILURE(status)) {
	return;
	}

	/* Construct the rule array and index table. We reorder the
	* rules by sorting them into 256 bins. Each bin contains all
	* rules matching the index value for that bin. A rule
	* matches an index value if string whose first key character
	* has a low byte equal to the index value can match the rule.
	*
	* Each bin contains zero or more rules, in the same order
	* they were found originally. However, the total rules in
	* the bins may exceed the number in the original vector,
	* since rules that have a variable as their first key
	* character will generally fall into more than one bin.
	*
	* That is, each bin contains all rules that either have that
	* first index value as their first key character, or have
	* a set containing the index value as their first character.
	*/
	int32_t n = ruleVector->size();
	int32_t j;
	int16_t x;
	UVector v(2*n); // heuristic; adjust as needed

	/* Precompute the index values. This saves a LOT of time.
	*/
	int16_t* indexValue = new int16_t[n];
	for (j=0; j<n; ++j) {
	TransliterationRule* r = (TransliterationRule*) ruleVector->elementAt(j);
	indexValue[j] = r->getIndexValue(data);
	}
	for (x=0; x<256; ++x) {
	index[x] = v.size();
	for (j=0; j<n; ++j) {
	if (indexValue[j] >= 0) {
	if (indexValue[j] == x) {
	v.addElement(ruleVector->elementAt(j));
	}
	} else {
	// If the indexValue is < 0, then the first key character is
	// a set, and we must use the more time-consuming
	// matchesIndexValue check. In practice this happens
	// rarely, so we seldom tread this code path.
	TransliterationRule* r = (TransliterationRule*) ruleVector->elementAt(j);
	if (r->matchesIndexValue((uint8_t)x, data)) {
	v.addElement(r);
	}
	}
	}
	}
	delete[] indexValue;
	index[256] = v.size();

	/* Freeze things into an array.
	*/
	delete[] rules; // Contains alias pointers
	rules = new TransliterationRule*[v.size()];
	for (j=0; j<v.size(); ++j) {
	rules[j] = (TransliterationRule*) v.elementAt(j);
	}

	// TODO Add error reporting that indicates the rules that
	// are being masked.
	//UnicodeString errors;

	/* Check for masking. This is MUCH faster than our old check,
	* which was each rule against each following rule, since we
	* only have to check for masking within each bin now. It's
	* 256*O(n2^2) instead of O(n1^2), where n1 is the total rule
	* count, and n2 is the per-bin rule count. But n2<<n1, so
	* it's a big win.
	*/
	for (x=0; x<256; ++x) {
	for (j=index[x]; j<index[x+1]-1; ++j) {
	TransliterationRule* r1 = rules[j];
	for (int32_t k=j+1; k<index[x+1]; ++k) {
	TransliterationRule* r2 = rules[k];
	if (r1->masks(*r2)) {
	//\| if (errors == null) {
	//\| errors = new StringBuffer();
	//\| } else {
	//\| errors.append("\n");
	//\| }
	//\| errors.append("Rule " + r1 + " masks " + r2);
	status = U_ILLEGAL_ARGUMENT_ERROR;
	return;
	}
	}
	}
	}

	//if (errors != null) {
	// throw new IllegalArgumentException(errors.toString());
	//}
	}

	/**
	* Attempt to find a matching rule at the specified point in the text.
	* @param text the text, both translated and untranslated
	* @param start the beginning index, inclusive; <code>0 <= start
	* <= limit</code>.
	* @param limit the ending index, exclusive; <code>start <= limit
	* <= text.length()</code>.
	* @param cursor position at which to translate next, representing offset
	* into text. This value must be between <code>start</code> and
	* <code>limit</code>.
	* @param data a dictionary mapping variables to the sets they
	* represent (maps <code>Character</code> to <code>UnicodeSet</code>)
	* @param filter the filter. Any character for which
	* <tt>filter.contains()</tt> returns <tt>false</tt> will not be
	* altered by this transliterator. If <tt>filter</tt> is
	* <tt>null</tt> then no filtering is applied.
	* @return the matching rule, or null if none found.
	*/
	TransliterationRule*
	TransliterationRuleSet::findMatch(const Replaceable& text,
	const UTransPosition& pos,
	const TransliterationRuleData& data,
	const UnicodeFilter* filter) const {
	/* We only need to check our indexed bin of the rule table,
	* based on the low byte of the first key character.
	*/
	int16_t x = (int16_t) (text.charAt(pos.start) & 0xFF);
	for (int32_t i=index[x]; i<index[x+1]; ++i) {
	if (rules[i]->matches(text, pos, data, filter)) {
	return rules[i];
	}
	}
	return NULL;
	}

	/**
	* Attempt to find a matching rule at the specified point in the text.
	* Unlike <code>findMatch()</code>, this method does an incremental match.
	* An incremental match requires that there be no partial matches that might
	* pre-empt the full match that is found. If there are partial matches,
	* then null is returned. A non-null result indicates that a full match has
	* been found, and that it cannot be pre-empted by a partial match
	* regardless of what additional text is added to the translation buffer.
	* @param text the text, both translated and untranslated
	* @param start the beginning index, inclusive; <code>0 <= start
	* <= limit</code>.
	* @param limit the ending index, exclusive; <code>start <= limit
	* <= text.length()</code>.
	* @param cursor position at which to translate next, representing offset
	* into text. This value must be between <code>start</code> and
	* <code>limit</code>.
	* @param data a dictionary mapping variables to the sets they
	* represent (maps <code>Character</code> to <code>UnicodeSet</code>)
	* @param partial output parameter. <code>partial[0]</code> is set to
	* true if a partial match is returned.
	* @param filter the filter. Any character for which
	* <tt>filter.contains()</tt> returns <tt>false</tt> will not be
	* altered by this transliterator. If <tt>filter</tt> is
	* <tt>null</tt> then no filtering is applied.
	* @return the matching rule, or null if none found, or if the text buffer
	* does not have enough text yet to unambiguously match a rule.
	*/
	TransliterationRule*
	TransliterationRuleSet::findIncrementalMatch(const Replaceable& text,
	const UTransPosition& pos,
	const TransliterationRuleData& data,
	UBool& isPartial,
	const UnicodeFilter* filter) const {

	/* We only need to check our indexed bin of the rule table,
	* based on the low byte of the first key character.
	*/
	isPartial = FALSE;
	int16_t x = (int16_t) (text.charAt(pos.start) & 0xFF);
	for (int32_t i=index[x]; i<index[x+1]; ++i) {
	int32_t match = rules[i]->getMatchDegree(text, pos, data, filter);
	switch (match) {
	case TransliterationRule::FULL_MATCH:
	return rules[i];
	case TransliterationRule::PARTIAL_MATCH:
	isPartial = TRUE;
	return NULL;
	}
	}
	return NULL;
	}