Method set_subtract

kdevplatform/language/util/setrepository.cpp:809–905

}

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

    if (first->start() >= second->end() || second->start() >= first->end())
        return firstNode;

    //The ranges of first and second do intersect
    uint firstStart = first->start(), firstEnd = first->end(), secondStart = second->start(), secondEnd = second->end();

    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 subtract 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());

        uint newLeftNode = set_subtract(firstLeftNode, secondLeftNode, firstLeft, secondLeft, splitBit);
        uint newRightNode = set_subtract(firstRightNode, secondRightNode, firstRight, secondRight, splitBit);

        if (newLeftNode && newRightNode)
            return createSetFromNodes(newLeftNode, newRightNode);
        else if (newLeftNode)
            return newLeftNode;
        else
            return newRightNode;
    } else if (splitPosition > firstStart && splitPosition < firstEnd) {
//    Q_ASSERT(splitPosition >= firstLeft->end() && splitPosition <= firstRight->start());

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

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

        //splitPosition does not intersect second. That means that second is completely on one side of it.