I have erros that need to be fixed:

Thank you. I really appreciate it!!!

you probably wont need most of these files

Description Resource Path Location Type The operator < is undefined for the argument type(s) support.Golfer, support.Golfer GolfApp2.java /project5/ch08 line 60 Java Problem - happens twice

Description Resource Path Location Type The field BinarySearchTree.root is not visible GolfApp2.java /project5/ch08 line 32 Java Problem - happens 4 times

Description Resource Path Location Type The operator && is undefined for the argument type(s) BSTNode, boolean BinarySearchTree.java /project5/ch08/trees line 155 Java Problem

What it is supposed to do:

modify GolfApp2

1st modifications

Write a client method that returns a count of the number of nodes in a binary search tree that contain a value less than or equal to the argument value. The signature of the method is

int countLess ( BinarySearchTree tree, Golfer maxValue )

answer:

int countLess ( BinarySearchTree tree, Golfer maxValue )

{

BSTNode maxNode = tree.root;

BSTNode minNode = tree.root;

int count = 0;

//Traverse Right Sub tree

while(maxNode!=null)

{

if( maxNode.getInfo() < maxValue){

count ++;

}

maxNode = maxNode.getRight();

}

//Traverse Left subtree

while(minNode!=null)

{

if( minNode.getInfo() < maxValue){

count ++;

}

minNode = minNode.getLeft();

}

return count;

}

2nd modification

Write a client method that returns a reference to the information in the node with the smallest value in a binary search tree. The signature of the method is

Golfer min( BinarySearchTree tree )

Answer:

Golfer min(BinarySearchTree tree) {

BSTNode minNode = tree.root;

if (minNode == null) {

return null;

}

while (minNode.getLeft() != null) {

minNode = minNode.getLeft();

}

return minNode.getInfo();

}

Write a client method that returns a reference to the information in the node with the largest value in a binary search tree. The signature of the method is

Golfer max( BinarySearchTree tree )

Answer:

Golfer min(BinarySearchTree tree) {

BSTNode maxNode = tree.root;

if (maxNode == null) {

return null;

}

while (maxNode.getRight() != null) {

maxNode = maxNode.getRight();

}

return maxNode.getInfo();

}

BinarySearchTree modifications

1st modification

Extend the Binary Search Tree ADT to include a basic public method getRoot that returns a reference to the root of the tree. If the tree is empty, the method should return null.

answer:

public BSTNode getRoot(){ if (root!=null){ return root; }else{ return null; } }

2nd modification

Extend the Binary Search Tree ADT to include a public method leafCount that returns the number of leaf nodes in the tree.

answer:

public int leafCount (BSTNode tree) // Initializes preOrderQueue with tree elements in preOrder order. { // if current node is not null if (tree != null) { // if node is on leaf if(tree.getLeft()==null && tree.getRight() == null) { return 1; } else { // try to get count from the sub trees return leafCount(tree.getLeft()) + leafCount(tree.getRight()); } } else { // for null node, count is 0 return 0; } }

3rd modification

Extend the Binary Search Tree ADT to include a public method singleParentCount that returns the number of nodes in the tree that have only one child.

answer:

public int singleParentCount(BSTNode tree) { if(tree == null) return 0; else { if(tree.getLeft() != null && tree.getRight() == null) { return 1 + singleParentCount(tree.getLeft()); } if(tree.getLeft() == null && tree.getRight() != null) { return 1 + singleParentCount(tree.getRight()); } } return 0; }

4th modification

The Binary Search Tree ADT is extended to include a boolean method similarTrees that receives references to two binary trees and determines whether the shapes of the trees are the same. (The nodes do not have to contain the same values, but each node must have the same number of children.)

a) Write the declaration of the similarTrees method. Include adequate comments.

b) Write the body of the similarTrees method.

answer:

ADT : The functions takes two trees as input parameters and returns true if they are equal private boolean similarTrees(BSTNode tree1, BSTNode tree2)

The code is as follows: private boolean similarTrees(BSTNode tree1, BSTNode tree2) { while(tree1 != null && tree2 != null) { if(tree1.getInfo() != tree2.getInfo()) return false; return similarTrees(tree1.getLeft(), tree2.getLeft() && similarTrees(tree1.getRight(), tree2.getRight())); } return tree1 == null && tree2 == null; }

The code:

File Name: GolfApp2.java

//---------------------------------------------------------------------

