Part 1 Design and implement a class Menu which uses doubly linked lists as main
ID: 3758295 • Letter: P
Question
Part 1
Design and implement a class Menu which uses doubly linked lists as main data structures. A menu object consists of a set of main menu items, organized as a doubly linked list. Each main menu item has an associated submenu of items which is also organized as a doubly linked list (see an example of a Menu object in the attached file MenuExample.pdf).
The class Menu should define a default constructor which builds an empty menu and the following methods:
- addMainMenuItem, for adding a new main menu item with an empty submenu. The method should have the following signature:
public boolean addMainMenuItem(String newItem, String existingItem, int position)
The method works in the following way:
-if parameter existingItem is null, the newItem will be added at the end of the list;
-if the parameter existingItem is not null, the newItem will be added before the existingItem if parameter position is -1 and after the existinItem if parameter position is 1;
- deleteMainMenuItem, deletes the main menu item specified by name (supplied as method parameter);
- addSubMenuItem, adds a submenu item specified by name to a main menu item specified by name (both names should be supplied as method parameters);
- toString, traverses the linked lists data structures and generates the string representation of a menu object, organized on lines. Each line should include the main menu item followed by its submenu items. The items should be separated by a semicolon character. The string representation should also include as the last line, the number of main menu items and the total number of submenu items. The toString method will be invoked from other programs (such as the driver of Part 2) to display the menu.
Notes
1.1 For implementing the class Menu you may use either an appropriate data structure designed by you from scratch or the LinkedList data structure defined by JCF (Java Collection Framework).
1.2 If necessary, additionally methods may be defined for the class Menu. Give reasons for the new added methods.
The class Menu.java should compile without errors.
Part 2
Write a driver program MenuTest.java to test the Menu class. In the driver program, do the following tasks:
a) Read menu items from the input file Menu.txt and build a menu object which includes the specified items. Each file line contains a main menu item followed by its submenu items, all items being separated by the semicolon character. The main menu and its submenus should be built node by node with the values taken from the input file. After reading the file and building the menu, display the menu using the toString method.
Example of the content of the input file Menu.txt:
File;New;Open;Save;SaveAs;Close;
View;Color;Gray;Zoom;Ruler;Grid;
Process;Select;Move;Rotate;Scale;Delete;Group;
About;Release;Version;Contact;Description;
In the example above, File, View, Process and About are the main menu items. The main menu item File has New, Open, Save, SaveAs and Close as its submenu items.
b) Add new main menu items and their associated submenus before a main menu item specified by the user from the keyboard. Read the new main menu items and their submenus from the input file MenuAdd.txt. Using the toString method, display the menu.
c) Delete a main menu item specified by the user from the keyboard then display the menu using the toString method.
d) Add new main menu items and their associated submenus after a main menu item specified by the user from the keyboard. Read the main menu items and their submenus from the input file MenuAdd.txt. Using the toString method, display the menu.
The input file MenuAdd.txt contains one or more lines specifying the new main menu item(s) and their submenu items.
An example of the content of the input file MenuAdd.txt for adding two new menu items and their submenus is given below:
Layout;Margins;Orientation;Size;
Insert;Table;Picture;Shapes;Chart;
Notes
2.1 The input files Menu.txt and MenuAdd.txt will be created by the students using a simple text editor (such as Notepad).
2.2 Where appropriate, Part 2 tasks a – d should be accomplished by invoking the Menu class methods defined in Part 1.
Submission requirements
Submit the following before the due date listed in the Calendar:
1. Source files Menu.java and MenuTest.java and input files Menu.txt and MenuAdd.txt.
2. The solution description document <YourSecondName>_HW2 (.pdf or .doc / .docx) containing:
(2.1) assumptions, main design decisions, error handling, (2.2) test plan, test cases and two relevant screenshots, (2.3) lessons learned and (2.4) possible improvements. The size of the document file (including the screenshots) should be of two pages, single spaced, font size 12.
Part 1
Design and implement a class Menu which uses doubly linked lists as main data structures. A menu object consists of a set of main menu items, organized as a doubly linked list. Each main menu item has an associated submenu of items which is also organized as a doubly linked list (see an example of a Menu object in the attached file MenuExample.pdf).
The class Menu should define a default constructor which builds an empty menu and the following methods:
- addMainMenuItem, for adding a new main menu item with an empty submenu. The method should have the following signature:
public boolean addMainMenuItem(String newItem, String existingItem, int position)
The method works in the following way:
-if parameter existingItem is null, the newItem will be added at the end of the list;
-if the parameter existingItem is not null, the newItem will be added before the existingItem if parameter position is -1 and after the existinItem if parameter position is 1;
- deleteMainMenuItem, deletes the main menu item specified by name (supplied as method parameter);
- addSubMenuItem, adds a submenu item specified by name to a main menu item specified by name (both names should be supplied as method parameters);
- toString, traverses the linked lists data structures and generates the string representation of a menu object, organized on lines. Each line should include the main menu item followed by its submenu items. The items should be separated by a semicolon character. The string representation should also include as the last line, the number of main menu items and the total number of submenu items. The toString method will be invoked from other programs (such as the driver of Part 2) to display the menu.
Notes
1.1 For implementing the class Menu you may use either an appropriate data structure designed by you from scratch or the LinkedList data structure defined by JCF (Java Collection Framework).
1.2 If necessary, additionally methods may be defined for the class Menu. Give reasons for the new added methods.
The class Menu.java should compile without errors.
Part 2
Write a driver program MenuTest.java to test the Menu class. In the driver program, do the following tasks:
a) Read menu items from the input file Menu.txt and build a menu object which includes the specified items. Each file line contains a main menu item followed by its submenu items, all items being separated by the semicolon character. The main menu and its submenus should be built node by node with the values taken from the input file. After reading the file and building the menu, display the menu using the toString method.
Example of the content of the input file Menu.txt:
File;New;Open;Save;SaveAs;Close;
View;Color;Gray;Zoom;Ruler;Grid;
Process;Select;Move;Rotate;Scale;Delete;Group;
About;Release;Version;Contact;Description;
In the example above, File, View, Process and About are the main menu items. The main menu item File has New, Open, Save, SaveAs and Close as its submenu items.
b) Add new main menu items and their associated submenus before a main menu item specified by the user from the keyboard. Read the new main menu items and their submenus from the input file MenuAdd.txt. Using the toString method, display the menu.
c) Delete a main menu item specified by the user from the keyboard then display the menu using the toString method.
d) Add new main menu items and their associated submenus after a main menu item specified by the user from the keyboard. Read the main menu items and their submenus from the input file MenuAdd.txt. Using the toString method, display the menu.
The input file MenuAdd.txt contains one or more lines specifying the new main menu item(s) and their submenu items.
An example of the content of the input file MenuAdd.txt for adding two new menu items and their submenus is given below:
Layout;Margins;Orientation;Size;
Insert;Table;Picture;Shapes;Chart;
Notes
2.1 The input files Menu.txt and MenuAdd.txt will be created by the students using a simple text editor (such as Notepad).
2.2 Where appropriate, Part 2 tasks a – d should be accomplished by invoking the Menu class methods defined in Part 1.
Submission requirements
Submit the following before the due date listed in the Calendar:
1. Source files Menu.java and MenuTest.java and input files Menu.txt and MenuAdd.txt.
2. The solution description document <YourSecondName>_HW2 (.pdf or .doc / .docx) containing:
(2.1) assumptions, main design decisions, error handling, (2.2) test plan, test cases and two relevant screenshots, (2.3) lessons learned and (2.4) possible improvements. The size of the document file (including the screenshots) should be of two pages, single spaced, font size 12.
Explanation / Answer
Programming :
This is a Java Program to implement a Doubly Linked List. A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence.
import java.util.Scanner;
class Node
{
protected int data;
protected Node next, prev;
public Node()
{
next = null;
prev = null;
data = 0;
}
public Node(int d, Node n, Node p)
{
data = d;
next = n;
prev = p;
}
/* Function to set link to next node */
public void setLinkNext(Node n)
{
next = n;
}
public void setLinkPrev(Node p)
{
prev = p;
}
public Node getLinkNext()
{
return next;
}
public Node getLinkPrev()
{
return prev;
}
public void setData(int d)
{
data = d;
}
public int getData()
{
return data;
}
}
class linkedList
{
protected Node start;
protected Node end ;
public int size;
public linkedList()
{
start = null;
end = null;
size = 0;
}
public boolean isEmpty()
{
return start == null;
}
public int getSize()
{
return size;
}
public void insertAtStart(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
start = nptr;
}
size++;
}
public void insertAtEnd(int val)
{
Node nptr = new Node(val, null, null);
if(start == null)
{
start = nptr;
end = start;
}
else
{
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
end = nptr;
}
size++;
}
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null, null);
if (pos == 1)
{
insertAtStart(val);
return;
}
Node ptr = start;
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();
}
size++ ;
}
public void deleteAtPos(int pos)
{
if (pos == 1)
{
if (size == 1)
{
start = null;
end = null;
size = 0;
return;
}
start = start.getLinkNext();
start.setLinkPrev(null);
size--;
return ;
}
if (pos == size)
{
end = end.getLinkPrev();
end.setLinkNext(null);
size-- ;
}
Node ptr = start.getLinkNext();
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node p = ptr.getLinkPrev();
Node n = ptr.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size-- ;
return;
}
ptr = ptr.getLinkNext();
}
}
public void display()
{
System.out.print(" Doubly Linked List = ");
if (size == 0)
{
System.out.print("empty ");
return;
}
if (start.getLinkNext() == null)
{
System.out.println(start.getData() );
return;
}
Node ptr = start;
System.out.print(start.getData()+ " <-> ");
ptr = start.getLinkNext();
while (ptr.getLinkNext() != null)
{
System.out.print(ptr.getData()+ " <-> ");
ptr = ptr.getLinkNext();
}
System.out.print(ptr.getData()+ " ");
}
}
public class DoublyLinkedList
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
linkedList list = new linkedList();
System.out.println("Doubly Linked List Test ");
char ch;
do
{
System.out.println(" Doubly Linked List Operations ");
System.out.println("1. insert at begining");
System.out.println("2. insert at end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
list.insertAtStart( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to insert");
list.insertAtEnd( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to insert");
int num = scan.nextInt() ;
System.out.println("Enter position");
int pos = scan.nextInt() ;
if (pos < 1 || pos > list.getSize() )
System.out.println("Invalid position ");
else
list.insertAtPos(num, pos);
break;
case 4 :
System.out.println("Enter position");
int p = scan.nextInt() ;
if (p < 1 || p > list.getSize() )
System.out.println("Invalid position ");
else
list.deleteAtPos(p);
break;
case 5 :
System.out.println("Empty status = "+ list.isEmpty());
break;
case 6 :
System.out.println("Size = "+ list.getSize() +" ");
break;
default :
System.out.println("Wrong Entry ");
break;
}
list.display();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}