



from __future__ import annotations




def 						UpperCAmelCase (    _lowerCamelCase     ):
			if not list_of_ints:
						return []

			if min(_lowerCamelCase     ) < 0:
						raise ValueError("All numbers must be positive"     )

			A				:       str														=    max(len(bin(_lowerCamelCase     )[2:]     ) for x in list_of_ints     )
			return _msd_radix_sort(_lowerCamelCase			,     _lowerCamelCase     )




def 						UpperCAmelCase (    _lowerCamelCase			,     _lowerCamelCase     ):
			if bit_position == 0 or len(_lowerCamelCase     ) in [0, 1]:
						return list_of_ints

			A				:       Optional[int]														=    []
			A				:       int														=    []
			# Split numbers based on bit at bit_position from the right
			for number in list_of_ints:
						if (number >> (bit_position - 1)) & 1:
									# number has a one at bit bit_position
									ones.append(_lowerCamelCase     )
						else:
									# number has a zero at bit bit_position
									zeros.append(_lowerCamelCase     )

    # recursively split both lists further
			A				:       Union[str, Any]														=    _msd_radix_sort(_lowerCamelCase			,     bit_position - 1     )
			A				:       int														=    _msd_radix_sort(_lowerCamelCase			,     bit_position - 1     )

			# recombine lists
			A				:       Optional[int]														=    zeros
			res.extend(_lowerCamelCase     )

			return res




def 						UpperCAmelCase (    _lowerCamelCase     ):
			A				:       Tuple														=    len(_lowerCamelCase     )
			if not list_of_ints or length == 1:
						return

			if min(_lowerCamelCase     ) < 0:
						raise ValueError("All numbers must be positive"     )

			A				:       Optional[int]														=    max(len(bin(_lowerCamelCase     )[2:]     ) for x in list_of_ints     )
			_msd_radix_sort_inplace(_lowerCamelCase			,     _lowerCamelCase			,     0			,     _lowerCamelCase     )




def 						UpperCAmelCase (    _lowerCamelCase			,     _lowerCamelCase			,     _lowerCamelCase			,     _lowerCamelCase     ):
			if bit_position == 0 or end_index - begin_index <= 1:
						return

			bit_position -= 1

			A				:       int														=    begin_index
			A				:       Union[str, Any]														=    end_index - 1
			while i <= j:
						A				:       List[str]														=    False
						if not (list_of_ints[i] >> bit_position) & 1:
									# found zero at the beginning
									i += 1
									A				:       str														=    True
						if (list_of_ints[j] >> bit_position) & 1:
									# found one at the end
									j -= 1
									A				:       Optional[int]														=    True

						if changed:
									continue

						A							,			A				:       str														=    list_of_ints[j], list_of_ints[i]
						j -= 1
						if j != i:
									i += 1

			_msd_radix_sort_inplace(_lowerCamelCase			,     _lowerCamelCase			,     _lowerCamelCase			,     _lowerCamelCase     )
			_msd_radix_sort_inplace(_lowerCamelCase			,     _lowerCamelCase			,     _lowerCamelCase			,     _lowerCamelCase     )


if __name__ == "__main__":
							import doctest

							doctest.testmod()




from copy import deepcopy
from unittest.case import TestCase

import pytest

from datasets.arrow_dataset import Dataset
from datasets.features import Audio, ClassLabel, Features, Image, Sequence, Value
from datasets.info import DatasetInfo
from datasets.tasks import (
    AudioClassification,
    AutomaticSpeechRecognition,
    ImageClassification,
    LanguageModeling,
    QuestionAnsweringExtractive,
    Summarization,
    TextClassification,
    task_template_from_dict,
)
from datasets.utils.py_utils import asdict