// GolfApp2.java by Dale/Joyce/Weems Chapter 8

//

// Allows user to enter golfer name and score information.

// Displays information ordered by score.

//----------------------------------------------------------------------

import java.util.Scanner;

import ch08.trees.*;

import support.*; // Golfer

public class GolfApp2

{

//CountLess() method

public static int countLess ( BinarySearchTree tree, Golfer maxValue )

{

BSTNode maxNode = tree.root;

BSTNode minNode = tree.root;

int count = 0;

//Traverse Right Sub tree

while(maxNode!=null)

{

if( maxNode.getInfo() < maxValue)

{

count ++;

}

maxNode = maxNode.getRight();

}

//Traverse Left subtree

while(minNode!=null)

{

if( minNode.getInfo() < maxValue)

{

count ++;

}

minNode = minNode.getLeft();

}

return count;

}

//min() method

public static Golfer min(BinarySearchTree tree)

{

BSTNode minNode = tree.root;

if (minNode == null)

{

return null;

}

while (minNode.getLeft() != null)

{

minNode = minNode.getLeft();

}

return minNode.getInfo();

}

//max() method

public static Golfer max(BinarySearchTree tree)

{

BSTNode maxNode = tree.root;

if (maxNode == null)

{

return null;

}

while (maxNode.getRight() != null)

{

maxNode = maxNode.getRight();

}

return maxNode.getInfo();

}

public static void main(String[] args)

{

Scanner conIn = new Scanner(System.in);

String name; // golfer's name

int score; // golfer's score

BSTInterface golfers = new BinarySearchTree();

Golfer golfer;

int numGolfers;

String skip; // Used to skip rest of input line after reading integer

System.out.print("Golfer name (press Enter to end): ");

name = conIn.nextLine();

while (!name.equals(""))

{

System.out.print("Score: ");

score = conIn.nextInt();

skip = conIn.nextLine();

golfer = new Golfer(name, score);

golfers.add(golfer);

System.out.print("Golfer name (press Enter to end): ");

name = conIn.nextLine();

}

System.out.println();

System.out.println("The final results are");

numGolfers = golfers.reset(BinarySearchTree.INORDER);

for (int count = 1; count <= numGolfers; count++)

{

System.out.println(golfers.getNext(BinarySearchTree.INORDER));

}

}

}

File Name: BinarySearchTree.java

//----------------------------------------------------------------------------

// BinarySearchTree.java by Dale/Joyce/Weems Chapter 8

//

// Defines all constructs for a reference-based BST

//----------------------------------------------------------------------------

package ch08.trees;

import ch05.queues.*;

import ch03.stacks.*;

import support.BSTNode;

public class BinarySearchTree>

implements BSTInterface

