




from __future__ import annotations

from random import random
from typing import Generic, TypeVar

_lowerCamelCase  :			Tuple        =       TypeVar('KT')
_lowerCamelCase  :			Union[str, Any]        =       TypeVar('VT')

class        lowercase      (    Generic[KT, VT]):







				def __init__(							self   :					Optional[int]      ,     _lowerCamelCase   :					List[str] = "root"      ,     _lowerCamelCase   :					Any = None       ):



					"""simple docstring"""

					A_  :				Tuple	   =		key
					A_  :				Optional[Any]	   =		value
					A_  :				List[Any]	   =		[]







				def __repr__(							self   :					Tuple       ):



					"""simple docstring"""

					return F"""Node({self.key}: {self.value})"""







				@property
				def 					a_  (							self   :					List[Any]       ):



					"""simple docstring"""

					return len(self.forward       )

class        lowercase      (    Generic[KT, VT]):







				def __init__(							self   :					Any      ,     _lowerCamelCase   :					Optional[int] = 0.5      ,     _lowerCamelCase   :					Dict = 16       ):



					"""simple docstring"""

					A_  :				Tuple	   =		Node[KT, VT]()
					A_  :				List[str]	   =		0
					A_  :				List[str]	   =		p
					A_  :				List[Any]	   =		max_level







				def __str__(							self   :					Optional[int]       ):



					"""simple docstring"""

					A_  :				Union[str, Any]	   =		list(self       )

					if len(_lowerCamelCase       ) == 0:
						return F"""SkipList(level={self.level})"""

					A_  :				int	   =		max((len(str(_lowerCamelCase       )       ) for item in items)      ,     default=4       )
					A_  :				int	   =		max(_lowerCamelCase      ,     4       ) + 4

					A_  :				Optional[int]	   =		self.head
					A_  :				int	   =		[]

					A_  :				Any	   =		node.forward.copy()
					lines.append(F"""[{node.key}]""".ljust(_lowerCamelCase      ,     '''-'''       ) + '''* ''' * len(_lowerCamelCase       )       )
					lines.append(''' ''' * label_size + '''| ''' * len(_lowerCamelCase       )       )

					while len(node.forward       ) != 0:
						A_  :				Any	   =		node.forward[0]

						lines.append(
						    F"""[{node.key}]""".ljust(_lowerCamelCase      ,     '''-'''       )
						    + ''' '''.join(str(n.key       ) if n.key == node.key else '''|''' for n in forwards       )       )
						lines.append(''' ''' * label_size + '''| ''' * len(_lowerCamelCase       )       )
						A_  :				Tuple	   =		node.forward

					lines.append('''None'''.ljust(_lowerCamelCase       ) + '''* ''' * len(_lowerCamelCase       )       )
					return F"""SkipList(level={self.level})\n""" + "\n".join(_lowerCamelCase       )







				def __iter__(							self   :					List[str]       ):



					"""simple docstring"""

					A_  :				List[str]	   =		self.head

					while len(node.forward       ) != 0:
						yield node.forward[0].key
						A_  :				Tuple	   =		node.forward[0]







				def 					a_  (							self   :					List[Any]       ):



					"""simple docstring"""

					A_  :				Any	   =		1
					while random() < self.p and level < self.max_level:
						level += 1

					return level







				def 					a_  (							self   :					Optional[Any]      ,     _lowerCamelCase   :					List[str]       ):



					"""simple docstring"""

					A_  :				Any	   =		[]

					A_  :				Union[str, Any]	   =		self.head

					for i in reversed(range(self.level       )       ):
						# i < node.level - When node level is lesser than `i` decrement `i`.
						# node.forward[i].key < key - Jumping to node with key value higher
						#                             or equal to searched key would result
						#                             in skipping searched key.
						while i < node.level and node.forward[i].key < key:
							A_  :				Dict	   =		node.forward[i]
						# Each leftmost node (relative to searched node) will potentially have to
						# be updated.
						update_vector.append(_lowerCamelCase       )

					update_vector.reverse()  # Note that we were inserting values in reverse order.

					# len(node.forward) != 0 - If current node doesn't contain any further
					#                          references then searched key is not present.
					# node.forward[0].key == key - Next node key should be equal to search key
					#                              if key is present.
					if len(node.forward       ) != 0 and node.forward[0].key == key:
						return node.forward[0], update_vector
					else:
						return None, update_vector







				def 					a_  (							self   :					Optional[int]      ,     _lowerCamelCase   :					List[str]       ):



					"""simple docstring"""

					A_   , A_  :				List[Any]	   =		self._locate_node(_lowerCamelCase       )

					if node is not None:
						for i, update_node in enumerate(_lowerCamelCase       ):
							# Remove or replace all references to removed node.
							if update_node.level > i and update_node.forward[i].key == key:
								if node.level > i:
									A_  :				str	   =		node.forward[i]
								else:
									A_  :				List[str]	   =		update_node.forward[:i]







				def 					a_  (							self   :					int      ,     _lowerCamelCase   :					List[Any]      ,     _lowerCamelCase   :					Tuple       ):



					"""simple docstring"""

					A_   , A_  :				Any	   =		self._locate_node(_lowerCamelCase       )
					if node is not None:
						A_  :				str	   =		value
					else:
						A_  :				Any	   =		self.random_level()

						if level > self.level:
							# After level increase we have to add additional nodes to head.
							for _ in range(self.level - 1      ,     _lowerCamelCase       ):
								update_vector.append(self.head       )
							A_  :				List[str]	   =		level

						A_  :				List[Any]	   =		Node(_lowerCamelCase      ,     _lowerCamelCase       )

						for i, update_node in enumerate(update_vector[:level]       ):
							# Change references to pass through new node.
							if update_node.level > i:
								new_node.forward.append(update_node.forward[i]       )

							if update_node.level < i + 1:
								update_node.forward.append(_lowerCamelCase       )
							else:
								A_  :				Union[str, Any]	   =		new_node







				def 					a_  (							self   :					Union[str, Any]      ,     _lowerCamelCase   :					str       ):



					"""simple docstring"""

					A_   , A_  :				str	   =		self._locate_node(_lowerCamelCase       )

					if node is not None:
						return node.value

					return None

