"""The naive layout: one contiguous slab of slots per request, sized for the maximum length."""


class ContiguousPool:
    """A row of `n_slots` token slots. Each request gets one slab, first fit."""

    def __init__(self, n_slots: int):
        self.n_slots = n_slots
        self.slabs = {}   # request id -> (start, size)
        self.used = {}    # request id -> tokens actually stored

    def allocate(self, rid, size: int):
        """Reserve `size` adjacent slots. Return the start slot, or None if no gap is big enough."""
        for start, length in self.free_runs():
            if length >= size:
                self.slabs[rid] = (start, size)
                self.used[rid] = 0
                return start
        return None

    def release(self, rid) -> None:
        del self.slabs[rid]
        del self.used[rid]

    def free_runs(self):
        """Gaps between slabs as (start, length), left to right."""
        runs, cursor = [], 0
        for start, size in sorted(self.slabs.values()):
            if start > cursor:
                runs.append((cursor, start - cursor))
            cursor = start + size
        if cursor < self.n_slots:
            runs.append((cursor, self.n_slots - cursor))
        return runs

    def free_total(self) -> int:
        return sum(length for _, length in self.free_runs())

    def largest_free_run(self) -> int:
        return max((length for _, length in self.free_runs()), default=0)

    def internal_waste(self) -> int:
        """Reserved slots that hold no token."""
        return sum(size - self.used[rid] for rid, (_, size) in self.slabs.items())


def requests_that_fit_contiguous(pool_tokens: int, max_len: int) -> int:
    """Each request reserves max_len slots, whatever its real length turns out to be."""
    return pool_tokens // max_len


def requests_that_fit_paged(lengths, pool_tokens: int, block_size: int) -> dict:
    """Admit requests in order while their blocks fit. Returns counts and slot accounting."""
    free_blocks = pool_tokens // block_size
    admitted = used = 0
    for n in map(int, lengths):
        need = -(-n // block_size)            # ceil(n / block_size)
        if need > free_blocks:
            break
        free_blocks -= need
        admitted += 1
        used += n
    allocated = (pool_tokens // block_size - free_blocks) * block_size
    return {"admitted": admitted, "used": used, "allocated": allocated, "waste": allocated - used}