{

protected BSTNode root; // reference to the root of this BST

boolean found; // used by remove

// for traversals

protected LinkedUnbndQueue inOrderQueue; // queue of info

protected LinkedUnbndQueue preOrderQueue; // queue of info

protected LinkedUnbndQueue postOrderQueue; // queue of info

public BinarySearchTree()

// Creates an empty BST object.

{

root = null;

}

public BSTNode getRoot()

{

if (root!=null)

{

return root;

}

return null;

}

public int leafCount (BSTNode tree)

// Initializes preOrderQueue with tree elements in preOrder order.

{

// if current node is not null

if (tree != null)

{

// if node is on leaf

if(tree.getLeft()==null && tree.getRight() == null)

{

return 1;

}

else

{

// try to get count from the sub trees

return leafCount(tree.getLeft()) + leafCount(tree.getRight());

}

}

else

{

// for null node, count is 0

return 0;

}

}

public int singleParentCount(BSTNode tree)

{

if(tree == null)

return 0;

else

{

if(tree.getLeft() != null && tree.getRight() == null)

{

return 1 + singleParentCount(tree.getLeft());

}

if(tree.getLeft() == null && tree.getRight() != null)

{

return 1 + singleParentCount(tree.getRight());

}

}

return 0;

}

private boolean similarTrees(BSTNode tree1, BSTNode tree2)

{

while(tree1 != null && tree2 != null)

{

if(tree1.getInfo() != tree2.getInfo())

return false;

return similarTrees(tree1.getLeft(), tree2.getLeft() && similarTrees(tree1.getRight(), tree2.getRight()));

}

return tree1 == null && tree2 == null;

}

public boolean isEmpty()

// Returns true if this BST is empty; otherwise, returns false.

{

return (root == null);

}

private int recSize(BSTNode tree)

// Returns the number of elements in tree.

{

if (tree == null)

return 0;

else

return recSize(tree.getLeft()) + recSize(tree.getRight()) + 1;

}

public int size()

// Returns the number of elements in this BST.

{

return recSize(root);

}

public int size2()

// Returns the number of elements in this BST.

{

int count = 0;

if (root != null)

{

LinkedStack> hold = new LinkedStack>();

BSTNode currNode;

hold.push(root);

while (!hold.isEmpty())

{

currNode = hold.top();

hold.pop();

count++;

if (currNode.getLeft() != null)

hold.push(currNode.getLeft());

if (currNode.getRight() != null)

hold.push(currNode.getRight());

}

}

return count;

}

private boolean recContains(T element, BSTNode tree)

// Returns true if tree contains an element e such that

// e.compareTo(element) == 0; otherwise, returns false.

{

if (tree == null)

return false; // element is not found

else if (element.compareTo(tree.getInfo()) < 0)

return recContains(element, tree.getLeft()); // Search left subtree

else if (element.compareTo(tree.getInfo()) > 0)

return recContains(element, tree.getRight()); // Search right subtree

else

return true; // element is found

}

public boolean contains (T element)

// Returns true if this BST contains an element e such that

// e.compareTo(element) == 0; otherwise, returns false.

{

return recContains(element, root);

}

private T recGet(T element, BSTNode tree)

// Returns an element e from tree such that e.compareTo(element) == 0;

// if no such element exists, returns null.

{

if (tree == null)

return null; // element is not found

else if (element.compareTo(tree.getInfo()) < 0)

return recGet(element, tree.getLeft()); // get from left subtree

else

if (element.compareTo(tree.getInfo()) > 0)

return recGet(element, tree.getRight()); // get from right subtree

else

return tree.getInfo(); // element is found

}

public T get(T element)

// Returns an element e from this BST such that e.compareTo(element) == 0;

// if no such element exists, returns null.

{

return recGet(element, root);

}

private BSTNode recAdd(T element, BSTNode tree)

// Adds element to tree; tree retains its BST property.

{

if (tree == null)

// Addition place found

tree = new BSTNode(element);

else if (element.compareTo(tree.getInfo()) <= 0)

tree.setLeft(recAdd(element, tree.getLeft())); // Add in left subtree

else

tree.setRight(recAdd(element, tree.getRight())); // Add in right subtree

return tree;

}

public void add (T element)

// Adds element to this BST. The tree retains its BST property.

{

root = recAdd(element, root);

}

private T getPredecessor(BSTNode tree)

// Returns the information held in the rightmost node in tree

{

while (tree.getRight() != null)

tree = tree.getRight();

return tree.getInfo();

}

private BSTNode removeNode(BSTNode tree)

// Removes the information at the node referenced by tree.

// The user's data in the node referenced by tree is no

// longer in the tree. If tree is a leaf node or has only

// a non-null child pointer, the node pointed to by tree is

// removed; otherwise, the user's data is replaced by its

// logical predecessor and the predecessor's node is removed.

{

T data;

if (tree.getLeft() == null)

return tree.getRight();

else if (tree.getRight() == null)

return tree.getLeft();

else

{

data = getPredecessor(tree.getLeft());

tree.setInfo(data);

tree.setLeft(recRemove(data, tree.getLeft()));

return tree;

}

}

private BSTNode recRemove(T element, BSTNode tree)

// Removes an element e from tree such that e.compareTo(element) == 0

// and returns true; if no such element exists, returns false.

{

if (tree == null)

found = false;

else if (element.compareTo(tree.getInfo()) < 0)

tree.setLeft(recRemove(element, tree.getLeft()));

else if (element.compareTo(tree.getInfo()) > 0)

tree.setRight(recRemove(element, tree.getRight()));

else

{

tree = removeNode(tree);

found = true;

}

return tree;

}

public boolean remove (T element)

// Removes an element e from this BST such that e.compareTo(element) == 0

// and returns true; if no such element exists, returns false.

{

root = recRemove(element, root);

return found;

}

private void inOrder(BSTNode tree)

// Initializes inOrderQueue with tree elements in inOrder order.

{

if (tree != null)

{

inOrder(tree.getLeft());

inOrderQueue.enqueue(tree.getInfo());

inOrder(tree.getRight());

}

}

private void preOrder(BSTNode tree)

// Initializes preOrderQueue with tree elements in preOrder order.

{

if (tree != null)

{

preOrderQueue.enqueue(tree.getInfo());

preOrder(tree.getLeft());

preOrder(tree.getRight());

}

}

private void postOrder(BSTNode tree)

// Initializes postOrderQueue with tree elements in postOrder order.

{

if (tree != null)

{

postOrder(tree.getLeft());

postOrder(tree.getRight());

postOrderQueue.enqueue(tree.getInfo());

}

}

public int reset(int orderType)

// Initializes current position for an iteration through this BST

// in orderType order. Returns current number of nodes in the BST.

{

int numNodes = size();

if (orderType == INORDER)

{

inOrderQueue = new LinkedUnbndQueue();

inOrder(root);

}

else

if (orderType == PREORDER)

{

preOrderQueue = new LinkedUnbndQueue();

preOrder(root);

}

if (orderType == POSTORDER)

{

postOrderQueue = new LinkedUnbndQueue();

postOrder(root);

}

return numNodes;

}

public T getNext (int orderType)

// Preconditions: The BST is not empty

// The BST has been reset for orderType

// The BST has not been modified since the most recent reset

// The end of orderType iteration has not been reached

//

// Returns the element at the current position on this BST for orderType

// and advances the value of the current position based on the orderType.

{

if (orderType == INORDER)

return inOrderQueue.dequeue();

else

if (orderType == PREORDER)

return preOrderQueue.dequeue();

else

if (orderType == POSTORDER)

return postOrderQueue.dequeue();

else return null;

}

}