def 		lowercase_      (		):




	"""simple docstring"""






	A_  :				str	   =		SkipList()
	skip_list.insert('''Key1'''  ,      3	)
	skip_list.insert('''Key2'''  ,      12	)
	skip_list.insert('''Key3'''  ,      41	)
	skip_list.insert('''Key4'''  ,      -19	)

	A_  :				List[Any]	   =		skip_list.head
	A_  :				List[Any]	   =		{}
	while node.level != 0:
		A_  :				Any	   =		node.forward[0]
		A_  :				Union[str, Any]	   =		node.value

	assert len(_UpperCAmelCase	) == 4
	assert all_values["Key1"] == 3
	assert all_values["Key2"] == 12
	assert all_values["Key3"] == 41
	assert all_values["Key4"] == -19

def 		lowercase_      (		):




	"""simple docstring"""






	A_  :				Optional[Any]	   =		SkipList()
	skip_list.insert('''Key1'''  ,      10	)
	skip_list.insert('''Key1'''  ,      12	)

	skip_list.insert('''Key5'''  ,      7	)
	skip_list.insert('''Key7'''  ,      10	)
	skip_list.insert('''Key10'''  ,      5	)

	skip_list.insert('''Key7'''  ,      7	)
	skip_list.insert('''Key5'''  ,      5	)
	skip_list.insert('''Key10'''  ,      10	)

	A_  :				Any	   =		skip_list.head
	A_  :				Tuple	   =		{}
	while node.level != 0:
		A_  :				Dict	   =		node.forward[0]
		A_  :				Optional[int]	   =		node.value

	if len(_UpperCAmelCase	) != 4:
		print()
	assert len(_UpperCAmelCase	) == 4
	assert all_values["Key1"] == 12
	assert all_values["Key7"] == 7
	assert all_values["Key5"] == 5
	assert all_values["Key10"] == 10

