Peruse these classes. This assingment 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 be outside the Obj inheritance hierarchy. In appropriate subclasses of Obj, implement the function traverse( ) that performs, by recursion, depth-first traversal of the object graph starting from "this" object. The function will visit all and only the objects that can be reached from "this" object by chains of reference pointers. The Boolean value of visited field of every visited object will be updated to true. In this project only traverse( ) function will update the values of visited field. In the traversal process none of the previously visited objects will be visited.

In the main function of MainBSTGraph class, implement the following process. All data must be displayed in an output file.

Your output should display the required data in legible format. To make grading efficient and uniform, MainBSTGraph.main is to read the output file name as external argument, argv[0].

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 = newObjId++; // the unique object identifier // assign newObjId to objId, then increment newObjId boolean visited = false; //indicates if this object has been visited by traverse() function Obj() { // This constructor is automatically invoked by constructors of subclasses. // This is the best place to add new Obj object to your data structure. } public abstract String toString(); abstract void traverse(); // the function to perform depth-first traversal of the object graph starting from this object }

Linked_List.java

abstract class Linked_List extends Obj // The class of linked lists of objects of C extending Obj. { abstract NonEmptyList insert(C c); // Returns the nonempty list obtained by inserting parameter C object as head element of the target list. // The type of this function is Linked_List x C --> NonEmptyList. } 

EmptyList.java

class EmptyList extends Linked_List // The class of empty linked lists. { public String toString() { return objId+":"+visited; } NonEmptyList insert(C c) // Inserts parameter C object into the empty tree, and returns the resulting non-empty tree. // The type of this function is EmptyList x C --> NonEmptyList. { return new NonEmptyList(c, this); } }

NonEmptyList.java

class NonEmptyList extends Linked_List // The class of nonempty lists containing C objects. { C obj; // the C object at the head Linked_List tail; // tail list NonEmptyList(C c, Linked_List tl) { obj = c; tail = tl; } public String toString() { return objId+":"+visited; } NonEmptyList insert(C c) // Returns the nonempty list obtained by inserting parameter C object as head element of the target list. // The type of this function is NonEmptyList x C --> NonEmptyList. { return new NonEmptyList(c, this); } }

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); // Returns the tree obtained by deleting 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+":"+visited; } 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+":"+visited; } 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 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 ) 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) // Returns the tree obtained by deleting 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 ) { 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; } } } } }

GraphNode.java

class GraphNode extends Obj // The class of graph nodes containing objects of parameter class C extending Data. { C data; // the C object in this node Linked_List> adjacentNodes = new EmptyList>(); // adjacency list of this node GraphNode(C c) { data = c; } public String toString() { return objId+":"+visited; } }

Data.java

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

PC.java

abstract class PC extends Data { PC(String ID) { super(ID); } } 

Smartphone.java

class Smartphone extends PC { Smartphone(String ID) { super(ID); } } 

Laptop.java

class Laptop extends PC { Laptop(String ID) { super(ID); } } 

Desktop.java

class Desktop extends PC { Desktop(String ID) { super(ID); } } 

Car.java

abstract class Car extends Data { Car(String ID) { super(ID); } } 

Sedan.java

class Sedan extends Car { Sedan(String ID) { super(ID); } } 

Coupe.java

class Coupe extends Car { Coupe(String ID) { super(ID); } } 

Van.java

class Van extends Car { Van(String ID) { super(ID); } }

MainBSTGraph.java

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

Output Obi 5 Linked List?C extends Obi> EmptyL?SKC extends Obi> . NonEmptyLisKC extends Obi> o BS ?C extends Data> 8 . EmptyBST?C extends Data . NonEmptyBST?C extends Datax o GraphNode o Data . PC Smartphone . Lapto . Deskto . Car - Sedan - Coupe Van MainBST Graph