95 lines
2.4 KiB
Python
95 lines
2.4 KiB
Python
from abc import ABC
|
|
from typing import Hashable, Iterable, Self
|
|
|
|
|
|
type Comparable = float | int
|
|
|
|
|
|
class Queue[Data](ABC):
|
|
"""
|
|
Common queue methods providing a minimal API for iteration.
|
|
"""
|
|
|
|
def __len__(self) -> int:
|
|
"""
|
|
:return: The number of items in the queue
|
|
"""
|
|
|
|
def __iter__(self) -> Self:
|
|
"""
|
|
:return: An iterator over the queue
|
|
"""
|
|
|
|
def __next__(self) -> Data:
|
|
"""
|
|
:return: The next item in the queue
|
|
"""
|
|
|
|
def pop(self) -> Data:
|
|
"""
|
|
:return: The next item in the queue
|
|
"""
|
|
|
|
|
|
class PureQueue[Data: Comparable](Queue[Data]):
|
|
"""
|
|
A min-queue that directly orders its items, allowing duplicates.
|
|
"""
|
|
|
|
def __init__(self, items: Iterable[Data] | None = None) -> None:
|
|
"""
|
|
:param items: An optional list of priorities with which to initialize the queue
|
|
"""
|
|
|
|
def insert(self, item: Data) -> None:
|
|
"""
|
|
:param item: Item to insert into the queue
|
|
"""
|
|
|
|
|
|
class PairedQueue[Data, Priority: Comparable](Queue[Data]):
|
|
"""
|
|
A min-queue that allows arbitrary data associated with some priority, allowing duplicates of both data and priority.
|
|
"""
|
|
|
|
def __init__(self, items: dict[Data, Priority] | Iterable[tuple[Data, Priority]] | None = None) -> None:
|
|
"""
|
|
:param items: An optional mapping/list of items to priorities with which to initialize the queue
|
|
"""
|
|
|
|
def __setitem__(self, key: Data, value: Priority) -> None:
|
|
"""
|
|
Inserts a new item into the queue
|
|
:param key: The item to insert
|
|
:param value: The priority of the item
|
|
"""
|
|
|
|
|
|
class IndexedQueue[Data: Hashable, Priority: Comparable](Queue[Data]):
|
|
"""
|
|
A min-queue that allows arbitrary data associated with some priority.
|
|
Disallows duplicate data but offers the ability to update priorities and delete arbitrary items.
|
|
"""
|
|
|
|
def __init__(self, items: dict[Data, Priority] | Iterable[tuple[Data, Priority]] | None = None) -> None:
|
|
"""
|
|
:param items: An optional mapping/list of items to priorities with which to initialize the queue
|
|
"""
|
|
|
|
def __setitem__(self, key: Data, value: Priority) -> None:
|
|
"""
|
|
Inserts an item into the queue, or updates its priority if it already exists
|
|
:param key: The item to insert or update
|
|
:param value: The priority of the item
|
|
"""
|
|
|
|
def __delitem__(self, key: Data) -> None:
|
|
"""
|
|
:param key: The item to delete from the queue
|
|
"""
|
|
|
|
def __contains__(self, key: Data) -> bool:
|
|
"""
|
|
:param key: The item to check the existence of
|
|
:return: Whether the item is in the queue
|
|
"""
|