




'''simple docstring'''







import math
import sys





class 	lowerCamelCase_				:




					'''simple docstring'''






					def __init__(       self					):
							_snake_case      			=			0
							_snake_case      			=			[]
							_snake_case      			=			{}  # To store the pos of node in array






					def 							__SCREAMING_SNAKE_CASE      (       self					):
							return self.cur_size == 0






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase					):
							_snake_case      			=			self.left(__UpperCamelCase					)
							_snake_case      			=			self.right(__UpperCamelCase					)
							if lc < self.cur_size and self.array(__UpperCamelCase					)[0] < self.array(__UpperCamelCase					)[0]:
									_snake_case      			=			lc
							else:
									_snake_case      			=			idx
							if rc < self.cur_size and self.array(__UpperCamelCase					)[0] < self.array(__UpperCamelCase					)[0]:
									_snake_case      			=			rc
							if smallest != idx:
									self.swap(__UpperCamelCase,    __UpperCamelCase					)
									self.min_heapify(__UpperCamelCase					)






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase					):
							# Inserts a node into the Priority Queue
							_snake_case      			=			self.cur_size
							self.cur_size += 1
							self.array.append((sys.maxsize, tup[1])					)
							self.decrease_key((sys.maxsize, tup[1]),    tup[0]					)






					def 							__SCREAMING_SNAKE_CASE      (       self					):
							# Removes and returns the min element at top of priority queue
							_snake_case      			=			self.array[0][1]
							_snake_case      			=			self.array[self.cur_size - 1]
							self.cur_size -= 1
							self.min_heapify(1					)
							del self.pos[min_node]
							return min_node






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase					):
							# returns the index of left child
							return 2 * i + 1






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase					):
							# returns the index of right child
							return 2 * i + 2






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase					):
							# returns the index of parent
							return math.floor(i / 2					)






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase,    __UpperCamelCase					):
							# swaps array elements at indices i and j
							# update the pos{}
							_snake_case      			=			j
							_snake_case      			=			i
							_snake_case      			=			self.array[i]
							_snake_case      			=			self.array[j]
							_snake_case      			=			temp






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase,    __UpperCamelCase					):
							_snake_case      			=			self.pos[tup[1]]
							# assuming the new_d is atmost old_d
							_snake_case      			=			(new_d, tup[1])
							while idx > 0 and self.array[self.par(__UpperCamelCase					)][0] > self.array[idx][0]:
									self.swap(__UpperCamelCase,    self.par(__UpperCamelCase					)					)
									_snake_case      			=			self.par(__UpperCamelCase					)





class 	lowerCamelCase_				:




					'''simple docstring'''






					def __init__(       self,    __UpperCamelCase					):
							_snake_case      			=			{}  # To store graph: u -> (v,w)
							_snake_case      			=			num  # Number of nodes in graph
							# To store the distance from source vertex
							_snake_case      			=			[0] * self.num_nodes
							_snake_case      			=			[-1] * self.num_nodes  # To store the path






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase,    __UpperCamelCase,    __UpperCamelCase					):
							#  Edge going from node u to v and v to u with weight w
							# u (w)-> v, v (w) -> u
							# Check if u already in graph
							if u in self.adjList:
									self.adjList[u].append((v, w)					)
							else:
									_snake_case      			=			[(v, w)]

							# Assuming undirected graph
							if v in self.adjList:
									self.adjList[v].append((u, w)					)
							else:
									_snake_case      			=			[(u, w)]






					def 							__SCREAMING_SNAKE_CASE      (       self					):
							# u -> v(w)
							for u in self.adjList:
									print(__UpperCamelCase,    "->",    " -> ".join(str(f'''{v}({w})'''					) for v, w in self.adjList[u]					)					)






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase					):
							# Flush old junk values in par[]
							_snake_case      			=			[-1] * self.num_nodes
							# src is the source node
							_snake_case      			=			0
							_snake_case      			=			PriorityQueue()
							q.insert((0, src)					)  # (dist from src, node)
							for u in self.adjList:
									if u != src:
											_snake_case      			=			sys.maxsize  # Infinity
											_snake_case      			=			-1

							while not q.is_empty():
									_snake_case      			=			q.extract_min()  # Returns node with the min dist from source
									# Update the distance of all the neighbours of u and
									# if their prev dist was INFINITY then push them in Q
									for v, w in self.adjList[u]:
											_snake_case      			=			self.dist[u] + w
											if self.dist[v] > new_dist:
													if self.dist[v] == sys.maxsize:
															q.insert((new_dist, v)					)
													else:
															q.decrease_key((self.dist[v], v),    __UpperCamelCase					)
													_snake_case      			=			new_dist
													_snake_case      			=			u

        # Show the shortest distances from src
							self.show_distances(__UpperCamelCase					)






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase					):
							print(f'''Distance from node: {src}'''					)
							for u in range(self.num_nodes					):
									print(f'''Node {u} has distance: {self.dist[u]}'''					)






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase,    __UpperCamelCase					):
							# To show the shortest path from src to dest
							# WARNING: Use it *after* calling dijkstra
							_snake_case      			=			[]
							_snake_case      			=			0
							_snake_case      			=			dest
							# Backtracking from dest to src
							while self.par[temp] != -1:
									path.append(__UpperCamelCase					)
									if temp != src:
											for v, w in self.adjList[temp]:
													if v == self.par[temp]:
															cost += w
															break
									_snake_case      			=			self.par[temp]
							path.append(__UpperCamelCase					)
							path.reverse()

							print(f'''----Path to reach {dest} from {src}----'''					)
							for u in path:
									print(f'''{u}''',    end=" "					)
									if u != dest:
											print("-> ",    end=""					)

							print("\nTotal cost of path: ",    __UpperCamelCase					)


