This project builds on Project_1. First, improve your Project_1 program to implement the required functionality fully
Peruse these classes: see the attachment for classes details
GraphNode and Linked_List classes are added to the classes in Project_1. Once again 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 be outside the Obj inheritance hierarchy.
We begin the following phases of the project with the realization that the constructed Obj objects will build a graph where the nodes are the objects and the links are reference pointers. 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 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. The depth-first traversal will be used in emulation of garbage collection in Project 4.
In the main function of MainBSTGraph class, implement the following process. All data must be displayed in an output file.
1.Construct a binary search tree of the following PC objects as per Project 1:
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"
2.Construct another binary search tree of the following Car objects as per Project 1:
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"
3.Display the following data of the constructed objects:
i.The total # of constructed Obj objects.
ii.For each subclass of Obj, total # of its objects, sorted list of their objId values, list of visited objects, # of visited objects, list of unvisited objects, # of unvisited objects. The subclasses are to be listed in decreasing order of the # of objects.
4.Using BST.delete function, delete the following objects from the PC binary search tree:
Smartphone IDcode = "s001"
Laptop IDcode = "l001"
Desktop IDcode = "d001"
These objects will remain in your data structure maintaining the constructed Obj objects.
5.Using BST.delete function, delete the following objects from the Car binary search tree:
Sedan IDcode = "se001"
Coupe IDcode = "co001"
Van IDcode = "va001"
These objects will remain in your data structure maintaining the constructed Obj objects.
6.Using GraphNode and Linked_List objects, construct the following undirected graph of Car objects: see image.
Each node contains in its data field a reference to the indicated Car object. For example, the node labeled "se001" has a reference to the Sedan object with IDcode = "se001". All Car objects in the graph must be the same Car objects inserted into the tree in step 2, not newly constructed copies/clones.
7.Perform a depth-first traversal of the PC binary search tree starting from the root, and display a list of the visited nodes and the # of nodes visited.
8.Without resetting the Boolean values of visited field, perform a depth-first traversal of the Car binary search tree starting from the root, and display a list of the visited nodes and the # of nodes visited.
9.Without resetting the Boolean values of visited field, perform a depth-first traversal of the Car graph, starting from the "se001" node, and display a list of the visited nodes and the # of nodes visited.
10.Display the data of the constructed Obj objects as per step 3.
See the attachment for sample Output. Your output need not be identical to this, but it should display the required data in legible format. MainBSTGraph.main is to read the output file name as external argument, argv[0].
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 = 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< C extends Obj>
abstract class Linked_List< C extends Obj> extends Obj
// The class of linked lists of objects of C extending Obj.
{
abstract NonEmptyList< C> 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< C> x C --> NonEmptyList< C>.
}
EmptyList< C extends Obj>
class EmptyList< C extends Obj> extends Linked_List< C>
// The class of empty linked lists.
{
public String toString()
{
return objId+":"+visited;
}
NonEmptyList< 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 EmptyList< C> x C --> NonEmptyList< C>.
{
return new NonEmptyList< C>(c, this);
}
}
NonEmptyList< C extends Obj>
class NonEmptyList< C extends Obj> extends Linked_List< C>
// The class of nonempty lists containing C objects.
{
C obj; // the C object at the head
Linked_List< C> tail; // tail list
NonEmptyList(C c, Linked_List< C> tl)
{
obj = c;
tail = tl;
}
public String toString()
{
return objId+":"+visited;
}
NonEmptyList< C> 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< C> x C --> NonEmptyList< C>.
{
return new NonEmptyList< C>(c, this);
}
}
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);
// 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< 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+":"+visited;
}
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+":"+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< 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)
// 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< 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 // t.right is nonempty
{
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;
}
}
}
}
}
GraphNode< C extends Data>
class GraphNode< C extends Data> 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< GraphNode< C>> adjacentNodes = new EmptyList< GraphNode< C>>(); // adjacency list of this node
GraphNode(C c)
{
data = c;
}
public String toString()
{
return objId+":"+visited;
}
}
Data
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
abstract class PC extends Data
{
PC(String ID)
{
super(ID);
}
}
Smartphone
class Smartphone extends PC
{
Smartphone(String ID)
{
super(ID);
}
}
Laptop
class Laptop extends PC
{
Laptop(String ID)
{
super(ID);
}
}
Desktop
class Desktop extends PC
{
Desktop(String ID)
{
super(ID);
}
}
Car
abstract class Car extends Data
{
Car(String ID)
{
super(ID);
}
}
Sedan
class Sedan extends Car
{
Sedan(String ID)
{
super(ID);
}
}
Coupe
class Coupe extends Car
{
Coupe(String ID)
{
super(ID);
}
}
Van
class Van extends Car
{
Van(String ID)
{
super(ID);
}
}
MainBSTGraph
public abstract class MainBSTGraph
{
public static void main(String argv[])
{
// argv[0]: output file
Output.setOutput( argv[0] );
Output.closeOutput();
}
}
Sample Output:
--------------------------------------------------------
Data of constructed Obj objects will be displayed.
--------------------------------------------------------
Total of 44 Obj objects have been constructed.
21 objects of class NonEmptyBST:
[2:false, 4:false, 6:false, 8:false, 10:false, 12:false, 14:false, 16:false, 18:false, 20:false, 22:false, 24:false, 35:false, 36:false, 37:false, 38:false, 39:false, 40:false, 41:false, 42:false, 43:false]
list of visited objects:
[]
0 objects visited.
list of unvisited objects:
[2:false, 4:false, 6:false, 8:false, 10:false, 12:false, 14:false, 16:false, 18:false, 20:false, 22:false, 24:false, 35:false, 36:false, 37:false, 38:false, 39:false, 40:false, 41:false, 42:false, 43:false]
21 objects unvisited.
4 objects of class Desktop:
[5:false:d001, 11:false:d002, 17:false:d003, 23:false:d004]
list of visited objects:
[]
0 objects visited.
list of unvisited objects:
[5:false:d001, 11:false:d002, 17:false:d003, 23:false:d004]
4 objects unvisited.
4 objects of class Laptop:
[3:false:l001, 9:false:l002, 15:false:l003, 21:false:l004]
list of visited objects:
[]
0 objects visited.
list of unvisited objects:
[3:false:l001, 9:false:l002, 15:false:l003, 21:false:l004]
4 objects unvisited.
4 objects of class Smartphone:
[1:false:s001, 7:false:s002, 13:false:s003, 19:false:s004]
list of visited objects:
[]
0 objects visited.
list of unvisited objects:
[1:false:s001, 7:false:s002, 13:false:s003, 19:false:s004]
4 objects unvisited.
3 objects of class Coupe:
[27:false:co001, 30:false:co002, 33:false:co003]
list of visited objects:
[]
0 objects visited.
list of unvisited objects:
[27:false:co001, 30:false:co002, 33:false:co003]
3 objects unvisited.
3 objects of class Sedan:
[26:false:se001, 29:false:se002, 32:false:se003]
list of visited objects:
[]
0 objects visited.
list of unvisited objects:
[26:false:se001, 29:false:se002, 32:false:se003]
3 objects unvisited.
3 objects of class Van:
[28:false:va001, 31:false:va002, 34:false:va003]
list of visited objects:
[]
0 objects visited.
list of unvisited objects:
[28:false:va001, 31:false:va002, 34:false:va003]
3 objects unvisited.
2 objects of class EmptyBST:
[0:false, 25:false]
list of visited objects:
[]
0 objects visited.
list of unvisited objects:
[0:false, 25:false]
2 objects unvisited.
--------------------------------------------------------
Traversing the PC BST
--------------------------------------------------------
Object-graph traversal has started ...
NonEmptyBST:2:true
Laptop:21:true:l004
NonEmptyBST:4:true
Desktop:23:true:d004
NonEmptyBST:12:true
Desktop:11:true:d002
EmptyBST:0:true
NonEmptyBST:18:true
Desktop:17:true:d003
NonEmptyBST:10:true
Laptop:9:true:l002
NonEmptyBST:16:true
Laptop:15:true:l003
NonEmptyBST:8:true
Smartphone:7:true:s002
NonEmptyBST:14:true
Smartphone:13:true:s003
NonEmptyBST:20:true
Smartphone:19:true:s004
Total of 19 Obj objects have been visited.
--------------------------------------------------------
Traversing the Car BST
--------------------------------------------------------
Object-graph traversal has started ...
NonEmptyBST:35:true
Coupe:33:true:co003
NonEmptyBST:39:true
Coupe:30:true:co002
EmptyBST:25:true
NonEmptyBST:37:true
Sedan:32:true:se003
NonEmptyBST:38:true
Sedan:29:true:se002
NonEmptyBST:40:true
Van:31:true:va002
NonEmptyBST:43:true
Van:34:true:va003
Total of 13 Obj objects have been visited.
--------------------------------------------------------
Traversing the Car Graph
--------------------------------------------------------
Object-graph traversal has started ...
GraphNode:44:true
Sedan:26:true:se001
NonEmptyList:63:true
GraphNode:52:true
NonEmptyList:76:true
GraphNode:58:true
NonEmptyList:86:true
GraphNode:60:true
NonEmptyList:89:true
NonEmptyList:88:true
GraphNode:56:true
NonEmptyList:84:true
NonEmptyList:83:true
GraphNode:54:true
NonEmptyList:81:true
NonEmptyList:80:true
NonEmptyList:79:true
NonEmptyList:78:true
GraphNode:48:true
Van:28:true:va001
NonEmptyList:70:true
NonEmptyList:69:true
GraphNode:50:true
NonEmptyList:72:true
NonEmptyList:71:true
EmptyList:51:true
NonEmptyList:68:true
GraphNode:46:true
Coupe:27:true:co001
NonEmptyList:67:true
NonEmptyList:66:true
NonEmptyList:65:true
NonEmptyList:64:true
EmptyList:47:true
EmptyList:49:true
NonEmptyList:77:true
EmptyList:55:true
NonEmptyList:82:true
EmptyList:57:true
NonEmptyList:87:true
EmptyList:61:true
NonEmptyList:85:true
EmptyList:59:true
NonEmptyList:75:true
NonEmptyList:74:true
NonEmptyList:73:true
EmptyList:53:true
NonEmptyList:62:true
EmptyList:45:true
Total of 49 Obj objects have been visited.
--------------------------------------------------------
Data of constructed Obj objects will be displayed.
--------------------------------------------------------
Total of 90 Obj objects have been constructed.
28 objects of class NonEmptyList:
[62:true, 63:true, 64:true, 65:true, 66:true, 67:true, 68:true, 69:true, 70:true, 71:true, 72:true, 73:true, 74:true, 75:true, 76:true, 77:true, 78:true, 79:true, 80:true, 81:true, 82:true, 83:true, 84:true, 85:true, 86:true, 87:true, 88:true, 89:true]
list of visited objects:
[62:true, 63:true, 64:true, 65:true, 66:true, 67:true, 68:true, 69:true, 70:true, 71:true, 72:true, 73:true, 74:true, 75:true, 76:true, 77:true, 78:true, 79:true, 80:true, 81:true, 82:true, 83:true, 84:true, 85:true, 86:true, 87:true, 88:true, 89:true]
28 objects visited.
list of unvisited objects:
[]
0 objects unvisited.
21 objects of class NonEmptyBST:
[2:true, 4:true, 6:false, 8:true, 10:true, 12:true, 14:true, 16:true, 18:true, 20:true, 22:false, 24:false, 35:true, 36:false, 37:true, 38:true, 39:true, 40:true, 41:false, 42:false, 43:true]
list of visited objects:
[2:true, 4:true, 8:true, 10:true, 12:true, 14:true, 16:true, 18:true, 20:true, 35:true, 37:true, 38:true, 39:true, 40:true, 43:true]
15 objects visited.
list of unvisited objects:
[6:false, 22:false, 24:false, 36:false, 41:false, 42:false]
6 objects unvisited.
9 objects of class EmptyList:
[45:true, 47:true, 49:true, 51:true, 53:true, 55:true, 57:true, 59:true, 61:true]
list of visited objects:
[45:true, 47:true, 49:true, 51:true, 53:true, 55:true, 57:true, 59:true, 61:true]
9 objects visited.
list of unvisited objects:
[]
0 objects unvisited.
9 objects of class GraphNode:
[44:true, 46:true, 48:true, 50:true, 52:true, 54:true, 56:true, 58:true, 60:true]
list of visited objects:
[44:true, 46:true, 48:true, 50:true, 52:true, 54:true, 56:true, 58:true, 60:true]
9 objects visited.
list of unvisited objects:
[]
0 objects unvisited.
4 objects of class Desktop:
[5:false:d001, 11:true:d002, 17:true:d003, 23:true:d004]
list of visited objects:
[11:true:d002, 17:true:d003, 23:true:d004]
3 objects visited.
list of unvisited objects:
[5:false:d001]
1 objects unvisited.
4 objects of class Laptop:
[3:false:l001, 9:true:l002, 15:true:l003, 21:true:l004]
list of visited objects:
[9:true:l002, 15:true:l003, 21:true:l004]
3 objects visited.
list of unvisited objects:
[3:false:l001]
1 objects unvisited.
4 objects of class Smartphone:
[1:false:s001, 7:true:s002, 13:true:s003, 19:true:s004]
list of visited objects:
[7:true:s002, 13:true:s003, 19:true:s004]
3 objects visited.
list of unvisited objects:
[1:false:s001]
1 objects unvisited.
3 objects of class Coupe:
[27:true:co001, 30:true:co002, 33:true:co003]
list of visited objects:
[27:true:co001, 30:true:co002, 33:true:co003]
3 objects visited.
list of unvisited objects:
[]
0 objects unvisited.
3 objects of class Sedan:
[26:true:se001, 29:true:se002, 32:true:se003]
list of visited objects:
[26:true:se001, 29:true:se002, 32:true:se003]
3 objects visited.
list of unvisited objects:
[]
0 objects unvisited.
3 objects of class Van:
[28:true:va001, 31:true:va002, 34:true:va003]
list of visited objects:
[28:true:va001, 31:true:va002, 34:true:va003]
3 objects visited.
list of unvisited objects:
[]
0 objects unvisited.
2 objects of class EmptyBST:
[0:true, 25:true]
list of visited objects:
[0:true, 25:true]
2 objects visited.
list of unvisited objects:
[]
0 objects unvisited.