from collections import deque
from math import floor
from random import random
from time import time



class __A     :

							'''simple docstring'''

							def __init__(				self ):
												_lowerCAmelCase			:		Any          = {}






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case   ,	_snake_case   ,	_snake_case=1 ):

												if self.graph.get(_snake_case ):
																	if self.graph[u].count([w, v] ) == 0:
																						self.graph[u].append([w, v] )
												else:
																	_lowerCAmelCase			:		Optional[int]          = [[w, v]]
												if not self.graph.get(_snake_case ):
																	_lowerCAmelCase			:		List[Any]          = []






							def 	SCREAMING_SNAKE_CASE__			(				self ):
												return list(self.graph )






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case   ,	_snake_case ):

												if self.graph.get(_snake_case ):
																	for _ in self.graph[u]:
																						if _[1] == v:
																											self.graph[u].remove(_snake_case )






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case=-2   ,	_snake_case=-1 ):

												if s == d:
																	return []
												_lowerCAmelCase			:		Union[str, Any]          = []
												_lowerCAmelCase			:		List[Any]          = []
												if s == -2:
																	_lowerCAmelCase			:		Union[str, Any]          = list(self.graph )[0]
												stack.append(_snake_case )
												visited.append(_snake_case )
												_lowerCAmelCase			:		Any          = s

												while True:
																	# check if there is any non isolated nodes
																	if len(self.graph[s] ) != 0:
																						_lowerCAmelCase			:		Any          = s
																						for node in self.graph[s]:
																											if visited.count(node[1] ) < 1:
																																if node[1] == d:
																																					visited.append(_snake_case )
																																					return visited
																																else:
																																					stack.append(node[1] )
																																					visited.append(node[1] )
																																					_lowerCAmelCase			:		Any          = node[1]
																																					break

            # check if all the children are visited
																	if s == ss:
																						stack.pop()
																						if len(_snake_case ) != 0:
																											_lowerCAmelCase			:		List[str]          = stack[len(_snake_case ) - 1]
																	else:
																						_lowerCAmelCase			:		Optional[int]          = ss

																	# check if se have reached the starting point
																	if len(_snake_case ) == 0:
																						return visited






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case=-1 ):

												if c == -1:
																	_lowerCAmelCase			:		Optional[Any]          = floor(random() * 1_0000 ) + 10
												for i in range(_snake_case ):
																	# every vertex has max 100 edges
																	for _ in range(floor(random() * 102 ) + 1 ):
																						_lowerCAmelCase			:		Tuple          = floor(random() * c ) + 1
																						if n != i:
																											self.add_pair(_snake_case   ,	_snake_case   ,	1 )






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case=-2 ):
												_lowerCAmelCase			:		Optional[Any]          = deque()
												_lowerCAmelCase			:		Any          = []
												if s == -2:
																	_lowerCAmelCase			:		List[str]          = list(self.graph )[0]
												d.append(_snake_case )
												visited.append(_snake_case )
												while d:
																	_lowerCAmelCase			:		Dict          = d.popleft()
																	if len(self.graph[s] ) != 0:
																						for node in self.graph[s]:
																											if visited.count(node[1] ) < 1:
																																d.append(node[1] )
																																visited.append(node[1] )
												return visited






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case ):
												_lowerCAmelCase			:		Union[str, Any]          = 0
												for x in self.graph:
																	for y in self.graph[x]:
																						if y[1] == u:
																											count += 1
												return count






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case ):
												return len(self.graph[u] )






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case=-2 ):
												_lowerCAmelCase			:		List[str]          = []
												_lowerCAmelCase			:		Any          = []
												if s == -2:
																	_lowerCAmelCase			:		Optional[Any]          = list(self.graph )[0]
												stack.append(_snake_case )
												visited.append(_snake_case )
												_lowerCAmelCase			:		Tuple          = s
												_lowerCAmelCase			:		int          = []

												while True:
																	# check if there is any non isolated nodes
																	if len(self.graph[s] ) != 0:
																						_lowerCAmelCase			:		List[Any]          = s
																						for node in self.graph[s]:
																											if visited.count(node[1] ) < 1:
																																stack.append(node[1] )
																																visited.append(node[1] )
																																_lowerCAmelCase			:		Tuple          = node[1]
																																break

            # check if all the children are visited
																	if s == ss:
																						sorted_nodes.append(stack.pop() )
																						if len(_snake_case ) != 0:
																											_lowerCAmelCase			:		List[str]          = stack[len(_snake_case ) - 1]
																	else:
																						_lowerCAmelCase			:		List[Any]          = ss

																	# check if se have reached the starting point
																	if len(_snake_case ) == 0:
																						return sorted_nodes






							def 	SCREAMING_SNAKE_CASE__			(				self ):
												_lowerCAmelCase			:		Union[str, Any]          = []
												_lowerCAmelCase			:		Union[str, Any]          = []
												_lowerCAmelCase			:		Dict          = list(self.graph )[0]
												stack.append(_snake_case )
												visited.append(_snake_case )
												_lowerCAmelCase			:		Optional[Any]          = -2
												_lowerCAmelCase			:		Optional[Any]          = []
												_lowerCAmelCase			:		Dict          = s
												_lowerCAmelCase			:		int          = False
												_lowerCAmelCase			:		Tuple          = set()

												while True:
																	# check if there is any non isolated nodes
																	if len(self.graph[s] ) != 0:
																						_lowerCAmelCase			:		Optional[Any]          = s
																						for node in self.graph[s]:
																											if (
																											    visited.count(node[1] ) > 0
																											    and node[1] != parent
																											    and indirect_parents.count(node[1] ) > 0
																											    and not on_the_way_back
																											):
																																_lowerCAmelCase			:		Tuple          = len(_snake_case ) - 1
																																while len_stack >= 0:
																																					if stack[len_stack] == node[1]:
																																										anticipating_nodes.add(node[1] )
																																										break
																																					else:
																																										anticipating_nodes.add(stack[len_stack] )
																																										len_stack -= 1
																											if visited.count(node[1] ) < 1:
																																stack.append(node[1] )
																																visited.append(node[1] )
																																_lowerCAmelCase			:		Any          = node[1]
																																break

            # check if all the children are visited
																	if s == ss:
																						stack.pop()
																						_lowerCAmelCase			:		str          = True
																						if len(_snake_case ) != 0:
																											_lowerCAmelCase			:		List[Any]          = stack[len(_snake_case ) - 1]
																	else:
																						_lowerCAmelCase			:		Optional[Any]          = False
																						indirect_parents.append(_snake_case )
																						_lowerCAmelCase			:		Optional[Any]          = s
																						_lowerCAmelCase			:		Any          = ss

																	# check if se have reached the starting point
																	if len(_snake_case ) == 0:
																						return list(_snake_case )






							def 	SCREAMING_SNAKE_CASE__			(				self ):
												_lowerCAmelCase			:		int          = []
												_lowerCAmelCase			:		Optional[Any]          = []
												_lowerCAmelCase			:		int          = list(self.graph )[0]
												stack.append(_snake_case )
												visited.append(_snake_case )
												_lowerCAmelCase			:		int          = -2
												_lowerCAmelCase			:		str          = []
												_lowerCAmelCase			:		List[Any]          = s
												_lowerCAmelCase			:		Dict          = False
												_lowerCAmelCase			:		List[Any]          = set()

												while True:
																	# check if there is any non isolated nodes
																	if len(self.graph[s] ) != 0:
																						_lowerCAmelCase			:		Tuple          = s
																						for node in self.graph[s]:
																											if (
																											    visited.count(node[1] ) > 0
																											    and node[1] != parent
																											    and indirect_parents.count(node[1] ) > 0
																											    and not on_the_way_back
																											):
																																_lowerCAmelCase			:		Optional[int]          = len(_snake_case ) - 1
																																while len_stack_minus_one >= 0:
																																					if stack[len_stack_minus_one] == node[1]:
																																										anticipating_nodes.add(node[1] )
																																										break
																																					else:
																																										return True
																											if visited.count(node[1] ) < 1:
																																stack.append(node[1] )
																																visited.append(node[1] )
																																_lowerCAmelCase			:		Tuple          = node[1]
																																break

            # check if all the children are visited
																	if s == ss:
																						stack.pop()
																						_lowerCAmelCase			:		Optional[int]          = True
																						if len(_snake_case ) != 0:
																											_lowerCAmelCase			:		Dict          = stack[len(_snake_case ) - 1]
																	else:
																						_lowerCAmelCase			:		Optional[int]          = False
																						indirect_parents.append(_snake_case )
																						_lowerCAmelCase			:		Optional[Any]          = s
																						_lowerCAmelCase			:		Optional[int]          = ss

																	# check if se have reached the starting point
																	if len(_snake_case ) == 0:
																						return False






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case=-2   ,	_snake_case=-1 ):
												_lowerCAmelCase			:		Optional[int]          = time()
												self.dfs(_snake_case   ,	_snake_case )
												_lowerCAmelCase			:		int          = time()
												return end - begin






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case=-2 ):
												_lowerCAmelCase			:		Optional[int]          = time()
												self.bfs(_snake_case )
												_lowerCAmelCase			:		Any          = time()
												return end - begin