def 		lowercase_      (		):




	"""simple docstring"""






	A_  :				int	   =		SkipList()
	assert skip_list.find('''Some key'''	) is None

def 		lowercase_      (		):




	"""simple docstring"""






	A_  :				Union[str, Any]	   =		SkipList()

	skip_list.insert('''Key2'''  ,      20	)
	assert skip_list.find('''Key2'''	) == 20

	skip_list.insert('''Some Key'''  ,      10	)
	skip_list.insert('''Key2'''  ,      8	)
	skip_list.insert('''V'''  ,      13	)

	assert skip_list.find('''Y'''	) is None
	assert skip_list.find('''Key2'''	) == 8
	assert skip_list.find('''Some Key'''	) == 10
	assert skip_list.find('''V'''	) == 13

def 		lowercase_      (		):




	"""simple docstring"""






	A_  :				List[str]	   =		SkipList()
	skip_list.delete('''Some key'''	)

	assert len(skip_list.head.forward	) == 0

def 		lowercase_      (		):




	"""simple docstring"""






	A_  :				Union[str, Any]	   =		SkipList()

	skip_list.insert('''Key1'''  ,      12	)
	skip_list.insert('''V'''  ,      13	)
	skip_list.insert('''X'''  ,      14	)
	skip_list.insert('''Key2'''  ,      15	)

	skip_list.delete('''V'''	)
	skip_list.delete('''Key2'''	)

	assert skip_list.find('''V'''	) is None
	assert skip_list.find('''Key2'''	) is None

def 		lowercase_      (		):




	"""simple docstring"""






	A_  :				Tuple	   =		SkipList()

	skip_list.insert('''Key1'''  ,      12	)
	skip_list.insert('''V'''  ,      13	)
	skip_list.insert('''X'''  ,      14	)
	skip_list.insert('''Key2'''  ,      15	)

	skip_list.delete('''V'''	)
	assert skip_list.find('''V'''	) is None
	assert skip_list.find('''X'''	) == 14
	assert skip_list.find('''Key1'''	) == 12
	assert skip_list.find('''Key2'''	) == 15

	skip_list.delete('''X'''	)
	assert skip_list.find('''V'''	) is None
	assert skip_list.find('''X'''	) is None
	assert skip_list.find('''Key1'''	) == 12
	assert skip_list.find('''Key2'''	) == 15

	skip_list.delete('''Key1'''	)
	assert skip_list.find('''V'''	) is None
	assert skip_list.find('''X'''	) is None
	assert skip_list.find('''Key1'''	) is None
	assert skip_list.find('''Key2'''	) == 15

	skip_list.delete('''Key2'''	)
	assert skip_list.find('''V'''	) is None
	assert skip_list.find('''X'''	) is None
	assert skip_list.find('''Key1'''	) is None
	assert skip_list.find('''Key2'''	) is None

def 		lowercase_      (		):




	"""simple docstring"""






	A_  :				Optional[int]	   =		SkipList()

	skip_list.insert('''Key1'''  ,      12	)
	skip_list.insert('''V'''  ,      13	)
	skip_list.insert('''X'''  ,      142	)
	skip_list.insert('''Key2'''  ,      15	)

	skip_list.delete('''X'''	)

	def traverse_keys(_UpperCAmelCase	):
		yield node.key
		for forward_node in node.forward:
			yield from traverse_keys(_UpperCAmelCase	)

	assert len(set(traverse_keys(skip_list.head	)	)	) == 4

def 		lowercase_      (		):




	"""simple docstring"""






	def is_sorted(_UpperCAmelCase	):
		return all(next_item >= item for item, next_item in zip(_UpperCAmelCase  ,      lst[1:]	)	)

	A_  :				Any	   =		SkipList()
	for i in range(10	):
		skip_list.insert(_UpperCAmelCase  ,      _UpperCAmelCase	)
	assert is_sorted(list(_UpperCAmelCase	)	)
	skip_list.delete(5	)
	skip_list.delete(8	)
	skip_list.delete(2	)
	assert is_sorted(list(_UpperCAmelCase	)	)
	skip_list.insert(-12  ,      -12	)
	skip_list.insert(77  ,      77	)
	assert is_sorted(list(_UpperCAmelCase	)	)

