Opus5
Class BTree

java.lang.Object
  |
  +--Opus5.AbstractObject
        |
        +--Opus5.AbstractContainer
              |
              +--Opus5.AbstractTree
                    |
                    +--Opus5.MWayTree
                          |
                          +--Opus5.BTree

All Implemented Interfaces:

Comparable, Container, SearchableContainer, SearchTree, Tree

public class BTree

extends MWayTree

A node in a B-tree.

Version:

$Id: BTree.java,v 3.2 1998/07/28 11:52:16 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

Inner classes inherited from class Opus5.AbstractTree

AbstractTree.TreeEnumeration

Field Summary

protected BTree

parent The parent of this node.

Fields inherited from class Opus5.MWayTree

key, subtree

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.SearchTree

copyright

Constructor Summary

BTree(int m)
Construcs an empty BTree with the specified order.

Method Summary

protected void	attachLeftHalfOf(BTree btree) Attaches the left half of the keys and subtrees of the specified B-tree to this B-tree node.
protected void	attachRightHalfOf(BTree btree) Attaches the right half of the keys and subtrees of the specified B-tree to this B-tree node.
void	attachSubtree(int i, MWayTree arg) Attaches the specified B-tree as the specified subtree of this B-tree.
void	insert(Comparable object) Inserts the specified object into this B-tree.
protected Comparable	insertKey(int index, Comparable object) Inserts the specified object at the specified position in the array of keys in this B-tree node, moving keys in the array to the right to make room.
protected void	insertPair(Comparable object, BTree child) Inserts the specified object and B-tree into this B-tree node.
protected BTree	insertSubtree(int index, BTree child) Inserts the specified B-tree at the specified position in the array of subtrees in this B-tree node, moving trees in the array to the right to make room.
void	withdraw(Comparable object) Withdraws the specified object from this B-tree.

Methods inherited from class Opus5.MWayTree

breadthFirstTraversal, compareTo, depthFirstTraversal, find, findIndex, findMax, findMin, findV2, getCount, getDegree, getEnumeration, getKey, getKey, getSubtree, isEmpty, isFull, isLeaf, isMember, purge

Methods inherited from class Opus5.AbstractTree

accept, getHeight

Methods inherited from class Opus5.AbstractContainer

hashCode, toString

Methods inherited from class Opus5.AbstractObject

compare, equals, isEQ, isGE, isGT, isLE, isLT, isNE

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Opus5.Tree

getHeight

Methods inherited from interface Opus5.Container

accept

Methods inherited from interface Opus5.Comparable

compare, isEQ, isGE, isGT, isLE, isLT, isNE

Field Detail

parent

protected BTree parent

The parent of this node.

Constructor Detail

BTree

public BTree(int m)

Construcs an empty BTree with the specified order.

Parameters:

m - The desired order.

Method Detail

attachSubtree

public void attachSubtree(int i,
                          MWayTree arg)

Attaches the specified B-tree as the specified subtree of this B-tree.

Parameters:

i - The position at which to attach the specified B-tree.

Returns:

arg The B-tree to attach.

insert

public void insert(Comparable object)

Inserts the specified object into this B-tree.

Overrides:

insert in class MWayTree

Parameters:

object - The object to insert.

Throws:

java.lang.IllegalArgumentException - If there is already a matching object in this tree.

insertPair

protected void insertPair(Comparable object,
                          BTree child)

Inserts the specified object and B-tree into this B-tree node.

Parameters:

object - A key smaller than all the keys in the specified B-tree.

child - The specified B-tree.

insertKey

protected Comparable insertKey(int index,
                               Comparable object)

Inserts the specified object at the specified position in the array of keys in this B-tree node, moving keys in the array to the right to make room.

Parameters:

index - The position in which to insert the specified object.

object - The object to insert.

Returns:

The object that falls off the end of the array.

insertSubtree

protected BTree insertSubtree(int index,
                              BTree child)

Inserts the specified B-tree at the specified position in the array of subtrees in this B-tree node, moving trees in the array to the right to make room.

Parameters:

index - The position in which to insert the specified B-tree.

object - The B-tree to insert.

Returns:

The B-tree that falls off the end of the array.

attachLeftHalfOf

protected void attachLeftHalfOf(BTree btree)

Attaches the left half of the keys and subtrees of the specified B-tree to this B-tree node.

Parameters:

btree - The tree from which to remove the keys and subtrees.

attachRightHalfOf

protected void attachRightHalfOf(BTree btree)

Attaches the right half of the keys and subtrees of the specified B-tree to this B-tree node.

Parameters:

btree - The tree from which to remove the keys and subtrees.

withdraw

public void withdraw(Comparable object)

Withdraws the specified object from this B-tree. This method is not implemented.

Overrides:

withdraw in class MWayTree

Parameters:

object - The object to withdraw from this B-tree.

Throws:

MethodNotImplemented - Always.