Using the following code implement an \"UnderflowException extends RuntimeExcept
ID: 3765743 • Letter: U
Question
Using the following code implement an "UnderflowException extends RuntimeException" in the same program (The program is already written but the implementation of the UnderflowException extends RuntimeException is not).
I need help understanding how to implement this without java's compiler going crazy.
Please use the following code (The program must run without any compiler errors):
Program starts here (You can copy and paste):
/
/
/
public class AvlTree>
{
/**
* Construct the tree.
*/
public AvlTree( )
{
root = null;
}
/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
root = insert( x, root );
}
/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
root = remove( x, root );
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private AvlNode remove( AnyType x, AvlNode t )
{
if( t == null )
return t; // Item not found; do nothing
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
t.left = remove( x, t.left );
else if( compareResult > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = remove( t.element, t.right );
}
else
t = ( t.left != null ) ? t.left : t.right;
return balance( t );
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public AnyType findMin( ) throws UnderflowException
{
if( isEmpty( ) )
throw new UnderflowException("Error" );
return findMin( root ).element;
}
/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public AnyType findMax( ) throws UnderflowException
{
if( isEmpty( ) )
throw new UnderflowException("Error" );
return findMax( root ).element;
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if x is found.
*/
public boolean contains( AnyType x )
{
return contains( x, root );
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}
/**
* Print the tree contents in sorted order.
*/
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}
private static final int ALLOWED_IMBALANCE = 1;
// Assume t is either balanced or within one of being balanced
private AvlNode balance( AvlNode t )
{
if( t == null )
return t;
if( height( t.left ) - height( t.right ) > ALLOWED_IMBALANCE )
if( height( t.left.left ) >= height( t.left.right ) )
t = rotateWithLeftChild( t );
else
t = doubleWithLeftChild( t );
else
if( height( t.right ) - height( t.left ) > ALLOWED_IMBALANCE )
if( height( t.right.right ) >= height( t.right.left ) )
t = rotateWithRightChild( t );
else
t = doubleWithRightChild( t );
t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
return t;
}
public void checkBalance( )
{
checkBalance( root );
}
private int checkBalance( AvlNode t )
{
if( t == null )
return -1;
if( t != null )
{
int hl = checkBalance( t.left );
int hr = checkBalance( t.right );
if( Math.abs( height( t.left ) - height( t.right ) ) > 1 ||
height( t.left ) != hl || height( t.right ) != hr )
System.out.println( "OOPS!!" );
}
return height( t );
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private AvlNode insert( AnyType x, AvlNode t )
{
if( t == null )
return new AvlNode( x, null, null );
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
t.left = insert( x, t.left );
else if( compareResult > 0 )
t.right = insert( x, t.right );
else
; // Duplicate; do nothing
return balance( t );
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
private AvlNode findMin( AvlNode t )
{
if( t == null )
return t;
while( t.left != null )
t = t.left;
return t;
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private AvlNode findMax( AvlNode t )
{
if( t == null )
return t;
while( t.right != null )
t = t.right;
return t;
}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return true if x is found in subtree.
*/
private boolean contains( AnyType x, AvlNode t )
{
while( t != null )
{
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
t = t.left;
else if( compareResult > 0 )
t = t.right;
else
return true; // Match
}
return false; // No match
}
/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the tree.
*/
private void printTree( AvlNode t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}
/**
* Return the height of node t, or -1, if null.
*/
private int height( AvlNode t )
{
return t == null ? -1 : t.height;
}
/**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then return new root.
*/
private AvlNode rotateWithLeftChild( AvlNode k2 )
{
AvlNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = Math.max( height( k1.left ), k2.height ) + 1;
return k1;
}
/**
* Rotate binary tree node with right child.
* For AVL trees, this is a single rotation for case 4.
* Update heights, then return new root.
*/
private AvlNode rotateWithRightChild( AvlNode k1 )
{
AvlNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = Math.max( height( k2.right ), k1.height ) + 1;
return k2;
}
/**
* Double rotate binary tree node: first left child
* with its right child; then node k3 with new left child.
* For AVL trees, this is a double rotation for case 2.
* Update heights, then return new root.
*/
private AvlNode doubleWithLeftChild( AvlNode k3 )
{
k3.left = rotateWithRightChild( k3.left );
return rotateWithLeftChild( k3 );
}
/**
* Double rotate binary tree node: first right child
* with its left child; then node k1 with new right child.
* For AVL trees, this is a double rotation for case 3.
* Update heights, then return new root.
*/
private AvlNode doubleWithRightChild( AvlNode k1 )
{
k1.right = rotateWithLeftChild( k1.right );
return rotateWithRightChild( k1 );
}
private static class AvlNode
{
// Constructors
AvlNode( AnyType theElement )
{
this( theElement, null, null );
}
AvlNode( AnyType theElement, AvlNode lt, AvlNode rt )
{
element = theElement;
left = lt;
right = rt;
height = 0;
}
AnyType element; // The data in the node
AvlNode left; // Left child
AvlNode right; // Right child
int height; // Height
}
/** The tree root. */
private AvlNode root;
// Test program
public static void main( String [ ] args )
{
AvlTree t = new AvlTree( );
final int SMALL = 40;
final int NUMS = 1000000; // must be even
final int GAP = 37;
System.out.println( "Checking... (no more output means success)" );
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
{
// System.out.println( "INSERT: " + i );
t.insert( i );
if( NUMS < SMALL )
t.checkBalance( );
}
for( int i = 1; i < NUMS; i+= 2 )
{
// System.out.println( "REMOVE: " + i );
t.remove( i );
if( NUMS < SMALL )
t.checkBalance( );
}
if( NUMS < SMALL )
t.printTree( );
if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
System.out.println( "FindMin or FindMax error!" );
for( int i = 2; i < NUMS; i+=2 )
if( !t.contains( i ) )
System.out.println( "Find error1!" );
for( int i = 1; i < NUMS; i+=2 )
{
if( t.contains( i ) )
System.out.println( "Find error2!" );
}
}
}
Explanation / Answer
public class ArrayStack implements Stack {
/**
* Construct the stack.
*/
public ArrayStack( ) {
theArray = new Object[ DEFAULT_CAPACITY ];
topOfStack = -1;
}
/**
* Test if the stack is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( ) {
return topOfStack == -1;
}
/**
* Make the stack logically empty.
*/
public void makeEmpty( ) {
topOfStack = -1;
}
/**
* Get the most recently inserted item in the stack.
* Does not alter the stack.
* @return the most recently inserted item in the stack.
* @throws UnderflowException if the stack is empty.
*/
public Object top( ) {
if( isEmpty( ) )
throw new UnderflowException( "ArrayStack top" );
return theArray[ topOfStack ];
}
/**
* Remove the most recently inserted item from the stack.
* @throws UnderflowException if the stack is empty.
*/
public void pop( ) {
if( isEmpty( ) )
throw new UnderflowException( "ArrayStack pop" );
topOfStack--;
}
/**
* Return and remove the most recently inserted item
* from the stack.
* @return the most recently inserted item in the stack.
* @throws Underflow if the stack is empty.
*/
public Object topAndPop( ) {
if( isEmpty( ) )
throw new UnderflowException( "ArrayStack topAndPop" );
return theArray[ topOfStack-- ];
}
/**
* Insert a new item into the stack.
* @param x the item to insert.
*/
public void push( Object x ) {
if( topOfStack + 1 == theArray.length )
doubleArray( );
theArray[ ++topOfStack ] = x;
}
/**
* Internal method to extend theArray.
*/
private void doubleArray( ) {
Object [ ] newArray;
newArray = new Object[ theArray.length * 2 ];
for( int i = 0; i < theArray.length; i++ )
newArray[ i ] = theArray[ i ];
theArray = newArray;
}
private Object [ ] theArray;
private int topOfStack;
private static final int DEFAULT_CAPACITY = 10;
}
/**
* Exception class for access in empty containers
* such as stacks, queues, and priority queues.
* @author Mark Allen Weiss
*/
public class UnderflowException extends RuntimeException {
/**
* Construct this exception object.
* @param message the error message.
*/
public UnderflowException( String message ) {
super( message );
}
}
// Stack interface
//
// ******************PUBLIC OPERATIONS*********************
// void push( x ) --> Insert x
// void pop( ) --> Remove most recently inserted item
// Object top( ) --> Return most recently inserted item
// Object topAndPop( ) --> Return and remove most recent item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// ******************ERRORS********************************
// top, pop, or topAndPop on empty stack
/**
* Protocol for stacks.
* @author Mark Allen Weiss
*/
public interface Stack {
/**
* Insert a new item into the stack.
* @param x the item to insert.
*/
void push( Object x );
/**
* Remove the most recently inserted item from the stack.
* @exception UnderflowException if the stack is empty.
*/
void pop( );
/**
* Get the most recently inserted item in the stack.
* Does not alter the stack.
* @return the most recently inserted item in the stack.
* @exception UnderflowException if the stack is empty.
*/
Object top( );
/**
* Return and remove the most recently inserted item
* from the stack.
* @return the most recently inserted item in the stack.
* @exception UnderflowException if the stack is empty.
*/
Object topAndPop( );
/**
* Test if the stack is logically empty.
* @return true if empty, false otherwise.
*/
boolean isEmpty( );
/**
* Make the stack logically empty.
*/
void makeEmpty( );
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.