


import math
import sys







class      __lowercase  :





							"""simple docstring"""







							def __init__(	self    ):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_						:			List[Any]       						= 0
										SCREAMING_SNAKE_CASE_						:			Any       						= []
										SCREAMING_SNAKE_CASE_						:			Union[str, Any]       						= {}  # To store the pos of node in array






							def  UpperCamelCase__			(	self    ):





										"""simple docstring"""




										return self.cur_size == 0






							def  UpperCamelCase__			(	self       ,		lowerCAmelCase__    ):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_						:			Optional[int]       						= self.left(lowerCAmelCase__    )
										SCREAMING_SNAKE_CASE_						:			Optional[int]       						= self.right(lowerCAmelCase__    )
										if lc < self.cur_size and self.array(lowerCAmelCase__    )[0] < self.array(lowerCAmelCase__    )[0]:
													SCREAMING_SNAKE_CASE_						:			Dict       						= lc
										else:
													SCREAMING_SNAKE_CASE_						:			str       						= idx
										if rc < self.cur_size and self.array(lowerCAmelCase__    )[0] < self.array(lowerCAmelCase__    )[0]:
													SCREAMING_SNAKE_CASE_						:			Optional[Any]       						= rc
										if smallest != idx:
													self.swap(lowerCAmelCase__       ,		lowerCAmelCase__    )
													self.min_heapify(lowerCAmelCase__    )






							def  UpperCamelCase__			(	self       ,		lowerCAmelCase__    ):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_						:			List[str]       						= self.cur_size
										self.cur_size += 1
										self.array.append((sys.maxsize, tup[1])    )
										self.decrease_key((sys.maxsize, tup[1])       ,		tup[0]    )






							def  UpperCamelCase__			(	self    ):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_						:			Tuple       						= self.array[0][1]
										SCREAMING_SNAKE_CASE_						:			Union[str, Any]       						= self.array[self.cur_size - 1]
										self.cur_size -= 1
										self.min_heapify(1    )
										del self.pos[min_node]
										return min_node






							def  UpperCamelCase__			(	self       ,		lowerCAmelCase__    ):





										"""simple docstring"""




										return 2 * i + 1






							def  UpperCamelCase__			(	self       ,		lowerCAmelCase__    ):





										"""simple docstring"""




										return 2 * i + 2






							def  UpperCamelCase__			(	self       ,		lowerCAmelCase__    ):





										"""simple docstring"""




										return math.floor(i / 2    )






							def  UpperCamelCase__			(	self       ,		lowerCAmelCase__       ,		lowerCAmelCase__    ):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_						:			Union[str, Any]       						= j
										SCREAMING_SNAKE_CASE_						:			int       						= i
										SCREAMING_SNAKE_CASE_						:			Any       						= self.array[i]
										SCREAMING_SNAKE_CASE_						:			str       						= self.array[j]
										SCREAMING_SNAKE_CASE_						:			List[str]       						= temp






							def  UpperCamelCase__			(	self       ,		lowerCAmelCase__       ,		lowerCAmelCase__    ):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_						:			List[Any]       						= self.pos[tup[1]]
										# assuming the new_d is atmost old_d
										SCREAMING_SNAKE_CASE_						:			List[str]       						= (new_d, tup[1])
										while idx > 0 and self.array[self.par(lowerCAmelCase__    )][0] > self.array[idx][0]:
													self.swap(lowerCAmelCase__       ,		self.par(lowerCAmelCase__    )    )
													SCREAMING_SNAKE_CASE_						:			Dict       						= self.par(lowerCAmelCase__    )







class      __lowercase  :





							"""simple docstring"""







							def __init__(	self       ,		lowerCAmelCase__    ):





										"""simple docstring"""




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






							def  UpperCamelCase__			(	self       ,		lowerCAmelCase__       ,		lowerCAmelCase__       ,		lowerCAmelCase__    ):





										"""simple docstring"""




										if u in self.adjList:
													self.adjList[u].append((v, w)    )
										else:
													SCREAMING_SNAKE_CASE_						:			Optional[int]       						= [(v, w)]

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






							def  UpperCamelCase__			(	self    ):





										"""simple docstring"""




										for u in self.adjList:
													print(lowerCAmelCase__       ,		'->'       ,		' -> '.join(str(F'''{v}({w})'''    ) for v, w in self.adjList[u]    )    )






							def  UpperCamelCase__			(	self       ,		lowerCAmelCase__    ):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_						:			List[Any]       						= [-1] * self.num_nodes
										# src is the source node
										SCREAMING_SNAKE_CASE_						:			Dict       						= 0
										SCREAMING_SNAKE_CASE_						:			Dict       						= PriorityQueue()
										q.insert((0, src)    )  # (dist from src, node)
										for u in self.adjList:
													if u != src:
																SCREAMING_SNAKE_CASE_						:			Union[str, Any]       						= sys.maxsize  # Infinity
																SCREAMING_SNAKE_CASE_						:			Optional[int]       						= -1

										while not q.is_empty():
													SCREAMING_SNAKE_CASE_						:			Optional[Any]       						= 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]:
																SCREAMING_SNAKE_CASE_						:			Dict       						= 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)       ,		lowerCAmelCase__    )
																			SCREAMING_SNAKE_CASE_						:			Optional[int]       						= new_dist
																			SCREAMING_SNAKE_CASE_						:			List[Any]       						= u

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






							def  UpperCamelCase__			(	self       ,		lowerCAmelCase__    ):





										"""simple docstring"""




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






							def  UpperCamelCase__			(	self       ,		lowerCAmelCase__       ,		lowerCAmelCase__    ):





										"""simple docstring"""




										SCREAMING_SNAKE_CASE_						:			Optional[Any]       						= []
										SCREAMING_SNAKE_CASE_						:			Any       						= 0
										SCREAMING_SNAKE_CASE_						:			Optional[Any]       						= dest
										# Backtracking from dest to src
										while self.par[temp] != -1:
													path.append(lowerCAmelCase__    )
													if temp != src:
																for v, w in self.adjList[temp]:
																			if v == self.par[temp]:
																						cost += w
																						break
													SCREAMING_SNAKE_CASE_						:			Union[str, Any]       						= self.par[temp]
										path.append(lowerCAmelCase__    )
										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: '       ,		lowerCAmelCase__    )


