void
CharacterNode::addValue(void *value, UObjectDeleter *valueDeleter, UErrorCode &status) {
    if (U_FAILURE(status)) {
        if (valueDeleter) {
            valueDeleter(value);
        }
        return;
    }
    if (fValues == NULL) {
        fValues = value;
    } else {
        // At least one value already.
        if (!fHasValuesVector) {
            // There is only one value so far, and not in a vector yet.
            // Create a vector and add the old value.
            UVector *values = new UVector(valueDeleter, NULL, DEFAULT_CHARACTERNODE_CAPACITY, status);
            if (U_FAILURE(status)) {
                if (valueDeleter) {
                    valueDeleter(value);
                }
                return;
            }
            values->addElement(fValues, status);
            fValues = values;
            fHasValuesVector = TRUE;
        }
        // Add the new value.
        ((UVector *)fValues)->addElement(value, status);
    }
}

UVector*
RuleBasedTimeZone::copyRules(UVector* source) {
    if (source == NULL) {
        return NULL;
    }
    UErrorCode ec = U_ZERO_ERROR;
    int32_t size = source->size();
    UVector *rules = new UVector(size, ec);
    if (U_FAILURE(ec)) {
        return NULL;
    }
    int32_t i;
    for (i = 0; i < size; i++) {
        rules->addElement(((TimeZoneRule*)source->elementAt(i))->clone(), ec);
        if (U_FAILURE(ec)) {
            break;
        }
    }
    if (U_FAILURE(ec)) {
        // In case of error, clean up
        for (i = 0; i < rules->size(); i++) {
            TimeZoneRule *rule = (TimeZoneRule*)rules->orphanElementAt(i);
            delete rule;
        }
        delete rules;
        return NULL;
    }
    return rules;
}

UVector *AlphabeticIndex::firstStringsInScript(UErrorCode &status) {
    if (U_FAILURE(status)) {
        return NULL;
    }
    UVector *dest = new UVector(status);
    if (dest == NULL) {
        if (U_SUCCESS(status)) {
            status = U_MEMORY_ALLOCATION_ERROR;
        }
        return NULL;
    }
    dest->setDeleter(uprv_deleteUObject);
    const UChar *src  = HACK_FIRST_CHARS_IN_SCRIPTS;
    const UChar *limit = src + sizeof(HACK_FIRST_CHARS_IN_SCRIPTS) / sizeof(HACK_FIRST_CHARS_IN_SCRIPTS[0]);
    do {
        if (U_FAILURE(status)) {
            return dest;
        }
        UnicodeString *str = new UnicodeString(src, -1);
        if (str == NULL) {
            status = U_MEMORY_ALLOCATION_ERROR;
        } else {
            dest->addElement(str, status);
            src += str->length() + 1;
        }
    } while (src < limit);
    dest->sortWithUComparator(sortCollateComparator, collator_, status);
    return dest;
}

UnicodeString& U_EXPORT2
ZoneMeta::getZoneIdByMetazone(const UnicodeString &mzid, const UnicodeString &region, UnicodeString &result) {
    initializeMetaToOlson();
    UBool isSet = FALSE;
    if (gMetaToOlson != NULL) {
        UErrorCode status = U_ZERO_ERROR;
        UChar mzidUChars[ZID_KEY_MAX];
        mzid.extract(mzidUChars, ZID_KEY_MAX, status);
        if (U_SUCCESS(status) && status!=U_STRING_NOT_TERMINATED_WARNING) {
            UVector *mappings = (UVector*)uhash_get(gMetaToOlson, mzidUChars);
            if (mappings != NULL) {
                // Find a preferred time zone for the given region.
                for (int32_t i = 0; i < mappings->size(); i++) {
                    MetaToOlsonMappingEntry *olsonmap = (MetaToOlsonMappingEntry*)mappings->elementAt(i);
                    if (region.compare(olsonmap->territory, -1) == 0) {
                        result.setTo(olsonmap->id);
                        isSet = TRUE;
                        break;
                    } else if (u_strcmp(olsonmap->territory, gWorld) == 0) {
                        result.setTo(olsonmap->id);
                        isSet = TRUE;
                    }
                }
            }
        }
    }
    if (!isSet) {
        result.remove();
    }
    return result;
}

