


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 							UpperCamelCase_(					_A :Dict					,  _A :int=False	)->		Dict:
			try:
						UpperCamelCase__       =							os.environ[key]
			except KeyError:
						# KEY isn't set, default to `default`.
						UpperCamelCase__       =							default
			else:
						# KEY is set, convert it to True or False.
						try:
									UpperCamelCase__       =							strtobool(_A	)
						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


__UpperCamelCase     		=							parse_flag_from_env('RUN_SLOW', default=False)
__UpperCamelCase     		=							parse_flag_from_env('RUN_REMOTE', default=False)
__UpperCamelCase     		=							parse_flag_from_env('RUN_LOCAL', default=True)
__UpperCamelCase     		=							parse_flag_from_env('RUN_PACKAGED', default=True)

# Compression
__UpperCamelCase     		=							pytest.mark.skipif(not config.LZ4_AVAILABLE, reason='test requires lz4')
__UpperCamelCase     		=							pytest.mark.skipif(not config.PY7ZR_AVAILABLE, reason='test requires py7zr')
__UpperCamelCase     		=							pytest.mark.skipif(not config.ZSTANDARD_AVAILABLE, reason='test requires zstandard')

# Audio
__UpperCamelCase     		=							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
__UpperCamelCase     		=							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
__UpperCamelCase     		=							pytest.mark.skipif(
    config.DILL_VERSION <= version.parse('0.3.2'),
    reason='test requires dill>0.3.2 for cloudpickle compatibility',
)

# Windows
__UpperCamelCase     		=							pytest.mark.skipif(
    sys.platform == 'win32',
    reason='test should not be run on Windows',
)
def 							UpperCamelCase_(					_A :List[Any]	)->		Union[str, Any]:
			try:
						import faiss  # noqa
			except ImportError:
						UpperCamelCase__       =							unittest.skip("test requires faiss"	)(_A	)
			return test_case
def 							UpperCamelCase_(					_A :List[Any]	)->		Union[str, Any]:
			try:
						import regex  # noqa
			except ImportError:
						UpperCamelCase__       =							unittest.skip("test requires regex"	)(_A	)
			return test_case
def 							UpperCamelCase_(					_A :List[Any]	)->		List[str]:
			try:
						import elasticsearch  # noqa
			except ImportError:
						UpperCamelCase__       =							unittest.skip("test requires elasticsearch"	)(_A	)
			return test_case
def 							UpperCamelCase_(					_A :List[str]	)->		Union[str, Any]:
			try:
						import sqlalchemy  # noqa
			except ImportError:
						UpperCamelCase__       =							unittest.skip("test requires sqlalchemy"	)(_A	)
			return test_case
def 							UpperCamelCase_(					_A :int	)->		Any:
			if not config.TORCH_AVAILABLE:
						UpperCamelCase__       =							unittest.skip("test requires PyTorch"	)(_A	)
			return test_case
def 							UpperCamelCase_(					_A :str	)->		List[Any]:
			if not config.TF_AVAILABLE:
						UpperCamelCase__       =							unittest.skip("test requires TensorFlow"	)(_A	)
			return test_case
def 							UpperCamelCase_(					_A :List[Any]	)->		Tuple:
			if not config.JAX_AVAILABLE:
						UpperCamelCase__       =							unittest.skip("test requires JAX"	)(_A	)
			return test_case
def 							UpperCamelCase_(					_A :Any	)->		Dict:
			if not config.PIL_AVAILABLE:
						UpperCamelCase__       =							unittest.skip("test requires Pillow"	)(_A	)
			return test_case
def 							UpperCamelCase_(					_A :List[str]	)->		int:
			try:
						import transformers  # noqa F401
			except ImportError:
						return unittest.skip("test requires transformers"	)(_A	)
			else:
						return test_case
def 							UpperCamelCase_(					_A :Tuple	)->		int:
			try:
						import tiktoken  # noqa F401
			except ImportError:
						return unittest.skip("test requires tiktoken"	)(_A	)
			else:
						return test_case
def 							UpperCamelCase_(					_A :Optional[Any]	)->		Any:
			try:
						import spacy  # noqa F401
			except ImportError:
						return unittest.skip("test requires spacy"	)(_A	)
			else:
						return test_case
