



import asyncio
import os
import re
import sys
import tempfile
import unittest
from contextlib import contextmanager
from copy import deepcopy
from distutils.util import strtobool
from enum import Enum
from importlib.util import find_spec
from pathlib import Path
from unittest.mock import patch

import pyarrow as pa
import pytest
import requests
from packaging import version

from datasets import config


if config.PY_VERSION < version.parse("""3.8"""):
	import importlib_metadata
else:
	import importlib.metadata as importlib_metadata



def    snake_case_				(    _SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE=False   ):






	try:
		__lowercase		       =			os.environ[key]
	except KeyError:
		# KEY isn't set, default to `default`.
		__lowercase		       =			default
	else:
		# KEY is set, convert it to True or False.
		try:
			__lowercase		       =			strtobool(_snake_case   )
		except ValueError:
			# More values are supported, but let's keep the message simple.
			raise ValueError(F"""If set, {key} must be yes or no."""   )
	return _value


snake_case__					:     Optional[Any]    		=   parse_flag_from_env("""RUN_SLOW""", default=False)
snake_case__					:     List[Any]    		=   parse_flag_from_env("""RUN_REMOTE""", default=False)
snake_case__					:     Dict    		=   parse_flag_from_env("""RUN_LOCAL""", default=True)
snake_case__					:     List[Any]    		=   parse_flag_from_env("""RUN_PACKAGED""", default=True)

# Compression
snake_case__					:     str    		=   pytest.mark.skipif(not config.LZ4_AVAILABLE, reason="""test requires lz4""")
snake_case__					:     List[str]    		=   pytest.mark.skipif(not config.PY7ZR_AVAILABLE, reason="""test requires py7zr""")
snake_case__					:     Optional[int]    		=   pytest.mark.skipif(not config.ZSTANDARD_AVAILABLE, reason="""test requires zstandard""")

# Audio
snake_case__					:     Dict    		=   pytest.mark.skipif(
    # On Windows and OS X, soundfile installs sndfile
    find_spec("""soundfile""") is None or version.parse(importlib_metadata.version("""soundfile""")) < version.parse("""0.12.0"""),
    reason="""test requires sndfile>=0.12.1: 'pip install \"soundfile>=0.12.1\"'; """,
)

# Beam
snake_case__					:     Tuple    		=   pytest.mark.skipif(
    not config.BEAM_AVAILABLE or config.DILL_VERSION >= version.parse("""0.3.2"""),
    reason="""test requires apache-beam and a compatible dill version""",
)

# Dill-cloudpickle compatibility
snake_case__					:     List[Any]    		=   pytest.mark.skipif(
    config.DILL_VERSION <= version.parse("""0.3.2"""),
    reason="""test requires dill>0.3.2 for cloudpickle compatibility""",
)