__SCREAMING_SNAKE_CASE     =	{
    """id""": """5733be284776f41900661182""",
    """title""": """University_of_Notre_Dame""",
    """context""": """Architecturally, the school has a Catholic character. Atop the Main Building\'s gold dome is a golden statue of the Virgin Mary. Immediately in front of the Main Building and facing it, is a copper statue of Christ with arms upraised with the legend \"Venite Ad Me Omnes\". Next to the Main Building is the Basilica of the Sacred Heart. Immediately behind the basilica is the Grotto, a Marian place of prayer and reflection. It is a replica of the grotto at Lourdes, France where the Virgin Mary reputedly appeared to Saint Bernadette Soubirous in 1858. At the end of the main drive (and in a direct line that connects through 3 statues and the Gold Dome), is a simple, modern stone statue of Mary.""",
    """question""": """To whom did the Virgin Mary allegedly appear in 1858 in Lourdes France?""",
    """answers""": {"""text""": ["""Saint Bernadette Soubirous"""], """answer_start""": [515]},
}




@pytest.mark.parametrize(
    "task_cls"			,     [
        AudioClassification,
        AutomaticSpeechRecognition,
        ImageClassification,
        LanguageModeling,
        QuestionAnsweringExtractive,
        Summarization,
        TextClassification,
    ]			,     )
def 						UpperCAmelCase (    _lowerCamelCase     ):
			A				:       Optional[int]														=    task_cls()
			A				:       int														=    asdict(_lowerCamelCase     )
			A				:       int														=    task_template_from_dict(_lowerCamelCase     )
			assert task == reloaded

class 						lowerCamelCase_     :






						'''simple docstring'''







						def       SCREAMING_SNAKE_CASE__		(						self   :      Union[str, Any]			)   ->					Any:
									A				:       str														=    LanguageModeling(text_column="input_text"			)
									assert {"input_text": "text"} == task.column_mapping







						def       SCREAMING_SNAKE_CASE__		(						self   :      Any			)   ->					str:
									A				:       Tuple														=    Features({"text": Value("string"			)}			)
									A				:       Dict														=    {"text_column": "input_text"}
									A				:       Optional[int]														=    LanguageModeling.from_dict(__lowerCamelCase			)
									assert "language-modeling" == task.task
									assert input_schema == task.input_schema







class 						lowerCamelCase_     (			_A    ):






						'''simple docstring'''







						def       SCREAMING_SNAKE_CASE__		(						self   :      List[Any]			)   ->					str:
									A				:       List[Any]														=    sorted(["pos", "neg"]			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      str			)   ->					Optional[int]:
									A				:       List[Any]														=    TextClassification(text_column="input_text"						,						label_column="input_label"			)
									self.assertDictEqual({"input_text": "text", "input_label": "labels"}						,						task.column_mapping			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      Dict			)   ->					Optional[int]:
									A				:       Tuple														=    Features({"text": Value("string"			)}			)
									# Labels are cast to tuple during `TextClassification.__post_init__`, so we do the same here
									A				:       str														=    Features({"labels": ClassLabel}			)
									A				:       List[Any]														=    {"text_column": "input_text", "label_column": "input_labels"}
									A				:       Any														=    TextClassification.from_dict(__lowerCamelCase			)
									self.assertEqual("text-classification"						,						task.task			)
									self.assertEqual(__lowerCamelCase						,						task.input_schema			)
									self.assertEqual(__lowerCamelCase						,						task.label_schema			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      Tuple			)   ->					int:
									A				:       Dict														=    TextClassification(text_column="input_text"						,						label_column="input_label"			)
									self.assertEqual(task.label_schema["labels"]						,						__lowerCamelCase			)
									A				:       Any														=    task.align_with_features(Features({"input_label": ClassLabel(names=self.labels			)}			)			)
									self.assertEqual(task.label_schema["labels"]						,						ClassLabel(names=self.labels			)			)







class 						lowerCamelCase_     (			_A    ):






						'''simple docstring'''







						def       SCREAMING_SNAKE_CASE__		(						self   :      str			)   ->					Dict:
									A				:       Optional[int]														=    QuestionAnsweringExtractive(
									    context_column="input_context"						,						question_column="input_question"						,						answers_column="input_answers"			)
									self.assertDictEqual(
									    {"input_context": "context", "input_question": "question", "input_answers": "answers"}						,						task.column_mapping			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      Optional[int]			)   ->					Tuple:
									A				:       Dict														=    Features({"question": Value("string"			), "context": Value("string"			)}			)
									A				:       int														=    Features(
									    {
									        "answers": Sequence(
									            {
									                "text": Value("string"			),
									                "answer_start": Value("int32"			),
									            }			)
									    }			)
									A				:       Optional[int]														=    {
									    "context_column": "input_input_context",
									    "question_column": "input_question",
									    "answers_column": "input_answers",
									}
									A				:       Tuple														=    QuestionAnsweringExtractive.from_dict(__lowerCamelCase			)
									self.assertEqual("question-answering-extractive"						,						task.task			)
									self.assertEqual(__lowerCamelCase						,						task.input_schema			)
									self.assertEqual(__lowerCamelCase						,						task.label_schema			)







