All projects must be implemented by Oracle Standard Edition compliant Java.
You will implement a series of programs involving emulation of management of objects and the runtime stack, leading to emulation of garbage collection.
Peruse these classes mentioned below. All the classes whose objects you will maintain and manage are to be subclasses of the root class Obj; examples of parametric binary search trees, Data class, and subclasses PC and Car are included. This project must be implemented by modifying/expanding these template classes. Additional classes may be created to implement some of the functionalities described below; however, such classes must not be subclasses of Obj.
Implement assignment of object identifiers to Obj objects: All Obj objects must be assigned unique sequential integers from 0 as their object identifiers, to be stored in objId field. Devise a suitable data structure to maintain all the constructed Obj objects; you may use standard Java library classes to implement this. This data structure, together with suitable functions, must support the following operation: For each subclass of Obj, display the total # of its objects followed by a sorted list of their objId values; the subclasses are to be listed in decreasing order of the # of objects. You may find getClass() and getName() functions useful (I used them). This part of the program must work generically on all Obj objects regardless of what or how many subclasses exist under it.
In the main function of MainBST class, implement the following process.
1.Construct and insert to an empty binary search tree the following PC objects in the order shown:
Smartphone IDcode = "s001"
Laptop IDcode = "l001"
Desktop IDcode = "d001"
Smartphone IDcode = "s002"
Laptop IDcode = "l002"
Desktop IDcode = "d002"
Smartphone IDcode = "s003"
Laptop IDcode = "l003"
Desktop IDcode = "d003"
Smartphone IDcode = "s004"
Laptop IDcode = "l004"
Desktop IDcode = "d004"
The type of this binary search tree must be BST< PC>.
2.Construct and insert to another empty binary search tree the following Car objects in the order shown:
Sedan IDcode = "se001"
Coupe IDcode = "co001"
Van IDcode = "va001"
Sedan IDcode = "se002"
Coupe IDcode = "co002"
Van IDcode = "va002"
Sedan IDcode = "se003"
Coupe IDcode = "co003"
Van IDcode = "va003"
The type of this binary search tree must be BST< Car>. No need to add fields to PC or Car classes in this project.
3.Display the following in an output file:
i.The total # of constructed Obj objects.
ii.For each subclass of Obj, the total # of its objects followed by a sorted list of their objId values; the subclasses are to be listed in decreasing order of the # of objects.
See sample output at the bottom. Your output need not be identical to this, but it should display the required data in legible format. To make grading efficient and uniform, MainBST.main is to read the output file name as external argument, argv[0].
Peruse these classes
Output
import java.io.*;
public abstract class Output
{
public static PrintWriter outStream;
public static void display(String s)
{
outStream.print(s);
}
public static void displayln(String s)
{
outStream.println(s);
}
public static void setOutput(String outFile)
// Sets the output stream to "outFile".
{
try
{
outStream = new PrintWriter( new FileOutputStream(outFile) );
}
catch(FileNotFoundException e)
{
e.printStackTrace();
}
}
public static void closeOutput()
{
outStream.close();
}
}
Obj
abstract class Obj
{
static int newObjId = 0;
int objId; // the unique object identifier
public abstract String toString();
}
BST< C extends Data>
abstract class BST< C extends Data> extends Obj
// The class of binary search trees containing objects of parameter class C extending Data.
// The ordering is determined by C.IDcode.
{
abstract C search(String ID);
// Returns the C object in the target tree whose IDcode is equal to ID; returns null if no such object found.
// The type of this function is BST< C> x String --> C.
abstract NonEmptyBST< C> insert(C c);
// Returns the nonempty tree obtained by inserting parameter C object into the target tree.
// If the tree already has the object with the same IDcode, issues a message and returns the target tree unchanged.
// The type of this function is BST< C> x C --> NonEmptyBST< C>.
abstract BST< C> delete(String ID);
// Deletes from the target tree the C object whose IDcode is equal to ID.
// If the tree has no such object, issues a message and returns the target tree unchanged.
// The type of this function is BST< C> x String --> BST< C>.
}
EmptyBST< C extends Data>
class EmptyBST< C extends Data> extends BST< C>
// The class of empty binary search trees.
{
public String toString()
{
return objId+"";
}
C search(String ID)
// The type of this function is EmptyBST< C> x String --> C.
{
return null;
}
NonEmptyBST< C> insert(C c)
// Inserts parameter C object into the empty tree, and returns the resulting non-empty tree.
// The type of this function is EmptyBST< C> x C --> NonEmptyBST< C>.
{
return new NonEmptyBST< C>(c, this, this);
}
EmptyBST< C> delete(String ID)
// Issues a message and returns the empty tree.
// The type of this function is EmptyBST< C> x String --> EmptyBST< C>.
{
System.out.println("Data object with the given IDcode "+ID+" does not exist in the tree.");
return this;
}
}
NonEmptyBST< C extends Data>
class NonEmptyBST< C extends Data> extends BST< C>
// The class of nonempty binary search trees containing C objects.
{
C data; // the C object at the root
BST< C> left; // left subtree
BST< C> right; // right subtree
NonEmptyBST(C c, BST< C> l, BST< C> r)
{
data = c;
left = l;
right = r;
}
public String toString()
{
return objId+"";
}
C search(String ID)
// Returns the C object in the target tree whose IDcode is equal to ID; returns null if no such object found.
// The type of this function is NonEmptyBST< C> x String--> C.
{
int i = ID.compareTo(data.IDcode);
if ( i == 0 )
return data;
else if ( i < 0 )
return left.search(ID);
else // i > 0
return right.search(ID);
}
NonEmptyBST< C> insert(C c)
// Returns the nonempty tree obtained by inserting parameter C object into the target tree.
// If the tree already has the object with the same IDcode, issues a message and returns the target tree unchanged.
// The type of this function is NonEmptyBST< C> x C --> NonEmptyBST< C>.
{
int i = (c.IDcode).compareTo(data.IDcode);
if ( i < 0 )
left = left.insert(c);
else if ( i > 0 )
right = right.insert(c);
else // i == 0, c.IDcode == data.IDcode
System.out.println("Data object with the same IDcode "+data.IDcode+" already exists in the tree.");
return this;
}
BST< C> delete(String ID)
// Deletes from the target tree the C object whose IDcode is equal to ID.
// If the tree has no such object, issues a message and returns the target tree unchanged.
// The type of this function is NonEmptyBST< C> x String --> BST< C>.
{
int i = ID.compareTo(data.IDcode);
if ( i < 0 )
{
left = left.delete(ID);
return this;
}
else if ( i > 0 )
{
right = right.delete(ID);
return this;
}
else // i == 0, ID == data.IDcode, the object with ID found at the root
{
if ( left instanceof EmptyBST )
return right;
else if ( right instanceof EmptyBST )
return left;
else // left is nonempty & right is nonempty
{
// search for the object whose IDcode is the predecessor of ID, which is the maximum (rightmost) key in the left subtree;
// replace data by that object;
// delete the node containing that object;
NonEmptyBST< C> t = (NonEmptyBST< C>)left;
if ( t.right instanceof EmptyBST )
{
data = t.data;
left = t.left;
return this;
}
else
{
while ( !( ((NonEmptyBST< C>)t.right).right instanceof EmptyBST ) )
t = (NonEmptyBST< C>)t.right;
data = ((NonEmptyBST< C>)t.right).data;
t.right = ((NonEmptyBST< C>)t.right).left;
return this;
}
}
}
}
}
Data
abstract class Data extends Obj
{
String IDcode; // the ID code of Data objects
public String toString()
{
return objId+":"+IDcode;
}
}
PC
abstract class PC extends Data
{
}
Smartphone
class Smartphone extends PC
{
}
Laptop
class Laptop extends PC
{
}
Desktop
class Desktop extends PC
{
}
Car
abstract class Car extends Data
{
}
Sedan
class Sedan extends Car
{
}
Coupe
class Coupe extends Car
{
}
Van
class Van extends Car
{
}
MainBST
public abstract class MainBST
{
public static void main(String argv[])
{
// argv[0]: output file
Output.setOutput( argv[0] );
Output.closeOutput();
}
}
Total of 44 Obj objects have been constructed.
21 objects of class NonEmptyBST:
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 27, 29, 31, 33, 35, 37, 39, 41, 43]
4 objects of class Desktop:
[5:d001, 17:d003, 23:d004]
4 objects of class Laptop:
[3:l001, 9:l002, 15:l003, 21:l004]
4 objects of class Smartphone:
[1:s001, 7:s002, 13:s003, 19:s004]
3 objects of class Coupe:
[28:co001, 34:co002, 40:co003]
3 objects of class Sedan:
[26:se001, 32:se002, 38:se003]
3 objects of class Van:
[30:va001, 36:va002, 42:va003]
2 objects of class EmptyBST:
[0, 25]