# Windows
snake_case__					:     List[Any]    		=   pytest.mark.skipif(
    sys.platform == """win32""",
    reason="""test should not be run on Windows""",
)



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	try:
		import faiss  # noqa
	except ImportError:
		__lowercase		       =			unittest.skip("test requires faiss"   )(_snake_case   )
	return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	try:
		import regex  # noqa
	except ImportError:
		__lowercase		       =			unittest.skip("test requires regex"   )(_snake_case   )
	return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	try:
		import elasticsearch  # noqa
	except ImportError:
		__lowercase		       =			unittest.skip("test requires elasticsearch"   )(_snake_case   )
	return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	try:
		import sqlalchemy  # noqa
	except ImportError:
		__lowercase		       =			unittest.skip("test requires sqlalchemy"   )(_snake_case   )
	return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	if not config.TORCH_AVAILABLE:
		__lowercase		       =			unittest.skip("test requires PyTorch"   )(_snake_case   )
	return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	if not config.TF_AVAILABLE:
		__lowercase		       =			unittest.skip("test requires TensorFlow"   )(_snake_case   )
	return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	if not config.JAX_AVAILABLE:
		__lowercase		       =			unittest.skip("test requires JAX"   )(_snake_case   )
	return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	if not config.PIL_AVAILABLE:
		__lowercase		       =			unittest.skip("test requires Pillow"   )(_snake_case   )
	return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	try:
		import transformers  # noqa F401
	except ImportError:
		return unittest.skip("test requires transformers"   )(_snake_case   )
	else:
		return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	try:
		import tiktoken  # noqa F401
	except ImportError:
		return unittest.skip("test requires tiktoken"   )(_snake_case   )
	else:
		return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	try:
		import spacy  # noqa F401
	except ImportError:
		return unittest.skip("test requires spacy"   )(_snake_case   )
	else:
		return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	def _require_spacy_model(_SCREAMING_SNAKE_CASE   ):
		try:
			import spacy  # noqa F401

			spacy.load(_snake_case   )
		except ImportError:
			return unittest.skip("test requires spacy"   )(_snake_case   )
		except OSError:
			return unittest.skip("test requires spacy model '{}'".format(_snake_case   )   )(_snake_case   )
		else:
			return test_case

	return _require_spacy_model



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	try:
		import pyspark  # noqa F401
	except ImportError:
		return unittest.skip("test requires pyspark"   )(_snake_case   )
	else:
		return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	try:
		import joblibspark  # noqa F401
	except ImportError:
		return unittest.skip("test requires joblibspark"   )(_snake_case   )
	else:
		return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	if not _run_slow_tests or _run_slow_tests == 0:
		__lowercase		       =			unittest.skip("test is slow"   )(_snake_case   )
	return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	if not _run_local_tests or _run_local_tests == 0:
		__lowercase		       =			unittest.skip("test is local"   )(_snake_case   )
	return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	if not _run_packaged_tests or _run_packaged_tests == 0:
		__lowercase		       =			unittest.skip("test is packaged"   )(_snake_case   )
	return test_case



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):






	if not _run_remote_tests or _run_remote_tests == 0:
		__lowercase		       =			unittest.skip("test requires remote"   )(_snake_case   )
	return test_case



def    snake_case_				(    *_SCREAMING_SNAKE_CASE   ):






	def decorate(cls   ):
		for name, fn in cls.__dict__.items():
			if callable(_snake_case   ) and name.startswith("test"   ):
				for decorator in decorators:
					__lowercase		       =			decorator(_snake_case   )
				setattr(cls  ,	_snake_case  ,	_snake_case   )
		return cls

	return decorate

class   _A   ( _lowercase	):


						'''simple docstring'''





						pass


class   _A   ( _lowercase	):


						'''simple docstring'''





						_snake_case			:     Tuple      							=      0
						_snake_case			:     Optional[Any]      							=      1
						_snake_case			:     Dict      							=      2



@contextmanager
def    snake_case_				(    _SCREAMING_SNAKE_CASE=OfflineSimulationMode.CONNECTION_FAILS  ,	_SCREAMING_SNAKE_CASE=1E-1_6   ):
	__lowercase		       =			requests.Session().request

	def timeout_request(_SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE  ,	**_SCREAMING_SNAKE_CASE   ):
		# Change the url to an invalid url so that the connection hangs
		__lowercase		       =			"https://10.255.255.1"
		if kwargs.get("timeout"   ) is None:
			raise RequestWouldHangIndefinitelyError(
			    F"""Tried a call to {url} in offline mode with no timeout set. Please set a timeout."""   )
		__lowercase		       =			timeout
		try:
			return online_request(_snake_case  ,	_snake_case  ,	**_snake_case   )
		except Exception as e:
			# The following changes in the error are just here to make the offline timeout error prettier
			__lowercase		       =			url
			__lowercase		       =			e.args[0]
			__lowercase		       =			(max_retry_error.args[0].replace("10.255.255.1"  ,	F"""OfflineMock[{url}]"""   ),)
			__lowercase		       =			(max_retry_error,)
			raise

	def raise_connection_error(_SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE  ,	**_SCREAMING_SNAKE_CASE   ):
		raise requests.ConnectionError("Offline mode is enabled."  ,	request=_snake_case   )

	if mode is OfflineSimulationMode.CONNECTION_FAILS:
		with patch("requests.Session.send"  ,	_snake_case   ):
			yield
	elif mode is OfflineSimulationMode.CONNECTION_TIMES_OUT:
		# inspired from https://stackoverflow.com/a/904609
		with patch("requests.Session.request"  ,	_snake_case   ):
			yield
	elif mode is OfflineSimulationMode.HF_DATASETS_OFFLINE_SET_TO_1:
		with patch("datasets.config.HF_DATASETS_OFFLINE"  ,	_snake_case   ):
			yield
	else:
		raise ValueError("Please use a value from the OfflineSimulationMode enum."   )