if __name__ == "__main__":
						_lowerCamelCase				:		str				      =    Graph(9)
						graph.add_edge(0, 1, 4)
						graph.add_edge(0, 7, 8)
						graph.add_edge(1, 2, 8)
						graph.add_edge(1, 7, 11)
						graph.add_edge(2, 3, 7)
						graph.add_edge(2, 8, 2)
						graph.add_edge(2, 5, 4)
						graph.add_edge(3, 4, 9)
						graph.add_edge(3, 5, 14)
						graph.add_edge(4, 5, 10)
						graph.add_edge(5, 6, 2)
						graph.add_edge(6, 7, 1)
						graph.add_edge(6, 8, 6)
						graph.add_edge(7, 8, 7)
						graph.show_graph()
						graph.dijkstra(0)
						graph.show_path(0, 4)

# OUTPUT
# 0 -> 1(4) -> 7(8)
# 1 -> 0(4) -> 2(8) -> 7(11)
# 7 -> 0(8) -> 1(11) -> 6(1) -> 8(7)
# 2 -> 1(8) -> 3(7) -> 8(2) -> 5(4)
# 3 -> 2(7) -> 4(9) -> 5(14)
# 8 -> 2(2) -> 6(6) -> 7(7)
# 5 -> 2(4) -> 3(14) -> 4(10) -> 6(2)
# 4 -> 3(9) -> 5(10)
# 6 -> 5(2) -> 7(1) -> 8(6)
# Distance from node: 0
# Node 0 has distance: 0
# Node 1 has distance: 4
# Node 2 has distance: 12
# Node 3 has distance: 19
# Node 4 has distance: 21
# Node 5 has distance: 11
# Node 6 has distance: 9
# Node 7 has distance: 8
# Node 8 has distance: 14
# ----Path to reach 4 from 0----
# 0 -> 7 -> 6 -> 5 -> 4
# Total cost of path:  21











'''simple docstring'''







import datasets

from .evaluate import (
    apply_no_ans_threshold,
    find_all_best_thresh,
    get_raw_scores,
    make_eval_dict,
    make_qid_to_has_ans,
    merge_eval,
)


_lowerCamelCase				:		str				      =    '\\n@inproceedings{Rajpurkar2016SQuAD10,\n  title={SQuAD: 100, 000+ Questions for Machine Comprehension of Text},\n  author={Pranav Rajpurkar and Jian Zhang and Konstantin Lopyrev and Percy Liang},\n  booktitle={EMNLP},\n  year={2016}\n}\n'

_lowerCamelCase				:		Union[str, Any]				      =    '\nThis metric wrap the official scoring script for version 2 of the Stanford Question\nAnswering Dataset (SQuAD).\n\nStanford Question Answering Dataset (SQuAD) is a reading comprehension dataset, consisting of questions posed by\ncrowdworkers on a set of Wikipedia articles, where the answer to every question is a segment of text, or span,\nfrom the corresponding reading passage, or the question might be unanswerable.\n\nSQuAD2.0 combines the 100,000 questions in SQuAD1.1 with over 50,000 unanswerable questions\nwritten adversarially by crowdworkers to look similar to answerable ones.\nTo do well on SQuAD2.0, systems must not only answer questions when possible, but also\ndetermine when no answer is supported by the paragraph and abstain from answering.\n'