def 							UpperCamelCase_(					_A :str	)->		str:

			def _require_spacy_model(_A :Optional[Any]	):
						try:
									import spacy  # noqa F401

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

			return _require_spacy_model
def 							UpperCamelCase_(					_A :str	)->		List[str]:
			try:
						import pyspark  # noqa F401
			except ImportError:
						return unittest.skip("test requires pyspark"	)(_A	)
			else:
						return test_case
def 							UpperCamelCase_(					_A :Tuple	)->		Optional[int]:
			try:
						import joblibspark  # noqa F401
			except ImportError:
						return unittest.skip("test requires joblibspark"	)(_A	)
			else:
						return test_case
def 							UpperCamelCase_(					_A :Tuple	)->		List[Any]:
			if not _run_slow_tests or _run_slow_tests == 0:
						UpperCamelCase__       =							unittest.skip("test is slow"	)(_A	)
			return test_case
def 							UpperCamelCase_(					_A :Union[str, Any]	)->		Optional[Any]:
			if not _run_local_tests or _run_local_tests == 0:
						UpperCamelCase__       =							unittest.skip("test is local"	)(_A	)
			return test_case
def 							UpperCamelCase_(					_A :Union[str, Any]	)->		Dict:
			if not _run_packaged_tests or _run_packaged_tests == 0:
						UpperCamelCase__       =							unittest.skip("test is packaged"	)(_A	)
			return test_case
def 							UpperCamelCase_(					_A :Optional[int]	)->		List[Any]:
			if not _run_remote_tests or _run_remote_tests == 0:
						UpperCamelCase__       =							unittest.skip("test requires remote"	)(_A	)
			return test_case
def 							UpperCamelCase_(					*_A :str	)->		Optional[int]:
			def decorate(cls :Any	):
						for name, fn in cls.__dict__.items():
									if callable(_A	) and name.startswith("test"	):
												for decorator in decorators:
															UpperCamelCase__       =							decorator(_A	)
												setattr(cls					,  _A					,  _A	)
						return cls

			return decorate







class 							lowerCamelCase__						(				UpperCAmelCase   ):






			"""simple docstring"""






			pass







class 							lowerCamelCase__						(				UpperCAmelCase   ):






			"""simple docstring"""






			_UpperCamelCase		:       Union[str, Any] 			=		0
			_UpperCamelCase		:       str 			=		1
			_UpperCamelCase		:       str 			=		2



@contextmanager
def 							UpperCamelCase_(					_A :List[Any]=OfflineSimulationMode.CONNECTION_FAILS					,  _A :Dict=1e-16	)->		Optional[Any]:
			UpperCamelCase__       =							requests.Session().request

			def timeout_request(_A :Optional[Any]					,  _A :List[Any]					,  _A :Optional[Any]					,  **_A :Any	):
						# Change the url to an invalid url so that the connection hangs
						UpperCamelCase__       =							"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.'''	)
						UpperCamelCase__       =							timeout
						try:
									return online_request(_A					,  _A					,  **_A	)
						except Exception as e:
									# The following changes in the error are just here to make the offline timeout error prettier
									UpperCamelCase__       =							url
									UpperCamelCase__       =							e.args[0]
									UpperCamelCase__       =							(max_retry_error.args[0].replace("10.255.255.1"					,  F'''OfflineMock[{url}]'''	),)
									UpperCamelCase__       =							(max_retry_error,)
									raise

			def raise_connection_error(_A :Union[str, Any]					,  _A :Dict					,  **_A :Optional[Any]	):
						raise requests.ConnectionError("Offline mode is enabled."					,  request=_A	)

			if mode is OfflineSimulationMode.CONNECTION_FAILS:
						with patch("requests.Session.send"					,  _A	):
									yield
			elif mode is OfflineSimulationMode.CONNECTION_TIMES_OUT:
						# inspired from https://stackoverflow.com/a/904609
						with patch("requests.Session.request"					,  _A	):
									yield
			elif mode is OfflineSimulationMode.HF_DATASETS_OFFLINE_SET_TO_1:
						with patch("datasets.config.HF_DATASETS_OFFLINE"					,  _A	):
									yield
			else:
						raise ValueError("Please use a value from the OfflineSimulationMode enum."	)