class 						lowerCamelCase_     (			_A    ):






						'''simple docstring'''







						def       SCREAMING_SNAKE_CASE__		(						self   :      Optional[Any]			)   ->					Tuple:
									A				:       Optional[Any]														=    Summarization(text_column="input_text"						,						summary_column="input_summary"			)
									self.assertDictEqual({"input_text": "text", "input_summary": "summary"}						,						task.column_mapping			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      List[Any]			)   ->					Any:
									A				:       Union[str, Any]														=    Features({"text": Value("string"			)}			)
									A				:       Tuple														=    Features({"summary": Value("string"			)}			)
									A				:       Optional[Any]														=    {"text_column": "input_text", "summary_column": "input_summary"}
									A				:       str														=    Summarization.from_dict(__lowerCamelCase			)
									self.assertEqual("summarization"						,						task.task			)
									self.assertEqual(__lowerCamelCase						,						task.input_schema			)
									self.assertEqual(__lowerCamelCase						,						task.label_schema			)







class 						lowerCamelCase_     (			_A    ):






						'''simple docstring'''







						def       SCREAMING_SNAKE_CASE__		(						self   :      Union[str, Any]			)   ->					Any:
									A				:       Union[str, Any]														=    AutomaticSpeechRecognition(audio_column="input_audio"						,						transcription_column="input_transcription"			)
									self.assertDictEqual({"input_audio": "audio", "input_transcription": "transcription"}						,						task.column_mapping			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      List[Any]			)   ->					str:
									A				:       Tuple														=    Features({"audio": Audio()}			)
									A				:       Any														=    Features({"transcription": Value("string"			)}			)
									A				:       List[str]														=    {
									    "audio_column": "input_audio",
									    "transcription_column": "input_transcription",
									}
									A				:       Dict														=    AutomaticSpeechRecognition.from_dict(__lowerCamelCase			)
									self.assertEqual("automatic-speech-recognition"						,						task.task			)
									self.assertEqual(__lowerCamelCase						,						task.input_schema			)
									self.assertEqual(__lowerCamelCase						,						task.label_schema			)







class 						lowerCamelCase_     (			_A    ):






						'''simple docstring'''







						def       SCREAMING_SNAKE_CASE__		(						self   :      List[Any]			)   ->					Tuple:
									A				:       Optional[Any]														=    sorted(["pos", "neg"]			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      Optional[Any]			)   ->					Union[str, Any]:
									A				:       Optional[int]														=    AudioClassification(audio_column="input_audio"						,						label_column="input_label"			)
									self.assertDictEqual({"input_audio": "audio", "input_label": "labels"}						,						task.column_mapping			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      Tuple			)   ->					Tuple:
									A				:       Union[str, Any]														=    Features({"audio": Audio()}			)
									A				:       Dict														=    Features({"labels": ClassLabel}			)
									A				:       Tuple														=    {
									    "audio_column": "input_image",
									    "label_column": "input_label",
									}
									A				:       Any														=    AudioClassification.from_dict(__lowerCamelCase			)
									self.assertEqual("audio-classification"						,						task.task			)
									self.assertEqual(__lowerCamelCase						,						task.input_schema			)
									self.assertEqual(__lowerCamelCase						,						task.label_schema			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      Tuple			)   ->					Any:
									A				:       str														=    AudioClassification(audio_column="input_audio"						,						label_column="input_label"			)
									self.assertEqual(task.label_schema["labels"]						,						__lowerCamelCase			)
									A				:       List[str]														=    task.align_with_features(Features({"input_label": ClassLabel(names=self.labels			)}			)			)
									self.assertEqual(task.label_schema["labels"]						,						ClassLabel(names=self.labels			)			)







