Question
The skeleton code on gitlab is the start of a program to schedule I/O requests to the head/arm of a hard disk. Each I/O request
The skeleton code on gitlab is the start of a program to schedule I/O requests to the head/arm of a hard disk. Each I/O request is for a specific track and sector. Your program must track all of the incoming requests and then, when told where the drive head is, return the n next or previous I/O requests. (This is the elevator method of I/O scheduling.) We will assume that requests are ordered first by track and then by sector, and that each request is unique. Tracks and sectors are both represented as non-negative numbers. The current implementation has a linked list that works poorly under common loads. Implement a binary search tree and the methods to support it. The skeleton code has an abstract LocationHolder class. This class has methods to build a data structure, find values in it, and find the next or previous location. It also has two important parts of a binary tree implemented: root and nil. There is one class already implemented:
// @Override tags tell the compiler that the method is implementing a method
// inherited from the abstract parent class
// TODO: document class
public class BST extends LocationHolder {
@Override
public DiskLocation find(DiskLocation d) {
// TODO: implement method
return null;
}
@Override
public DiskLocation next(DiskLocation d) {
// TODO: implement method
return null;
}
@Override
public DiskLocation prev(DiskLocation d) {
// TODO: implement method
return null;
}
@Override
public void insert(DiskLocation d) {
// TODO: implement method
}
@Override
public int height() {
// TODO: implement method
return -1;
}
}
import java.util.Scanner;
/* Provides next/previous/height info on (int, int) disk locations
*
* Wentworth Institute of Technology
* COMP 2350
* Lab Assignment 4
*
*/
public class LAB4 {
// read pairs of ints from scanner
// returns an array of DiskLocations
private static DiskLocation getLoc(Scanner s) {
int track, sector = 0;
track = s.nextInt();
if (s.hasNextInt())
sector = s.nextInt();
else {
System.err.println("Track/sector mismatch on input " + s.next());
System.exit(0);
}
if (track < 0 || sector < 0) {
System.err.println("Track and sector values must be non-negative");
System.exit(0);
}
DiskLocation d = new DiskLocation(track, sector);
return d;
}
// prints the next/prev n items after a specific location
// the location must be a valid location in l
private static void printIter(LocationHolder l, DiskLocation d, char direction, int number) {
DiskLocation temp = l.find(d);
for (int i = 0; i < number; i++) {
if (temp == LocationHolder.nil)
return;
if (direction == 'n')
temp = l.next(temp);
else if (direction == 'p')
temp = l.prev(temp);
if (temp.toString().length() == 0)
break;
System.out.println(temp.toString());
}
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
s.useDelimiter("(\\s|,)+"); //delimit with commas
LocationHolder l = new BST();
System.out.printf("Enter the data structure to use ([l]ist, [b]inary tree): ");
char algo = s.next().charAt(0);
switch (algo) {
case 'l':
l = new L();
break;
case 'b':
l = new BST();
break;
default:
System.out.println("Invalid data structure");
System.exit(0);
break;
}
System.out.printf("Enter non-negative track/sector pairs separated by commas. Terminate the list with one of the following options: ");
System.out.printf("Enter [n] to print the next values after a location (must be valid location). ");
System.out.printf("Enter [p] to print the previous values before a location (must be valid location). ");
System.out.printf("Enter [h] to print the height of the data structure ");
System.out.printf("Enter [q] to quit ");
System.out.printf("*** Example (inserts three locations and asks for the previous 2 before (2, 1): 0 1, 1 1, 2 1 p 2 1 2 *** ");
char nextAction = ',';
while (nextAction == ',') {
l.insert(getLoc(s));
if (!s.hasNextInt())
nextAction = s.next().charAt(0); // read in option
}
switch (nextAction) {
case 'n':
case 'p':
int track = -1;
int sector = -1;
int number = -1;
System.out.printf("Enter starting
if (s.hasNextInt())
track = s.nextInt();
if (s.hasNextInt())
sector = s.nextInt();
System.out.printf("Enter number of locations to seek: ");
if (s.hasNextInt())
number = s.nextInt();
else {
System.err.println("Couldn't read track/sector and number");
System.exit(0);
}
printIter(l, new DiskLocation(track, sector), nextAction, number);
break;
case 'h':
System.out.printf("height: %d ", l.height());
break;
case 'q':
System.exit(0);
default:
System.out.println("Invalid action");
System.exit(0);
break;
}
s.close();
}
}
/*
* A class that represents a binary tree node to hold disk location information
* The node has parent, left, and right references for binary trees
*/
public class DiskLocation {
private int track;
private int sector;
public DiskLocation left;
public DiskLocation right;
public DiskLocation parent;
public boolean isGreaterThan(DiskLocation that) {
if (this.track > that.track)
return true;
else if (this.track == that.track && this.sector > that.sector)
return true;
return false;
}
public boolean equals(Object that) {
if (that.getClass() != this.getClass())
return false;
DiskLocation d = (DiskLocation) that;
return (this.track == d.track && this.sector == d.sector);
}
public DiskLocation(int t, int s) {
track = t;
sector = s;
left = null;
right = null;
parent = null;
}
public String toString() {
if (track < 0)
return new String("");
return String.format("Track: %d, Sector: %d", track, sector);
}
}
/*
* An abstract class to insert and retrieve some info about disk locations
*/
public abstract class LocationHolder {
public static DiskLocation nil = new DiskLocation(-1, -1);
protected DiskLocation root;
public abstract DiskLocation find(DiskLocation d); // returns the object or nil
public abstract DiskLocation next(DiskLocation d); // returns the next object or nil
public abstract DiskLocation prev(DiskLocation d); // returns the previous object or nil
public abstract void insert(DiskLocation d); // inserts the object
public abstract int height(); // returns the largest tree height
public int size() {
return _size(root);
}
private int _size(DiskLocation D) {
if (D == null || D == nil)
return 0;
return 1 + _size(D.left) + _size(D.right);
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started