@contextmanager
def 							UpperCamelCase_(					*_A :Optional[Any]					,  **_A :Dict	)->		int:
			UpperCamelCase__       =							str(Path().resolve()	)
			with tempfile.TemporaryDirectory(*_A					,  **_A	) as tmp_dir:
						try:
									os.chdir(_A	)
									yield
						finally:
									os.chdir(_A	)
@contextmanager
def 							UpperCamelCase_(					)->		Union[str, Any]:
			import gc

			gc.collect()
			UpperCamelCase__       =							pa.total_allocated_bytes()
			yield
			assert pa.total_allocated_bytes() - previous_allocated_memory > 0, "Arrow memory didn't increase."
@contextmanager
def 							UpperCamelCase_(					)->		Optional[Any]:
			import gc

			gc.collect()
			UpperCamelCase__       =							pa.total_allocated_bytes()
			yield
			assert pa.total_allocated_bytes() - previous_allocated_memory <= 0, "Arrow memory wasn't expected to increase."
def 							UpperCamelCase_(					_A :List[str]					,  _A :List[str]	)->		List[Any]:
			return deepcopy(_A	).integers(0					,  1_00					,  10	).tolist() == deepcopy(_A	).integers(0					,  1_00					,  10	).tolist()
def 							UpperCamelCase_(					_A :Optional[Any]	)->		int:
			import decorator
			from requests.exceptions import HTTPError

			def _wrapper(_A :Optional[Any]					,  *_A :Union[str, Any]					,  **_A :List[Any]	):
						try:
									return func(*_A					,  **_A	)
						except HTTPError as err:
									if str(_A	).startswith("500"	) or str(_A	).startswith("502"	):
												pytest.xfail(str(_A	)	)
									raise err

			return decorator.decorator(_wrapper					,  _A	)







