// © 2016 and later: Unicode, Inc. and others.

// License & terms of use: http://www.unicode.org/copyright.html

/*

*******************************************************************************

*   Copyright (C) 2010-2012, International Business Machines

*   Corporation and others.  All Rights Reserved.

*******************************************************************************

*   file name:  stringtriebuilder.cpp

*   encoding:   UTF-8

*   tab size:   8 (not used)

*   indentation:4

*

*   created on: 2010dec24

*   created by: Markus W. Scherer

*/

#include "utypeinfo.h"  // for 'typeid' to work

#include "unicode/utypes.h"

#include "unicode/stringtriebuilder.h"

#include "uassert.h"

#include "uhash.h"

U_CDECL_BEGIN

static int32_t U_CALLCONV

hashStringTrieNode(const UHashTok key) {

    return icu::StringTrieBuilder::hashNode(key.pointer);

}

static UBool U_CALLCONV

equalStringTrieNodes(const UHashTok key1, const UHashTok key2) {

    return icu::StringTrieBuilder::equalNodes(key1.pointer, key2.pointer);

}

U_CDECL_END

U_NAMESPACE_BEGIN

StringTrieBuilder::StringTrieBuilder() : nodes(NULL) {}

StringTrieBuilder::~StringTrieBuilder() {

    deleteCompactBuilder();

}

void

StringTrieBuilder::createCompactBuilder(int32_t sizeGuess, UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) {

        return;

    }

    nodes=uhash_openSize(hashStringTrieNode, equalStringTrieNodes, NULL,

                         sizeGuess, &errorCode);

    if(U_SUCCESS(errorCode)) {

        if(nodes==NULL) {

          errorCode=U_MEMORY_ALLOCATION_ERROR;

        } else {

          uhash_setKeyDeleter(nodes, uprv_deleteUObject);

        }

    }

}

void

StringTrieBuilder::deleteCompactBuilder() {

    uhash_close(nodes);

    nodes=NULL;

}

void

StringTrieBuilder::build(UStringTrieBuildOption buildOption, int32_t elementsLength,

                       UErrorCode &errorCode) {

    if(buildOption==USTRINGTRIE_BUILD_FAST) {

        writeNode(0, elementsLength, 0);

    } else /* USTRINGTRIE_BUILD_SMALL */ {

        createCompactBuilder(2*elementsLength, errorCode);

        Node *root=makeNode(0, elementsLength, 0, errorCode);

        if(U_SUCCESS(errorCode)) {

            root->markRightEdgesFirst(-1);

            root->write(*this);

        }

        deleteCompactBuilder();

    }

}

// Requires start<limit,

// and all strings of the [start..limit[ elements must be sorted and

// have a common prefix of length unitIndex.

int32_t

StringTrieBuilder::writeNode(int32_t start, int32_t limit, int32_t unitIndex) {

    UBool hasValue=FALSE;

    int32_t value=0;

    int32_t type;

    if(unitIndex==getElementStringLength(start)) {

        // An intermediate or final value.

        value=getElementValue(start++);

        if(start==limit) {

            return writeValueAndFinal(value, TRUE);  // final-value node

        }

        hasValue=TRUE;

    }

    // Now all [start..limit[ strings are longer than unitIndex.

    int32_t minUnit=getElementUnit(start, unitIndex);

    int32_t maxUnit=getElementUnit(limit-1, unitIndex);

    if(minUnit==maxUnit) {

        // Linear-match node: All strings have the same character at unitIndex.

        int32_t lastUnitIndex=getLimitOfLinearMatch(start, limit-1, unitIndex);

        writeNode(start, limit, lastUnitIndex);

        // Break the linear-match sequence into chunks of at most kMaxLinearMatchLength.

        int32_t length=lastUnitIndex-unitIndex;

        int32_t maxLinearMatchLength=getMaxLinearMatchLength();

        while(length>maxLinearMatchLength) {

            lastUnitIndex-=maxLinearMatchLength;

            length-=maxLinearMatchLength;

            writeElementUnits(start, lastUnitIndex, maxLinearMatchLength);

            write(getMinLinearMatch()+maxLinearMatchLength-1);

        }

        writeElementUnits(start, unitIndex, length);

        type=getMinLinearMatch()+length-1;

    } else {

        // Branch node.

        int32_t length=countElementUnits(start, limit, unitIndex);

        // length>=2 because minUnit!=maxUnit.

        writeBranchSubNode(start, limit, unitIndex, length);

        if(--length<getMinLinearMatch()) {

            type=length;

        } else {

            write(length);

            type=0;

        }

    }

    return writeValueAndType(hasValue, value, type);

}