extra files:

BSTNode.java

//----------------------------------------------------------------------------

// BSTNode.java by Dale/Joyce/Weems Chapter 8

//

// Implements Comparable nodes for a binary search tree.

//----------------------------------------------------------------------------

package support;

public class BSTNode>

{

// Used to hold references to BST nodes for the linked implementation

protected T info; // The info in a BST node

protected BSTNode left; // A link to the left child node

protected BSTNode right; // A link to the right child node

public BSTNode(T info)

{

this.info = info;

left = null;

right = null;

}

public void setInfo(T info)

// Sets info of this BSTNode.

{

this.info = info;

}

public T getInfo()

// Returns info of this BSTNode.

{

return info;

}

public void setLeft(BSTNode link)

// Sets left link of this BSTNode.

{

left = link;

}

public void setRight(BSTNode link)

// Sets right link of this BSTNode.

{

right = link;

}

public BSTNode getLeft()

// Returns left link of this BSTNode.

{

return left;

}

public BSTNode getRight()

// Returns right link of this BSTNode.

{

return right;

}

}

ArrayListStack.java

//----------------------------------------------------------------------

// ArrayListStack.java by Dale/Joyce/Weems Chapter 3

//

// Implements UnboundedStackInterface using an ArrayList to

// hold the stack elements.

//----------------------------------------------------------------------

package ch03.stacks;

import java.util.*;

public class ArrayListStack implements UnboundedStackInterface

{

protected ArrayList stack; // ArrayList that holds stack elements

public ArrayListStack()

{

stack = new ArrayList();

}

public void push(T element)

// Places element at the top of this stack.

{

stack.add(element);

}

public void pop()

// Throws StackUnderflowException if this stack is empty,

// otherwise removes top element from this stack.

{

if (!isEmpty())

{

stack.remove(stack.size() - 1);

}

else

throw new StackUnderflowException("Pop attempted on an empty stack.");

}

public T top()

// Throws StackUnderflowException if this stack is empty,

// otherwise returns top element from this stack.

{

T topOfStack = null;

if (!isEmpty())

topOfStack = stack.get(stack.size() - 1);

else

throw new StackUnderflowException("Top attempted on an empty stack.");

return topOfStack;

}

public boolean isEmpty()

// Returns true if this stack is empty, otherwise returns false.

{

if (stack.size() == 0)

return true;

else

return false;

}

}

ArrayStack.java

//----------------------------------------------------------------

// ArrayStack.java by Dale/Joyce/Weems Chapter 3

//

// Implements BoundedStackInterface using an array to hold the

// stack elements.

//

// Two constructors are provided: one that creates an array of a

// default size and one that allows the calling program to

// specify the size.

//----------------------------------------------------------------

package ch03.stacks;

public class ArrayStack implements BoundedStackInterface

