dxbbnode.java

用Java写的面相对象的数据库管理系统

// You can redistribute this software and/or modify it under the terms of
// the Ozone Library License version 1 published by ozone-db.org.
//
// The original code and portions created by SMB are
// Copyright (C) 1997-2000 by SMB GmbH. All rights reserved.
//
// $Id: DxBBnode.java,v 1.7 2000/10/28 16:55:14 daniela Exp $

package org.ozoneDB.DxLib;

import java.io.IOException;


final class DxBBnode extends DxObject {
    
    final static long serialVersionUID = 1L;
    
    DxBBnode pa;
    DxBBnode re;
    DxBBnode li;
    boolean isRight;
    int lWeight;
    int rWeight;
    Object data;
    Object key;
    DxComparator comparator;
    
    
    /** */
    public DxBBnode() {
        lWeight = 1;
        rWeight = 1;
    }
    
    
    /** */
    public DxBBnode( Object _data, Object _key, DxComparator _comparator ) {
        lWeight = 1;
        rWeight = 1;
        data = _data;
        key = _key;
        comparator = _comparator;
    }
    
    
    /** */
    public DxBBnode findNodeKey( Object _key ) {
        if (comparator.compareEquals( key, _key )) {
            return this;
        } 
        if (comparator.compareIsLess( key, _key ) && re != null) {
            return re.findNodeKey( _key );
        } else {
            if (li != null) {
                return li.findNodeKey( _key );
            } 
        } 
        return null;
    } 
    
    
    /** */
    public DxBBnode findNodeObject( Object obj ) {
        if (data.equals( obj )) {
            return this;
        } 
        DxBBnode node = null;
        if (li != null) {
            node = li.findNodeObject( obj );
        } 
        if (re != null && node == null) {
            node = re.findNodeObject( obj );
        } 
        return node;
    } 
    
    
    /** */
    public boolean insertNode( DxBBnode node ) {
        boolean ret = true;
        if (key != null && comparator.compareEquals( node.key, key )) {
            return false;
        } 
        if (key != null && comparator.compareIsLess( node.key, key )) {
            if (li == null) {
                li = node;
                node.pa = this;
                node.isRight = false;
                lWeight++;
            } else {
                if (ret = li.insertNode( node )) {
                    lWeight++;
                } 
            } 
        } else {
            if (re == null) {
                re = node;
                node.pa = this;
                node.isRight = true;
                rWeight++;
            } else {
                if (ret = re.insertNode( node )) {
                    rWeight++;
                } 
            } 
        } 
        checkWeight();
        return ret;
    } 
    
    
    /** */
    public DxBBnode removeNodeKey( Object _key ) {
        DxBBnode P = null;
        
        if (comparator.compareEquals( key, _key )) {
            
            // ohne linken und rechten sohn
            if (re == null && li == null) {
                if (isRight) {
                    pa.re = null;
                } else {
                    pa.li = null;
                } 
                pa = null;
                return this;
            } 
            
            // in knoten gefunden (nur linker sohn)
            if (re == null && li != null) {
                li.isRight = isRight;
                li.pa = pa;
                if (isRight) {
                    pa.re = li;
                } else {
                    pa.li = li;
                } 
                return this;
            } 
            
            // in knoten gefunden (nur rechter sohn)
            if (re != null && li == null) {
                re.isRight = isRight;
                re.pa = pa;
                if (isRight) {
                    pa.re = re;
                } else {
                    pa.li = re;
                } 
                return this;
            } 
            
            // in knoten gefunden (mit beiden soehnen)
            if (re != null && li != null) {
                DxBBnode pre = li.succNode();
                removeNodeKey( pre.key );
                DxBBnode ret = new DxBBnode( data, key, comparator );
                data = pre.data;
                key = pre.key;
                return ret;
            } 
        } 
        // in diesem knoten nicht gefunden;
        if (comparator.compareIsLess( _key, key )) {
            if (li != null) {
                P = li.removeNodeKey( _key );
                if (P != null) {
                    if (li != null) {
                        lWeight--;
                    } else {
                        lWeight = 1;
                    } 
                } 
            } 
        } else {
            if (re != null) {
                P = re.removeNodeKey( _key );
                if (P != null) {
                    if (re != null) {
                        rWeight--;
                    } else {
                        rWeight = 1;
                    } 
                } 
            } 
        } 
        
        checkWeight();
        return P;
    } 
    
    
    /** */
    public DxBBnode succNode() {
        if (re != null) {
            return re.succNode();
        } else {
            return this;
        } 
    } 
    
    
    /** */
    public int p() {
        return lWeight * 100 / (rWeight + lWeight);
    } 
    
    
    /** */
    public void checkWeight() {
        int _p = p();
        if (_p <= DxBBTree.BB_ALPHA) {
            if (re != null && re.p() > DxBBTree.BB_BALANCE) {
                re.rotRight();
            } 
            rotLeft();
            return;
        } 
        if (_p >= (DxBBTree.BB_MAX - DxBBTree.BB_ALPHA)) {
            if (li != null && li.p() < DxBBTree.BB_BALANCE) {
                li.rotLeft();
            } 
            rotRight();
        } 
    } 
    
    
    /** */
    public void rotLeft() {
        DxBBnode rl;
        if (isRight) {
            pa.re = re;
        } else {
            pa.li = re;
        } 
        re.pa = pa;
        re.isRight = isRight;
        isRight = false;
        
        rl = re.li;
        re.li = this;
        pa = re;
        re = rl;
        if (re != null) {
            re.pa = this;
            rWeight = re.rWeight + re.lWeight;
            re.isRight = true;
        } else {
            rWeight = 1;
        } 
        pa.lWeight = lWeight + rWeight;
    } 
    
    
    /** */
    public void rotRight() {
        DxBBnode lr;
        if (isRight) {
            pa.re = li;
        } else {
            pa.li = li;
        } 
        li.pa = pa;
        li.isRight = isRight;
        isRight = true;
        
        lr = li.re;
        li.re = this;
        pa = li;
        li = lr;
        if (li != null) {
            li.pa = this;
            lWeight = li.lWeight + li.rWeight;
            li.isRight = false;
        } else {
            lWeight = 1;
        } 
        pa.rWeight = lWeight + rWeight;
    } 
    
    
    /** */
    public void print( int n ) {
        if (re != null) {
            re.print( n + 5 );
        } 
        
        for (int i = 0; i < n; i++) {
            System.out.print( " " );
        } 
        if (data != null) {
            System.out.println( ":" + p() );
        } else {
            System.out.println( "-------------------------" );
        } 
        
        if (li != null) {
            li.print( n + 5 );
        } 
    } 
}