/**
 * Returns an enumeration over the IDs of all the regions that are children of this region anywhere in the region
 * hierarchy and match the given type.  This API may return an empty enumeration if this region doesn't have any
 * sub-regions that match the given type. For example, calling this method with region "150" (Europe) and type
 * "URGN_TERRITORY" returns a set containing all the territories in Europe ( "FR" (France) - "IT" (Italy) - "DE" (Germany) etc. )
 */
StringEnumeration*
Region::getContainedRegions( URegionType type, UErrorCode &status ) const {
    umtx_initOnce(gRegionDataInitOnce, &loadRegionData, status); // returns immediately if U_FAILURE(status)
    if (U_FAILURE(status)) {
        return NULL;
    }

    UVector *result = new UVector(NULL, uhash_compareChars, status);

    StringEnumeration *cr = getContainedRegions(status);

    for ( int32_t i = 0 ; i < cr->count(status) ; i++ ) {
        const char *id = cr->next(NULL,status);
        const Region *r = Region::getInstance(id,status);
        if ( r->getType() == type ) {
            result->addElement((void *)&r->idStr,status);
        } else {
            StringEnumeration *children = r->getContainedRegions(type, status);
            for ( int32_t j = 0 ; j < children->count(status) ; j++ ) {
                const char *id2 = children->next(NULL,status);
                const Region *r2 = Region::getInstance(id2,status);
                result->addElement((void *)&r2->idStr,status);
            }
            delete children;
        }
    }
    delete cr;
    StringEnumeration* resultEnumeration = new RegionNameEnumeration(result,status);
    delete result;
    return resultEnumeration;
}

//-----------------------------------------------------------------------------
//
//  sortedAdd  Add a value to a vector of sorted values (ints).
//             Do not replicate entries; if the value is already there, do not
//                add a second one.
//             Lazily create the vector if it does not already exist.
//
//-----------------------------------------------------------------------------
void RBBITableBuilder::sortedAdd(UVector ** vector, int32_t val)
{
	int32_t i;

	if (*vector == NULL)
	{
		*vector = new UVector(*fStatus);
	}
	if (*vector == NULL || U_FAILURE(*fStatus))
	{
		return;
	}
	UVector * vec = *vector;
	int32_t  vSize = vec->size();
	for (i = 0; i < vSize; i++)
	{
		int32_t valAtI = vec->elementAti(i);
		if (valAtI == val)
		{
			// The value is already in the vector.  Don't add it again.
			return;
		}
		if (valAtI > val)
		{
			break;
		}
	}
	vec->insertElementAt(val, i, *fStatus);
}

void CompactData::getUniquePatterns(UVector &output, UErrorCode &status) const {
    U_ASSERT(output.isEmpty());
    // NOTE: In C++, this is done more manually with a UVector.
    // In Java, we can take advantage of JDK HashSet.
    for (auto pattern : patterns) {
        if (pattern == nullptr || pattern == USE_FALLBACK) {
            continue;
        }

        // Insert pattern into the UVector if the UVector does not already contain the pattern.
        // Search the UVector from the end since identical patterns are likely to be adjacent.
        for (int32_t i = output.size() - 1; i >= 0; i--) {
            if (u_strcmp(pattern, static_cast<const UChar *>(output[i])) == 0) {
                goto continue_outer;
            }
        }

        // The string was not found; add it to the UVector.
        // ANDY: This requires a const_cast.  Why?
        output.addElement(const_cast<UChar *>(pattern), status);

        continue_outer:
        continue;
    }
}