def 		lowercase_      (		):




	"""simple docstring"""






	for _ in range(100	):
		# Repeat test 100 times due to the probabilistic nature of skip list
		# random values == random bugs
		test_insert()
		test_insert_overrides_existing_value()

		test_searching_empty_list_returns_none()
		test_search()

		test_deleting_item_from_empty_list_do_nothing()
		test_deleted_items_are_not_founded_by_find_method()
		test_delete_removes_only_given_key()
		test_delete_doesnt_leave_dead_nodes()

		test_iter_always_yields_sorted_values()

def 		lowercase_      (		):




	"""simple docstring"""






	A_  :				List[str]	   =		SkipList()
	skip_list.insert(2  ,      '''2'''	)
	skip_list.insert(4  ,      '''4'''	)
	skip_list.insert(6  ,      '''4'''	)
	skip_list.insert(4  ,      '''5'''	)
	skip_list.insert(8  ,      '''4'''	)
	skip_list.insert(9  ,      '''4'''	)

	skip_list.delete(4	)

	print(_UpperCAmelCase	)


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		main()











"""simple docstring"""

from queue import PriorityQueue
from typing import Any

import numpy as np

def 		lowercase_      (		_UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      ):




	"""simple docstring"""






	for nxt, d in graph[v]:
		if nxt in visited_forward:
			continue
		A_  :				Tuple	   =		cst_fwd.get(_UpperCAmelCase  ,      np.inf	)
		A_  :				Any	   =		cst_fwd[v] + d
		if new_cost_f < old_cost_f:
			queue.put((new_cost_f, nxt)	)
			A_  :				Tuple	   =		new_cost_f
			A_  :				Dict	   =		v
		if nxt in visited_backward:
			if cst_fwd[v] + d + cst_bwd[nxt] < shortest_distance:
				A_  :				Optional[Any]	   =		cst_fwd[v] + d + cst_bwd[nxt]
	return shortest_distance

def 		lowercase_      (		_UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase	):




	"""simple docstring"""






	A_  :				Tuple	   =		-1

	A_  :				Any	   =		set()
	A_  :				Tuple	   =		set()
	A_  :				Optional[int]	   =		{source: 0}
	A_  :				Dict	   =		{destination: 0}
	A_  :				Any	   =		{source: None}
	A_  :				Optional[Any]	   =		{destination: None}
	A_  :				PriorityQueue[Any]	   =		PriorityQueue()
	A_  :				PriorityQueue[Any]	   =		PriorityQueue()

	A_  :				Union[str, Any]	   =		np.inf

	queue_forward.put((0, source)	)
	queue_backward.put((0, destination)	)

	if source == destination:
		return 0

	while not queue_forward.empty() and not queue_backward.empty():
		A_   , A_  :				Union[str, Any]	   =		queue_forward.get()
		visited_forward.add(_UpperCAmelCase	)

		A_   , A_  :				Optional[int]	   =		queue_backward.get()
		visited_backward.add(_UpperCAmelCase	)

		A_  :				Any	   =		pass_and_relaxation(
		    _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      )

		A_  :				Dict	   =		pass_and_relaxation(
		    _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      _UpperCAmelCase  ,      )

		if cst_fwd[v_fwd] + cst_bwd[v_bwd] >= shortest_distance:
			break

	if shortest_distance != np.inf:
		A_  :				Optional[Any]	   =		shortest_distance
	return shortest_path_distance


_lowerCamelCase  :			Optional[Any]        =       {
    'B': [['C', 1]],
    'C': [['D', 1]],
    'D': [['F', 1]],
    'E': [['B', 1], ['G', 2]],
    'F': [],
    'G': [['F', 1]],
}
_lowerCamelCase  :			Any        =       {
    'B': [['E', 1]],
    'C': [['B', 1]],
    'D': [['C', 1]],
    'F': [['D', 1], ['G', 1]],
    'E': [[None, np.inf]],
    'G': [['E', 2]],
}

if __name__ == "__main__":
		import doctest

		doctest.testmod()





