Circular Linked Data Structure

Not all linked data structures are linear - it is often helpful to have nodes that link to multiple nodes (as in Trees and Graphs), or nodes that link together in other non-linear ways.

In this assignment, we build a circular linked data structure - a list that loops around on itself. This is useful when we need to repeatedly loop through a series of nodes. For instance, an operating system may keep such a circular list of tasks that need CPU time, and continually cycle through the list of tasks.

We will implement two classes:

• Task - a task for the operating system to complete. Each task has the following attributes, in addition to any "linking" attributes (like next or prev) you decide are necessary:
  • id - a unique identifier (an int)
  • cycles_left - the amount of cycles necessary to complete this task
  • reduce_cycles () - reduces cycles_left by the appropriate amount
• TaskQueue - A circular data structure with attributes:
  • current - the current task to process
  • cycles_per_task - the amount of cycles to dedicate to each task before moving to the next one. This has a default value of 1, but should be a parameter a user can specify when creating a TaskQueue.
  • add_task() - adds a task immediately before current. This means it will be the last task to be processed. Should be O(1).
  • remove_task() - removes the task with a given id. O(n) is fine, but you can get this to O(1) if you're clever.
  • len - the number of tasks in the TaskQueue. O(1).
  • is_empty() returns True if the TaskQueue is empty; false otherwise. O(1).
  • execute_tasks() - executes tasks cyclically until all tasks are exhuasted. Each task will run for cycles_per_task or the amount of clock cycles it has remaining, whichever is lower. This should print out information whenever a task is finished (see examples for string formatting). At the end, return the total number of cycles it took to execute all tasks. You do not need to test the print outs but should test the return value.

Special Behavior

• If a task is reduced to 0 cycles by reduce_cycles, then the TaskQueue should remove that task from the queue and print out info - the task id and the total numer of clock cycles executed before it finished (see Examples below for formatting)
• If a user tries to remove a task with an id that is not in the TaskQueue, you should raise a RuntimeError with an appropriate string.
  • This check should run in O(1). Think what data structure can you use that allows O(1) membership testing?
  • Test this behavior. (The error, not the running time)

Tests

You should have a file TestTaskQueue.py that includes unit tests for all functionality in your class TaskQueue. Use the unittest module.

As a reminder for testing:

• test the public interface of your class. You do not need to test any private methods or attributes you create.
• Exceptions are part of the public interface: test that your code raises the correct Errors in the correct circumstances.
• Boolean functions like is_empty should have tests for True and False scenarios (self.assertTrue() and self.assertFalse())

Examples

Any examples below are intended to be illustrative, not exhaustive. Your code may have bugs even if it behaves as below. Write your own tests, and think carefully about edge cases.

>>> from TaskQueue import *
>>> t1 = Task(id=1, cycles_left=3)
>>> t2 = Task(id=2, cycles_left=1)
>>> t3 = Task(id=3, cycles_left=5)
>>> tasks = [t1, t2, t3]
>>> TQ TaskQueue (cycles_per_task=1)
>>> for task in tasks:
… TQ.add_task (task)
>>> TQ.remove_task (17) # should raise an error
… # info truncated to not give away the answer
RuntimeError: id 17 not in TaskQueue
>>> t_total = TQ.execute_tasks() # note that this prints info *and* returns a time
Finished task 2 after 2 clock cycles
Finished task 1 after 6 clock cycles
Finished task 3 after 9 clock cycles
>>> print (f"cycles = {t_toal}")
cycles = 9

External Modules

Do not use any imported modules (math, collections, ...) when implementing functionality. It is okay to use imported modules for testing; e.g. the random and string modules for generating random items.

It is okay to import modules you write yourself for this assignment; e.g. any data structures you write yourself.

Class Diagram

Figure 1: Class diagram for a Task. see image.

Figure 2: Class diagram for a TaskQueue. We use red solid arrows for next and blue dotted arrows for prev pointers. Note that TaskQueue.current is expected to cycle through Tasks as the program runs. Note - this class uses next and prev pointers. Decide for yourself if you need both. see image.