// start<limit && all strings longer than unitIndex &&

// length different units at unitIndex

int32_t

StringTrieBuilder::writeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex, int32_t length) {

    UChar middleUnits[kMaxSplitBranchLevels];

    int32_t lessThan[kMaxSplitBranchLevels];

    int32_t ltLength=0;

    while(length>getMaxBranchLinearSubNodeLength()) {

        // Branch on the middle unit.

        // First, find the middle unit.

        int32_t i=skipElementsBySomeUnits(start, unitIndex, length/2);

        // Encode the less-than branch first.

        middleUnits[ltLength]=getElementUnit(i, unitIndex);  // middle unit

        lessThan[ltLength]=writeBranchSubNode(start, i, unitIndex, length/2);

        ++ltLength;

        // Continue for the greater-or-equal branch.

        start=i;

        length=length-length/2;

    }

    // For each unit, find its elements array start and whether it has a final value.

    int32_t starts[kMaxBranchLinearSubNodeLength];

    UBool isFinal[kMaxBranchLinearSubNodeLength-1];

    int32_t unitNumber=0;

    do {

        int32_t i=starts[unitNumber]=start;

        UChar unit=getElementUnit(i++, unitIndex);

        i=indexOfElementWithNextUnit(i, unitIndex, unit);

        isFinal[unitNumber]= start==i-1 && unitIndex+1==getElementStringLength(start);

        start=i;

    } while(++unitNumber<length-1);

    // unitNumber==length-1, and the maxUnit elements range is [start..limit[

    starts[unitNumber]=start;

    // Write the sub-nodes in reverse order: The jump lengths are deltas from

    // after their own positions, so if we wrote the minUnit sub-node first,

    // then its jump delta would be larger.

    // Instead we write the minUnit sub-node last, for a shorter delta.

    int32_t jumpTargets[kMaxBranchLinearSubNodeLength-1];

    do {

        --unitNumber;

        if(!isFinal[unitNumber]) {

            jumpTargets[unitNumber]=writeNode(starts[unitNumber], starts[unitNumber+1], unitIndex+1);

        }

    } while(unitNumber>0);

    // The maxUnit sub-node is written as the very last one because we do

    // not jump for it at all.

    unitNumber=length-1;

    writeNode(start, limit, unitIndex+1);

    int32_t offset=write(getElementUnit(start, unitIndex));

    // Write the rest of this node's unit-value pairs.

    while(--unitNumber>=0) {

        start=starts[unitNumber];

        int32_t value;

        if(isFinal[unitNumber]) {

            // Write the final value for the one string ending with this unit.

            value=getElementValue(start);

        } else {

            // Write the delta to the start position of the sub-node.

            value=offset-jumpTargets[unitNumber];

        }

        writeValueAndFinal(value, isFinal[unitNumber]);

        offset=write(getElementUnit(start, unitIndex));

    }

    // Write the split-branch nodes.

    while(ltLength>0) {

        --ltLength;

        writeDeltaTo(lessThan[ltLength]);

        offset=write(middleUnits[ltLength]);

    }

    return offset;

}

// Requires start<limit,

// and all strings of the [start..limit[ elements must be sorted and

// have a common prefix of length unitIndex.

StringTrieBuilder::Node *

