Shortest seek time first algorithm using Comparator

Question

Working on a SSTF algorithm using java.util.Comparator
This is what i have so far:

private int nextHeadPosition;

public SSTF(int currentHeadPosition) {
    nextHeadPosition = currentHeadPosition;
}

@Override
public int compare(DiskRequest r1, DiskRequest r2) {         
    if (nextHeadPosition - r1.getTrackNumber()  < nextHeadPosition -  r2.getTrackNumber()) {
        nextHeadPosition = r1.getTrackNumber();
        return -1;
    } else if (nextHeadPosition - r1.getTrackNumber() > nextHeadPosition - r2.getTrackNumber()) {
         nextHeadPosition = r2.getTrackNumber();
        return 1;
    } else {
        return 0;
    }
}

with an initial head position of 50 it is producing this order:

[100, 99, 50, 45, 44, 1]

The output I am trying to produce:

[50, 45, 44, 1, 99, 100]

this might not be posible with comparator

edit

SSTF

for a queue of requests that have track numbers, the first request to be serviced will be the track that is closest to the current position of the head. Each subsequent request will be ordered by least distance from the position of the last request.

so for a queue with tracks [100, 99, 50, 45, 44, 1] and a current head position of 50, the first request will be 50. The next will be the track closest to 50, which is 45 in this case. lather rinse repeat.

Your expression `nextHeadPosition - rw.getTrackNumber()` makes no sense. If you want to compare two fields, you have to do them independently. — Peter Lawrey, Apr 26 '13 at 15:27
@Austin can you write the steps down? in which order did you compare the items? can you get the same expected output by hand by reversing the array? Peter made a good point about just comparing in a `compare()` call. What is this `nextHeadPosition` and where is it used? — Shark, Apr 26 '13 at 15:37

score 3 · Accepted Answer · answered Apr 26 '13 at 16:02

3

First, you want to compare the distance between the track and the head position, so you have to use the absolute value in your conditions.

if (Math.abs(nextHeadPosition - r1.getTrackNumber())  < Math.abs(nextHeadPosition -  r2.getTrackNumber()))

But your compare method modifies the object, which is not a good idea since you don't know how Collections.sort() (I guess that's what you're trying to use) will use it. You have to write your own sorting algorithm I think.

answered Apr 26 '13 at 16:02

WilQu

7,131
6
30
38

Thanks, I knew it was something small, its still giving an incorrect result of `[44, 45, 50, 99, 1, 100]` but it's closer. This is purely academic to see if it could be done with Comparator. no production code has been harmed in my shenanigans – Apr 26 '13 at 16:16

score 1 · Answer 2 · answered Apr 26 '13 at 16:06

problem line is

 if (nextHeadPosition - r1.getTrackNumber()  < nextHeadPosition -  r2.getTrackNumber()) {

nextHeadPosition =50

r1.getTrackNumber()=99

r2.getTrackNumber()=45

if((50-99) < (50-45)) translates to if(-44< 5)

Using Math.abs is one solution . Also if you show us code where you are using provided code... it will be better to help.

Shortest seek time first algorithm using Comparator

SSTF

2 Answers2

Linked