Practical 10: the Combined Application

"""A library issue desk built from five data structures.

Each structure is here because of the operation named in its docstring, which is
what MU's Course Objective 8 asks for: choose, and justify the choice.
"""

from collections import deque


# --------------------------------------------------------------------------
# 1. the CATALOGUE: a hash table, because a book is looked up by its exact
#    accession number far more often than anything else happens.
# --------------------------------------------------------------------------
def accession_hash(key, base=31):
    """A polynomial hash, written out so bucket numbers are reproducible."""
    total = 0
    for character in str(key):
        total = total * base + ord(character)
    return total


class Catalogue:
    """Hash table with separate chaining. Lookup by accession number, O(1)."""

    def __init__(self, buckets=11):
        self.buckets = [[] for _ in range(buckets)]
        self.count = 0

    def _index(self, key):
        return accession_hash(key) % len(self.buckets)

    def add(self, accession, title, author):
        chain = self.buckets[self._index(accession)]
        for position, (existing, _) in enumerate(chain):
            if existing == accession:
                chain[position] = (accession, (title, author))
                return False
        chain.append((accession, (title, author)))
        self.count += 1
        return True

    def find(self, accession):
        """(title, author) or None. Searches one bucket's chain only."""
        for existing, value in self.buckets[self._index(accession)]:
            if existing == accession:
                return value
        return None

    def __len__(self):
        return self.count

    def all_items(self):
        for chain in self.buckets:
            for accession, value in chain:
                yield accession, value

    def chain_lengths(self):
        return [len(chain) for chain in self.buckets]


# --------------------------------------------------------------------------
# 2. the TITLE INDEX: a binary search tree, because the catalogue has to be
#    listed in title order and an in-order walk gives that for nothing.
# --------------------------------------------------------------------------
class TitleNode:
    def __init__(self, title, accession):
        self.title = title
        self.accessions = [accession]
        self.left = None
        self.right = None


class TitleIndex:
    """BST keyed on title. in_order() is the sorted catalogue, free."""

    def __init__(self):
        self.root = None
        self.count = 0

    def add(self, title, accession):
        if self.root is None:
            self.root = TitleNode(title, accession)
            self.count += 1
            return
        here = self.root
        while True:
            if title == here.title:
                here.accessions.append(accession)
                return
            if title < here.title:
                if here.left is None:
                    here.left = TitleNode(title, accession)
                    self.count += 1
                    return
                here = here.left
            else:
                if here.right is None:
                    here.right = TitleNode(title, accession)
                    self.count += 1
                    return
                here = here.right

    def find(self, title):
        """(accessions, comparisons). O(log n) when the tree is balanced."""
        here = self.root
        comparisons = 0
        while here is not None:
            comparisons += 1
            if title == here.title:
                return here.accessions, comparisons
            here = here.left if title < here.title else here.right
        return None, comparisons

    def in_order(self):
        """Every title in order, which is the whole point of using a tree."""
        out = []

        def walk(node):
            if node is not None:
                walk(node.left)
                out.append((node.title, node.accessions))
                walk(node.right)

        walk(self.root)
        return out

    def height(self):
        def deepest(node):
            return -1 if node is None else 1 + max(deepest(node.left),
                                                   deepest(node.right))

        return deepest(self.root)


# --------------------------------------------------------------------------
# 3. RESERVATIONS: a queue per book, because a waiting list is fair only if
#    it is first come, first served.
# --------------------------------------------------------------------------
class Reservations:
    """A FIFO queue per accession number. deque, so both ends are O(1)."""

    def __init__(self):
        self.queues = {}

    def reserve(self, accession, borrower):
        queue = self.queues.setdefault(accession, deque())
        if borrower in queue:
            return -1
        queue.append(borrower)
        return len(queue)

    def next_in_line(self, accession):
        queue = self.queues.get(accession)
        if not queue:
            return None
        return queue.popleft()

    def waiting(self, accession):
        return list(self.queues.get(accession, ()))


# --------------------------------------------------------------------------
# 4. UNDO: a stack, because the most recent action is the one to undo.
# --------------------------------------------------------------------------
class UndoStack:
    """LIFO, over a fixed array, so it can overflow like a real one."""

    def __init__(self, capacity=20):
        self.slots = [None] * capacity
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def push(self, action):
        if self.top == len(self.slots) - 1:
            # the oldest action is dropped rather than refusing the newest
            self.slots.pop(0)
            self.slots.append(None)
            self.top -= 1
        self.top += 1
        self.slots[self.top] = action

    def pop(self):
        if self.is_empty():
            raise IndexError("nothing left to undo")
        action = self.slots[self.top]
        self.slots[self.top] = None
        self.top -= 1
        return action

    def peek(self):
        if self.is_empty():
            return None
        return self.slots[self.top]

    def __len__(self):
        return self.top + 1


