Module assignment: containers in practice

What you will build

This assignment brings the whole module together in one program. You will build a print queue manager. A print queue is a line of documents waiting to be printed. Each document belongs to a user and has a number of pages and a priority. A more urgent document must print before a less urgent one. A user can also cancel a waiting document, undo a recent submission, and ask for a summary of what is still waiting.

You will need every idea from the module. The priority order needs a heap, from the third lesson. Finding a document by its id needs a dict, from the fourth lesson. The undo history needs a stack, which is a list used at one end, from the second lesson. Cancelling a document from the middle of the heap needs a trick called lazy deletion, which the third lesson introduced. The summary of users needs sorted output, from the fifth lesson. The first lesson's rule applies too: pick the container by the operations you do most.

Treat this as a real program. Read the spec, build the parts one at a time, test each part, and only then put them together. The step-by-step path below shows how.

The spec

The program reads input from standard input. The first line holds a number n, which is how many commands follow. Each of the next n lines holds one command. The program prints one or more output lines for each command, in the order the commands arrive.

Every document gets an id, a whole number. The first document submitted gets id 1, the next gets id 2, and so on. Ids are never reused, even after a document prints or is cancelled.

The commands are:

• submit NAME PAGES PRIORITY adds a document. NAME is the user's name, a single word of lowercase letters. PAGES is a whole number greater than 0. PRIORITY is a whole number from 1 to 9, where a larger number is more urgent. The program prints queued ID, where ID is the new id.
• next removes and prints the document that prints next. That is the document with the highest priority. If two documents have the same priority, the one with the smaller id goes first. The program prints printing ID NAME PAGES. If nothing is waiting, it prints no jobs.
• cancel ID removes a waiting document with that id. If it removes one, it prints cancelled ID. If no waiting document has that id, it prints not waiting ID. A document that already printed, or that was already cancelled, is not waiting.
• undo reverses the most recent submission that is still waiting. Every submit pushes its id onto a history stack. An undo pops ids from the stack until it finds one whose document is still waiting. It removes that document and prints undid ID. An id popped while searching is gone for good, even if it was skipped. If the stack empties before a waiting document is found, the program prints nothing to undo.
• stats prints two lines. The first is waiting COUNT pages TOTAL, where COUNT is the number of waiting documents and TOTAL is the sum of their pages. The second is users NAME1 NAME2 ..., listing each distinct name among the waiting documents once, in alphabetical order, separated by single spaces. If nothing is waiting, the second line is users none.

Any other command word prints unknown command WORD, where WORD is the first word of the line. You may assume that the numbers in each command are valid, so you do not have to check them.

Sample inputs and expected outputs

Test your program on these three inputs before you submit. Each input is shown with the output it must produce. The output is exact, including the spacing.

Sample 1 covers submitting, printing, cancelling and undoing:

9
submit ana 12 2
submit ben 5 3
submit cy 8 2
next
cancel 3
undo
submit dev 4 3
undo
stats

queued 1
queued 2
queued 3
printing 2 ben 5
cancelled 3
undid 1
queued 4
undid 4
waiting 0 pages 0
users none

Study the undo line after cancel 3. The history stack holds ids 1, 2, 3, with 3 on top. Id 3 was cancelled, so it is skipped. Id 2 printed, so it is skipped. Id 1 is still waiting, so it is removed and reported. The ids 3 and 2 are gone from the history for good.

Sample 2 covers the stats summary and the priority rule:

6
submit mina 3 1
submit omar 7 5
submit mina 2 5
stats
next
stats

queued 1
queued 2
queued 3
waiting 3 pages 12
users mina omar
printing 2 omar 7
waiting 2 pages 5
users mina

Documents 2 and 3 both have priority 5. Document 2 has the smaller id, so it prints first. Notice that mina still appears after the print, because document 1 is waiting.

Sample 3 covers the empty and missing cases:

7
next
cancel 5
undo
submit zoe 1 1
cancel 1
cancel 1
stats

no jobs
not waiting 5
nothing to undo
queued 1
cancelled 1
not waiting 1
waiting 0 pages 0
users none

These three samples are not the whole test. Your program will also be run on larger inputs, with many more commands. Make sure it works for every case the spec describes, not only for these three.

Requirements checklist

Copy this checklist into your notes and tick each item when your program meets it. The rubric below uses the same items.

• Reads n, then reads exactly n command lines, one per line.
• Assigns ids starting at 1, and never reuses an id.
• submit prints queued ID and adds the document to the heap and the dict.
• The heap serves the highest priority first, and breaks ties by the smaller id.
• next prints printing ID NAME PAGES and removes the document from the waiting dict.
• next prints no jobs when nothing is waiting, and does not crash.
• cancel removes a waiting document from the dict, and the heap skips its entry later.
• cancel prints not waiting ID for a document that already printed, was cancelled, or never existed.
• undo pushes and pops ids on a history stack, skips documents that are no longer waiting, and removes the first waiting one it finds.
• undo prints nothing to undo when the history has no waiting document left.
• stats prints the count and the page total of the waiting documents.
• stats lists the distinct waiting users once each, alphabetically, or prints users none.
• Any unknown command prints unknown command WORD.
• All three samples produce exactly the expected output.

Grading rubric

Your grade depends on which items work and how cleanly the code is written. Read the three levels below to see what each one looks like in practice.

A 60 percent solution handles the basic flow. It reads the commands, assigns ids, and prints queued for each submission. It serves documents in priority order, so next and printing work. It handles no jobs. The other commands may be missing or partly wrong, but the program runs without crashing on sample 1 up to the next line.

An 80 percent solution meets every item on the checklist for submit, next, cancel, stats and unknown commands, and it passes samples 1 and 2 exactly. The undo command works in the simple case, where the most recent document is still waiting. It may fail when older ids have to be skipped. The code uses the right containers, but some parts repeat work, such as scanning the whole waiting dict on every next.

A 100 percent solution passes all three samples and every edge case in the spec. It skips non-waiting ids in undo and does not reuse ids. It removes a cancelled document by deleting it from the dict and skipping its heap entry later, not by rebuilding the heap. The tie-breaker is part of the heap entry, not a special case in the loop. The code is clear: each command is one elif branch or one small function, and the names say what the variables hold. A reader can explain each choice of container in one sentence.

Build it in four steps

The reference solution is long, so build it in four parts. Each part below is a complete program that you can run. Each one covers one feature of the spec. When you understand each part, the full solution is mostly putting the parts together.

Step 1: the priority order

The waiting documents must come out highest priority first, with ties broken by id. heapq is a min-heap, so the program stores the priority as a negative number. The number -3 is smaller than -2, so the document with priority 3 comes first. The id is the second item of each heap entry, so ties are broken by the smaller id automatically.

The output is:

2 ben priority 3
4 dev priority 3
1 ana priority 2
3 cy priority 2

Look at the tuple (-job.priority, job.id, job.user, job.pages). The first item is the negated priority, so the largest priority comes first. The second item is the id, which only matters when priorities are equal. The heap compares the items in order, and it stops at the first one that differs, so the user and pages are never compared. Read the tuple from left to right, and you see the spec's rule. If you wrote the priority without the minus sign, the lowest priority would come first, which is a common bug.

The @dataclass class Job holds the four facts about a document. The @dataclass line is a decorator, a line that changes the class below it. It writes the __init__ and __repr__ methods for you, so the printed form is Job(id=1, user='ana', pages=12, priority=2).

Step 2: cancelling without searching the heap

Cancelling a document can happen anywhere in the waiting line, so the program cannot simply pop the heap. The heap has no method to remove an arbitrary item. The standard fix is lazy deletion. The program removes the id from a dict of waiting documents, and it leaves the heap entry where it is. When that entry reaches the top of the heap, next checks the dict. If the id is missing, the entry is stale, so next throws it away and pops again.

