Problem Statements Based on the simulation of CPU execution queue from the Progr

Question

Problem Statements

Based on the simulation of CPU execution queue from the Programming Assignment I, a CPU process might have waiting time in the queue based on the priority code.

For this programming assignment, you are a software engineer and are asked to develop a simulation software application for CPU to dynamically keep track of the process scheduling according to the sorted priority codes in the waiting queue. A process with a larger priority code will pre-empt others even if they have been waiting longer in the process queue.

Programming Requirements

The CPU process scheduling simulation software application MUST be written in Java and is required to use two separate approaches, Binary Search Tree (for sorting) and Hash Tables (for searching), which pseudo codes are specified in textbook. ( You MUST use the pseudo codes provided in textbook to write your Java codes. Any other codes will be treated as failing requirements and will receive 0 points.)

The CPU process waiting list always contains 20 processes with name of a process and a priority code. Each process will be randomly assigned a distinct priority code.

Your simulation software application MUST at least contains the following functions:

(3.1) Process Binary Search Tress (BST):

Build up a Process BST. (MUST follow BST properties specified in textbook and ppt slides. Your own tree structure will not be accepted.)

Insert a process to the BST based on its priority code.

Delete a process from the BST.

Make a sorted list of processes according to the priority codes from the BST.

(3.2) Process Hash Tables:

Create a 11-slots separate chaining Hash Table for the 20 processes.

Insert a process to the chaining Hash Table.

Search a process's name by entering a priority code.

Delete a process from the chaining Hash Table.

Make a list of processes in the hash table.

Each java file/class/subroutine/function call must contain a header comment in the beginning of it. (Points will be taking off if no comments.)

Explanation / Answer

Answer::

import java.util.Scanner;

class LinkedHashEntry
{
String key;
int value;
LinkedHashEntry next;

LinkedHashEntry(String key, int value)
{
this.key = key;
this.value = value;
this.next = null;
}
}

class HashTable
{
private int TABLE_SIZE;
private int size;
private LinkedHashEntry[] table;

public HashTable(int ts)
{
size = 0;
TABLE_SIZE = ts;
table = new LinkedHashEntry[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = null;
}
public int getSize()
{
return size;
}
public void makeEmpty()
{
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = null;
}
public int get(String key)
{
int hash = (myhash( key ) % TABLE_SIZE);
if (table[hash] == null)
return -1;
else
{
LinkedHashEntry entry = table[hash];
while (entry != null && !entry.key.equals(key))
entry = entry.next;
if (entry == null)
return -1;
else
return entry.value;
}
}
public void insert(String key, int value)
{
int hash = (myhash( key ) % TABLE_SIZE);
if (table[hash] == null)
table[hash] = new LinkedHashEntry(key, value);
else
{
LinkedHashEntry entry = table[hash];
while (entry.next != null && !entry.key.equals(key))
entry = entry.next;
if (entry.key.equals(key))
entry.value = value;
else
entry.next = new LinkedHashEntry(key, value);
}
size++;
}

public void remove(String key)
{
int hash = (myhash( key ) % TABLE_SIZE);
if (table[hash] != null)
{
LinkedHashEntry prevEntry = null;
LinkedHashEntry entry = table[hash];
while (entry.next != null && !entry.key.equals(key))
{
prevEntry = entry;
entry = entry.next;
}
if (entry.key.equals(key))
{
if (prevEntry == null)
table[hash] = entry.next;
else
prevEntry.next = entry.next;
size--;
}
}
}
private int myhash(String x )
{
int hashVal = x.hashCode( );
hashVal %= TABLE_SIZE;
if (hashVal < 0)
hashVal += TABLE_SIZE;
return hashVal;
}
/* Function to print hash table */
public void printHashTable()
{
for (int i = 0; i < TABLE_SIZE; i++)
{
System.out.print(" Bucket "+ (i + 1) +" : ");
LinkedHashEntry entry = table[i];
while (entry != null)
{
System.out.print(entry.value +" ");
entry = entry.next;
}   
}
}
}

public class HashTablesChainingListHeadsTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Hash Table Test ");
System.out.println("Enter size");
HashTable ht = new HashTable(scan.nextInt() );

char ch;
do   
{
System.out.println("1. insert ");
System.out.println("2. remove");
System.out.println("3. get");   
System.out.println("4. clear");
System.out.println("5. size");

int choice = scan.nextInt();   
switch (choice)
{
case 1 :
System.out.println("Enter key and value");
ht.insert(scan.next(), scan.nextInt() );
break;   
case 2 :
System.out.println("Enter key");
ht.remove( scan.next() );
break;   
case 3 :
System.out.println("Enter key");
System.out.println("Value = "+ ht.get( scan.next() ));
break;
case 4 :
ht.makeEmpty();
System.out.println("Hash Table Cleared ");
break;
case 5 :
System.out.println("Size = "+ ht.getSize() );
break;
default :
System.out.println("Wrong Entry ");
break;
}
ht.printHashTable();  

System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);   
} while (ch == 'Y'|| ch == 'y');  
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.