graduate_code/solutions/network.py

"""G07: offline prefix lookup and a one-server finite-capacity FIFO trace."""
from collections import deque
import ipaddress
import math


def route(address, routes):
    address = ipaddress.ip_address(address)
    parsed, seen = [], set()
    for prefix, destination in routes:
        network = ipaddress.ip_network(prefix,strict=True)
        if network in seen:
            raise ValueError("duplicate prefix")
        seen.add(network)
        if network.version != address.version:
            raise ValueError("mixed address families are outside this lab contract")
        parsed.append((network,destination))
    matches = [(n,d) for n,d in parsed if address in n]
    if not matches:
        return None
    network,destination = max(matches,key=lambda item:item[0].prefixlen)
    return str(network),destination


def queue_trace(arrivals, service=1., capacity=3):
    arrivals = list(arrivals)
    if len(arrivals) > 100000 or any(not math.isfinite(t) or t < 0 for t in arrivals):
        raise ValueError("bounded finite nonnegative arrival times required")
    if any(b < a for a,b in zip(arrivals,arrivals[1:])):
        raise ValueError("arrivals must be nondecreasing")
    if not math.isfinite(service) or service <= 0:
        raise ValueError("positive finite service duration required")
    if type(capacity) is not int or not 1 <= capacity <= 100000:
        raise ValueError("capacity counts waiting plus in-service jobs")
    finishes, records = deque(), []
    for job,arrival in enumerate(arrivals):
        while finishes and finishes[0] <= arrival:
            finishes.popleft()  # completions precede arrivals at the same time
        if len(finishes) >= capacity:
            records.append({"job":job,"arrival":arrival,"accepted":False,
                            "start":None,"finish":None})
            continue
        start = max(arrival,finishes[-1] if finishes else arrival)
        finish = start+service
        if not math.isfinite(finish) or finish <= start:
            raise ValueError("service endpoint overflow or no represented progress")
        finishes.append(finish)
        records.append({"job":job,"arrival":arrival,"accepted":True,
                        "start":start,"finish":finish})
    return records


if __name__ == "__main__":
    print(route("10.2.1.8",[("0.0.0.0/0","default"),("10.2.0.0/16","local")]))
    print(queue_trace([0,0,0,4]))