The output is:

cancelled 2
not waiting 2
(1, 'ana')
(3, 'cy')
None

The first call to cancel removes id 2 from the dict and returns True. The second call finds nothing in the dict and returns False. The heap still holds the entry for id 2, because nothing removed it. When next_job runs, the entry for id 2 has the highest priority, so it reaches the top first. The check if job_id in waiting fails, so the function throws it away and pops again. The next entry is id 1, which is waiting, so it is returned. The last call finds the heap empty and returns None.

Lazy deletion costs O(1) per cancel, because it only touches the dict. Each stale entry is popped once, at O(log n), so the extra cost is paid once per cancel. The trade-off is covered after the reference solution.

Step 3: undo with a history stack

Undo needs to remember ids in the order they were submitted, and it needs to skip ids whose documents are no longer waiting. A list is the right structure, because the most recent submission is the first one to undo, and append and pop at the end are both O(1). The third building block keeps a set of waiting ids and a history list of submitted ids. Each undo pops ids until it finds one that is still waiting.

The output is:

undid 1
nothing to undo
set()

Trace the first undo. The history list holds ids 1, 2, 3 with 3 at the end, which is the top of the stack. The program pops 3, but 3 is not in the waiting set, so the if fails and the loop continues. It pops 2, which is also not waiting. It pops 1, which is waiting, so the program removes it and returns undid 1. The second undo finds the list empty and returns nothing to undo. Notice that the ids 3 and 2 are gone from the history for good, as the spec says.

Step 4: the summary with sorted users

The stats command needs two things: a total of the pages, and a list of users in alphabetical order with each name listed once. A set removes duplicates in one step, and sorted puts the names in alphabetical order, so the program does not need to check for repeats by hand. The fourth building block prints the summary for a dict with documents, and for an empty dict.

The output is:

waiting 3 pages 12
users mina omar
waiting 0 pages 0
users none

The set comprehension {user for user, _ in waiting.values()} holds mina once, even though two documents belong to that user. The sorted call puts the names in order. The empty case is handled by the conditional expression, so the program prints users none instead of a blank line.

Putting the parts together

With the four building blocks, the full program is a loop over the commands with one if or elif branch for each command word. The waiting documents live in a dict from id to document, which is the source of truth. The heap holds the order, and it can hold stale entries that the dict has already dropped. The history is a list used as a stack. The summary reads the dict and sorts the names.

Start with the loop and the submit branch, and check that sample 1 prints the first three queued lines. Then add next, and check that sample 2 prints the right document. Add cancel and the lazy-deletion helper next. Add undo after that, and test it with sample 1, because sample 1 is the one that needs skipping. Add stats last. After each step, run all three samples again. A bug found in one step is much easier to fix than a bug found in the whole program at the end.

Keep the code readable. Give each command its own branch or small function. Name the variables for what they hold, such as waiting and history, not a and lst.

Hints

Use these hints only after you have tried each step on your own. Each one is hidden until you open it.

Hint 1: reading the input. Read the first line with int(input()). Then read each command with input().split(). The first element is the command word, and the others are its arguments. Convert numbers with int(...) when you need them.

Hint 2: keeping ids and the waiting dict. Keep a next_id = 1 counter. Each submit uses it and then adds one. A dict from id to document tells you at once whether a document is still waiting. Delete the entry whenever a document leaves the waiting set, whether it printed, was cancelled, or was undone.

Hint 3: keeping the heap and the dict in step. The heap may hold entries whose ids are no longer in the dict. For next, pop from the heap and skip any entry whose id is not in the dict. For cancel and undo, check the dict first. If the id is there, delete it from the dict and leave the heap alone.