{

protected final int DEFCAP = 100; // default capacity

protected T[] stack; // holds stack elements

protected int topIndex = -1; // index of top element in stack

public ArrayStack()

{

stack = (T[]) new Object[DEFCAP];

}

public ArrayStack(int maxSize)

{

stack = (T[]) new Object[maxSize];

}

public void push(T element)

// Throws StackOverflowException if this stack is full,

// otherwise places element at the top of this stack.

{

if (!isFull())

{

topIndex++;

stack[topIndex] = element;

}

else

throw new StackOverflowException("Push attempted on a full stack.");

}

public void pop()

// Throws StackUnderflowException if this stack is empty,

// otherwise removes top element from this stack.

{

if (!isEmpty())

{

stack[topIndex] = null;

topIndex--;

}

else

throw new StackUnderflowException("Pop attempted on an empty stack.");

}

public T top()

// Throws StackUnderflowException if this stack is empty,

// otherwise returns top element from this stack.

{

T topOfStack = null;

if (!isEmpty())

topOfStack = stack[topIndex];

else

throw new StackUnderflowException("Top attempted on an empty stack.");

return topOfStack;

}

public boolean isEmpty()

// Returns true if this stack is empty, otherwise returns false.

{

if (topIndex == -1)

return true;

else

return false;

}

public boolean isFull()

// Returns true if this stack is full, otherwise returns false.

{

if (topIndex == (stack.length - 1))

return true;

else

return false;

}

}

BoundedStackInterface.java

//----------------------------------------------------------------------------

// BoundedStackInterface.java by Dale/Joyce/Weems Chapter 3

//

// Interface for a class that implements a stack of with a bound

// on the size of the stack. A stack is a last-in, first-out structure.

//----------------------------------------------------------------------------

package ch03.stacks;

public interface BoundedStackInterface extends StackInterface

{

void push(T element) throws StackOverflowException;

// Throws StackOverflowException if this stack is full,

// otherwise places element at the top of this stack.

boolean isFull();

// Returns true if this stack is full, otherwise returns false.

}

LinkedStack.java

//----------------------------------------------------------------------

// LinkedStack.java by Dale/Joyce/Weems Chapter 3

//

// Implements UnboundedStackInterface using a linked list

// to hold the stack elements.

//-----------------------------------------------------------------------

package ch03.stacks;

import support.LLNode;

public class LinkedStack implements UnboundedStackInterface

{

protected LLNode top; // reference to the top of this stack

public LinkedStack()

{

top = null;

}

public void push(T element)

// Places element at the top of this stack.

{

LLNode newNode = new LLNode(element);

newNode.setLink(top);

top = newNode;

}

public void pop()

// Throws StackUnderflowException if this stack is empty,

// otherwise removes top element from this stack.

{

if (!isEmpty())

{

top = top.getLink();

}

else

throw new StackUnderflowException("Pop attempted on an empty stack.");

}

public T top()

// Throws StackUnderflowException if this stack is empty,

// otherwise returns top element from this stack.

{

if (!isEmpty())

return top.getInfo();

else

throw new StackUnderflowException("Top attempted on an empty stack.");

}

public boolean isEmpty()

// Returns true if this stack is empty, otherwise returns false.

{

if (top == null)

return true;

else

return false;

}

}

StackInterface.java

//----------------------------------------------------------------------------

// StackInterface.java by Dale/Joyce/Weems Chapter 3

//

// Interface for a class that implements a stack of .

// A stack is a last-in, first-out structure.

//----------------------------------------------------------------------------

package ch03.stacks;

public interface StackInterface

{

void pop() throws StackUnderflowException;

// Throws StackUnderflowException if this stack is empty,

// otherwise removes top element from this stack.

T top() throws StackUnderflowException;

// Throws StackUnderflowException if this stack is empty,

// otherwise returns top element from this stack.

boolean isEmpty();

// Returns true if this stack is empty, otherwise returns false.

}

StackOverflowException.java

package ch03.stacks;

public class StackOverflowException extends RuntimeException

{

public StackOverflowException()

{

super();

}

public StackOverflowException(String message)

{

super(message);

}

}

StackUnderflowException.java

package ch03.stacks;

public class StackUnderflowException extends RuntimeException

{

public StackUnderflowException()

{

super();

}

public StackUnderflowException(String message)

{

super(message);

}

}

UnboundedStackInterface.java

//----------------------------------------------------------------------------