StringEnumeration*
TimeZoneNamesImpl::getAvailableMetaZoneIDs(const UnicodeString& tzID, UErrorCode& status) const {
    if (U_FAILURE(status)) {
        return NULL;
    }
    const UVector* mappings = ZoneMeta::getMetazoneMappings(tzID);
    if (mappings == NULL) {
        return new MetaZoneIDsEnumeration();
    }

    MetaZoneIDsEnumeration *senum = NULL;
    UVector* mzIDs = new UVector(NULL, uhash_compareUChars, status);
    if (mzIDs == NULL) {
        status = U_MEMORY_ALLOCATION_ERROR;
    }
    if (U_SUCCESS(status)) {
        U_ASSERT(mzIDs != NULL);
        for (int32_t i = 0; U_SUCCESS(status) && i < mappings->size(); i++) {

            OlsonToMetaMappingEntry *map = (OlsonToMetaMappingEntry *)mappings->elementAt(i);
            const UChar *mzID = map->mzid;
            if (!mzIDs->contains((void *)mzID)) {
                mzIDs->addElement((void *)mzID, status);
            }
        }
        if (U_SUCCESS(status)) {
            senum = new MetaZoneIDsEnumeration(mzIDs);
        } else {
            delete mzIDs;
        }
    }
    return senum;
}

UVector *AlphabeticIndex::firstStringsInScript(UErrorCode &status) {
    if (U_FAILURE(status)) {
        return NULL;
    }
    UVector *dest = new UVector(status);
    if (dest == NULL) {
        status = U_MEMORY_ALLOCATION_ERROR;
        return NULL;
    }
    dest->setDeleter(uprv_deleteUObject);
    const UChar *src  = HACK_FIRST_CHARS_IN_SCRIPTS;
    const UChar *limit = src + LENGTHOF(HACK_FIRST_CHARS_IN_SCRIPTS);
    do {
        if (U_FAILURE(status)) {
            return dest;
        }
        UnicodeString *str = new UnicodeString(src, -1);
        if (str == NULL) {
            status = U_MEMORY_ALLOCATION_ERROR;
            return dest;
        }
        dest->addElement(str, status);
        src += str->length() + 1;
    } while (src < limit);
    return dest;
}

int32_t TransliteratorRegistry::countAvailableVariants(const UnicodeString& source,
                                                       const UnicodeString& target) const {
    Hashtable *targets = (Hashtable*) specDAG.get(source);
    if (targets == 0) {
        return 0;
    }
    UVector *variants = (UVector*) targets->get(target);
    // variants may be 0 if the source/target are invalid
    return (variants == 0) ? 0 : variants->size();
}

//-----------------------------------------------------------------------------
//
//   bofFixup.    Fixup for state tables that include {bof} beginning of input testing.
//                Do an swizzle similar to chaining, modifying the followPos set of
//                the bofNode to include the followPos nodes from other {bot} nodes
//                scattered through the tree.
//
//                This function has much in common with calcChainedFollowPos().
//
//-----------------------------------------------------------------------------
void RBBITableBuilder::bofFixup()
{

	if (U_FAILURE(*fStatus))
	{
		return;
	}

	//   The parse tree looks like this ...
	//         fTree root  --->       <cat>
	//                               /     \       .
	//                            <cat>   <#end node>
	//                           /     \  .
	//                     <bofNode>   rest
	//                               of tree
	//
	//    We will be adding things to the followPos set of the <bofNode>
	//
	RBBINode * bofNode = fTree->fLeftChild->fLeftChild;
	U_ASSERT(bofNode->fType == RBBINode::leafChar);
	U_ASSERT(bofNode->fVal == 2);

	// Get all nodes that can be the start a match of the user-written rules
	//  (excluding the fake bofNode)
	//  We want the nodes that can start a match in the
	//     part labeled "rest of tree"
	//
	UVector * matchStartNodes = fTree->fLeftChild->fRightChild->fFirstPosSet;

	RBBINode * startNode;
	int       startNodeIx;
	for (startNodeIx = 0; startNodeIx < matchStartNodes->size(); startNodeIx++)
	{
		startNode = (RBBINode *)matchStartNodes->elementAt(startNodeIx);
		if (startNode->fType != RBBINode::leafChar)
		{
			continue;
		}

		if (startNode->fVal == bofNode->fVal)
		{
			//  We found a leaf node corresponding to a {bof} that was
			//    explicitly written into a rule.
			//  Add everything from the followPos set of this node to the
			//    followPos set of the fake bofNode at the start of the tree.
			//
			setAdd(bofNode->fFollowPos, startNode->fFollowPos);
		}
	}
}

