qfragmentmap.cpp

奇趣公司比较新的qt/emd版本

                    rotateLeft(x);
                    p = X.parent;
                    pp = P.parent;
                }
                P.color = Black;
                if (pp) {
                    PP.color = Red;
                    rotateRight(pp);
                }
            }
        } else {
            uint y = PP.left;
            if (y && Y.color == Red) {
                P.color = Black;
                Y.color = Black;
                PP.color = Red;
                x = pp;
            } else {
                if (x == P.left) {
                    x = p;
                    rotateRight(x);
                    p = X.parent;
                    pp = P.parent;
                }
                P.color = Black;
                if (pp) {
                    PP.color = Red;
                    rotateLeft(pp);
                }
            }
        }
    }
    F(root()).color = Black;
    check();
}


uint QFragmentMapData::erase_single(uint z)
{
    uint w = previous(z);
    uint y = z;
    uint x;
    uint p;

    if (!Y.left) {
        x = Y.right;
    } else if (!Y.right) {
        x = Y.left;
    } else {
        y = Y.right;
        while (Y.left)
            y = Y.left;
        x = Y.right;
    }

    PMDEBUG("removeAndRebalance on %d (x=%d, y=%d)", z, x, y);
    inorder();

    if (y != z) {
        F(Z.left).parent = y;
        Y.left = Z.left;
        Y.size_left = Z.size_left;
        if (y != Z.right) {
            /*
                     z                y
                    / \              / \
                   a   b            a   b
                      /                /
                    ...     -->      ...
                    /                /
                   y                x
                  / \
                 0   x
             */
            p = Y.parent;
            if (x)
                X.parent = p;
            P.left = x;
            Y.right = Z.right;
            F(Z.right).parent = y;
            uint n = p;
            while (n != y) {
                N.size_left -= Y.size;
                n = N.parent;
            }
        } else {
            /*
                     z                y
                    / \              / \
                   a   y     -->    a   x
                      / \
                     0   x
             */
            p = y;
        }
        uint zp = Z.parent;
        if (!zp) {
            Q_ASSERT(head->root == z);
            head->root = y;
        } else if (F(zp).left == z) {
            F(zp).left = y;
            F(zp).size_left -= Z.size;
        } else {
            F(zp).right = y;
        }
        Y.parent = zp;
        // Swap the colors
        uint c = Y.color;
        Y.color = Z.color;
        Z.color = c;
        y = z;
    } else {
        /*
                p          p            p          p
               /          /              \          \
              z    -->   x                z  -->     x
              |                           |
              x                           x
         */
        p = Z.parent;
        if (x)
            X.parent = p;
        if (!p) {
            Q_ASSERT(head->root == z);
            head->root = x;
        } else if (P.left == z) {
            P.left = x;
            P.size_left -= Z.size;
        } else {
            P.right = x;
        }
    }
    uint n = z;
    while (N.parent) {
        uint p = N.parent;
        if (P.left == n) {
            PMDEBUG("reducing size_left of %d by %d", N.parent, Z.size);
            P.size_left -= Z.size;
        }
        n = p;
    }

    freeFragment(z);
    PMDEBUG("after removal");
    inorder();
    check();


    if (Y.color != Red) {
        while (X.parent && (x == 0 || X.color == Black)) {
            if (x == P.left) {
                uint w = P.right;
                if (W.color == Red) {
                    W.color = Black;
                    P.color = Red;
                    rotateLeft(p);
                    w = P.right;
                }
                if ((W.left == 0 || F(W.left).color == Black) &&
                    (W.right == 0 || F(W.right).color == Black)) {
                    W.color = Red;
                    x = p;
                    p = X.parent;
                } else {
                    if (W.right == 0 || F(W.right).color == Black) {
                        if (W.left)
                            F(W.left).color = Black;
                        W.color = Red;
                        rotateRight(P.right);
                        w = P.right;
                    }
                    W.color = P.color;
                    P.color = Black;
                    if (W.right)
                        F(W.right).color = Black;
                    rotateLeft(p);
                    break;
                }
            } else {
                uint w = P.left;
                if (W.color == Red) {
                    W.color = Black;
                    P.color = Red;
                    rotateRight(p);
                    w = P.left;
                }
                if ((W.right == 0 || F(W.right).color == Black) &&
                    (W.left == 0 || F(W.left).color == Black)) {
                    W.color = Red;
                    x = p;
                    p = X.parent;
                } else {
                    if (W.left == 0 || F(W.left).color == Black) {
                        if (W.right)
                            F(W.right).color = Black;
                        W.color = Red;
                        rotateLeft(P.left);
                        w = P.left;
                    }
                    W.color = P.color;
                    P.color = Black;
                    if (W.left)
                        F(W.left).color = Black;
                    rotateRight(p);
                    break;
                }
            }
        }
        if (x)
            X.color = Black;
    }

    PMDEBUG("after rebalance");
    inorder();
    check();

    return w;
}

uint QFragmentMapData::findNode(int k) const
{
    uint x = root();

    uint s = k;
    while (x) {
        if (sizeLeft(x) <= s) {
            if (s < sizeLeft(x) + size(x))
                return x;
            s -= sizeLeft(x) + size(x);
            x = X.right;
        } else {
            x = X.left;
        }
    }
    return 0;
}

uint QFragmentMapData::insert_single(int key, uint length)
{
    Q_ASSERT(!findNode(key) || (int)this->position(findNode(key)) == key);

    uint z = createFragment();

    Z.size = length;
    Z.left = 0;
    Z.right = 0;
    Z.size_left = 0;

    PMDEBUG("inserting with key %d", key);
    uint y = 0;
    uint x = root();

    Q_ASSERT(!x || X.parent == 0);

    uint s = key;
//     inorder();
    bool right = false;
    while (x) {
        y = x;
//          PMDEBUG("x=%p: x->size_left=%d, key=%d, s=%d", x, x->size_left, x->key(), s);
        if (s <= X.size_left) {
            x = X.left;
            right = false;
        } else {
            s -= X.size_left + X.size;
            x = X.right;
            right = true;
        }
    }
//     if (y)
//         PMDEBUG("  y=%p: y->size_left=%d, y->key=%d s=%d", y, y->size_left, y ? y->key() : -1, s);

    Z.parent = y;
    if (!y) {
        head->root = z;
    } else if (!right) {
//          PMDEBUG("inserting left");
        Y.left = z;
        Y.size_left = Z.size;
    } else {
//          PMDEBUG("inserting right");
        Y.right = z;
    }
    while (y && Y.parent) {
        uint p = Y.parent;
        if (P.left == y)
            P.size_left += Z.size;
        y = p;
    }
//     PMDEBUG("before rebalance");
//     inorder();
    rebalance(z);

    inorder();
    PMDEBUG("end insert\n");

    return z;
}


int QFragmentMapData::length() const {
    uint root = this->root();
    return root ? sizeLeft(root) + size(root) + sizeRight(root) : 0;
}