StringTrieBuilder::makeNode(int32_t start, int32_t limit, int32_t unitIndex, UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) {

        return NULL;

    }

    UBool hasValue=FALSE;

    int32_t value=0;

    if(unitIndex==getElementStringLength(start)) {

        // An intermediate or final value.

        value=getElementValue(start++);

        if(start==limit) {

            return registerFinalValue(value, errorCode);

        }

        hasValue=TRUE;

    }

    Node *node;

    // Now all [start..limit[ strings are longer than unitIndex.

    int32_t minUnit=getElementUnit(start, unitIndex);

    int32_t maxUnit=getElementUnit(limit-1, unitIndex);

    if(minUnit==maxUnit) {

        // Linear-match node: All strings have the same character at unitIndex.

        int32_t lastUnitIndex=getLimitOfLinearMatch(start, limit-1, unitIndex);

        Node *nextNode=makeNode(start, limit, lastUnitIndex, errorCode);

        // Break the linear-match sequence into chunks of at most kMaxLinearMatchLength.

        int32_t length=lastUnitIndex-unitIndex;

        int32_t maxLinearMatchLength=getMaxLinearMatchLength();

        while(length>maxLinearMatchLength) {

            lastUnitIndex-=maxLinearMatchLength;

            length-=maxLinearMatchLength;

            node=createLinearMatchNode(start, lastUnitIndex, maxLinearMatchLength, nextNode);

            nextNode=registerNode(node, errorCode);

        }

        node=createLinearMatchNode(start, unitIndex, length, nextNode);

    } else {

        // Branch node.

        int32_t length=countElementUnits(start, limit, unitIndex);

        // length>=2 because minUnit!=maxUnit.

        Node *subNode=makeBranchSubNode(start, limit, unitIndex, length, errorCode);

        node=new BranchHeadNode(length, subNode);

    }

    if(hasValue && node!=NULL) {

        if(matchNodesCanHaveValues()) {

            ((ValueNode *)node)->setValue(value);

        } else {

            node=new IntermediateValueNode(value, registerNode(node, errorCode));

        }

    }

    return registerNode(node, errorCode);

}

// start<limit && all strings longer than unitIndex &&

// length different units at unitIndex

StringTrieBuilder::Node *

StringTrieBuilder::makeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex,

                                   int32_t length, UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) {

        return NULL;

    }

    UChar middleUnits[kMaxSplitBranchLevels];

    Node *lessThan[kMaxSplitBranchLevels];

    int32_t ltLength=0;

    while(length>getMaxBranchLinearSubNodeLength()) {

        // Branch on the middle unit.

        // First, find the middle unit.

        int32_t i=skipElementsBySomeUnits(start, unitIndex, length/2);

        // Create the less-than branch.

        middleUnits[ltLength]=getElementUnit(i, unitIndex);  // middle unit

        lessThan[ltLength]=makeBranchSubNode(start, i, unitIndex, length/2, errorCode);

        ++ltLength;

        // Continue for the greater-or-equal branch.

        start=i;

        length=length-length/2;

    }

    if(U_FAILURE(errorCode)) {

        return NULL;

    }

    ListBranchNode *listNode=new ListBranchNode();

    if(listNode==NULL) {

        errorCode=U_MEMORY_ALLOCATION_ERROR;

        return NULL;

    }

    // For each unit, find its elements array start and whether it has a final value.

    int32_t unitNumber=0;

    do {

        int32_t i=start;

        UChar unit=getElementUnit(i++, unitIndex);

        i=indexOfElementWithNextUnit(i, unitIndex, unit);

        if(start==i-1 && unitIndex+1==getElementStringLength(start)) {

            listNode->add(unit, getElementValue(start));

        } else {

            listNode->add(unit, makeNode(start, i, unitIndex+1, errorCode));

        }

        start=i;

    } while(++unitNumber<length-1);

    // unitNumber==length-1, and the maxUnit elements range is [start..limit[

    UChar unit=getElementUnit(start, unitIndex);

    if(start==limit-1 && unitIndex+1==getElementStringLength(start)) {

        listNode->add(unit, getElementValue(start));

    } else {

        listNode->add(unit, makeNode(start, limit, unitIndex+1, errorCode));

    }

    Node *node=registerNode(listNode, errorCode);

    // Create the split-branch nodes.

    while(ltLength>0) {

        --ltLength;

        node=registerNode(

            new SplitBranchNode(middleUnits[ltLength], lessThan[ltLength], node), errorCode);

    }

    return node;

}

StringTrieBuilder::Node *

StringTrieBuilder::registerNode(Node *newNode, UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) {

        delete newNode;

        return NULL;

    }

    if(newNode==NULL) {

        errorCode=U_MEMORY_ALLOCATION_ERROR;

        return NULL;

    }

    const UHashElement *old=uhash_find(nodes, newNode);

    if(old!=NULL) {

        delete newNode;

        return (Node *)old->key.pointer;

    }

    // If uhash_puti() returns a non-zero value from an equivalent, previously

    // registered node, then uhash_find() failed to find that and we will leak newNode.

#if U_DEBUG

    int32_t oldValue=  // Only in debug mode to avoid a compiler warning about unused oldValue.

#endif

    uhash_puti(nodes, newNode, 1, &errorCode);

    U_ASSERT(oldValue==0);

    if(U_FAILURE(errorCode)) {

        delete newNode;

        return NULL;

    }

    return newNode;

}

StringTrieBuilder::Node *