if __name__ == "__main__":
				lowerCAmelCase__       :	Tuple     				=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 json
import os
from dataclasses import dataclass

import numpy as np
import pyarrow as pa

import datasets
from utils import get_duration


snake_case    =		1_0_0_0_0_0_0_0_0_0_0_0
snake_case    =		1_0_0_0_0

snake_case   ,			snake_case    =		os.path.split(__file__)
snake_case    =		os.path.join(RESULTS_BASEPATH, 'results', RESULTS_FILENAME.replace('.py', '.json'))

def   UpperCamelCase_  (		SCREAMING_SNAKE_CASE_,     SCREAMING_SNAKE_CASE_			):
					SCREAMING_SNAKE_CASE				=	pa.Table.from_pydict({'col': [0] * chunk_size}			)
					SCREAMING_SNAKE_CASE				=	pa.concat_tables([table] * (num_examples // chunk_size)			)
					return datasets.Dataset(SCREAMING_SNAKE_CASE_,     fingerprint='table_100B'			)




@dataclass
class      UpperCamelCase	:

				"""simple docstring"""



				UpperCAmelCase_				:      int
				UpperCAmelCase_				:      int
				UpperCAmelCase_				:      int
				UpperCAmelCase_				:      int


				def 							A					(				self			)    ->    Optional[Any]:
									"""simple docstring"""







									SCREAMING_SNAKE_CASE				=	np.random.default_rng(self.seed			)
									SCREAMING_SNAKE_CASE				=	rng.integers(low=self.low		,	high=self.high		,	size=self.size			).tolist()


				def __iter__(				self			)    ->    Union[str, Any]:
									"""simple docstring"""







									return iter(self._sampled_values			)




				def __len__(				self			)    ->    Optional[Any]:
									"""simple docstring"""







									return self.size






@get_duration
def   UpperCamelCase_  (		SCREAMING_SNAKE_CASE_			):
					SCREAMING_SNAKE_CASE				=	dataset[0]

@get_duration
def   UpperCamelCase_  (		SCREAMING_SNAKE_CASE_			):
					SCREAMING_SNAKE_CASE				=	dataset[-1]

@get_duration
def   UpperCamelCase_  (		SCREAMING_SNAKE_CASE_			):
					SCREAMING_SNAKE_CASE				=	dataset[range(len(SCREAMING_SNAKE_CASE_			) // 2,     len(SCREAMING_SNAKE_CASE_			) // 2 + 1_0_2_4			)]

@get_duration
def   UpperCamelCase_  (		SCREAMING_SNAKE_CASE_			):
					SCREAMING_SNAKE_CASE				=	dataset[RandIter(0,     len(SCREAMING_SNAKE_CASE_			),     1_0_2_4,     seed=4_2			)]

def   UpperCamelCase_  (		):
					SCREAMING_SNAKE_CASE				=	{'num examples': SPEED_TEST_N_EXAMPLES}
					SCREAMING_SNAKE_CASE				=	(get_first_row, get_last_row, get_batch_of_aaaa_rows, get_batch_of_aaaa_random_rows)
					print('generating dataset'			)
					SCREAMING_SNAKE_CASE				=	generate_100B_dataset(num_examples=SCREAMING_SNAKE_CASE_,     chunk_size=SCREAMING_SNAKE_CASE_			)
					print('Functions'			)
					for func in functions:
										print(func.__name__			)
										SCREAMING_SNAKE_CASE				=	func(SCREAMING_SNAKE_CASE_			)

					with open(SCREAMING_SNAKE_CASE_,     'wb'			) as f:
										f.write(json.dumps(SCREAMING_SNAKE_CASE_			).encode('utf-8'			)			)


if __name__ == "__main__":  # useful to run the profiler
	benchmark_table_100B()
