Opus5
Class MWayTree

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

All Implemented Interfaces:

Comparable, Container, SearchableContainer, SearchTree, Tree

Direct Known Subclasses:

BTree

public class MWayTree

extends AbstractTree

implements SearchTree

A node in an M-way tree.

Version:

$Id: MWayTree.java,v 3.7 1998/09/22 13:22:06 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

Inner classes inherited from class Opus5.AbstractTree

AbstractTree.TreeEnumeration

Field Summary

protected Comparable[]	key Array of keys.
protected MWayTree[]	subtree Array of subtrees.

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.SearchTree

copyright

Constructor Summary

MWayTree(int m)
Constructs an empty MWayTree with the specified order.

Method Summary

void	breadthFirstTraversal(Visitor visitor) Causes a visitor to visit the nodes of this tree in breadth-first traversal order starting from this node.
protected int	compareTo(Comparable arg) Compares this M-way tree with the specified comparable object.
void	depthFirstTraversal(PrePostVisitor visitor) Causes a visitor to visit the nodes of this tree in depth-first traversal order starting from this node.
Comparable	find(Comparable object) Finds an object in this M-way tree that matches the specified object.
protected int	findIndex(Comparable object) Finds the position of the specified object in the array of keys contained in this M-way tree node.
Comparable	findMax() Finds the "largest" key in this M-way tree.
Comparable	findMin() Finds the "smallest" key in this M-way tree.
Comparable	findV2(Comparable object) Finds an object in this M-way tree that matches the specified object.
int	getCount() Returns the number of keys in this M-way tree.
int	getDegree() Returns the degree of this M-way tree node.
Enumeration	getEnumeration() Returns an enumeration that enumerates the keys in this M-way tree.
java.lang.Object	getKey() Undefined in an M-way tree node.
java.lang.Object	getKey(int i) Returns the specified key in this M-way tree node.
Tree	getSubtree(int i) Returns the specified subtree of this M-way tree node.
void	insert(Comparable object) Inserts the specified object into this M-way tree.
boolean	isEmpty() Tests whether this M-way tree node is empty.
boolean	isFull() Tests whether this M-way tree node is full.
boolean	isLeaf() Tests whether this M-way tree node is a leaf node.
boolean	isMember(Comparable object) Tests whether the specified object is a key in this M-way tree.
void	purge() Purges this M-way tree node, making it empty.
void	withdraw(Comparable object) Withdraws the specfied object from this M-way tree.

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

key

protected Comparable[] key

Array of keys.

subtree

protected MWayTree[] subtree

Array of subtrees.

Constructor Detail

MWayTree

public MWayTree(int m)

Constructs an empty MWayTree with the specified order.

Parameters:

m - The desired order.

Throws:

java.lang.IllegalArgumentException - If the order is less than two.

Method Detail

purge

public void purge()

Purges this M-way tree node, making it empty.

Specified by:

purge in interface Container

breadthFirstTraversal

public void breadthFirstTraversal(Visitor visitor)

Causes a visitor to visit the nodes of this tree in breadth-first traversal order starting from this node. This method invokes the visit method of the visitor for each node in this tree. Uses a queue to keep track of the nodes to be visited. The traversal continues as long as the isDone method of the visitor returns false.

Specified by:

breadthFirstTraversal in interface Tree

Overrides:

breadthFirstTraversal in class AbstractTree

Parameters:

visitor - The visitor to accept.

See Also:

Visitor

isEmpty

public boolean isEmpty()

Tests whether this M-way tree node is empty.

Specified by:

isEmpty in interface Tree

Overrides:

isEmpty in class AbstractContainer

Returns:

True if this M-way tree node is empty; false otherwise.

isFull

public boolean isFull()

Tests whether this M-way tree node is full.

Specified by:

isFull in interface Container

Overrides:

isFull in class AbstractContainer

Returns:

True if this M-way tree node is full; false otherwise.

isLeaf

public boolean isLeaf()

Tests whether this M-way tree node is a leaf node.

Specified by:

isLeaf in interface Tree

Returns:

True if this M-way tree node is not empty and all its subtrees are empty; false otherwise.

getDegree