StringTrieBuilder::registerFinalValue(int32_t value, UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) {

        return NULL;

    }

    FinalValueNode key(value);

    const UHashElement *old=uhash_find(nodes, &key);

    if(old!=NULL) {

        return (Node *)old->key.pointer;

    }

    Node *newNode=new FinalValueNode(value);

    if(newNode==NULL) {

        errorCode=U_MEMORY_ALLOCATION_ERROR;

        return NULL;

    }

    // If uhash_puti() returns a non-zero value from an equivalent, previously

    // registered node, then uhash_find() failed to find that and we will leak newNode.

#if U_DEBUG

    int32_t oldValue=  // Only in debug mode to avoid a compiler warning about unused oldValue.

#endif

    uhash_puti(nodes, newNode, 1, &errorCode);

    U_ASSERT(oldValue==0);

    if(U_FAILURE(errorCode)) {

        delete newNode;

        return NULL;

    }

    return newNode;

}

int32_t

StringTrieBuilder::hashNode(const void *node) {

    return ((const Node *)node)->hashCode();

}

UBool

StringTrieBuilder::equalNodes(const void *left, const void *right) {

    return *(const Node *)left==*(const Node *)right;

}

UBool

StringTrieBuilder::Node::operator==(const Node &other) const {

    return this==&other || (typeid(*this)==typeid(other) && hash==other.hash);

}

int32_t

StringTrieBuilder::Node::markRightEdgesFirst(int32_t edgeNumber) {

    if(offset==0) {

        offset=edgeNumber;

    }

    return edgeNumber;

}

UBool

StringTrieBuilder::FinalValueNode::operator==(const Node &other) const {

    if(this==&other) {

        return TRUE;

    }

    if(!Node::operator==(other)) {

        return FALSE;

    }

    const FinalValueNode &o=(const FinalValueNode &)other;

    return value==o.value;

}

void

StringTrieBuilder::FinalValueNode::write(StringTrieBuilder &builder) {

    offset=builder.writeValueAndFinal(value, TRUE);

}

UBool

StringTrieBuilder::ValueNode::operator==(const Node &other) const {

    if(this==&other) {

        return TRUE;

    }

    if(!Node::operator==(other)) {

        return FALSE;

    }

    const ValueNode &o=(const ValueNode &)other;

    return hasValue==o.hasValue && (!hasValue || value==o.value);

}

UBool

StringTrieBuilder::IntermediateValueNode::operator==(const Node &other) const {

    if(this==&other) {

        return TRUE;

    }

    if(!ValueNode::operator==(other)) {

        return FALSE;

    }

    const IntermediateValueNode &o=(const IntermediateValueNode &)other;

    return next==o.next;

}

int32_t

StringTrieBuilder::IntermediateValueNode::markRightEdgesFirst(int32_t edgeNumber) {

    if(offset==0) {

        offset=edgeNumber=next->markRightEdgesFirst(edgeNumber);

    }

    return edgeNumber;

}

void

StringTrieBuilder::IntermediateValueNode::write(StringTrieBuilder &builder) {

    next->write(builder);

    offset=builder.writeValueAndFinal(value, FALSE);

}

UBool

StringTrieBuilder::LinearMatchNode::operator==(const Node &other) const {

    if(this==&other) {

        return TRUE;

    }

    if(!ValueNode::operator==(other)) {

        return FALSE;

    }

    const LinearMatchNode &o=(const LinearMatchNode &)other;

    return length==o.length && next==o.next;

}

int32_t

StringTrieBuilder::LinearMatchNode::markRightEdgesFirst(int32_t edgeNumber) {

    if(offset==0) {

        offset=edgeNumber=next->markRightEdgesFirst(edgeNumber);

    }

    return edgeNumber;

}

UBool

StringTrieBuilder::ListBranchNode::operator==(const Node &other) const {

    if(this==&other) {

        return TRUE;

    }

    if(!Node::operator==(other)) {

        return FALSE;

    }

    const ListBranchNode &o=(const ListBranchNode &)other;

    for(int32_t i=0; i<length; ++i) {

        if(units[i]!=o.units[i] || values[i]!=o.values[i] || equal[i]!=o.equal[i]) {

            return FALSE;

        }

    }

    return TRUE;

}

int32_t