@contextmanager
def    snake_case_				(    *_SCREAMING_SNAKE_CASE  ,	**_SCREAMING_SNAKE_CASE   ):
	__lowercase		       =			str(Path().resolve()   )
	with tempfile.TemporaryDirectory(*_snake_case  ,	**_snake_case   ) as tmp_dir:
		try:
			os.chdir(_snake_case   )
			yield
		finally:
			os.chdir(_snake_case   )



@contextmanager
def    snake_case_				(    ):
	import gc

	gc.collect()
	__lowercase		       =			pa.total_allocated_bytes()
	yield
	assert pa.total_allocated_bytes() - previous_allocated_memory > 0, "Arrow memory didn't increase."



@contextmanager
def    snake_case_				(    ):
	import gc

	gc.collect()
	__lowercase		       =			pa.total_allocated_bytes()
	yield
	assert pa.total_allocated_bytes() - previous_allocated_memory <= 0, "Arrow memory wasn't expected to increase."



def    snake_case_				(    _SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE   ):
	return deepcopy(_snake_case   ).integers(0  ,	1_0_0  ,	1_0   ).tolist() == deepcopy(_snake_case   ).integers(0  ,	1_0_0  ,	1_0   ).tolist()



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):
	import decorator
	from requests.exceptions import HTTPError

	def _wrapper(_SCREAMING_SNAKE_CASE  ,	*_SCREAMING_SNAKE_CASE  ,	**_SCREAMING_SNAKE_CASE   ):
		try:
			return func(*_snake_case  ,	**_snake_case   )
		except HTTPError as err:
			if str(_snake_case   ).startswith("500"   ) or str(_snake_case   ).startswith("502"   ):
				pytest.xfail(str(_snake_case   )   )
			raise err

	return decorator.decorator(_wrapper  ,	_snake_case   )

class   _A   :


						'''simple docstring'''





						def __init__(	self	:							List[str]							,      lowerCamelCase	:							Dict							,      lowerCamelCase	:							str							,      lowerCamelCase	:							Any	):






							'''simple docstring'''



							__lowercase		       =			returncode
							__lowercase		       =			stdout
							__lowercase		       =			stderr



async def    snake_case_				(    _SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE   ):






	while True:
		__lowercase		       =			await stream.readline()
		if line:
			callback(_snake_case   )
		else:
			break



async def    snake_case_				(    _SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE=None  ,	_SCREAMING_SNAKE_CASE=None  ,	_SCREAMING_SNAKE_CASE=None  ,	_SCREAMING_SNAKE_CASE=False  ,	_SCREAMING_SNAKE_CASE=False   ):






	if echo:
		print("\nRunning: "  ,	" ".join(_snake_case   )   )

	__lowercase		       =			await asyncio.create_subprocess_exec(
	    cmd[0]  ,	*cmd[1:]  ,	stdin=_snake_case  ,	stdout=asyncio.subprocess.PIPE  ,	stderr=asyncio.subprocess.PIPE  ,	env=_snake_case  ,	)

	# note: there is a warning for a possible deadlock when using `wait` with huge amounts of data in the pipe
	# https://docs.python.org/3/library/asyncio-subprocess.html#asyncio.asyncio.subprocess.Process.wait
	#
	# If it starts hanging, will need to switch to the following code. The problem is that no data
	# will be seen until it's done and if it hangs for example there will be no debug info.
	# out, err = await p.communicate()
	# return _RunOutput(p.returncode, out, err)

	__lowercase		       =			[]
	__lowercase		       =			[]

	def tee(_SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE=""   ):
		__lowercase		       =			line.decode("utf-8"   ).rstrip()
		sink.append(_snake_case   )
		if not quiet:
			print(_snake_case  ,	_snake_case  ,	file=_snake_case   )

    # XXX: the timeout doesn't seem to make any difference here
	await asyncio.wait(
	    [
	        _read_stream(p.stdout  ,	lambda _SCREAMING_SNAKE_CASE   : tee(_snake_case  ,	_snake_case  ,	sys.stdout  ,	label="stdout:"   )   ),
	        _read_stream(p.stderr  ,	lambda _SCREAMING_SNAKE_CASE   : tee(_snake_case  ,	_snake_case  ,	sys.stderr  ,	label="stderr:"   )   ),
	    ]  ,	timeout=_snake_case  ,	)
	return _RunOutput(await p.wait()  ,	_snake_case  ,	_snake_case   )



