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:

L Implements a linked list data structure

For this assignment, you will implement the methods in the remaining class: BST.java as a binary search tree. For sources for this assignment, you should use the lecture slides and the book (chapter 12). I would recommend sticking closely to the pseudocode, and using the nil construct that the book suggests. (nil is implemented in LocationHolder for you already.)

This skeleton code has a lot of moving parts. There is an abstract LocationHolder class, which L and BST both inherit from. There is a supporting node class called DiskLocation.java that holds the location and all necessary node information. It also has a comparator method, isGreaterThan, that you should use. You should not modify any file besides BST.java. You can add as many private supporting methods as you need.

// @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;

}

}

/*

* 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);

}

}

/*

* A doubly linked list implementation to hold DiskLocations

* The list is sorted on inserts so that next and prev are fast

*

* The class uses DiskLocation's right/parent for next/prev in the list

*/

public class L extends LocationHolder {

@Override

public DiskLocation find(DiskLocation d) {

return _find(d, root);

}

private DiskLocation _find(DiskLocation d, DiskLocation curr) {

if (curr == nil)

return nil;

else if (d.equals(curr))

return curr;

else

return _find(d, curr.right);

}

@Override

public DiskLocation next(DiskLocation d) {

return d.right;

}

@Override

public DiskLocation prev(DiskLocation d) {

return d.parent;

}

@Override

public void insert(DiskLocation d) {

if (root == null) { //empty list

root = d;

d.parent = nil;

d.right = nil;

return;

}

DiskLocation temp = root;

DiskLocation prev = nil;

while (!temp.isGreaterThan(d) && !temp.equals(nil)) {

prev = temp;

temp = temp.right;

}

d.parent = prev;

d.right = temp;

if (temp != nil)

temp.parent = d;

if (prev != nil)

prev.right = d;

else

root = d;

}

@Override

public int height() {

int h = 0;

DiskLocation d = root;

while (d != nil) {

h++;

d = d.right;

}

return h;

}

}

/* Provides next/previous/height info on (int, int) disk locations

*

*/

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();

}

}

/*

* 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);

}

}