


"""simple docstring"""


from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

A  :     List[Any]    					=    TypeVar("T")


def _lowerCamelCase			(	_UpperCamelCase   ):

			'''simple docstring'''




			return (position - 1) // 2


def _lowerCamelCase			(	_UpperCamelCase   ):

			'''simple docstring'''




			return (2 * position) + 1


def _lowerCamelCase			(	_UpperCamelCase   ):

			'''simple docstring'''




			return (2 * position) + 2



class 						_UpperCamelCase						(     Generic[T]	):
							'''simple docstring'''







							def __init__(  self			):
										__lowerCAmelCase       					=    []
										__lowerCAmelCase       					=    {}
										__lowerCAmelCase       					=    0

							def __len__(  self			):
										return self.elements

							def __repr__(  self			):
										return str(self.heap			)

							def     snake_case       (  self			):
										return self.elements == 0

							def     snake_case       (  self					,     __a					,     __a			):
										self.heap.append((elem, weight)			)
										__lowerCAmelCase       					=    self.elements
										self.elements += 1
										self._bubble_up(UpperCAmelCase__			)

							def     snake_case       (  self			):
										# Remove and return the element with lowest weight (highest priority)
										if self.elements > 1:
													self._swap_nodes(0					,     self.elements - 1			)
										__lowerCAmelCase       					=    self.heap.pop()
										del self.position_map[elem]
										self.elements -= 1
										if self.elements > 0:
													__lowerCAmelCase       					=    self.heap[0]
													self._bubble_down(UpperCAmelCase__			)
										return elem

							def     snake_case       (  self					,     __a					,     __a			):
										__lowerCAmelCase       					=    self.position_map[elem]
										__lowerCAmelCase       					=    (elem, weight)
										if position > 0:
													__lowerCAmelCase       					=    get_parent_position(UpperCAmelCase__			)
													__lowerCAmelCase       					=    self.heap[parent_position]
													if parent_weight > weight:
																self._bubble_up(UpperCAmelCase__			)
													else:
																self._bubble_down(UpperCAmelCase__			)
										else:
													self._bubble_down(UpperCAmelCase__			)

							def     snake_case       (  self					,     __a			):
										__lowerCAmelCase       					=    self.position_map[elem]
										if curr_pos == 0:
													return None
										__lowerCAmelCase       					=    get_parent_position(UpperCAmelCase__			)
										__lowerCAmelCase       					=    self.heap[curr_pos]
										__lowerCAmelCase       					=    self.heap[parent_position]
										if parent_weight > weight:
													self._swap_nodes(UpperCAmelCase__					,     UpperCAmelCase__			)
													return self._bubble_up(UpperCAmelCase__			)
										return None

							def     snake_case       (  self					,     __a			):
										__lowerCAmelCase       					=    self.position_map[elem]
										__lowerCAmelCase       					=    self.heap[curr_pos]
										__lowerCAmelCase       					=    get_child_left_position(UpperCAmelCase__			)
										__lowerCAmelCase       					=    get_child_right_position(UpperCAmelCase__			)
										if child_left_position < self.elements and child_right_position < self.elements:
													__lowerCAmelCase       					=    self.heap[child_left_position]
													__lowerCAmelCase       					=    self.heap[child_right_position]
													if child_right_weight < child_left_weight and child_right_weight < weight:
																self._swap_nodes(UpperCAmelCase__					,     UpperCAmelCase__			)
																return self._bubble_down(UpperCAmelCase__			)
										if child_left_position < self.elements:
													__lowerCAmelCase       					=    self.heap[child_left_position]
													if child_left_weight < weight:
																self._swap_nodes(UpperCAmelCase__					,     UpperCAmelCase__			)
																return self._bubble_down(UpperCAmelCase__			)
										else:
													return None
										if child_right_position < self.elements:
													__lowerCAmelCase       					=    self.heap[child_right_position]
													if child_right_weight < weight:
																self._swap_nodes(UpperCAmelCase__					,     UpperCAmelCase__			)
																return self._bubble_down(UpperCAmelCase__			)
										return None



							def     snake_case       (  self					,     __a					,     __a			):
										__lowerCAmelCase       					=    self.heap[nodea_pos][0]
										__lowerCAmelCase       					=    self.heap[nodea_pos][0]
										__lowerCAmelCase       					=    (
										    self.heap[nodea_pos],
										    self.heap[nodea_pos],
										)
										__lowerCAmelCase       					=    nodea_pos
										__lowerCAmelCase       					=    nodea_pos