def    snake_case_				(    _SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE=None  ,	_SCREAMING_SNAKE_CASE=None  ,	_SCREAMING_SNAKE_CASE=1_8_0  ,	_SCREAMING_SNAKE_CASE=False  ,	_SCREAMING_SNAKE_CASE=True   ):
	__lowercase		       =			asyncio.get_event_loop()
	__lowercase		       =			loop.run_until_complete(
	    _stream_subprocess(_snake_case  ,	env=_snake_case  ,	stdin=_snake_case  ,	timeout=_snake_case  ,	quiet=_snake_case  ,	echo=_snake_case   )   )

	__lowercase		       =			" ".join(_snake_case   )
	if result.returncode > 0:
		__lowercase		       =			"\n".join(result.stderr   )
		raise RuntimeError(
		    F"""\'{cmd_str}\' failed with returncode {result.returncode}\n\n"""
		    F"""The combined stderr from workers follows:\n{stderr}"""   )

	# check that the subprocess actually did run and produced some output, should the test rely on
	# the remote side to do the testing
	if not result.stdout and not result.stderr:
		raise RuntimeError(F"""\'{cmd_str}\' produced no output."""   )

	return result



def    snake_case_				(    ):
	__lowercase		       =			os.environ.get("PYTEST_XDIST_WORKER"  ,	"gw0"   )
	__lowercase		       =			re.sub(R"^gw"  ,	""  ,	_snake_case  ,	0  ,	re.M   )
	return int(_snake_case   )



def    snake_case_				(    ):
	__lowercase		       =			2_9_5_0_0
	__lowercase		       =			pytest_xdist_worker_id()
	return port + uniq_delta








from __future__ import annotations

from collections import namedtuple
from dataclasses import dataclass

@dataclass
class   _A   :


						'''simple docstring'''





						_snake_case			:     int
						_snake_case			:     TreeNode | None      							=      None
						_snake_case			:     TreeNode | None      							=      None

snake_case__					:     Dict    		=   namedtuple("""CoinsDistribResult""", """moves excess""")



def    snake_case_				(    _SCREAMING_SNAKE_CASE   ):

	if root is None:
		return 0

	# Validation
	def count_nodes(_SCREAMING_SNAKE_CASE   ) -> int:
		if node is None:
			return 0

		return count_nodes(node.left   ) + count_nodes(node.right   ) + 1

	def count_coins(_SCREAMING_SNAKE_CASE   ) -> int:
		if node is None:
			return 0

		return count_coins(node.left   ) + count_coins(node.right   ) + node.data

	if count_nodes(_SCREAMING_SNAKE_CASE   ) != count_coins(_SCREAMING_SNAKE_CASE   ):
		raise ValueError("The nodes number should be same as the number of coins"   )

	# Main calculation
	def get_distrib(_SCREAMING_SNAKE_CASE   ) -> CoinsDistribResult:

		if node is None:
			return CoinsDistribResult(0  ,	1   )

		__lowercase       ,    __lowercase		       =			get_distrib(node.left   )
		__lowercase       ,    __lowercase		       =			get_distrib(node.right   )

		__lowercase		       =			1 - left_distrib_excess
		__lowercase		       =			1 - right_distrib_excess

		__lowercase		       =			(
		    left_distrib_moves
		    + right_distrib_moves
		    + abs(_SCREAMING_SNAKE_CASE   )
		    + abs(_SCREAMING_SNAKE_CASE   )
		)
		__lowercase		       =			node.data - coins_to_left - coins_to_right

		return CoinsDistribResult(_SCREAMING_SNAKE_CASE  ,	_SCREAMING_SNAKE_CASE   )

	return get_distrib(_SCREAMING_SNAKE_CASE   )[0]


if __name__ == "__main__":
	import doctest

	doctest.testmod()



