ttreepage.cs

Perst开源实时数据库

                        rp.left = this;
                        balance = 0;
                        rp.balance = 0;
                        pgRef = rp;
                    } 
                    else 
                    { // double RL turn
                        lp = rp.left;
                        lp.Load();
                        lp.Modify();
                        rp.left = lp.right;
                        lp.right = rp;
                        this.right = lp.left;
                        lp.left = this;
                        balance = (lp.balance > 0) ? -1 : 0;
                        rp.balance = (lp.balance < 0) ? 1 : 0;
                        lp.balance = 0;
                        pgRef = lp;
                    }
                    return OK;
                }
            }
            int l = 1, r = n-1;
            while (l < r)  
            {
                int i = (l+r) >> 1;
                diff = comparator.CompareMembers(mbr, loadItem(i));
                if (diff > 0) 
                { 
                    l = i + 1;
                } 
                else 
                { 
                    r = i;
                    if (diff == 0) 
                    { 
                        if (unique) 
                        { 
                            return NOT_UNIQUE;
                        }
                        break;
                    }
                }
            }
            // Insert before item[r]
            Modify();
            if (n != maxItems) 
            {
                Array.Copy(item, r, item, r+1, n-r);
                //for (int i = n; i > r; i--) item[i] = item[i-1]; 
                item[r] = mbr;
                nItems += 1;
                return OK;
            } 
            else 
            { 
                if (balance >= 0) 
                { 
                    reinsertItem = loadItem(0);
                    Array.Copy(item, 1, item, 0, r-1);
                    //for (int i = 1; i < r; i++) item[i-1] = item[i]; 
                    item[r-1] = mbr;
                } 
                else 
                { 
                    reinsertItem = loadItem(n-1);
                    Array.Copy(item, r, item, r+1, n-r-1);
                    //for (int i = n-1; i > r; i--) item[i] = item[i-1]; 
                    item[r] = mbr;
                }
                return insert(comparator, reinsertItem, unique, ref pgRef);
            }
        }
       