class __A     :

							'''simple docstring'''

							def __init__(				self ):
												_lowerCAmelCase			:		Tuple          = {}






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case   ,	_snake_case   ,	_snake_case=1 ):

												if self.graph.get(_snake_case ):
																	# if there already is a edge
																	if self.graph[u].count([w, v] ) == 0:
																						self.graph[u].append([w, v] )
												else:
																	# if u does not exist
																	_lowerCAmelCase			:		str          = [[w, v]]
												# add the other way
												if self.graph.get(_snake_case ):
																	# if there already is a edge
																	if self.graph[v].count([w, u] ) == 0:
																						self.graph[v].append([w, u] )
												else:
																	# if u does not exist
																	_lowerCAmelCase			:		Union[str, Any]          = [[w, u]]






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case   ,	_snake_case ):

												if self.graph.get(_snake_case ):
																	for _ in self.graph[u]:
																						if _[1] == v:
																											self.graph[u].remove(_snake_case )
        # the other way round
												if self.graph.get(_snake_case ):
																	for _ in self.graph[v]:
																						if _[1] == u:
																											self.graph[v].remove(_snake_case )






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case=-2   ,	_snake_case=-1 ):

												if s == d:
																	return []
												_lowerCAmelCase			:		Tuple          = []
												_lowerCAmelCase			:		Dict          = []
												if s == -2:
																	_lowerCAmelCase			:		Any          = list(self.graph )[0]
												stack.append(_snake_case )
												visited.append(_snake_case )
												_lowerCAmelCase			:		Any          = s

												while True:
																	# check if there is any non isolated nodes
																	if len(self.graph[s] ) != 0:
																						_lowerCAmelCase			:		int          = s
																						for node in self.graph[s]:
																											if visited.count(node[1] ) < 1:
																																if node[1] == d:
																																					visited.append(_snake_case )
																																					return visited
																																else:
																																					stack.append(node[1] )
																																					visited.append(node[1] )
																																					_lowerCAmelCase			:		List[Any]          = node[1]
																																					break

            # check if all the children are visited
																	if s == ss:
																						stack.pop()
																						if len(_snake_case ) != 0:
																											_lowerCAmelCase			:		int          = stack[len(_snake_case ) - 1]
																	else:
																						_lowerCAmelCase			:		List[str]          = ss

																	# check if se have reached the starting point
																	if len(_snake_case ) == 0:
																						return visited






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case=-1 ):

												if c == -1:
																	_lowerCAmelCase			:		Union[str, Any]          = floor(random() * 1_0000 ) + 10
												for i in range(_snake_case ):
																	# every vertex has max 100 edges
																	for _ in range(floor(random() * 102 ) + 1 ):
																						_lowerCAmelCase			:		List[str]          = floor(random() * c ) + 1
																						if n != i:
																											self.add_pair(_snake_case   ,	_snake_case   ,	1 )






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case=-2 ):
												_lowerCAmelCase			:		Any          = deque()
												_lowerCAmelCase			:		Dict          = []
												if s == -2:
																	_lowerCAmelCase			:		int          = list(self.graph )[0]
												d.append(_snake_case )
												visited.append(_snake_case )
												while d:
																	_lowerCAmelCase			:		int          = d.popleft()
																	if len(self.graph[s] ) != 0:
																						for node in self.graph[s]:
																											if visited.count(node[1] ) < 1:
																																d.append(node[1] )
																																visited.append(node[1] )
												return visited






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case ):
												return len(self.graph[u] )






							def 	SCREAMING_SNAKE_CASE__			(				self ):
												_lowerCAmelCase			:		Any          = []
												_lowerCAmelCase			:		Optional[Any]          = []
												_lowerCAmelCase			:		List[Any]          = list(self.graph )[0]
												stack.append(_snake_case )
												visited.append(_snake_case )
												_lowerCAmelCase			:		Tuple          = -2
												_lowerCAmelCase			:		int          = []
												_lowerCAmelCase			:		Any          = s
												_lowerCAmelCase			:		str          = False
												_lowerCAmelCase			:		Tuple          = set()

												while True:
																	# check if there is any non isolated nodes
																	if len(self.graph[s] ) != 0:
																						_lowerCAmelCase			:		List[str]          = s
																						for node in self.graph[s]:
																											if (
																											    visited.count(node[1] ) > 0
																											    and node[1] != parent
																											    and indirect_parents.count(node[1] ) > 0
																											    and not on_the_way_back
																											):
																																_lowerCAmelCase			:		Any          = len(_snake_case ) - 1
																																while len_stack >= 0:
																																					if stack[len_stack] == node[1]:
																																										anticipating_nodes.add(node[1] )
																																										break
																																					else:
																																										anticipating_nodes.add(stack[len_stack] )
																																										len_stack -= 1
																											if visited.count(node[1] ) < 1:
																																stack.append(node[1] )
																																visited.append(node[1] )
																																_lowerCAmelCase			:		Union[str, Any]          = node[1]
																																break

            # check if all the children are visited
																	if s == ss:
																						stack.pop()
																						_lowerCAmelCase			:		int          = True
																						if len(_snake_case ) != 0:
																											_lowerCAmelCase			:		int          = stack[len(_snake_case ) - 1]
																	else:
																						_lowerCAmelCase			:		str          = False
																						indirect_parents.append(_snake_case )
																						_lowerCAmelCase			:		Any          = s
																						_lowerCAmelCase			:		Union[str, Any]          = ss

																	# check if se have reached the starting point
																	if len(_snake_case ) == 0:
																						return list(_snake_case )






							def 	SCREAMING_SNAKE_CASE__			(				self ):
												_lowerCAmelCase			:		int          = []
												_lowerCAmelCase			:		Dict          = []
												_lowerCAmelCase			:		Union[str, Any]          = list(self.graph )[0]
												stack.append(_snake_case )
												visited.append(_snake_case )
												_lowerCAmelCase			:		Optional[Any]          = -2
												_lowerCAmelCase			:		Optional[Any]          = []
												_lowerCAmelCase			:		List[str]          = s
												_lowerCAmelCase			:		List[Any]          = False
												_lowerCAmelCase			:		str          = set()

												while True:
																	# check if there is any non isolated nodes
																	if len(self.graph[s] ) != 0:
																						_lowerCAmelCase			:		Optional[int]          = s
																						for node in self.graph[s]:
																											if (
																											    visited.count(node[1] ) > 0
																											    and node[1] != parent
																											    and indirect_parents.count(node[1] ) > 0
																											    and not on_the_way_back
																											):
																																_lowerCAmelCase			:		Optional[int]          = len(_snake_case ) - 1
																																while len_stack_minus_one >= 0:
																																					if stack[len_stack_minus_one] == node[1]:
																																										anticipating_nodes.add(node[1] )
																																										break
																																					else:
																																										return True
																											if visited.count(node[1] ) < 1:
																																stack.append(node[1] )
																																visited.append(node[1] )
																																_lowerCAmelCase			:		List[Any]          = node[1]
																																break

            # check if all the children are visited
																	if s == ss:
																						stack.pop()
																						_lowerCAmelCase			:		List[Any]          = True
																						if len(_snake_case ) != 0:
																											_lowerCAmelCase			:		List[str]          = stack[len(_snake_case ) - 1]
																	else:
																						_lowerCAmelCase			:		List[str]          = False
																						indirect_parents.append(_snake_case )
																						_lowerCAmelCase			:		int          = s
																						_lowerCAmelCase			:		str          = ss

																	# check if se have reached the starting point
																	if len(_snake_case ) == 0:
																						return False






							def 	SCREAMING_SNAKE_CASE__			(				self ):
												return list(self.graph )






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case=-2   ,	_snake_case=-1 ):
												_lowerCAmelCase			:		List[str]          = time()
												self.dfs(_snake_case   ,	_snake_case )
												_lowerCAmelCase			:		str          = time()
												return end - begin






							def 	SCREAMING_SNAKE_CASE__			(				self   ,	_snake_case=-2 ):
												_lowerCAmelCase			:		int          = time()
												self.bfs(_snake_case )
												_lowerCAmelCase			:		Any          = time()
												return end - begin