StringTrieBuilder::ListBranchNode::markRightEdgesFirst(int32_t edgeNumber) {

    if(offset==0) {

        firstEdgeNumber=edgeNumber;

        int32_t step=0;

        int32_t i=length;

        do {

            Node *edge=equal[--i];

            if(edge!=NULL) {

                edgeNumber=edge->markRightEdgesFirst(edgeNumber-step);

            }

            // For all but the rightmost edge, decrement the edge number.

            step=1;

        } while(i>0);

        offset=edgeNumber;

    }

    return edgeNumber;

}

void

StringTrieBuilder::ListBranchNode::write(StringTrieBuilder &builder) {

    // Write the sub-nodes in reverse order: The jump lengths are deltas from

    // after their own positions, so if we wrote the minUnit sub-node first,

    // then its jump delta would be larger.

    // Instead we write the minUnit sub-node last, for a shorter delta.

    int32_t unitNumber=length-1;

    Node *rightEdge=equal[unitNumber];

    int32_t rightEdgeNumber= rightEdge==NULL ? firstEdgeNumber : rightEdge->getOffset();

    do {

        --unitNumber;

        if(equal[unitNumber]!=NULL) {

            equal[unitNumber]->writeUnlessInsideRightEdge(firstEdgeNumber, rightEdgeNumber, builder);

        }

    } while(unitNumber>0);

    // The maxUnit sub-node is written as the very last one because we do

    // not jump for it at all.

    unitNumber=length-1;

    if(rightEdge==NULL) {

        builder.writeValueAndFinal(values[unitNumber], TRUE);

    } else {

        rightEdge->write(builder);

    }

    offset=builder.write(units[unitNumber]);

    // Write the rest of this node's unit-value pairs.

    while(--unitNumber>=0) {

        int32_t value;

        UBool isFinal;

        if(equal[unitNumber]==NULL) {

            // Write the final value for the one string ending with this unit.

            value=values[unitNumber];

            isFinal=TRUE;

        } else {

            // Write the delta to the start position of the sub-node.

            U_ASSERT(equal[unitNumber]->getOffset()>0);

            value=offset-equal[unitNumber]->getOffset();

            isFinal=FALSE;

        }

        builder.writeValueAndFinal(value, isFinal);

        offset=builder.write(units[unitNumber]);

    }

}

UBool

StringTrieBuilder::SplitBranchNode::operator==(const Node &other) const {

    if(this==&other) {

        return TRUE;

    }

    if(!Node::operator==(other)) {

        return FALSE;

    }

    const SplitBranchNode &o=(const SplitBranchNode &)other;

    return unit==o.unit && lessThan==o.lessThan && greaterOrEqual==o.greaterOrEqual;

}

int32_t

StringTrieBuilder::SplitBranchNode::markRightEdgesFirst(int32_t edgeNumber) {

    if(offset==0) {

        firstEdgeNumber=edgeNumber;

        edgeNumber=greaterOrEqual->markRightEdgesFirst(edgeNumber);

        offset=edgeNumber=lessThan->markRightEdgesFirst(edgeNumber-1);

    }

    return edgeNumber;

}

void

StringTrieBuilder::SplitBranchNode::write(StringTrieBuilder &builder) {

    // Encode the less-than branch first.

    lessThan->writeUnlessInsideRightEdge(firstEdgeNumber, greaterOrEqual->getOffset(), builder);

    // Encode the greater-or-equal branch last because we do not jump for it at all.

    greaterOrEqual->write(builder);

    // Write this node.

    U_ASSERT(lessThan->getOffset()>0);

    builder.writeDeltaTo(lessThan->getOffset());  // less-than

    offset=builder.write(unit);

}

UBool

StringTrieBuilder::BranchHeadNode::operator==(const Node &other) const {

    if(this==&other) {

        return TRUE;

    }

    if(!ValueNode::operator==(other)) {

        return FALSE;

    }

    const BranchHeadNode &o=(const BranchHeadNode &)other;

    return length==o.length && next==o.next;

}

int32_t

StringTrieBuilder::BranchHeadNode::markRightEdgesFirst(int32_t edgeNumber) {

    if(offset==0) {

        offset=edgeNumber=next->markRightEdgesFirst(edgeNumber);

    }

    return edgeNumber;

}

void

StringTrieBuilder::BranchHeadNode::write(StringTrieBuilder &builder) {

    next->write(builder);

    if(length<=builder.getMinLinearMatch()) {

        offset=builder.writeValueAndType(hasValue, value, length-1);

    } else {

        builder.write(length-1);

        offset=builder.writeValueAndType(hasValue, value, 0);

    }

}

U_NAMESPACE_END