public int getDegree()

Returns the degree of this M-way tree node.

Specified by:

getDegree in interface Tree

Returns:

the degree of this M-way tree node.

getKey

public java.lang.Object getKey(int i)

Returns the specified key in this M-way tree node.

Parameters:

i - The number of the key to return.

Returns:

The specified key in this M-way tree node

Throws:

InvalidOperationException - If this node is empty.

getKey

public java.lang.Object getKey()

Undefined in an M-way tree node.

Specified by:

getKey in interface Tree

Throws:

InvalidOperationException - Always.

getSubtree

public Tree getSubtree(int i)

Returns the specified subtree of this M-way tree node.

Specified by:

getSubtree in interface Tree

Parameters:

i - The number of the subtree to return.

Returns:

The specified subtree of this M-way tree node.

Throws:

InvalidOperationException - If this node is empty.

depthFirstTraversal

public void depthFirstTraversal(PrePostVisitor visitor)

Causes a visitor to visit the nodes of this tree in depth-first traversal order starting from this node. This method invokes the preVisit, inVisit and postVisit methods of the visitor for each node in this tree.

Specified by:

depthFirstTraversal in interface Tree

Overrides:

depthFirstTraversal in class AbstractTree

Parameters:

visitor - The visitor to accept.

getCount

public int getCount()

Returns the number of keys in this M-way tree.

Specified by:

getCount in interface Container

Overrides:

getCount in class AbstractTree

Returns:

the number of keys in this M-way tree.

find

public Comparable find(Comparable object)

Finds an object in this M-way tree that matches the specified object. Uses linear search.

Specified by:

find in interface SearchableContainer

Parameters:

object - The object to match.

Returns:

An object that matches the specified one; null if the tree is empty.

See Also:

findV2(Opus5.Comparable)

isMember

public boolean isMember(Comparable object)

Tests whether the specified object is a key in this M-way tree.

Specified by:

isMember in interface SearchableContainer

Parameters:

object - The object for which to look.

Returns:

True if the specified object is in this tree; false otherwise.

findMin

public Comparable findMin()

Finds the "smallest" key in this M-way tree. The smallest key is the key which is less than or equal to all other keys in the tree.

Specified by:

findMin in interface SearchTree

Returns:

The "smallest" key in this M-way tree; null if the tree is empty.

findMax

public Comparable findMax()

Finds the "largest" key in this M-way tree. The largest key is the key which is greater than or equal to all other keys in the tree.

Specified by:

findMax in interface SearchTree

Returns:

The "largest" key in this M-way tree; null if the tree is empty.

findIndex

protected int findIndex(Comparable object)

Finds the position of the specified object in the array of keys contained in this M-way tree node. Uses binary search.

Parameters:

object - The object for which to look.

Returns:

The position of the object in the array of keys. If the object is not present, the result is the position of the largest key less than the specified one.

findV2

public Comparable findV2(Comparable object)

Finds an object in this M-way tree that matches the specified object. Uses binary search.

Parameters:

object - The object to match.

Returns:

An object that matches the specified one; null if the tree is empty.

See Also:

find(Opus5.Comparable)

insert

public void insert(Comparable object)

Inserts the specified object into this M-way tree.

Specified by:

insert in interface SearchableContainer

Parameters:

object - The object to insert.

Throws:

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

withdraw

public void withdraw(Comparable object)

Withdraws the specfied object from this M-way tree.

Specified by:

withdraw in interface SearchableContainer

Parameters:

object - The object to withdraw.

Throws:

java.lang.IllegalArgumentException - If the specified object is not in this tree.

getEnumeration

public Enumeration getEnumeration()

Returns an enumeration that enumerates the keys in this M-way tree.

Specified by:

getEnumeration in interface Container

Overrides:

getEnumeration in class AbstractTree

Returns:

an enumeration that enumerates the keys in this M-way tree.

compareTo

protected int compareTo(Comparable arg)

Compares this M-way tree with the specified comparable object. This method is not implemented.

Overrides:

compareTo in class AbstractObject

Parameters:

arg - The comparable object with which to compare this tree.

Throws:

MethodNotImplemented - Always.