Hint 4: the undo loop. Use a while loop that runs while the history is not empty. Pop an id. If the dict contains it, undo that document and stop. If the loop ends without undoing anything, print nothing to undo. Popped ids are gone for good, even when they are skipped.

Hint 5: the stats line. Use the dict's values() to loop over the waiting documents. Add each page count to a total. Add each user to a set, then sort it. Print the count from len(waiting), so the count stays correct without a separate counter.

Reference solution

Try the assignment on your own before you open this section. The solution below passes all three samples. Compare it with your own version, look for any differences in behaviour, and test the edge cases yourself.

import heapq
 
 
def pop_next(heap, waiting):
    while heap:
        _neg_priority, job_id = heapq.heappop(heap)
        if job_id in waiting:
            return job_id
    return None
 
 
def main():
    n = int(input())
    heap = []
    waiting = {}
    history = []
    next_id = 1
    for _ in range(n):
        parts = input().split()
        cmd = parts[0]
        if cmd == "submit":
            name, pages, priority = parts[1], int(parts[2]), int(parts[3])
            job_id = next_id
            next_id += 1
            waiting[job_id] = (name, pages, priority)
            heapq.heappush(heap, (-priority, job_id))
            history.append(job_id)
            print(f"queued {job_id}")
        elif cmd == "next":
            job_id = pop_next(heap, waiting)
            if job_id is None:
                print("no jobs")
            else:
                name, pages, _ = waiting.pop(job_id)
                print(f"printing {job_id} {name} {pages}")
        elif cmd == "cancel":
            job_id = int(parts[1])
            if job_id in waiting:
                del waiting[job_id]
                print(f"cancelled {job_id}")
            else:
                print(f"not waiting {job_id}")
        elif cmd == "undo":
            found = None
            while history:
                job_id = history.pop()
                if job_id in waiting:
                    found = job_id
                    break
            if found is None:
                print("nothing to undo")
            else:
                del waiting[found]
                print(f"undid {found}")
        elif cmd == "stats":
            total = sum(pages for _, pages, _ in waiting.values())
            print(f"waiting {len(waiting)} pages {total}")
            users = sorted({user for user, _, _ in waiting.values()})
            print("users " + " ".join(users) if users else "users none")
        else:
            print(f"unknown command {cmd}")
 
 
main()

The reference solution is correct for all three samples and runs in the expected cost. The next command costs O(log n) for each heap pop, and each stale entry is popped at most once. The cancel command costs O(1). The undo command costs time proportional to the number of ids it pops. The stats command costs O(n) over the waiting documents. The trade-off is memory. A cancelled document leaves its entry in the heap until that entry reaches the top, so a long run of cancels that never reach the top keeps stale entries alive. A stricter solution could rebuild the heap when stale entries pass half of its size, which bounds the memory. Explain this trade-off in a short note if you choose either design.

Stretch goal

Once your program passes every sample, try one extension. Add a bump ID command that raises a waiting document's priority by 1, up to a maximum of 9, and prints bumped ID to P. A heap does not notice when a value changes, so the old entry still has the old priority. The fix uses lazy deletion again. Store the current priority in the dict, push a new heap entry with the new priority, and skip any heap entry whose priority no longer matches the dict. Explain in one sentence why the heap needs the new entry.

What this module covered

• A list is the default sequence. Reads by index are O(1), and inserts in the middle are O(n). A deque is better for work at both ends.
• A list used with append and pop works as a stack in O(1) per step.
• heapq is a min-heap on a list, with O(log n) heappush and heappop. Negate a value to get a max-heap, and put a tie-breaker second in the tuple.
• A dict and a set give O(1) average lookups. A sorted list with bisect answers order questions in O(log n).
• Lazy deletion removes an item from a heap by marking it stale and skipping it when it reaches the top.
• Loops over a list must not change the list, and loops over a dict must not change its size.
• sorted, set and dict views give clean summaries. Pick a container by the operations you do most, and by whether order matters.