Peruse following classes. 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.

Output.java: 

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.java:

abstract class Obj { static int newObjId = 0; int objId; // the unique object identifier public abstract String toString(); } 

BST.java: 

abstract class BST 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 x String --> C. abstract NonEmptyBST 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 x C --> NonEmptyBST. abstract BST 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 x String --> BST. } 

EmptyBST.java: 

class EmptyBST extends BST // The class of empty binary search trees. { public String toString() { return objId+""; } C search(String ID) // The type of this function is EmptyBST x String --> C. { return null; } NonEmptyBST 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 x C --> NonEmptyBST. { return new NonEmptyBST(c, this, this); } EmptyBST delete(String ID) // Issues a message and returns the empty tree. // The type of this function is EmptyBST x String --> EmptyBST. { System.out.println("Data object with the given IDcode "+ID+" does not exist in the tree."); return this; } } 

NonEmptyBST.java 

class NonEmptyBST extends BST // The class of nonempty binary search trees containing C objects. { C data; // the C object at the root BST left; // left subtree BST right; // right subtree NonEmptyBST(C c, BST l, BST 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 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 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 x C --> NonEmptyBST. { 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 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 x String --> BST. { 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 t = (NonEmptyBST)left; if ( t.right instanceof EmptyBST ) { data = t.data; left = t.left; return this; } else // t.right is nonempty { while ( !( ((NonEmptyBST)t.right).right instanceof EmptyBST ) ) t = (NonEmptyBST)t.right; data = ((NonEmptyBST)t.right).data; t.right = ((NonEmptyBST)t.right).left; return this; } } } } } 

Data.java

abstract class Data extends Obj { String IDcode; // the ID code of Data objects public String toString() { return objId+":"+IDcode; } } 

PC.java

abstract class PC extends Data { } 

Smartphone.java

class Smartphone extends PC { } 

Laptop.java

class Laptop extends PC { } 

Desktop.java

class Desktop extends PC { } 

Car.java

abstract class Car extends Data { } 

Sedan.java

class Sedan extends Car { } 

Coupe.java

class Coupe extends Car { } 

Van.java 

class Van extends Car { } 

MainBST.java

public abstract class MainBST { public static void main(String argv[]) { // argv[0]: output file Output.setOutput( argv[0] ); Output.closeOutput(); } } 

In the main function of MainBST class, implement the following process.

Construct and insert into an empty binary search tree the following PC objects cumulatively 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. Construct and insert into another empty binary search tree the following Car objects cumulatively 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. No need to add fields to PC or Car classes in this project. Display the following in an output file:

The total # of constructed Obj objects.

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.

sample output:

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, 11:d002, 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]