class 						_UpperCamelCase						(     Generic[T]	):
							'''simple docstring'''







							def __init__(  self			):
										__lowerCAmelCase       					=    {}
										__lowerCAmelCase       					=    0

							def __repr__(  self			):
										return str(self.connections			)

							def __len__(  self			):
										return self.nodes

							def     snake_case       (  self					,     __a			):
										# Add a node in the graph if it is not in the graph
										if node not in self.connections:
													__lowerCAmelCase       					=    {}
													self.nodes += 1



							def     snake_case       (  self					,     __a					,     __a					,     __a			):
										self.add_node(UpperCAmelCase__			)
										self.add_node(UpperCAmelCase__			)
										__lowerCAmelCase       					=    weight
										__lowerCAmelCase       					=    weight


def _lowerCamelCase			(	_UpperCamelCase					,				):

			'''simple docstring'''




			__lowerCAmelCase       					=    {node: maxsize for node in graph.connections}
			__lowerCAmelCase       					=    {node: None for node in graph.connections}

			__lowerCAmelCase       					=    MinPriorityQueue()
			for node, weight in dist.items():
						priority_queue.push(_UpperCamelCase					,				_UpperCamelCase   )

			if priority_queue.is_empty():
						return dist, parent

			# initialization
			__lowerCAmelCase       					=    priority_queue.extract_min()
			__lowerCAmelCase       					=    0
			for neighbour in graph.connections[node]:
						if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
									__lowerCAmelCase       					=    dist[node] + graph.connections[node][neighbour]
									priority_queue.update_key(_UpperCamelCase					,				dist[neighbour]   )
									__lowerCAmelCase       					=    node

    # running prim's algorithm
			while not priority_queue.is_empty():
						__lowerCAmelCase       					=    priority_queue.extract_min()
						for neighbour in graph.connections[node]:
									if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
												__lowerCAmelCase       					=    dist[node] + graph.connections[node][neighbour]
												priority_queue.update_key(_UpperCamelCase					,				dist[neighbour]   )
												__lowerCAmelCase       					=    node
			return dist, parent








"""simple docstring"""


from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available


A  :     Union[str, Any]    					=    {
    "configuration_x_clip": [
        "XCLIP_PRETRAINED_CONFIG_ARCHIVE_MAP",
        "XCLIPConfig",
        "XCLIPTextConfig",
        "XCLIPVisionConfig",
    ],
    "processing_x_clip": ["XCLIPProcessor"],
}

try:
	if not is_torch_available():
		raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
	pass
else:
	A  :     Optional[int]    					=    [
	    "XCLIP_PRETRAINED_MODEL_ARCHIVE_LIST",
	    "XCLIPModel",
	    "XCLIPPreTrainedModel",
	    "XCLIPTextModel",
	    "XCLIPVisionModel",
	]

if TYPE_CHECKING:
	from .configuration_x_clip import (
	    XCLIP_PRETRAINED_CONFIG_ARCHIVE_MAP,
	    XCLIPConfig,
	    XCLIPTextConfig,
	    XCLIPVisionConfig,
	)
	from .processing_x_clip import XCLIPProcessor

	try:
		if not is_torch_available():
			raise OptionalDependencyNotAvailable()
	except OptionalDependencyNotAvailable:
		pass
	else:
		from .modeling_x_clip import (
		    XCLIP_PRETRAINED_MODEL_ARCHIVE_LIST,
		    XCLIPModel,
		    XCLIPPreTrainedModel,
		    XCLIPTextModel,
		    XCLIPVisionModel,
		)

else:
	import sys

	A  :     Union[str, Any]    					=    _LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)




