ttreepage.java

这个是perst-269.zip下面的SOURCECODE,和大家分享了。

            }
            if (balance < 0) { 
                balance = 0;
                return OK;
            } else if (balance == 0) { 
                balance = 1;
                return OVERFLOW;
            } else { 
                TtreePage right = this.right;
                right.load();
                right.modify();
                if (right.balance > 0) { // single RR turn
                    this.right = right.left;
                    right.left = this;
                    balance = 0;
                    right.balance = 0;
                    ref.pg = right;
                } else { // double RL turn
                    TtreePage left = right.left;
                    left.load();
                    left.modify();
                    right.left = left.right;
                    left.right = right;
                    this.right = left.left;
                    left.left = this;
                    balance = (left.balance > 0) ? -1 : 0;
                    right.balance = (left.balance < 0) ? 1 : 0;
                    left.balance = 0;
                    ref.pg = left;
                }
                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) {
            System.arraycopy(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 { 
            IPersistent reinsertItem;
            if (balance >= 0) { 
                reinsertItem = loadItem(0);
                System.arraycopy(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);
                System.arraycopy(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);
        }
    }
       
    final int balanceLeftBranch(PageReference ref) 
    {
        if (balance < 0) { 
            balance = 0;
            return UNDERFLOW;
        } else if (balance == 0) { 
            balance = 1;
            return OK;
        } else { 
            TtreePage right = this.right;
            right.load();
            right.modify();
            if (right.balance >= 0) { // single RR turn
                this.right = right.left;
                right.left = this;
                if (right.balance == 0) { 
                    this.balance = 1;
                    right.balance = -1;
                    ref.pg = right;
                    return OK;
                } else { 
                    balance = 0;
                    right.balance = 0;
                    ref.pg = right;
                    return UNDERFLOW;
                }
            } else { // double RL turn
                TtreePage left = right.left;
                left.load();
                left.modify();
                right.left = left.right;
                left.right = right;
                this.right = left.left;
                left.left = this;
                balance = left.balance > 0 ? -1 : 0;
                right.balance = left.balance < 0 ? 1 : 0;
                left.balance = 0;
                ref.pg = left;
                return UNDERFLOW;
            }
        }
    }

    final int balanceRightBranch(PageReference ref) 
    {
        if (balance > 0) { 
            balance = 0;
            return UNDERFLOW;
        } else if (balance == 0) { 
            balance = -1;
            return OK;
        } else { 
            TtreePage left = this.left;
            left.load();
            left.modify();
            if (left.balance <= 0) { // single LL turn
                this.left = left.right;
                left.right = this;
                if (left.balance == 0) { 
                    balance = -1;
                    left.balance = 1;
                    ref.pg = left;
                    return OK;
                } else { 
                    balance = 0;
                    left.balance = 0;
                    ref.pg = left;
                    return UNDERFLOW;
                }
            } else { // double LR turn
                TtreePage right = left.right;
                right.load();
                right.modify();
                left.right = right.left;
                right.left = left;
                this.left = right.right;
                right.right = this;
                balance = right.balance < 0 ? 1 : 0;
                left.balance = right.balance > 0 ? -1 : 0;
                right.balance = 0;
                ref.pg = right;
                return UNDERFLOW;
            }
        }
    }
    
    final int remove(PersistentComparator comparator, IPersistent mbr, PageReference ref)
    {
        load();
        TtreePage pg;
        int n = nItems;
        int diff = comparator.compareMembers(mbr, loadItem(0));
        if (diff <= 0) { 
            if (left != null) { 
                modify();
                pg = ref.pg;
                ref.pg = left;
                int h = left.remove(comparator, mbr, ref);
                left = ref.pg;
                ref.pg = pg;
                if (h == UNDERFLOW) { 
                    return balanceLeftBranch(ref);
                } 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();
                            ref.pg = left;
                            return UNDERFLOW;
                        } else if (left == null) { 
                            deallocate();
                            ref.pg = right;
                            return UNDERFLOW;
                        } 
                    }
                    modify();
                    if (n <= minItems) { 
                        if (left != null && balance <= 0) {  
                            TtreePage prev = left;
                            prev.load();
                            while (prev.right != null) {                                 
                                prev = prev.right;
                                prev.load();
                            }
                            System.arraycopy(item, 0, item, 1, i);
                            //while (--i >= 0) { 
                            //    item[i+1] = item[i];
                            //}
                            item[0] = prev.item[prev.nItems-1];
                            pg = ref.pg;
                            ref.pg = left;
                            int h = left.remove(comparator, loadItem(0), ref);
                            left = ref.pg;
                            ref.pg = pg;
                            if (h == UNDERFLOW) {
                                h = balanceLeftBranch(ref);
                            }
                            return h;
                        } else if (right != null) { 
                            TtreePage next = right;
                            next.load();
                            while (next.left != null) { 
                                next = next.left;
                                next.load();
                            }
                            System.arraycopy(item, i+1, item, i, n-i-1);
                            //while (++i < n) { 
                            //    item[i-1] = item[i];
                            //}
                            item[n-1] = next.item[0];
                            pg = ref.pg;
                            ref.pg = right;
                            int h = right.remove(comparator, loadItem(n-1), ref);
                            right = ref.pg;
                            ref.pg = pg;
                            if (h == UNDERFLOW) {
                                h = balanceRightBranch(ref);
                            }
                            return h;
                        }
                    }
                    System.arraycopy(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 = ref.pg;
            ref.pg = right;
            int h = right.remove(comparator, mbr, ref);
            right = ref.pg;
            ref.pg = pg;
            if (h == UNDERFLOW) { 
                return balanceRightBranch(ref);
            } else { 
                return h;
            }
        }
        return NOT_FOUND;
    }


    final 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;
    }

    final void prune() { 
        load();
        if (left != null) { 
            left.prune();
        }
        if (right != null) { 
            right.prune();
        }
        deallocate();
    }

}