• A -2 indicates that all currently queued up requests should be processed before reading any more.

• After processing one request (i.e. the next track), the next request (if not eof or not -1) should be added to the waiting list. Then 3 more should be loading (with a -1 or eof stopping the loading)

Complete example (with one number per line and using a queue)

1. First add 2, 3, and 8 to the queue
2. Enter the loop
3. Add 5, 3 to the queue (stopping because a -1 is encountered)
4. Remove 2 from the queue (since was at 0, it is going in an increasing direction)
5. Add 4 to queue (now at 3, 8, 5, 3, 4)
6. Start at the beginning of the loop and add "three numbers" (only 3 because -1 encountered). Queue is now 3, 8, 5, 3, 4, 3
7. Remove 3 from queue (increasing so no change in direction). (Queue is now 8, 5, 3, 4, 3)
8. Read the -2 -> time to empty the queue (take no more requests until the queue is empty)
   1. Remove 8 . Still increasing
   2. Remove 5. Since going from 8 down to 5 -> now decreasing -> one change in direction
   3. Remove 3. Still decreasing
   4. Remove 4. Now increasing -> another change in direction
   5. Remove 3. Now decreasing -> third change in direction
9. Back to start of loop -> add three numbers to queue (5, 6, 10)
10. Remove 5 from queue -> Now increasing -> fourth change in direction
11. Add 15 to queue
12. Start of loop -> add "three numbers" (only 6 because of -1) to queue -> now 6, 10, 15, 6
13. Process 6 from queue -> still increasing
14. Read -2 -> time to empty queue
    1. Remove 10 from queue -> still increasing
    2. Remove 15 from queue -> still increasing
    3. Remove 6 from queue -> decreasing -> fifth change in direction
15. Start of loop -> add "three numbers" (only 5, 1 because of end of file)
16. Process 5 -> still decreasing
17. No change to queue because end of file (but queue not empty)
18. Start of loop -> add "three numbers" (none because at end of file)
19. Process 1 -> still decreasing
20. No change to queue because end of file
21. End loop (end of file and queue is empty)
22. There were five changes in direction

Hard drive simulator

Learning Objective(s)

1. Be able to code stack, queues, and priority queues
2. Create different types of testing data to different types of situations
3. Introduction to optimization of a hard drive

Overview of the Challenge

Specifics:

• You need to create your own data files (reading in integers, one per line).
• A -1 indicates that all currently queued up requests should be processed before reading any more.
• The drive should be initially loaded with three requests (less if -1 or eof is encountered) before processing any.
• After processing one request (i.e. the next track), the next request (if not eof or not -1) should be added to the waiting list.
• Output each track number as it is processed.
• When done, output the number of changes in directions made.
• Run with the same input for a stack and a queue
• You must use an array to implement the queue
• You must use a linked list to implement the stack.
• Your implementations of stacks and queues need to handle faults by correctly throwing exceptions.

Design components

• A quality set of testing data. This should include many different types of situations as possible and the results you expect
• Try to have a somewhat accurate estimate of how long you think it will take to code your design.
• An estimation of which data type is better under which situations.

Optional improvements

1. Add the use of priority queues. Have two queues. one that is "increasing" and one that is "decreasing" (hint: negative numbers). If the next track to be added is helpful in your current direction, add it to that priority queue, otherwise added to the second one. When you change directions swap around the priority queues.
2. Track when a track request went in (the sequence number) and when it came out. The difference is "how long it waited". Analyze the results based on the average and maximum wait in addition to the number of times it changes directions.
3. Have the file be specified at the command line