ttreepage.java

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

package org.garret.perst.impl;

import org.garret.perst.*;
import java.util.ArrayList;

public class TtreePage extends Persistent  { 
    static final int maxItems = (Page.pageSize-ObjectHeader.sizeof-4*5)/4;
    static final int minItems = maxItems - 2; // minimal number of items in internal node

    TtreePage   left;
    TtreePage   right;
    int         balance;
    int         nItems;
    IPersistent item[];

    static class PageReference { 
        TtreePage pg;
        
        PageReference(TtreePage p) { pg = p; }
    }

    public boolean recursiveLoading() {
        return false;
    }

    TtreePage() {}

    TtreePage(IPersistent mbr) { 
        nItems = 1;
        item = new IPersistent[maxItems];
        item[0] = mbr;
    }

    final IPersistent loadItem(int i) 
    { 
        IPersistent mbr = item[i];
        mbr.load();
        return mbr;
    }

    final boolean find(PersistentComparator comparator, Object minValue, int minInclusive, 
                       Object maxValue, int maxInclusive, ArrayList selection)
    { 
        int l, r, m, n;
        load();
        n = nItems;
        if (minValue != null) { 
            if (-comparator.compareMemberWithKey(loadItem(0), minValue) >= minInclusive) {       
                if (-comparator.compareMemberWithKey(loadItem(n-1), minValue) >= minInclusive) { 
                    if (right != null) { 
                        return right.find(comparator, minValue, minInclusive, maxValue, maxInclusive, selection); 
                    } 
                    return true;
                }
                for (l = 0, r = n; l < r;) { 
                    m = (l + r) >> 1;
                    if (-comparator.compareMemberWithKey(loadItem(m), minValue) >= minInclusive) {
                        l = m+1;
                    } else { 
                        r = m;
                    }
                }
                while (r < n) { 
                    if (maxValue != null
                        && comparator.compareMemberWithKey(loadItem(r), maxValue) >= maxInclusive)
                    { 
                        return false;
                    }
                    selection.add(loadItem(r));
                    r += 1;
                }
                if (right != null) { 
                    return right.find(comparator, minValue, minInclusive, maxValue, maxInclusive, selection); 
                } 
                return true;    
            }
        }       
        if (left != null) { 
            if (!left.find(comparator, minValue, minInclusive, maxValue, maxInclusive, selection)) { 
                return false;
            }
        }
        for (l = 0; l < n; l++) { 
            if (maxValue != null && comparator.compareMemberWithKey(loadItem(l), maxValue) >= maxInclusive) {
                return false;
            }
            selection.add(loadItem(l));
        }
        if (right != null) { 
            return right.find(comparator, minValue, minInclusive, maxValue, maxInclusive, selection);
        }         
        return true;
    }
    
    final boolean contains(PersistentComparator comparator, IPersistent mbr)
    { 
        int l, r, m, n;
        load();
        n = nItems;
        if (comparator.compareMembers(loadItem(0), mbr) < 0) {      
            if (comparator.compareMembers(loadItem(n-1), mbr) < 0) { 
                if (right != null) { 
                    return right.contains(comparator, mbr); 
                } 
                return false;
            }
            for (l = 0, r = n; l < r;) { 
                m = (l + r) >> 1;
                if (comparator.compareMembers(loadItem(m), mbr) < 0) {
                    l = m+1;
                } else { 
                    r = m;
                }
            }
            while (r < n) { 
                if (mbr == item[r]) { 
                    return true;
                }
                if (comparator.compareMembers(item[r], mbr) > 0) { 
                    return false;
                }
                r += 1;
            }
            if (right != null) { 
                return right.contains(comparator, mbr); 
            } 
            return false;       
        }
        if (left != null) { 
            if (left.contains(comparator, mbr)) { 
                return true;
            }
        }
        for (l = 0; l < n; l++) { 
            if (mbr == item[l]) { 
                return true;
            }
            if (comparator.compareMembers(item[l], mbr) > 0) {
                return false;
            }
        }
        if (right != null) { 
            return right.contains(comparator, mbr);
        }         
        return false;
    }