/**
 * Finish constructing a transliterator: only to be called by
 * constructors.  Before calling init(), set trans and filter to NULL.
 * @param list a vector of transliterator objects to be adopted.  It
 * should NOT be empty.  The list should be in declared order.  That
 * is, it should be in the FORWARD order; if direction is REVERSE then
 * the list order will be reversed.
 * @param direction either FORWARD or REVERSE
 * @param fixReverseID if TRUE, then reconstruct the ID of reverse
 * entries by calling getID() of component entries.  Some constructors
 * do not require this because they apply a facade ID anyway.
 * @param status the error code indicating success or failure
 */
void CompoundTransliterator::init(UVector& list,
                                  UTransDirection direction,
                                  UBool fixReverseID,
                                  UErrorCode& status) {
    // assert(trans == 0);

    // Allocate array
    if (U_SUCCESS(status)) {
        count = list.size();
        trans = (Transliterator **)uprv_malloc(count * sizeof(Transliterator *));
        /* test for NULL */
        if (trans == 0) {
            status = U_MEMORY_ALLOCATION_ERROR;
            return;
        }
    }

    if (U_FAILURE(status) || trans == 0) {
         // assert(trans == 0);
        return;
    }

    // Move the transliterators from the vector into an array.
    // Reverse the order if necessary.
    int32_t i;
    for (i=0; i<count; ++i) {
        int32_t j = (direction == UTRANS_FORWARD) ? i : count - 1 - i;
        trans[i] = (Transliterator*) list.elementAt(j);
    }

    // Fix compoundRBTIndex for REVERSE transliterators
    if (compoundRBTIndex >= 0 && direction == UTRANS_REVERSE) {
        compoundRBTIndex = count - 1 - compoundRBTIndex;
    }

    // If the direction is UTRANS_REVERSE then we may need to fix the
    // ID.
    if (direction == UTRANS_REVERSE && fixReverseID) {
        UnicodeString newID;
        for (i=0; i<count; ++i) {
            if (i > 0) {
                newID.append(ID_DELIM);
            }
            newID.append(trans[i]->getID());
        }
        setID(newID);
    }

    computeMaximumContextLength();
}

static void appendUnicodeSetToUVector(UVector &dest, const UnicodeSet &source, UErrorCode &status) {
    UnicodeSetIterator setIter(source);
    while (setIter.next()) {
        const UnicodeString &str = setIter.getString();
        dest.addElement(str.clone(), status);
    }
}

   static void buildFilenameListFrom(UVector<UString>& vec, const UString& arg)
      {
      U_TRACE(5, "Application::buildFilenameListFrom(%p,%.*S)", &vec, U_STRING_TO_TRACE(arg))

      uint32_t pos;
      UTokenizer t(arg);
      UString dir, filename, filter;

      while (t.next(filename, ','))
         {
         if (filename.find_first_of("?*", 0, 2) == U_NOT_FOUND) vec.push(filename);
         else
            {
            pos = filename.find_last_of('/');

            U_INTERNAL_DUMP("pos = %u", pos)

            if (pos == U_NOT_FOUND)
               {
               UDirWalk dirwalk(0, U_STRING_TO_PARAM(filename));

               (void) dirwalk.walk(vec);
               }
            else
               {
               dir    = filename.substr(0U, pos);
               filter = filename.substr(pos + 1);

               UDirWalk dirwalk(dir, U_STRING_TO_PARAM(filter));

               (void) dirwalk.walk(vec);
               }
            }
         }
      }

UBool UVector::containsNone(const UVector& other) const {
    for (int32_t i=0; i<other.size(); ++i) {
        if (indexOf(other.elements[i]) >= 0) {
            return FALSE;
        }
    }
    return TRUE;
}

