Method set_union

kdevplatform/language/util/setrepository.cpp:595–685

}

uint SetRepositoryAlgorithms::set_union(uint firstNode, uint secondNode, const SetNodeData* first,
                                        const SetNodeData* second, uchar splitBit)
{
    if (firstNode == secondNode)
        return firstNode;

    uint firstStart = first->start(), secondEnd = second->end();

    if (firstStart >= secondEnd)
        return computeSetFromNodes(secondNode, firstNode, second, first, splitBit);

    uint firstEnd = first->end(), secondStart = second->start();

    if (secondStart >= firstEnd)
        return computeSetFromNodes(firstNode, secondNode, first, second, splitBit);

    //The ranges of first and second do intersect

    uint newStart = firstStart < secondStart ? firstStart : secondStart;
    uint newEnd = firstEnd > secondEnd ? firstEnd : secondEnd;

    //Compute the split-position for the resulting merged node
    uint splitPosition = splitPositionForRange(newStart, newEnd, splitBit);

    //Since the ranges overlap, we can be sure that either first or second contain splitPosition.
    //The node that contains it, will also be split by it.

    if (splitPosition > firstStart && splitPosition < firstEnd && splitPosition > secondStart &&
        splitPosition < secondEnd) {
        //The split-position intersect with both first and second. Continue the union on both sides of the split-position, and merge it.

        uint firstLeftNode = first->leftNode();
        uint firstRightNode = first->rightNode();
        uint secondLeftNode = second->leftNode();
        uint secondRightNode = second->rightNode();

        const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode);
        const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode);
        const SetNodeData* secondLeft = repository.itemFromIndex(secondLeftNode);
        const SetNodeData* secondRight = repository.itemFromIndex(secondRightNode);

        Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start());
        Q_ASSERT(splitPosition >= secondLeft->end() && splitPosition <= secondRight->start());

        return createSetFromNodes(set_union(firstLeftNode, secondLeftNode, firstLeft, secondLeft, splitBit),
                                  set_union(firstRightNode, secondRightNode, firstRight, secondRight, splitBit));
    } else if (splitPosition > firstStart && splitPosition < firstEnd) {
        uint firstLeftNode = first->leftNode();
        uint firstRightNode = first->rightNode();

        const SetNodeData* firstLeft = repository.itemFromIndex(firstLeftNode);
        const SetNodeData* firstRight = repository.itemFromIndex(firstRightNode);

        Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start());

        //splitPosition does not intersect second. That means that second is completely on one side of it.
        //So we only need to union that side of first with second.