Write a program to keep track of who is enrolled for a two-week summer camp.The
ID: 3673197 • Letter: W
Question
Write a program to keep track of who is enrolled for a two-week summer camp.The program needs to use a binary search tree to maintain the set of campers enrolled in Camp Posanivee. Should not be case-sensitive. Needs to consist of a loop to process commands. The commands should come from a text file (say, "camp.txt"). The program quits when the command 'Q' is given. Below is a list of commands the program should support:
H Help: print a list of commands
E name age gender Enroll a new camper (insert)
W name Withdraw a camper (delete)
D name Display the age and gender of a camper
A Print the average age of the campers
L List all campers names in alphabetical order
S Print the number of boy and girl campers
P List all campers names in preorder
Q Quit
Here name is a string of at most 20 non-blank characters, age is an integer, and gender is either M or F. It can be assumed command arguments are separated by one or more spaces.
It should echo the input, especially for commands that give no output (like E or W), and handle special cases in a clean way (for example, computing the average age of an empty tree should not crash your program).
Here is a sample input file:
A
E Kanga 26 F
E Tigger 28 M
E Pooh 31 M
L
D Tigger
E Rabbit 30 M
A
S
E Eeyore 36 M
W Kanga
P
Q
Here is the output that corresponds:
Welcome to Camp Posanivee!!
Command: A
There are no campers.
Command: E Kanga 26 F
New camper added.
Command: E Tigger 28 M
New camper added.
Command: E Pooh 31 M
New camper added.
Command: L
Alphabetical List of Campers:
Kanga
Pooh
Tigger
Command: D Tigger
Name: Tigger
Age: 28
Gender: M
Command: E Rabbit 30 M
New camper added.
Command: A
Average age = 28.75
Command: S
Camper count by gender:
boys = 3
girls = 1
Command: E Eeyore 36 M
New camper added.
Command: W Kanga
Camper withdrawn.
Command: P
Preorder Traversal:
Pooh
Eeyore
Tigger
Rabbit
Command: Q
End of program.
Bring plenty of calomine lotion!
Here follows a program template that can be used
import java.util.Scanner;
import java.io.*;
public class CampPosanivee {
static String name;
static String age;
static String gender;
static Camper camper = null;
public static void main(String[] args) throws IOException {
logic here…
}
public class Camper implements Comparable<Camper> {
logic here….
}
public class BST {
private class treenode {
Comparable item;
treenode left, right;
}
treenode root; // ref to the root of the bst
int count;
private Queue Q; // create for info
public static final int PREORDER = 0;
public static final int INORDER = 1;
public static final int POSTORDER = 2;
public BST() { // create an empty BST object
root = null;
count = 0;
Q = new QueueLL(); // create new LL for objects
}
public void makeEmpty() {
root = null;
count = 0;
Q.makeEmpty();
}
public boolean isEmpty() {
return root == null;
}
public int size() {
return count;
}
public Comparable lookup(Comparable x) {
return lookup(root, x);
}
private Comparable lookup(treenode r, Comparable x) { // base cases
if (r == null)
return null;
if (r.item.compareTo(x) == 0)
return r.item;
// recursive case
if (x.compareTo(r.item) < 0)
return lookup(r.left, x);
else
return lookup(r.right, x);
}
public void insert(Comparable x) {
root = insert(root, x);
count++;
}
// returns a reference to the root of the tree with x inserted
private treenode insert(treenode r, Comparable x) {
// base case
if (r == null) {
treenode t = new treenode();
t.item = x;
t.left = t.right = null;
return t;
}
// recursive case
if (x.compareTo(r.item) < 0) {
r.left = insert(r.left, x);
return r;
} else {
r.right = insert(r.right, x);
return r;
}
}
private Comparable todelete; // item that gets deleted
public Comparable delete(Comparable x)
// returns the item deleted, or null if not found
{
todelete = lookup(x);
if (todelete != null)
root = delete(root, x);
return todelete;
}
// returns a reference to the root of the modified tree
private treenode delete(treenode r, Comparable x) {
// base case: all the work is here
if (r.item.compareTo(x) == 0) {
// code to handle 3 cases
// 0 children
if (r.left == null && r.right == null)
return null;
// 1 child
if (r.left == null) // we have only a right child
return r.right; // promote the right child
if (r.right == null)
return r.left;
// 2 children case
Comparable successor = min(r.right);
r.item = successor;
r.right = delete(r.right, successor);
return r;
}
// recursive case
if (x.compareTo(r.item) < 0) {
r.left = delete(r.left, x);
return r;
} else {
r.right = delete(r.right, x);
return r;
}
}
private Comparable min(treenode r) {
// base cases
if (r == null)
return null;
if (r.left == null)
return r.item;
// recursive case
return min(r.left);
}
// Iterator functions
public void reset() {
reset(INORDER);
}
public void reset(int order) {
Q.makeEmpty();
traverse(root, order);
}
private void traverse(treenode r, int order) {
if (r == null)
return;
if (order == PREORDER)
Q.enqueue(r.item);
traverse(r.left, order);
if (order == INORDER)
Q.enqueue(r.item);
traverse(r.right, order);
if (order == POSTORDER)
Q.enqueue(r.item);
}
public Comparable getNext() {
return (Comparable) Q.dequeue();
}
public boolean hasNext() {
return !Q.isEmpty();
}
public void print() {
print(root);
}
private void print(treenode r) // inorder
{
// base case: empty tree
if (r == null)
return;
// recursive case
print(r.left);
System.out.println(r.item);
print(r.right);
}
}
public interface Queue {
// Transformers/Mutators
public void enqueue(Object x);
public Object dequeue();
public void makeEmpty();
// Observers/Accessors
public Object getFront();
public int size();
public boolean isEmpty();
public boolean isFull();
}
public class QueueLL implements Queue {
private class node {
public Object data;
public node next;
}
node front, back;
int count;
public QueueLL() {
makeEmpty();
}
// Transformers/Mutators
public void enqueue(Object x) {
node nn = new node();
nn.data = x;
nn.next = null;
if (isEmpty())
front = nn;
else
back.next = nn;
back = nn;
count++;
}
public Object dequeue() {
if (isEmpty())
return null;
Object frontitem = getFront();
front = front.next;
count--;
if (count == 0)
back = null;
return frontitem;
}
public void makeEmpty() {
front = back = null;
count = 0;
}
// Observers/Accessors
public Object getFront() {
if (isEmpty())
return null;
return front.data;
}
public int size() {
return count;
}
public boolean isEmpty() {
return count == 0;
}
public boolean isFull() {
return false;
}
}
Explanation / Answer
BST.java
public class BST
{
private class treenode
{
public Comparable item;
public treenode left, right;
}
treenode root;
int count;
public BST()
{ root=null; count=0; }
public int size() { return count; }
public boolean isEmpty()
{ return count==0; }
public void makeEmpty()
{ root=null; count=0; }
public void insert(Comparable x)
{
root=insert(x,root);
count++;
}
private treenode insert(Comparable x,
treenode r)
{
// base case - empty tree
if(r==null)
{
treenode tn=new treenode();
tn.item=x;
tn.left=tn.right=null;
return tn;
}
// recursive cases
//left side
if(x.compareTo(r.item)<0)
{ r.left=insert(x,r.left); }
// right side
else
{ r.right=insert(x,r.right); }
return r;
}
public void print() { print(root); }
private void print(treenode r)
{
if(r==null) return;
print(r.left);
System.out.println(r.item);
print(r.right);
}
public Comparable lookup(Comparable x)
{
return lookup(x,root);
}
private Comparable lookup(
Comparable x, treenode r)
{
// base case
if(r==null) return null;
if(x.compareTo(r.item)==0) // found it
{ return r.item; }
// recursive cases
else if(x.compareTo(r.item)<0)
{ return lookup(x,r.left); }
// right side
else
{ return lookup(x,r.right); }
}
public void delete(Comparable x)
{
root=delete(x,root);
}
private treenode delete(Comparable x,
treenode r)
{
// base case
if(r==null) return null;
if(x.compareTo(r.item)==0) // found it
{
// 3 cases
// 0 children case
if(r.left==null && r.right==null)
{ count--; return null; }
// 1 child on the left
else if(r.right==null)
{
count--;
return r.left;
}
// 1 child on the right
else if(r.left==null)
{
count--;
return r.right;
}
// 2 children
else
{
Comparable ins=findmin(r.right);
r.item=ins;
r.right=delete(ins,r.right);
return r;
}
}
// recursive cases
else if(x.compareTo(r.item)<0)
{
r.left=delete(x,r.left);
return r;
}
// right side
else
{
r.right=delete(x,r.right);
return r;
}
}
private Comparable findmin(treenode r)
{
if(r==null) return null;
if(r.left==null)
{ return r.item; }
return findmin(r.left);
}
public Comparable getMin()
{
return findmin(root);
}
// iterator/traversal functions
public static final int PREORDER=0;
public static final int INORDER=1;
public static final int POSTORDER=2;
private Queue q;
public void reset(int order)
{
q=new QueueLL();
fillq(root,order);
}
private void fillq(treenode r, int order)
{
if(r==null) return;
if(order==PREORDER)
q.enqueue(r.item);
fillq(r.left,order);
if(order==INORDER)
q.enqueue(r.item);
fillq(r.right,order);
if(order==POSTORDER)
q.enqueue(r.item);
}
public Comparable getNext()
{
return (Comparable) q.dequeue();
}
public boolean hasNext()
{
return !q.isEmpty();
}
}
MainSort.java
import java.io.*;
import java.util.*;
public class MainSort implements Comparable
{
// Sorting algorithms
public static void select(Comparable []A)
{
for(int n=A.length; n>1; n--) {
int maxpos=findmax(A,n);
swap(A,maxpos,n-1);
} // end for loop
}
private static void swap(Object [] A, int x, int y)
{
Object temp=A[x];
A[x]=A[y]; A[y]=temp;
}
private static int findmax(Comparable [] A, int n)
{
int maxsofar=0;
for(int i=1; i<n; i++) {
if(A[i].compareTo(A[maxsofar])>0) {
maxsofar=i;
} // end if
} // end for loop
return maxsofar;
}
public static void bubble(Comparable [] A)
{
for(int i=0; i<A.length; i++)
// Loop to swap items out of order
for(int j=0; j+1<A.length; j++)
if(A[j].compareTo(A[j+1])>0) {
swap(A,j,j+1);
} // end if
}
public static void insertion(Comparable [] A)
{
for(int toinsert=1; toinsert<A.length; toinsert++) {
// Copy stuff over
Comparable save=A[toinsert];
int j;
for(j=toinsert; j>0 && A[j-1].compareTo(save)>0; j--) {
A[j]=A[j-1];
A[j]=save;
} // end for loop
}
public static void insert(Comparable [] A, int offset, int gap)
{
for(int toinsert=offset+gap; toinsert<A.length; toinsert+=gap) {
// Copy stuff over
Comparable save=A[toinsert];
int j;
for(j=toinsert; j>=gap && A[j-gap].compareTo(save)>0; j-=gap) {
A[j]=A[j-gap];
} // end for loop
A[j]=save;
} // end for loop
}
public static void shell(Comparable [] A)
{
int gap=A.length/4;
while(gap>1) {
// Sort groups
for(int offset=0; offset<gap; offset++)
insert(A,offset,gap);
// Reduce the gap
gap=(int)(gap/2.2);
} // end while loop
insertion(A);
}
public static void quick(Comparable [] A)
{
quick(A,0,A.length-1);
}
private static void quick(Comparable [] A, int start, int stop)
{
// Base cases
// Length 0 or 1:
if(stop<=start) return;
// Length 2
if(start+1==stop) {
if(A[start].compareTo(A[stop])>0)
swap(A,start,stop);
return;
} // end if
// Recursive case
int pivot=partition(A,start,stop);
quick(A,start,pivot-1);
quick(A,pivot+1,stop);
}
private static int partition(Comparable [] A, int start, int stop)
{
Comparable pivot=A[stop];
int right=stop-1;
int left=start;
while(left<right) {
// Move left to find large items
while(A[left].compareTo(pivot)<0)
left++;
// Move right to find small items
while(right>=start && A[right].compareTo(pivot)>=0)
right--;
// Swap
if(left<right)
swap(A,left,right);
} // end while
swap(A,left,stop);
return left;
}
public static void merge(Comparable [] A)
{
mergesort(A,0,A.length-1);
}
private static void mergesort(Comparable [] A,int start, int stop)
{
// Base cases
// Length 0 or 1:
if(stop<=start) return;
// Length 2
if(start+1==stop) {
if(A[start].compareTo(A[stop])>0)
swap(A,start,stop);
return;
} // end if
// Recursive case
int mid=(start+stop)/2;
mergesort(A,start,mid);
mergesort(A,mid+1,stop);
domerge(A,start,stop);
}
private static void domerge(Comparable [] A, int start, int stop)
{
int mid=(start+stop)/2;
Comparable [] B=new Comparable[stop-start+1];
int left=start;
int right=mid+1;
for(int i=0; i<B.length; i++) {
// Does it come from the left?
if(right>stop // Right is empty
|| (left<=mid && // Left is not empty
A[left].compareTo(A[right])<0)) {
B[i]=A[left++];
} // end if
else {
B[i]=A[right++];
} // end else
} // end for loop
for(int i=0; i<B.length; i++)
A[start+i]=B[i];
}
// Global variables
static Integer [] data;
static int i;
static int x;
static int y;
static int z;
static int n;
static char go;
static char enter;
public static void main(String [] args)
throws IOException
{
Scanner cin=new Scanner(System.in);
// Loop to reset data and compare algorithms again
do {
input(cin, n);
// Array for the random numbers to be sorted
int [] sort = new int[n];
// Creates an object using the Integer wrapper class
data = new Integer[sort.length];
// Loop fills the data object array with the random numbers, and prints if
// there are less then 101 integers
for(i=0; i<n; i++) {
int number = (int)(1+n*Math.random());
sort [i] = number;
if(n<=100) { System.out.println(number); }
data[i] = new Integer(sort[i]);
} // end for loop
sort(cin, go, data, i, x, y, z);
restart(cin, enter);
}while(enter == 'y' || enter == 'Y'); // end do-while loop
}
// Method for inputing the number of integers to sort
public static void input(Scanner cin, int n)
{
System.out.println("Please enter the integer value you would like to use.");
n = cin.nextInt();
System.out.println("This is your integer: " + n + ".");
}
// Method for sorting data; also uses time method
public static void sort(Scanner cin, char go, Integer [] data, int i, int x, int y, int z)
{
System.out.println("Do you want to sort your data? (Y or N)");
go = cin.next().charAt(0);
if(go == 'y' || go == 'Y') {
int h = (int)System.currentTimeMillis();
quick(data);
int j = (int)System.currentTimeMillis();
int u = j-h;
System.out.println("This is your run time: " + u);
y = (int)System.currentTimeMillis();
insertion(data);
time(data, i, x, z);
} // end if
}
// Method to call the time after the sorting algorithm takes place
// and calculate/display what the run time is in milliseconds
// Also prints out sorted data if there are less than 101 integers
public static void time(Integer [] data, int i, int x, int z)
{
z = (int)System.currentTimeMillis();
x = z-y;
System.out.println("The run time is: " + x);
for(int pos=0; pos<data.length; pos++) {
if(data.length<=100){ System.out.println(data[pos]); }
} // end for loop
x = 0;
}
// Method for user input to decide to use the program again
public static void restart(Scanner cin, char enter)
{
System.out.println("Do you want to run this program again? (Y or N)");
enter = cin.next().charAt(0);
}
// CompareTo function uses the built-in Comparable interface to compare the objects
public int compareTo(Object o)
{
Integer x = (Integer) o;
return data[i].compareTo(data[i-1]);
}
}
camp.java
import java.io.*;
import java.util.*;
public class camp implements Comparable
{
char command;
String camper;
int age;
String gender;
String blank;
/**
Constructor to read form a file
@param r Scanner object to read from
*/
public camp(Scanner r)
{
if(r.hasNext()) {
camper = r.next();
if(r.hasNextInt()) {
age = r.nextInt();
if(r.hasNext()) {
gender = r.next();
blank = r.nextLine();
} // end if
} // end if
} // end if
else{
blank = r.nextLine();
} // end else
}
/**
Print - observer
@return a string representing the info
*/
public String toString()
{
return command + " " + camper + " " + age + " " + gender;
}
/**
Get the command - observer
@return the command
*/
public char getCommand()
{ return command; }
/**
Get the camper's name - observer
@return the camper's name
*/
public String getCamper()
{ return camper; }
/**
Get the age of the camper - observer
@return the camper's age
*/
public int getAge()
{ return age; }
/**
Get the gender of the camper - observer
@return the camper's gender
*/
public String getGender()
{ return gender; }
/**
CompareTo function
Uses built-in comparable interface
*/
public int compareTo(Object x)
{
camp b=(camp) x;
return camper.compareTo(b.camper);
}
}
poisonivy.java
import java.io.*;
import java.util.*;
public class poisonivy
{
// Global variables
static camp camper;
static camp camper2;
static camp camper3;
static camp name;
static char command;
static double sum;
static double total;
static double avg;
static int boy;
static int girl;
/**
* Main Method
*/
public static void main(String [] args)
throws IOException
{
Scanner campfile=new Scanner(new FileReader("camp.txt"));
Scanner cin=new Scanner(System.in);
// Creates an object for the binary search tree
BST tree=new BST();
System.out.println("Welcome to Camp Posanivee!!");
while(command != 'Q') {
command = campfile.next().charAt(0);
System.out.print(" Command: " + command);
help();
enroll(campfile, tree);
withdraw(campfile, tree);
display(campfile, tree);
average();
list(tree);
gender(tree);
preorder(tree);
} // end while loop
System.out.println(" End of program.");
System.out.println("Bring plenty of calomine!");
}
/**
* Displays the help command
* @param The help command
*/
public static void help()
{
if(command == 'H') {
System.out.println("Here is a list of commands: ");
System.out.println("H = Help: print a list of commands");
System.out.println("E = Enroll a new camper(insert)");
System.out.println("W = Withdraw a camper(delete)");
System.out.println("D = Display the age and gender of a camper");
System.out.println("A = Print the average age of the campers");
System.out.println("L = List all campers names in alphabetical order");
System.out.println("S = Print the number of boy and girl campers");
System.out.println("P = List all campers names in preorder");
System.out.println("Q = Quit");
} // end if
}
/**
* Enrolls the new campers in the camp
* @param Enrolls the new camper
*/
public static void enroll(Scanner campfile, BST tree)
{
if(command == 'E') {
camper = new camp(campfile);
tree.insert(camper);
sum = sum + camper.getAge();
total++;
System.out.println(camper);
System.out.println("New camper added.");
} // end if
}
/**
* Withdraws the campers already enrolled in the camp
* @param Withdraws a camper
*/
public static void withdraw(Scanner campfile, BST tree)
{
if(command == 'W') {
camper = new camp(campfile);
tree.delete(camper);
sum = sum - camper.getAge();
total--;
System.out.println(" " + camper.getCamper());
System.out.println("Camper withdrawn.");
} // end if
}
/**
* Displays the name, age and gender of a camper
* @param Diplays name, age and gender
*/
public static void display(Scanner campfile, BST tree)
{
if(command == 'D') {
name = new camp(campfile);
System.out.print(" " + name.getCamper());
camper3 = (camp)tree.lookup(name);
if(camper3 == null) {
System.out.println("Camper not found.");
} // end if
else {
System.out.println(" Name: " + camper3.getCamper() + " Age: " + camper3.getAge() + " Gender: " + camper3.getGender());
} // end else
} // end if
}
/**
* Calculates and displays the average age of the campers enrolled
* @param Calculates and displays the average age
*/
public static void average()
{
if(command == 'A') {
if(total == 0) {
System.out.println(" There are no campers.");
} // end if
else {
avg = sum/total;
System.out.println(" Average age = " + avg + ".");
} // end else
} // end if
}
/**
* Displays the camper in alphbetical order by first their name
* @param Displays campers in alphabetical order
*/
public static void list(BST tree)
{
if(command == 'L') {
System.out.println(" Alphabetical List of Campers:");
tree.reset(BST.INORDER);
while(tree.hasNext()) {
System.out.println(((camp)tree.getNext()).getCamper());
} // end while loop
} // end if
}
/**
* Displays the # of campers based on gender
* @param displays the # of M/F campers
*/
public static void gender(BST tree)
{
if(command == 'S') {
tree.reset(BST.POSTORDER);
while(tree.hasNext()) {
camper2 = ((camp)tree.getNext());
if(camper2.getGender().charAt(0) == 'M') {
boy++;
} // end if
if(camper2.getGender().charAt(0) == 'F'){
girl++;
} // end if
} // end while loop
System.out.println(" Camper count by gender: ");
System.out.println("Boys = " + boy);
System.out.println("Girls = " + girl);
}
}
/**
* Displays the campers in a preorder traversal of the tree they are located in
@param Does a preorder traversal of the tree
*/
public static void preorder(BST tree)
{
if(command == 'P') {
System.out.println(" Preorder Traversal: ");
tree.reset(BST.PREORDER);
while(tree.hasNext()) {
System.out.println(((camp)tree.getNext()).getCamper());
} // end while loop
} // end if
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.