class 							lowerCamelCase__						:






			"""simple docstring"""






			def __init__(				self   ,    snake_case   ,    snake_case   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							returncode
						UpperCamelCase__       =							stdout
						UpperCamelCase__       =							stderr



async def 							UpperCamelCase_(					_A :Any					,  _A :Optional[Any]	)->		List[str]:
			while True:
						UpperCamelCase__       =							await stream.readline()
						if line:
									callback(_A	)
						else:
									break
async def 							UpperCamelCase_(					_A :str					,  _A :List[str]=None					,  _A :Tuple=None					,  _A :List[Any]=None					,  _A :List[Any]=False					,  _A :Any=False	)->		_RunOutput:
			if echo:
						print("\nRunning: "					,  " ".join(_A	)	)

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

			# 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)

			UpperCamelCase__       =							[]
			UpperCamelCase__       =							[]

			def tee(_A :int					,  _A :Optional[Any]					,  _A :List[str]					,  _A :Optional[int]=""	):
						UpperCamelCase__       =							line.decode("utf-8"	).rstrip()
						sink.append(_A	)
						if not quiet:
									print(_A					,  _A					,  file=_A	)

    # XXX: the timeout doesn't seem to make any difference here
			await asyncio.wait(
			    [
			        _read_stream(p.stdout					,  lambda _A	: tee(_A					,  _A					,  sys.stdout					,  label="stdout:"	)	),
			        _read_stream(p.stderr					,  lambda _A	: tee(_A					,  _A					,  sys.stderr					,  label="stderr:"	)	),
			    ]					,  timeout=_A					,  )
			return _RunOutput(await p.wait()					,  _A					,  _A	)
def 							UpperCamelCase_(					_A :int					,  _A :Optional[int]=None					,  _A :Dict=None					,  _A :str=1_80					,  _A :Union[str, Any]=False					,  _A :int=True	)->		_RunOutput:
			UpperCamelCase__       =							asyncio.get_event_loop()
			UpperCamelCase__       =							loop.run_until_complete(
			    _stream_subprocess(_A					,  env=_A					,  stdin=_A					,  timeout=_A					,  quiet=_A					,  echo=_A	)	)

			UpperCamelCase__       =							" ".join(_A	)
			if result.returncode > 0:
						UpperCamelCase__       =							"\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 							UpperCamelCase_(					)->		Any:
			UpperCamelCase__       =							os.environ.get("PYTEST_XDIST_WORKER"					,  "gw0"	)
			UpperCamelCase__       =							re.sub(r"^gw"					,  ""					,  _A					,  0					,  re.M	)
			return int(_A	)







def 							UpperCamelCase_(					)->		Dict:
			UpperCamelCase__       =							2_95_00
			UpperCamelCase__       =							pytest_xdist_worker_id()
			return port + uniq_delta






from __future__ import annotations

import math
import random
from typing import Any







class 							lowerCamelCase__						:






			"""simple docstring"""






			def __init__(				self  ):

						'''simple docstring'''


						UpperCamelCase__       =							[]
						UpperCamelCase__       =							0
						UpperCamelCase__       =							0




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.head == self.tail




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						self.data.append(snake_case  )
						UpperCamelCase__       =							self.tail + 1




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						UpperCamelCase__       =							self.data[self.head]
						UpperCamelCase__       =							self.head + 1
						return ret




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.tail - self.head







			def 					snake_case__					(				self  ):

						'''simple docstring'''


						print(self.data  )
						print("**************"  )
						print(self.data[self.head : self.tail]  )







class 							lowerCamelCase__						:






			"""simple docstring"""






			def __init__(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							data
						UpperCamelCase__       =							None
						UpperCamelCase__       =							None
						UpperCamelCase__       =							1




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.data




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.left




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.right




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return self.height




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							data




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							node




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							node







			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						UpperCamelCase__       =							height



def 							UpperCamelCase_(					_A :MyNode | None	)->		int:
			if node is None:
						return 0
			return node.get_height()
def 							UpperCamelCase_(					_A :int					,  _A :int	)->		int:
			if a > b:
						return a
			return b
def 							UpperCamelCase_(					_A :MyNode	)->		MyNode:
			print("left rotation node:"					,  node.get_data()	)
			UpperCamelCase__       =							node.get_left()
			assert ret is not None
			node.set_left(ret.get_right()	)
			ret.set_right(_A	)
			UpperCamelCase__       =							my_max(get_height(node.get_right()	)					,  get_height(node.get_left()	)	) + 1
			node.set_height(_A	)
			UpperCamelCase__       =							my_max(get_height(ret.get_right()	)					,  get_height(ret.get_left()	)	) + 1
			ret.set_height(_A	)
			return ret
def 							UpperCamelCase_(					_A :MyNode	)->		MyNode:
			print("right rotation node:"					,  node.get_data()	)
			UpperCamelCase__       =							node.get_right()
			assert ret is not None
			node.set_right(ret.get_left()	)
			ret.set_left(_A	)
			UpperCamelCase__       =							my_max(get_height(node.get_right()	)					,  get_height(node.get_left()	)	) + 1
			node.set_height(_A	)
			UpperCamelCase__       =							my_max(get_height(ret.get_right()	)					,  get_height(ret.get_left()	)	) + 1
			ret.set_height(_A	)
			return ret
def 							UpperCamelCase_(					_A :MyNode	)->		MyNode:
			UpperCamelCase__       =							node.get_left()
			assert left_child is not None
			node.set_left(left_rotation(_A	)	)
			return right_rotation(_A	)
def 							UpperCamelCase_(					_A :MyNode	)->		MyNode:
			UpperCamelCase__       =							node.get_right()
			assert right_child is not None
			node.set_right(right_rotation(_A	)	)
			return left_rotation(_A	)
def 							UpperCamelCase_(					_A :MyNode | None					,  _A :Any	)->		MyNode | None:
			if node is None:
						return MyNode(_A	)
			if data < node.get_data():
						node.set_left(insert_node(node.get_left()					,  _A	)	)
						if (
						    get_height(node.get_left()	) - get_height(node.get_right()	) == 2
						):  # an unbalance detected
									UpperCamelCase__       =							node.get_left()
									assert left_child is not None
									if (
									    data < left_child.get_data()
									):  # new node is the left child of the left child
												UpperCamelCase__       =							right_rotation(_A	)
									else:
												UpperCamelCase__       =							lr_rotation(_A	)
			else:
						node.set_right(insert_node(node.get_right()					,  _A	)	)
						if get_height(node.get_right()	) - get_height(node.get_left()	) == 2:
									UpperCamelCase__       =							node.get_right()
									assert right_child is not None
									if data < right_child.get_data():
												UpperCamelCase__       =							rl_rotation(_A	)
									else:
												UpperCamelCase__       =							left_rotation(_A	)
			UpperCamelCase__       =							my_max(get_height(node.get_right()	)					,  get_height(node.get_left()	)	) + 1
			node.set_height(_A	)
			return node
def 							UpperCamelCase_(					_A :MyNode	)->		Any:
			while True:
						UpperCamelCase__       =							root.get_right()
						if right_child is None:
									break
						UpperCamelCase__       =							right_child
			return root.get_data()
def 							UpperCamelCase_(					_A :MyNode	)->		Any:
			while True:
						UpperCamelCase__       =							root.get_left()
						if left_child is None:
									break
						UpperCamelCase__       =							left_child
			return root.get_data()
def 							UpperCamelCase_(					_A :MyNode					,  _A :Any	)->		MyNode | None:
			UpperCamelCase__       =							root.get_left()
			UpperCamelCase__       =							root.get_right()
			if root.get_data() == data:
						if left_child is not None and right_child is not None:
									UpperCamelCase__       =							get_left_most(_A	)
									root.set_data(_A	)
									root.set_right(del_node(_A					,  _A	)	)
						elif left_child is not None:
									UpperCamelCase__       =							left_child
						elif right_child is not None:
									UpperCamelCase__       =							right_child
						else:
									return None
			elif root.get_data() > data:
						if left_child is None:
									print("No such data"	)
									return root
						else:
									root.set_left(del_node(_A					,  _A	)	)
			else:  # root.get_data() < data
						if right_child is None:
									return root
						else:
									root.set_right(del_node(_A					,  _A	)	)

			if get_height(_A	) - get_height(_A	) == 2:
						assert right_child is not None
						if get_height(right_child.get_right()	) > get_height(right_child.get_left()	):
									UpperCamelCase__       =							left_rotation(_A	)
						else:
									UpperCamelCase__       =							rl_rotation(_A	)
			elif get_height(_A	) - get_height(_A	) == -2:
						assert left_child is not None
						if get_height(left_child.get_left()	) > get_height(left_child.get_right()	):
									UpperCamelCase__       =							right_rotation(_A	)
						else:
									UpperCamelCase__       =							lr_rotation(_A	)
			UpperCamelCase__       =							my_max(get_height(root.get_right()	)					,  get_height(root.get_left()	)	) + 1
			root.set_height(_A	)
			return root







class 							lowerCamelCase__						:






			"""simple docstring"""






			def __init__(				self  ):

						'''simple docstring'''


						UpperCamelCase__       =							None




			def 					snake_case__					(				self  ):

						'''simple docstring'''


						return get_height(self.root  )




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						print("insert:" + str(snake_case  )  )
						UpperCamelCase__       =							insert_node(self.root   ,    snake_case  )




			def 					snake_case__					(				self   ,    snake_case  ):

						'''simple docstring'''


						print("delete:" + str(snake_case  )  )
						if self.root is None:
									print("Tree is empty!"  )
									return
						UpperCamelCase__       =							del_node(self.root   ,    snake_case  )







			def __str__(				self   ,    ):  # a level traversale, gives a more intuitive look on the tree

						'''simple docstring'''


						UpperCamelCase__       =							""
						UpperCamelCase__       =							MyQueue()
						q.push(self.root  )
						UpperCamelCase__       =							self.get_height()
						if layer == 0:
									return output
						UpperCamelCase__       =							0
						while not q.is_empty():
									UpperCamelCase__       =							q.pop()
									UpperCamelCase__       =							" " * int(math.pow(2   ,    layer - 1  )  )
									output += space
									if node is None:
												output += "*"
												q.push(snake_case  )
												q.push(snake_case  )
									else:
												output += str(node.get_data()  )
												q.push(node.get_left()  )
												q.push(node.get_right()  )
									output += space
									UpperCamelCase__       =							cnt + 1
									for i in range(100  ):
												if cnt == math.pow(2   ,    snake_case  ) - 1:
															UpperCamelCase__       =							layer - 1
															if layer == 0:
																		output += "\n*************************************"
																		return output
															output += "\n"
															break
						output += "\n*************************************"
						return output



def 							UpperCamelCase_(					)->		None:
			import doctest

			doctest.testmod()


if __name__ == "__main__":
						_test()
						__UpperCamelCase     		=							AVLtree()
						__UpperCamelCase     		=							list(range(1_0))
						random.shuffle(lst)
						for i in lst:
												t.insert(i)
												print(str(t))
						random.shuffle(lst)
						for i in lst:
												t.del_node(i)
												print(str(t))