class 						lowerCamelCase_     (			_A    ):






						'''simple docstring'''







						def       SCREAMING_SNAKE_CASE__		(						self   :      List[str]			)   ->					Optional[int]:
									A				:       int														=    sorted(["pos", "neg"]			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      Tuple			)   ->					int:
									A				:       List[Any]														=    ImageClassification(image_column="input_image"						,						label_column="input_label"			)
									self.assertDictEqual({"input_image": "image", "input_label": "labels"}						,						task.column_mapping			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      Any			)   ->					int:
									A				:       Optional[int]														=    Features({"image": Image()}			)
									A				:       str														=    Features({"labels": ClassLabel}			)
									A				:       List[str]														=    {
									    "image_column": "input_image",
									    "label_column": "input_label",
									}
									A				:       Tuple														=    ImageClassification.from_dict(__lowerCamelCase			)
									self.assertEqual("image-classification"						,						task.task			)
									self.assertEqual(__lowerCamelCase						,						task.input_schema			)
									self.assertEqual(__lowerCamelCase						,						task.label_schema			)







						def       SCREAMING_SNAKE_CASE__		(						self   :      Union[str, Any]			)   ->					Tuple:
									A				:       str														=    ImageClassification(image_column="input_image"						,						label_column="input_label"			)
									self.assertEqual(task.label_schema["labels"]						,						__lowerCamelCase			)
									A				:       Optional[Any]														=    task.align_with_features(Features({"input_label": ClassLabel(names=self.labels			)}			)			)
									self.assertEqual(task.label_schema["labels"]						,						ClassLabel(names=self.labels			)			)







class 						lowerCamelCase_     (			_A    ):






						'''simple docstring'''







						def       SCREAMING_SNAKE_CASE__		(						self   :      Optional[Any]			)   ->					Optional[int]:
									A				:       Dict														=    DatasetInfo(task_templates=QuestionAnsweringExtractive()			)
									A				:       List[Any]														=    Dataset.from_dict({k: [v] for k, v in SAMPLE_QUESTION_ANSWERING_EXTRACTIVE.items()}						,						info=__lowerCamelCase			)
									assert isinstance(dataset.info.task_templates						,						__lowerCamelCase			)
									assert len(dataset.info.task_templates			) == 1

									def keep_task(__lowerCamelCase   :      List[str]			):
												return x

									def dont_keep_task(__lowerCamelCase   :      Any			):
												A				:       Optional[Any]														=    deepcopy(__lowerCamelCase			)
												A				:       List[Any]														=    0
												return out

									A				:       Optional[int]														=    dataset.map(__lowerCamelCase			)
									assert mapped_dataset.info.task_templates == dataset.info.task_templates
									# reload from cache
									A				:       List[Any]														=    dataset.map(__lowerCamelCase			)
									assert mapped_dataset.info.task_templates == dataset.info.task_templates

									A				:       Union[str, Any]														=    dataset.map(__lowerCamelCase			)
									assert mapped_dataset.info.task_templates == []
									# reload from cache
									A				:       Optional[Any]														=    dataset.map(__lowerCamelCase			)
									assert mapped_dataset.info.task_templates == []







						def       SCREAMING_SNAKE_CASE__		(						self   :      str			)   ->					Tuple:
									A				:       Optional[Any]														=    Features({"text": Value("string"			), "label": ClassLabel(names=("pos", "neg")			)}			)
									A				:       Optional[Any]														=    TextClassification(text_column="text"						,						label_column="label"			)
									A				:       Optional[Any]														=    DatasetInfo(features=__lowerCamelCase						,						task_templates=__lowerCamelCase			)
									A				:       Optional[int]														=    Dataset.from_dict({"text": ["A sentence."], "label": ["pos"]}						,						info=__lowerCamelCase			)

									def process(__lowerCamelCase   :      Dict			):
												return example

									A				:       List[Any]														=    dataset.remove_columns("label"			)
									A				:       Dict														=    modified_dataset.map(__lowerCamelCase			)
									assert mapped_dataset.info.task_templates == []