// UnboundedStackInterface.java by Dale/Joyce/Weems Chapter 3

//

// Interface for a class that implements a stack of with no bound

// on the size of the stack. A stack is a last-in, first-out structure.

//----------------------------------------------------------------------------

package ch03.stacks;

public interface UnboundedStackInterface extends StackInterface

{

void push(T element);

// Places element at the top of this stack.

}

ArrayBndQueue.java

//---------------------------------------------------------------------------

// ArrayBndQueue.java by Dale/Joyce/Weems Chapter 5

//

// Implements BoundedQueueInterface with an array to hold the queue elements.

//

// Two constructors are provided: one that creates a queue of a default

// capacity and one that allows the calling program to specify the capacity.

//---------------------------------------------------------------------------

package ch05.queues;

public class ArrayBndQueue implements BoundedQueueInterface

{

protected final int DEFCAP = 100; // default capacity

protected T[] queue; // array that holds queue elements

protected int numElements = 0; // number of elements n the queue

protected int front = 0; // index of front of queue

protected int rear; // index of rear of queue

public ArrayBndQueue()

{

queue = (T[]) new Object[DEFCAP];

rear = DEFCAP - 1;

}

public ArrayBndQueue(int maxSize)

{

queue = (T[]) new Object[maxSize];

rear = maxSize - 1;

}

public void enqueue(T element)

// Throws QueueOverflowException if this queue is full;

// otherwise, adds element to the rear of this queue.

{

if (isFull())

throw new QueueOverflowException("Enqueue attempted on a full queue.");

else

{

rear = (rear + 1) % queue.length;

queue[rear] = element;

numElements = numElements + 1;

}

}

public T dequeue()

// Throws QueueUnderflowException if this queue is empty;

// otherwise, removes front element from this queue and returns it.

{

if (isEmpty())

throw new QueueUnderflowException("Dequeue attempted on empty queue.");

else

{

T toReturn = queue[front];

queue[front] = null;

front = (front + 1) % queue.length;

numElements = numElements - 1;

return toReturn;

}

}

public boolean isEmpty()

// Returns true if this queue is empty; otherwise, returns false

{

return (numElements == 0);

}

public boolean isFull()

// Returns true if this queue is full; otherwise, returns false.

{

return (numElements == queue.length);

}

}

ArrayUnbndQueue.java

//---------------------------------------------------------------------------

// ArrayUnbndQueue.java by Dale/Joyce/Weems Chapter 5

//

// Implements UnboundedQueueInterface with an array to hold queue elements.

//

// Two constructors are provided; one that creates a queue of a default

// original capacity and one that allows the calling program to specify the

// original capacity.

//

// If an enqueue is attempted when there is no room available in the array, a

// new array is created, with capacity incremented by the original capacity.

//---------------------------------------------------------------------------

package ch05.queues;

public class ArrayUnbndQueue implements UnboundedQueueInterface

{

protected final int DEFCAP = 100; // default capacity

protected T[] queue; // array that holds queue elements

protected int origCap; // original capacity

protected int numElements = 0; // number of elements in the queue

protected int front = 0; // index of front of queue

protected int rear; // index of rear of queue

public ArrayUnbndQueue()

{

queue = (T[]) new Object[DEFCAP];

rear = DEFCAP - 1;

origCap = DEFCAP;

}

public ArrayUnbndQueue(int origCap)

{

queue = (T[]) new Object[origCap];

rear = origCap - 1;

this.origCap = origCap;

}

private void enlarge()

// Increments the capacity of the queue by an amount

// equal to the original capacity.

{

// create the larger array

T[] larger = (T[]) new Object[queue.length + origCap];

// copy the contents from the smaller array into the larger array

int currSmaller = front;

for (int currLarger = 0; currLarger < numElements; currLarger++)

{

larger[currLarger] = queue[currSmaller];

currSmaller = (currSmaller + 1) % queue.length;

}

// update instance variables

queue = larger;

front = 0;

rear = numElements - 1;

}

public void enqueue(T element)

// Adds element to the rear of this queue.

{

if (numElements == queue.length)

enlarge();

rear = (rear + 1) % queue.length;

queue[rear] = element;

numElements = numElements + 1;

}

public T dequeue()

// Throws QueueUnderflowException if this queue is empty;

// otherwise, removes front element from this queue and returns it.

{

if (isEmpty())

throw new QueueUnderflowException("Dequeue attempted on empty queue.");

else

{

T toReturn = queue[front];

queue[front] = null;

front = (front + 1) % queue.length;

numElements = numElements - 1;

return toReturn;

}

}

public boolean isEmpty()

// Returns true if this queue is empty; otherwise, returns false

{

return (numElements == 0);

}

}