_lowerCamelCase				:		List[Any]				      =    '\nComputes SQuAD v2 scores (F1 and EM).\nArgs:\n    predictions: List of triple for question-answers to score with the following elements:\n        - the question-answer \'id\' field as given in the references (see below)\n        - the text of the answer\n        - the probability that the question has no answer\n    references: List of question-answers dictionaries with the following key-values:\n            - \'id\': id of the question-answer pair (see above),\n            - \'answers\': a list of Dict {\'text\': text of the answer as a string}\n    no_answer_threshold: float\n        Probability threshold to decide that a question has no answer.\nReturns:\n    \'exact\': Exact match (the normalized answer exactly match the gold answer)\n    \'f1\': The F-score of predicted tokens versus the gold answer\n    \'total\': Number of score considered\n    \'HasAns_exact\': Exact match (the normalized answer exactly match the gold answer)\n    \'HasAns_f1\': The F-score of predicted tokens versus the gold answer\n    \'HasAns_total\': Number of score considered\n    \'NoAns_exact\': Exact match (the normalized answer exactly match the gold answer)\n    \'NoAns_f1\': The F-score of predicted tokens versus the gold answer\n    \'NoAns_total\': Number of score considered\n    \'best_exact\': Best exact match (with varying threshold)\n    \'best_exact_thresh\': No-answer probability threshold associated to the best exact match\n    \'best_f1\': Best F1 (with varying threshold)\n    \'best_f1_thresh\': No-answer probability threshold associated to the best F1\nExamples:\n\n    >>> predictions = [{\'prediction_text\': \'1976\', \'id\': \'56e10a3be3433e1400422b22\', \'no_answer_probability\': 0.}]\n    >>> references = [{\'answers\': {\'answer_start\': [97], \'text\': [\'1976\']}, \'id\': \'56e10a3be3433e1400422b22\'}]\n    >>> squad_v2_metric = datasets.load_metric("squad_v2")\n    >>> results = squad_v2_metric.compute(predictions=predictions, references=references)\n    >>> print(results)\n    {\'exact\': 100.0, \'f1\': 100.0, \'total\': 1, \'HasAns_exact\': 100.0, \'HasAns_f1\': 100.0, \'HasAns_total\': 1, \'best_exact\': 100.0, \'best_exact_thresh\': 0.0, \'best_f1\': 100.0, \'best_f1_thresh\': 0.0}\n'





@datasets.utils.file_utils.add_start_docstrings(_DESCRIPTION,			_KWARGS_DESCRIPTION				)
class 	lowerCamelCase_				(			datasets.Metric				):




					'''simple docstring'''






					def 							__SCREAMING_SNAKE_CASE      (       self					):
							return datasets.MetricInfo(
							    description=_DESCRIPTION,    citation=_CITATION,    inputs_description=_KWARGS_DESCRIPTION,    features=datasets.Features(
							        {
							            "predictions": {
							                "id": datasets.Value("string"					),
							                "prediction_text": datasets.Value("string"					),
							                "no_answer_probability": datasets.Value("float32"					),
							            },
							            "references": {
							                "id": datasets.Value("string"					),
							                "answers": datasets.features.Sequence(
							                    {"text": datasets.Value("string"					), "answer_start": datasets.Value("int32"					)}					),
							            },
							        }					),    codebase_urls=["https://rajpurkar.github.io/SQuAD-explorer/"],    reference_urls=["https://rajpurkar.github.io/SQuAD-explorer/"],    )






					def 							__SCREAMING_SNAKE_CASE      (       self,    __UpperCamelCase,    __UpperCamelCase,    __UpperCamelCase=1.0					):
							_snake_case      			=			{p["id"]: p["no_answer_probability"] for p in predictions}
							_snake_case      			=			[{"paragraphs": [{"qas": references}]}]
							_snake_case      			=			{p["id"]: p["prediction_text"] for p in predictions}

							_snake_case      			=			make_qid_to_has_ans(__UpperCamelCase					)  # maps qid to True/False
							_snake_case      			=			[k for k, v in qid_to_has_ans.items() if v]
							_snake_case      			=			[k for k, v in qid_to_has_ans.items() if not v]

							_snake_case			,       _snake_case      			=			get_raw_scores(__UpperCamelCase,    __UpperCamelCase					)
							_snake_case      			=			apply_no_ans_threshold(__UpperCamelCase,    __UpperCamelCase,    __UpperCamelCase,    __UpperCamelCase					)
							_snake_case      			=			apply_no_ans_threshold(__UpperCamelCase,    __UpperCamelCase,    __UpperCamelCase,    __UpperCamelCase					)
							_snake_case      			=			make_eval_dict(__UpperCamelCase,    __UpperCamelCase					)

							if has_ans_qids:
									_snake_case      			=			make_eval_dict(__UpperCamelCase,    __UpperCamelCase,    qid_list=__UpperCamelCase					)
									merge_eval(__UpperCamelCase,    __UpperCamelCase,    "HasAns"					)
							if no_ans_qids:
									_snake_case      			=			make_eval_dict(__UpperCamelCase,    __UpperCamelCase,    qid_list=__UpperCamelCase					)
									merge_eval(__UpperCamelCase,    __UpperCamelCase,    "NoAns"					)
							find_all_best_thresh(__UpperCamelCase,    __UpperCamelCase,    __UpperCamelCase,    __UpperCamelCase,    __UpperCamelCase,    __UpperCamelCase					)
							return dict(__UpperCamelCase					)