import os
from typing import BinaryIO, Optional, Union

import numpy as np
import pyarrow.parquet as pq

from .. import Audio, Dataset, Features, Image, NamedSplit, Value, config
from ..features.features import FeatureType, _visit
from ..formatting import query_table
from ..packaged_modules import _PACKAGED_DATASETS_MODULES
from ..packaged_modules.parquet.parquet import Parquet
from ..utils import logging
from ..utils.typing import NestedDataStructureLike, PathLike
from .abc import AbstractDatasetReader


def 				__A(lowerCAmelCase			)		->					Optional[int]:

		"""simple docstring"""






		_UpperCamelCase         =						np.inf

		def set_batch_size(lowerCAmelCase			) -> None:
				nonlocal batch_size
				if isinstance(lowerCAmelCase    ,	lowerCAmelCase			):
						_UpperCamelCase         =						min(lowerCAmelCase    ,	config.PARQUET_ROW_GROUP_SIZE_FOR_IMAGE_DATASETS			)
				elif isinstance(lowerCAmelCase    ,	lowerCAmelCase			):
						_UpperCamelCase         =						min(lowerCAmelCase    ,	config.PARQUET_ROW_GROUP_SIZE_FOR_AUDIO_DATASETS			)
				elif isinstance(lowerCAmelCase    ,	lowerCAmelCase			) and feature.dtype == "binary":
						_UpperCamelCase         =						min(lowerCAmelCase    ,	config.PARQUET_ROW_GROUP_SIZE_FOR_BINARY_DATASETS			)

		_visit(lowerCAmelCase    ,	lowerCAmelCase			)

		return None if batch_size is np.inf else batch_size