BoundedQueueInterface.java

//----------------------------------------------------------------------------

// BoundedQueueInterface.java by Dale/Joyce/Weems Chapter 5

//

// Interface for a class that implements a queue of T with a bound

// on the size of the queue. A queue is a "first in, first out" structure.

//----------------------------------------------------------------------------

package ch05.queues;

public interface BoundedQueueInterface extends QueueInterface

{

void enqueue(T element) throws QueueOverflowException;

// Throws QueueOverflowException if this queue is full;

// otherwise, adds element to the rear of this queue.

boolean isFull();

// Returns true if this queue is full; otherwise, returns false.

}

GlassQueue.java

//---------------------------------------------------------------------------

// GlassQueue.java by Dale/Joyce/Weems Chapter 5

//

// Extends ArrayUnbndQueue with operations to determine the size of the queue

// and to access the front and rear queue elements without removing them.

//---------------------------------------------------------------------------

package ch05.queues;

public class GlassQueue extends ArrayUnbndQueue

{

public GlassQueue()

{

super();

}

public GlassQueue(int origCap)

{

super(origCap);

}

public int size()

// Returns the number of elements in this queue.

{

return numElements;

}

public T peekFront()

// Returns the object at the front of this queue.

// If the queue is empty, returns null.

{

return queue[front];

}

public T peekRear()

// Returns the object at the rear of this queue.

// If the queue is empty, returns null.

{

return queue[rear];

}

}

LinkedUnbndQueue.java

//---------------------------------------------------------------------------

// LinkedUnbndQueue.java by Dale/Joyce/Weems Chapter 5

//

// Implements UnboundedQueueInterface using a linked list

//---------------------------------------------------------------------------

package ch05.queues;

import support.LLNode;

public class LinkedUnbndQueue implements UnboundedQueueInterface

{

protected LLNode front; // reference to the front of this queue

protected LLNode rear; // reference to the rear of this queue

public LinkedUnbndQueue()

{

front = null;

rear = null;

}

public void enqueue(T element)

// Adds element to the rear of this queue.

{

LLNode newNode = new LLNode(element);

if (rear == null)

front = newNode;

else

rear.setLink(newNode);

rear = newNode;

}

public T dequeue()

// Throws QueueUnderflowException if this queue is empty;

// otherwise, removes front element from this queue and returns it.

{

if (isEmpty())

throw new QueueUnderflowException("Dequeue attempted on empty queue.");

else

{

T element;

element = front.getInfo();

front = front.getLink();

if (front == null)

rear = null;

return element;

}

}

public boolean isEmpty()

// Returns true if this queue is empty; otherwise, returns false.

{

if (front == null)

return true;

else

return false;

}

}

QueueInterface.java

//----------------------------------------------------------------------------

// QueueInterface.java by Dale/Joyce/Weems Chapter 5

//

// Interface for a class that implements a queue of T.

// A queue is a "first in, first out" structure.

//----------------------------------------------------------------------------

package ch05.queues;

public interface QueueInterface

{

T dequeue() throws QueueUnderflowException;

// Throws QueueUnderflowException if this queue is empty;

// otherwise, removes front element from this queue and returns it.

boolean isEmpty();

// Returns true if this queue is empty; otherwise, returns false.

}

QueueOverflowException.java

package ch05.queues;

public class QueueOverflowException extends RuntimeException

{

public QueueOverflowException()

{

super();

}

public QueueOverflowException(String message)

{

super(message);

}

}

QueueUnderflowException.java

package ch05.queues;

public class QueueUnderflowException extends RuntimeException

{

public QueueUnderflowException()

{

super();

}

public QueueUnderflowException(String message)

{

super(message);

}

}

SyncArrayBndQueue.java

//---------------------------------------------------------------------------

// SyncArrayBndQueue.java by Dale/Joyce/Weems Chapter 5

//

// Implements BoundedQueueInterface with an array to hold the queue elements.

// Operations are synchronized to allow concurrent access.

//

// Two constructors are provided: one that creates a queue of a default

// capacity and one that allows the calling program to specify the capacity.

//---------------------------------------------------------------------------

