For the following questions you will implement the data stru

For the following questions, you will implement the data structure to store information used by a local car dealer. Each car has some information and stored in a text files called cars: Write a main program for all questions to let the user enter, delete, search for information, and print current cars stored in the data structure. Cars formatted so car records separated by a blank line. Each record contains (in order, each in a single line): Make (manufacturer). Model, Year, Mileage, Price. Implement a double linked-list to store cars data. Write a double linked-list class including search, delete, append (to the head and tail), and remove (from the head and tail). Implement a FIFO queue of car data using the double linked-list. You can use the double linked list you wrote in Q1. Implement a max-heap of cars data that can extract the car with the highest price. Write a max-heap class including heapify, build heap, extract, and insertion. Implement a binary search tree of car data. Write a BST class including search, insertion, and deletion.

Solution

Cars.java

package pacages;

public class Cars {

   String make;
   String model;
   int year;
   double mileage;
   double price;
  
   // Setters and getters for the Cars member variables
   public String getMake() {
       return make;
   }
   public void setMake(String make) {
       this.make = make;
   }
   public String getModel() {
       return model;
   }
   public void setModel(String model) {
       this.model = model;
   }
   public int getYear() {
       return year;
   }
   public void setYear(int year) {
       this.year = year;
   }
   public double getMileage() {
       return mileage;
   }
   public void setMileage(double mileage) {
       this.mileage = mileage;
   }
   public double getPrice() {
       return price;
   }
   public void setPrice(double price) {
       this.price = price;
   }
  
   public String toString()
   {
       return \"Make: \"+getMake()+ \" Model: \"+getModel()+ \" Year: \"+getYear() + \" Mileage: \"+getMileage() + \" Price: \"+getPrice();
   }
  
}

DoublyLinkedList.java

package pacages;

class Node
{
protected Cars data;
protected Node next, prev;

/* Constructor */
public Node()
{
next = null;
prev = null;
data = null;
}
/* Constructor */
public Node(Cars 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;
}
/* Function to set link to previous node */
public void setLinkPrev(Node p)
{
prev = p;
}
/* Funtion to get link to next node */
public Node getLinkNext()
{
return next;
}
/* Function to get link to previous node */
public Node getLinkPrev()
{
return prev;
}
/* Function to set data to node */
public void setData(Cars d)
{
data = d;
}
/* Function to get data from node */
public Cars getData()
{
return data;
}
  
}

/* Class linkedList */
public class DoublyLinkedList
{
protected Node start;
protected Node end ;
public int size;

/* Constructor */
public DoublyLinkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert element at begining */
public void appendAtHead(Cars 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++;
}
/* Function to insert element at end */
public void appendAtTail(Cars 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++;
}
  
/* Function to remove element at end */
public void deleteAtTail()
{
   end = end.getLinkPrev();
end.setLinkNext(null);
size-- ;
}
  
public void deleteAtHead()
{
   start = start.getLinkNext();
start.setLinkPrev(null);
size--;
}

  
/* Function to display the list */
public void display()
{
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()+ \"\ \ \");
}
}


MaxHeap.java

package pacages;

public class MaxHeap
{
private Cars[] Heap;
private int size;
private int maxsize;

private static final int FRONT = 1;

public MaxHeap(int maxsize)
{
this.maxsize = maxsize;
this.size = 0;
Heap = new Cars[this.maxsize + 1];
Heap[0] = null;
}

private int parent(int pos)
{
return pos / 2;
}

private int leftChild(int pos)
{
return (2 * pos);
}

private int rightChild(int pos)
{
return (2 * pos) + 1;
}

private boolean isLeaf(int pos)
{
if (pos >= (size / 2) && pos <= size)
{
return true;
}
return false;
}

private void swap(int fpos,int spos)
{
Cars tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}

private void maxHeapify(int pos)
{
if (!isLeaf(pos))
{
if ( Heap[pos].getPrice() < Heap[leftChild(pos)].getPrice() || Heap[pos].getPrice() < Heap[rightChild(pos)].getPrice())
{
if (Heap[leftChild(pos)].getPrice() > Heap[rightChild(pos)].getPrice())
{
swap(pos, leftChild(pos));
maxHeapify(leftChild(pos));
}else
{
swap(pos, rightChild(pos));
maxHeapify(rightChild(pos));
}
}
}
}

public void insertion(Cars car)
{
Heap[++size] = car;
int current = size-1;
if(size>2)
{
   while(Heap[current].getPrice() > Heap[parent(current)].getPrice())
   {
   swap(current,parent(current));
   current = parent(current);
   }  
}
  
}

  
public void maxHeap()
{
for (int pos = (size / 2); pos >= 1; pos--)
{
maxHeapify(pos);
}
}

public Cars extraction()
{
Cars popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
maxHeapify(FRONT);
return popped;
}
  

public void print()
{
for (int i = 1; i <= size / 2; i++ )
{
System.out.print(\" PARENT : \" + Heap[i] + \" LEFT CHILD : \" + Heap[2*i]
+ \" RIGHT CHILD :\" + Heap[2 * i + 1]);
System.out.println();
}
}
}

BST.java

package pacages;

public class BST {
   Node root;
     
// Constructor
BST() {
root = null;
}
   public Node search(Node root, Cars car)
   {
   // Base Cases: root is null or key is present at root
   if (root==null || root.data.getMake().equals(car.getMake()))
   {
       if(root.data.getModel().equals(car.getModel()))
       {
           if(root.data.getYear() == car.getYear())
           {
               if(root.data.getMileage() == car.getMileage())
               {
                   if(root.data.getPrice() == car.getPrice())
                   {
                       return root;
                   }
               }
           }
       }
   }
     
   // val is greater than root\'s key
   if (root.data.getPrice() > car.getPrice())
   return search(root.prev, car);
     
   // val is less than root\'s key
   return search(root.next, car);
   }
  