class 							lowerCAmelCase__   ( __lowercase						):

						def __init__(      self							,				a							,				a = None							,				a = None							,				a = None							,				a = False							,				a = False							,				a = None							,				**a							,				)       ->   Tuple:


								'''simple docstring'''

								super().__init__(
								    a							,				split=a							,				features=a							,				cache_dir=a							,				keep_in_memory=a							,				streaming=a							,				num_proc=a							,				**a							,				)
								_UpperCamelCase         =						path_or_paths if isinstance(a							,				a					) else {self.split: path_or_paths}
								_UpperCamelCase         =						_PACKAGED_DATASETS_MODULES["""parquet"""][1]
								_UpperCamelCase         =						Parquet(
								    cache_dir=a							,				data_files=a							,				features=a							,				hash=a							,				**a							,				)







						def 			A_					(      self					)       ->   Optional[int]:


								'''simple docstring'''

								if self.streaming:
										_UpperCamelCase         =						self.builder.as_streaming_dataset(split=self.split					)
								# Build regular (map-style) dataset
								else:
										_UpperCamelCase         =						None
										_UpperCamelCase         =						None
										_UpperCamelCase         =						None
										_UpperCamelCase         =						None

										self.builder.download_and_prepare(
										    download_config=a							,				download_mode=a							,				verification_mode=a							,				base_path=a							,				num_proc=self.num_proc							,				)
										_UpperCamelCase         =						self.builder.as_dataset(
										    split=self.split							,				verification_mode=a							,				in_memory=self.keep_in_memory					)
								return dataset







