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
		"""