//-----------------------------------------------------------------------------
//
//   calcFollowPos.    Impossible to explain succinctly.  See Aho, section 3.9
//
//-----------------------------------------------------------------------------
void RBBITableBuilder::calcFollowPos(RBBINode * n)
{
	if (n == NULL ||
	    n->fType == RBBINode::leafChar ||
	    n->fType == RBBINode::endMark)
	{
		return;
	}

	calcFollowPos(n->fLeftChild);
	calcFollowPos(n->fRightChild);

	// Aho rule #1
	if (n->fType == RBBINode::opCat)
	{
		RBBINode * i;  // is 'i' in Aho's description
		uint32_t     ix;

		UVector * LastPosOfLeftChild = n->fLeftChild->fLastPosSet;

		for (ix = 0; ix < (uint32_t)LastPosOfLeftChild->size(); ix++)
		{
			i = (RBBINode *)LastPosOfLeftChild->elementAt(ix);
			setAdd(i->fFollowPos, n->fRightChild->fFirstPosSet);
		}
	}

	// Aho rule #2
	if (n->fType == RBBINode::opStar ||
	    n->fType == RBBINode::opPlus)
	{
		RBBINode  * i;  // again, n and i are the names from Aho's description.
		uint32_t    ix;

		for (ix = 0; ix < (uint32_t)n->fLastPosSet->size(); ix++)
		{
			i = (RBBINode *)n->fLastPosSet->elementAt(ix);
			setAdd(i->fFollowPos, n->fFirstPosSet);
		}
	}



}

/**
 * Register a source-target/variant in the specDAG.  Variant may be
 * empty, but source and target must not be.  If variant is empty then
 * the special variant NO_VARIANT is stored in slot zero of the
 * UVector of variants.
 */
void TransliteratorRegistry::registerSTV(const UnicodeString& source,
                                         const UnicodeString& target,
                                         const UnicodeString& variant) {
    // assert(source.length() > 0);
    // assert(target.length() > 0);
    UErrorCode status = U_ZERO_ERROR;
    Hashtable *targets = (Hashtable*) specDAG.get(source);
    if (targets == 0) {
        targets = new Hashtable(TRUE, status);
        if (U_FAILURE(status) || targets == 0) {
            return;
        }
        targets->setValueDeleter(uprv_deleteUObject);
        specDAG.put(source, targets, status);
    }
    UVector *variants = (UVector*) targets->get(target);
    if (variants == 0) {
        variants = new UVector(uprv_deleteUObject,
                               uhash_compareCaselessUnicodeString, status);
        if (variants == 0) {
            return;
        }
        targets->put(target, variants, status);
    }
    // assert(NO_VARIANT == "");
    // We add the variant string.  If it is the special "no variant"
    // string, that is, the empty string, we add it at position zero.
    if (!variants->contains((void*) &variant)) {
    	UnicodeString *tempus; // Used for null pointer check.
        if (variant.length() > 0) {
        	tempus = new UnicodeString(variant);
        	if (tempus != NULL) {
        		variants->addElement(tempus, status);
        	}
        } else {
        	tempus = new UnicodeString();  // = NO_VARIANT
        	if (tempus != NULL) {
        		variants->insertElementAt(tempus, 0, status);
        	}
        }
    }
}

void RBBITableBuilder::printRuleStatusTable() {
    int32_t  thisRecord = 0;
    int32_t  nextRecord = 0;
    int      i;
    UVector  *tbl = fRB->fRuleStatusVals;

    RBBIDebugPrintf("index |  tags \n");
    RBBIDebugPrintf("-------------------\n");

    while (nextRecord < tbl->size()) {
        thisRecord = nextRecord;
        nextRecord = thisRecord + tbl->elementAti(thisRecord) + 1;
        RBBIDebugPrintf("%4d   ", thisRecord);
        for (i=thisRecord+1; i<nextRecord; i++) {
            RBBIDebugPrintf("  %5d", tbl->elementAti(i));
        }
        RBBIDebugPrintf("\n");
    }
    RBBIDebugPrintf("\n\n");
}

UBool UVector::retainAll(const UVector& other) {
    UBool changed = FALSE;
    for (int32_t j=size()-1; j>=0; --j) {
        int32_t i = other.indexOf(elements[j]);
        if (i < 0) {
            removeElementAt(j);
            changed = TRUE;
        }
    }
    return changed;
}

UBool UVector::removeAll(const UVector& other) {
    UBool changed = FALSE;
    for (int32_t i=0; i<other.size(); ++i) {
        int32_t j = indexOf(other.elements[i]);
        if (j >= 0) {
            removeElementAt(j);
            changed = TRUE;
        }
    }
    return changed;
}