   Node insert(Node root, Cars car) {
         
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(car, null, null);
return root;
}

/* Otherwise, recur down the tree */
if (car.getPrice() < root.data.getPrice())
root.prev = insert(root.prev, car);
else if (car.getPrice() > root.data.getPrice())
root.next = insert(root.next, car);

/* return the (unchanged) node pointer */
return root;
}
}

MyClass.java

package pacages;

import java.util.Scanner;

public class MyClass {
   static DoublyLinkedList list = new DoublyLinkedList();
   static MaxHeap heap = new MaxHeap(100);
   static Scanner sc = new Scanner(System.in);
  
   public static void main(String args[])
   {
       String choice = \"y\";
       int menuChoice = 0;
       do
       {
           System.out.println(\"MENU\ 1. Enter car Details\ 2. Delete Last car Data\ 3. Delete first Car data\ 4. Display all Cars\ 5. Exit\");
           menuChoice = sc.nextInt();
           switch(menuChoice)
           {
           case 1: getCarDetails();
           break;
           case 2: list.deleteAtTail();
           break;
           case 3: list.deleteAtHead();
           heap.extraction();
           break;
           case 4: list.display();
           }
           System.out.println(\"Do you wish to continue? y or n\");
           choice = sc.next();
          
       }while(choice.equals(\"y\") || choice.equals(\"Y\"));
         
   }
  
   public static void getCarDetails(){
       Cars car = new Cars();
      
       System.out.println(\"Enter Make: \");
       car.setMake(sc.next());
       System.out.println(\"Enter Model: \");
       car.setModel(sc.next());
       System.out.println(\"Enter Year: \");
       car.setYear(sc.nextInt());
       System.out.println(\"Enter Mileage: \");
       car.setMileage(sc.nextDouble());
       System.out.println(\"Enter Price: \");
       car.setPrice(sc.nextDouble());
       list.appendAtTail(car);
       heap.insertion(car);
   }
}

OUTPUT:

MENU
1. Enter car Details
2. Delete Last car Data
3. Delete first Car data
4. Display all Cars
5. Exit
1
Enter Make:
Hyundai
Enter Model:
324rtf
Enter Year:
2011
Enter Mileage:
30.0
Enter Price:
945677
Do you wish to continue? y or n
y
MENU
1. Enter car Details
2. Delete Last car Data
3. Delete first Car data
4. Display all Cars
5. Exit
1
Enter Make:
Toyota
Enter Model:
375jdg
Enter Year:
2005
Enter Mileage:
25.0
Enter Price:
673522
Do you wish to continue? y or n
y
MENU
1. Enter car Details
2. Delete Last car Data
3. Delete first Car data
4. Display all Cars
5. Exit
4
Make: Hyundai Model: 324rtf Year: 2011 Mileage: 30.0 Price: 945677.0
Make: Toyota Model: 375jdg Year: 2005 Mileage: 25.0 Price: 673522.0

Do you wish to continue? y or n
y
MENU
1. Enter car Details
2. Delete Last car Data
3. Delete first Car data
4. Display all Cars
5. Exit
2
Do you wish to continue? y or n
y
MENU
1. Enter car Details
2. Delete Last car Data
3. Delete first Car data
4. Display all Cars
5. Exit
4
Make: Hyundai Model: 324rtf Year: 2011 Mileage: 30.0 Price: 945677.0
Do you wish to continue? y or n
n