class 							lowerCAmelCase__   :

						def __init__(      self							,				a							,				a							,				a = None							,				**a							,				)       ->   str:


								'''simple docstring'''

								_UpperCamelCase         =						dataset
								_UpperCamelCase         =						path_or_buf
								_UpperCamelCase         =						batch_size or get_writer_batch_size(dataset.features					)
								_UpperCamelCase         =						parquet_writer_kwargs

						def 			A_					(      self					)       ->   int:


								'''simple docstring'''

								_UpperCamelCase         =						self.batch_size if self.batch_size else config.DEFAULT_MAX_BATCH_SIZE

								if isinstance(self.path_or_buf							,				(str, bytes, os.PathLike)					):
										with open(self.path_or_buf							,				"""wb+"""					) as buffer:
												_UpperCamelCase         =						self._write(file_obj=a							,				batch_size=a							,				**self.parquet_writer_kwargs					)
								else:
										_UpperCamelCase         =						self._write(file_obj=self.path_or_buf							,				batch_size=a							,				**self.parquet_writer_kwargs					)
								return written







						def 			A_					(      self							,				a							,				a							,				**a					)       ->   int:


								'''simple docstring'''

								_UpperCamelCase         =						0
								_UpperCamelCase         =						parquet_writer_kwargs.pop("""path_or_buf"""							,				a					)
								_UpperCamelCase         =						self.dataset.features.arrow_schema

								_UpperCamelCase         =						pq.ParquetWriter(a							,				schema=a							,				**a					)

								for offset in logging.tqdm(
								    range(0							,				len(self.dataset					)							,				a					)							,				unit="""ba"""							,				disable=not logging.is_progress_bar_enabled()							,				desc="""Creating parquet from Arrow format"""							,				):
										_UpperCamelCase         =						query_table(
										    table=self.dataset._data							,				key=slice(a							,				offset + batch_size					)							,				indices=self.dataset._indices if self.dataset._indices is not None else None							,				)
										writer.write_table(a					)
										written += batch.nbytes
								writer.close()
								return written