    final boolean containsObject(PersistentComparator comparator, IPersistent mbr)
    { 
        int l, r, m, n;
        load();
        n = nItems;
        if (comparator.compareMembers(loadItem(0), mbr) < 0) {      
            if (comparator.compareMembers(loadItem(n-1), mbr) < 0) { 
                if (right != null) { 
                    return right.containsObject(comparator, mbr); 
                } 
                return false;
            }
            for (l = 0, r = n; l < r;) { 
                m = (l + r) >> 1;
                if (comparator.compareMembers(loadItem(m), mbr) < 0) {
                    l = m+1;
                } else { 
                    r = m;
                }
            }
            while (r < n) { 
                if (mbr.equals(loadItem(r))) { 
                    return true;
                }
                if (comparator.compareMembers(item[r], mbr) > 0) { 
                    return false;
                }
                r += 1;
            }
            if (right != null) { 
                return right.containsObject(comparator, mbr); 
            } 
            return false;       
        }
        if (left != null) { 
            if (left.containsObject(comparator, mbr)) { 
                return true;
            }
        }
        for (l = 0; l < n; l++) { 
            if (mbr.equals(loadItem(l))) { 
                return true;
            }
            if (comparator.compareMembers(item[l], mbr) > 0) {
                return false;
            }
        }
        if (right != null) { 
            return right.containsObject(comparator, mbr);
        }         
        return false;
    }

    
    static final int OK         = 0;
    static final int NOT_UNIQUE = 1;
    static final int NOT_FOUND  = 2;
    static final int OVERFLOW   = 3;
    static final int UNDERFLOW  = 4;

    final int insert(PersistentComparator comparator, IPersistent mbr, boolean unique, PageReference ref) 
    { 
        load();
        int n = nItems;
        TtreePage pg;
        int diff = comparator.compareMembers(mbr, loadItem(0));
        if (diff <= 0) { 
            if (unique && diff == 0) { 
                return NOT_UNIQUE;
            }
            if ((left == null || diff == 0) && n != maxItems) { 
                modify();
                //for (int i = n; i > 0; i--) item[i] = item[i-1];
                System.arraycopy(item, 0, item, 1, n);
                item[0] = mbr;
                nItems += 1;
                return OK;
            } 
            if (left == null) { 
                modify();
                left = new TtreePage(mbr);
            } else {
                pg = ref.pg;
                ref.pg = left;
                int result = left.insert(comparator, mbr, unique, ref);
                if (result == NOT_UNIQUE) { 
                    return NOT_UNIQUE;
                }
                modify();
                left = ref.pg;
                ref.pg = pg;
                if (result == OK) return OK;
            }
            if (balance > 0) { 
                balance = 0;
                return OK;
            } else if (balance == 0) { 
                balance = -1;
                return OVERFLOW;
            } else { 
                TtreePage left = this.left;
                left.load();
                left.modify();
                if (left.balance < 0) { // single LL turn
                    this.left = left.right;
                    left.right = this;
                    balance = 0;
                    left.balance = 0;
                    ref.pg = left;
                } 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 OK;
            }
        } 
        diff = comparator.compareMembers(mbr, loadItem(n-1));
        if (diff >= 0) { 
            if (unique && diff == 0) { 
                return NOT_UNIQUE;
            }
            if ((right == null || diff == 0) && n != maxItems) { 
                modify();
                item[n] = mbr;
                nItems += 1;
                return OK;
            }
            if (right == null) { 
                 modify();
                 right = new TtreePage(mbr);
            } else { 
                pg = ref.pg;
                ref.pg = right;
                int result = right.insert(comparator, mbr, unique, ref);
                if (result == NOT_UNIQUE) { 
                    return NOT_UNIQUE;
                }
                modify();
                right = ref.pg;
                ref.pg = pg;
                if (result == OK) return OK;