Method computeSetFromNodes

kdevplatform/language/util/setrepository.cpp:554–593

Constructs a set node from the given two sub-nodes. Those must be valid, they must not intersect, and they must have a correct split-hierarchy. The do not need to be split around their computed split-position.

//Constructs a set node from the given two sub-nodes. Those must be valid, they must not intersect, and they must have a correct split-hierarchy.
//The do not need to be split around their computed split-position.
uint SetRepositoryAlgorithms::computeSetFromNodes(uint leftNode, uint rightNode, const SetNodeData* left,
                                                  const SetNodeData* right, uchar splitBit)
{
    Q_ASSERT(left->end() <= right->start());
    uint splitPosition = splitPositionForRange(left->start(), right->end(), splitBit);

    Q_ASSERT(splitPosition);

    if (splitPosition < left->end()) {
        //The split-position intersects the left node
        uint leftLeftNode = left->leftNode();
        uint leftRightNode = left->rightNode();

        const SetNodeData* leftLeft = this->getLeftNode(left);
        const SetNodeData* leftRight = this->getRightNode(left);

        Q_ASSERT(splitPosition >= leftLeft->end() && splitPosition <= leftRight->start());

        //Create a new set from leftLeft, and from leftRight + right. That set will have the correct split-position.
        uint newRightNode = computeSetFromNodes(leftRightNode, rightNode, leftRight, right, splitBit);

        return createSetFromNodes(leftLeftNode, newRightNode, leftLeft);
    } else if (splitPosition > right->start()) {
        //The split-position intersects the right node
        uint rightLeftNode = right->leftNode();
        uint rightRightNode = right->rightNode();

        const SetNodeData* rightLeft = this->getLeftNode(right);
        const SetNodeData* rightRight = this->getRightNode(right);

        Q_ASSERT(splitPosition >= rightLeft->end() && splitPosition <= rightRight->start());

        //Create a new set from left + rightLeft, and from rightRight. That set will have the correct split-position.
        uint newLeftNode = computeSetFromNodes(leftNode, rightLeftNode, left, rightLeft, splitBit);

        return createSetFromNodes(newLeftNode, rightRightNode, nullptr, rightRight);
    } else {
        return createSetFromNodes(leftNode, rightNode, left, right);
    }
}

uint SetRepositoryAlgorithms::set_union(uint firstNode, uint secondNode, const SetNodeData* first,
                                        const SetNodeData* second, uchar splitBit)