package ch05.queues;

public class SyncArrayBndQueue implements BoundedQueueInterface

{

protected final int DEFCAP = 100; // default capacity

protected T[] queue; // array that holds queue elements

protected int numElements = 0; // number of elements n the queue

protected int front = 0; // index of front of queue

protected int rear; // index of rear of queue

public SyncArrayBndQueue()

{

queue = (T[]) new Object[DEFCAP];

rear = DEFCAP - 1;

}

public SyncArrayBndQueue(int maxSize)

{

queue = (T[]) new Object[maxSize];

rear = maxSize - 1;

}

public synchronized void enqueue(T element)

// Throws QueueOverflowException if this queue is full;

// otherwise, adds element to the rear of this queue.

{

if (isFull())

throw new QueueOverflowException("Enqueue attempted on a full queue.");

else

{

rear = (rear + 1) % queue.length;

queue[rear] = element;

numElements = numElements + 1;

}

}

public synchronized T dequeue()

// Throws QueueUnderflowException if this queue is empty;

// otherwise, removes front element from this queue and returns it.

{

if (isEmpty())

throw new QueueUnderflowException("Dequeue attempted on empty queue.");

else

{

T toReturn = queue[front];

queue[front] = null;

front = (front + 1) % queue.length;

numElements = numElements - 1;

return toReturn;

}

}

public synchronized boolean isEmpty()

// Returns true if this queue is empty; otherwise, returns false

{

return (numElements == 0);

}

public synchronized boolean isFull()

// Returns true if this queue is full; otherwise, returns false.

{

return (numElements == queue.length);

}

}

UnboundedQueueInterface.java

//----------------------------------------------------------------------------

// UnboundedQueueInterface.java by Dale/Joyce/Weems Chapter 5

//

// Interface for a class that implements a queue of T with no bound

// on the size of the queue. A queue is a "first in, first out" structure.

//----------------------------------------------------------------------------

package ch05.queues;

public interface UnboundedQueueInterface extends QueueInterface

{

void enqueue(T element);

// Adds element to the rear of this queue.

}

BSTInterface.java

//----------------------------------------------------------------------------

// BSTInterface.java by Dale/Joyce/Weems Chapter 8

//

// Interface for a class that implements a binary search tree (BST).

//

// The trees are unbounded and allow duplicate elements, but do not allow null

// elements. As a general precondition, null elements are not passed as

// arguments to any of the methods.

//

// The tree supports iteration through its elements in INORDER, PREORDER,

// and POSTORDER.

//----------------------------------------------------------------------------

package ch08.trees;

public interface BSTInterface>

{

// used to specify traversal order

static final int INORDER = 1;

static final int PREORDER = 2;

static final int POSTORDER = 3;

boolean isEmpty();

// Returns true if this BST is empty; otherwise, returns false.

int size();

// Returns the number of elements in this BST.

boolean contains (T element);

// Returns true if this BST contains an element e such that

// e.compareTo(element) == 0; otherwise, returns false.

boolean remove (T element);

// Removes an element e from this BST such that e.compareTo(element) == 0

// and returns true; if no such element exists, returns false.

T get(T element);

// Returns an element e from this BST such that e.compareTo(element) == 0;

// if no such element exists, returns null.

void add (T element);

// Adds element to this BST. The tree retains its BST property.

int reset(int orderType);

// Initializes current position for an iteration through this BST

// in orderType order. Returns current number of nodes in the BST.

T getNext (int orderType);

// Preconditions: The BST is not empty

// The BST has been reset for orderType

// The BST has not been modified since the most recent reset

// The end of orderType iteration has not been reached

//

// Returns the element at the current position on this BST for orderType

// and advances the value of the current position based on the orderType.

}

Golfer.java

//----------------------------------------------------------------------

// Golfer.java by Dale/Joyce/Weems Chapter 6

//

// Supports golfer objects having a name and a score.

// Allows golfers to be compared based on their scores.

//----------------------------------------------------------------------

package support;

public class Golfer implements Comparable

{

protected String name;

protected int score;

public Golfer(String name, int score)

{

this.name = name;

this.score = score;

}

public String getName()

{

return name;

}

public int getScore()

{

return score;

}

public int compareTo(Golfer other)

{

if (this.score < other.score)

return -1;

else

if (this.score == other.score)

return 0;

else

return +1;

}

public String toString()

{

return (score + ": " + name);

}

}