# --------------------------------------------------------------------------
# 5. BORROWER GRAPH: two borrowers are joined when they have borrowed the same
#    book. Nothing linear can hold a relation between any two things.
# --------------------------------------------------------------------------
class BorrowerGraph:
    """Undirected graph, adjacency list. Used for 'who else read this'."""

    def __init__(self):
        self.neighbours = {}
        self.borrowed = {}

    def record(self, borrower, accession):
        self.neighbours.setdefault(borrower, set())
        others = self.borrowed.setdefault(accession, set())
        for other in others:
            if other != borrower:
                self.neighbours[borrower].add(other)
                self.neighbours.setdefault(other, set()).add(borrower)
        others.add(borrower)

    def also_borrowed_by(self, borrower):
        return sorted(self.neighbours.get(borrower, ()))

    def suggestions(self, borrower, catalogue):
        """Books read by people who read what this borrower read. BFS, depth 1."""
        mine = {a for a, who in self.borrowed.items() if borrower in who}
        out = {}
        for neighbour in self.neighbours.get(borrower, ()):
            for accession, who in self.borrowed.items():
                if neighbour in who and accession not in mine:
                    found = catalogue.find(accession)
                    if found:
                        out.setdefault(found[0], set()).add(neighbour)
        return {title: sorted(who) for title, who in sorted(out.items())}

    def connected_group(self, start):
        """Everyone reachable from a borrower. BFS with a seen set."""
        if start not in self.neighbours:
            return []
        seen = {start}
        order = []
        waiting = deque([start])
        while waiting:
            here = waiting.popleft()
            order.append(here)
            for neighbour in sorted(self.neighbours[here]):
                if neighbour not in seen:
                    seen.add(neighbour)
                    waiting.append(neighbour)
        return order


# --------------------------------------------------------------------------
# the DESK, which ties them together
# --------------------------------------------------------------------------
class IssueDesk:
    def __init__(self):
        self.catalogue = Catalogue()
        self.titles = TitleIndex()
        self.reservations = Reservations()
        self.undo = UndoStack()
        self.graph = BorrowerGraph()
        self.on_loan = {}
        self.borrow_count = {}

    def add_book(self, accession, title, author):
        if self.catalogue.add(accession, title, author):
            self.titles.add(title, accession)
            self.borrow_count.setdefault(accession, 0)
            return f"added {accession} {title!r}"
        return f"{accession} was already in the catalogue, details updated"

    def issue(self, accession, borrower):
        book = self.catalogue.find(accession)
        if book is None:
            return f"no such accession number {accession}"
        if accession in self.on_loan:
            place = self.reservations.reserve(accession, borrower)
            if place == -1:
                return f"{borrower} is already waiting for {book[0]!r}"
            return (f"{book[0]!r} is out with {self.on_loan[accession]}; "
                    f"{borrower} is number {place} in the queue")
        self.on_loan[accession] = borrower
        self.borrow_count[accession] += 1
        self.graph.record(borrower, accession)
        self.undo.push(("issue", accession, borrower))
        return f"issued {book[0]!r} to {borrower}"

    def give_back(self, accession):
        if accession not in self.on_loan:
            return f"{accession} is not on loan"
        was = self.on_loan.pop(accession)
        self.undo.push(("return", accession, was))
        nxt = self.reservations.next_in_line(accession)
        title = self.catalogue.find(accession)[0]
        if nxt is None:
            return f"{title!r} returned by {was}, back on the shelf"
        self.on_loan[accession] = nxt
        self.borrow_count[accession] += 1
        self.graph.record(nxt, accession)
        return (f"{title!r} returned by {was} and issued straight to {nxt}, "
                f"who was first in the queue")

    def undo_last(self):
        if self.undo.is_empty():
            return "nothing left to undo"
        what, accession, who = self.undo.pop()
        title = self.catalogue.find(accession)[0]
        if what == "issue":
            self.on_loan.pop(accession, None)
            self.borrow_count[accession] -= 1
            return f"undid the issue of {title!r} to {who}"
        self.on_loan[accession] = who
        return f"undid the return of {title!r}, it is with {who} again"

    def sorted_catalogue(self):
        return self.titles.in_order()

    def most_borrowed(self, how_many=3):
        """A SORTED ARRAY, built once and then read. Ties broken by title."""
        rows = []
        for accession, count in self.borrow_count.items():
            title = self.catalogue.find(accession)[0]
            rows.append((count, title, accession))
        rows.sort(key=lambda row: (-row[0], row[1]))
        return rows[:how_many]