#if USE_GENERICS
        internal int balanceLeftBranch(ref TtreePage<K,V> pgRef) 
        {
            TtreePage<K,V> lp, rp;
#else
        internal int balanceLeftBranch(ref TtreePage pgRef) 
        {
            TtreePage lp, rp;
#endif
            if (balance < 0) 
            { 
                balance = 0;
                return UNDERFLOW;
            } 
            else if (balance == 0) 
            { 
                balance = 1;
                return OK;
            } 
            else 
            { 
                rp = this.right;
                rp.Load();
                rp.Modify();
                if (rp.balance >= 0) 
                { // single RR turn
                    this.right = rp.left;
                    rp.left = this;
                    if (rp.balance == 0) 
                    { 
                        this.balance = 1;
                        rp.balance = -1;
                        pgRef = rp;
                        return OK;
                    } 
                    else 
                    { 
                        balance = 0;
                        rp.balance = 0;
                        pgRef = rp;
                        return UNDERFLOW;
                    }
                } 
                else 
                { // double RL turn
                    lp = rp.left;
                    lp.Load();
                    lp.Modify();
                    rp.left = lp.right;
                    lp.right = rp;
                    this.right = lp.left;
                    lp.left = this;
                    balance = lp.balance > 0 ? -1 : 0;
                    rp.balance = lp.balance < 0 ? 1 : 0;
                    lp.balance = 0;
                    pgRef = lp;
                    return UNDERFLOW;
                }
            }
        }

#if USE_GENERICS
        internal int balanceRightBranch(ref TtreePage<K,V> pgRef) 
        {
            TtreePage<K,V> lp, rp;
#else
        internal int balanceRightBranch(ref TtreePage pgRef) 
        {
            TtreePage lp, rp;
#endif
            if (balance > 0) 
            { 
                balance = 0;
                return UNDERFLOW;
            } 
            else if (balance == 0) 
            { 
                balance = -1;
                return OK;
            } 
            else 
            { 
                lp = this.left;
                lp.Load();
                lp.Modify();
                if (lp.balance <= 0) 
                { // single LL turn
                    this.left = lp.right;
                    lp.right = this;
                    if (lp.balance == 0) 
                    { 
                        balance = -1;
                        lp.balance = 1;
                        pgRef = lp;
                        return OK;
                    } 
                    else 
                    { 
                        balance = 0;
                        lp.balance = 0;
                        pgRef = lp;
                        return UNDERFLOW;
                    }
                } 
                else 
                { // double LR turn
                    rp = lp.right;
                    rp.Load();
                    rp.Modify();
                    lp.right = rp.left;
                    rp.left = lp;
                    this.left = rp.right;
                    rp.right = this;
                    balance = rp.balance < 0 ? 1 : 0;
                    lp.balance = rp.balance > 0 ? -1 : 0;
                    rp.balance = 0;
                    pgRef = rp;
                    return UNDERFLOW;
                }
            }
        }
    
#if USE_GENERICS
        internal int remove(PersistentComparator<K,V> comparator, V mbr, ref TtreePage<K,V> pgRef)
        {
            TtreePage<K,V> pg, next, prev;
#else
        internal int remove(PersistentComparator comparator, IPersistent mbr, ref TtreePage pgRef)
        {
            TtreePage pg, next, prev;
#endif
            Load();
            int n = nItems;
            int diff = comparator.CompareMembers(mbr, loadItem(0));
            if (diff <= 0) 
            { 
                if (left != null) 
                { 
                    Modify();
                    pg = pgRef;
                    pgRef = left;
                    int h = left.remove(comparator, mbr, ref pgRef);
                    left = pgRef;
                    pgRef = pg;
                    if (h == UNDERFLOW) 
                    { 
                        return balanceLeftBranch(ref pgRef);
                    } 
                    else if (h == OK) 
                    { 
                        return OK;
                    }
                }
            }
            diff = comparator.CompareMembers(mbr, loadItem(n-1));
            if (diff <= 0) 
            {	    
                for (int i = 0; i < n; i++) 
                { 
                    if (item[i] == mbr) 
                    { 
                        if (n == 1) 
                        { 
                            if (right == null) 
                            { 
                                Deallocate();
                                pgRef = left;
                                return UNDERFLOW;
                            } 
                            else if (left == null) 
                            { 
                                Deallocate();
                                pgRef = right;
                                return UNDERFLOW;
                            } 
                        }
                        Modify();
                        if (n <= minItems) 
                        { 
                            if (left != null && balance <= 0) 
                            {  
                                prev = left;
                                prev.Load();
                                while (prev.right != null) 
                                {                                 
                                    prev = prev.right;
                                    prev.Load();
                                }
                                Array.Copy(item, 0, item, 1, i);
                                //while (--i >= 0) 
                                //{ 
                                //    item[i+1] = item[i];
                                //}
                                item[0] = prev.item[prev.nItems-1];
                                pg = pgRef;
                                pgRef = left;
                                int h = left.remove(comparator, loadItem(0), ref pgRef);
                                left = pgRef;
                                pgRef = pg;
                                if (h == UNDERFLOW) 
                                {
                                    h = balanceLeftBranch(ref pgRef);
                                }
                                return h;
                            } 
                            else if (right != null) 
                            { 
                                next = right;
                                next.Load();
                                while (next.left != null) 
                                { 
                                    next = next.left;
                                    next.Load();
                                }
                                Array.Copy(item, i+1, item, i, n-i-1);
                                //while (++i < n) 
                                //{ 
                                //    item[i-1] = item[i];
                                //}
                                item[n-1] = next.item[0];
                                pg = pgRef;
                                pgRef = right;
                                int h = right.remove(comparator, loadItem(n-1), ref pgRef);
                                right = pgRef;
                                pgRef = pg;
                                if (h == UNDERFLOW) 
                                {
                                    h = balanceRightBranch(ref pgRef);
                                }
                                return h;
                            }
                        }
                        Array.Copy(item, i+1, item, i, n-i-1);
                        //while (++i < n) 
                        //{ 
                        //    item[i-1] = item[i];
                        //}
                        item[n-1] = null;
                        nItems -= 1;
                        return OK;
                    }
                }
            }
            if (right != null) 
            { 
                Modify();
                pg = pgRef;
                pgRef = right;
                int h = right.remove(comparator, mbr, ref pgRef);
                right = pgRef;
                pgRef = pg;
                if (h == UNDERFLOW) 
                { 
                    return balanceRightBranch(ref pgRef);
                }
                else 
                { 
                    return h;
                }
            }
            return NOT_FOUND;
        }


        internal int toArray(IPersistent[] arr, int index) 
        { 
            Load();
            if (left != null) 
            { 
                index = left.toArray(arr, index);
            }
            for (int i = 0, n = nItems; i < n; i++) 
            { 
                arr[index++] = loadItem(i);
            }
            if (right != null) 
            { 
                index = right.toArray(arr, index);
            }
            return index;
        }

        internal void prune() 
        { 
            Load();
            if (left != null) 
            { 
                left.prune();
            }
            if (right != null) 
            { 
                right.prune();
            }
            Deallocate();
        }

    }
}