




import unittest

from transformers import FunnelConfig, FunnelTokenizer, is_torch_available
from transformers.models.auto import get_values
from transformers.testing_utils import require_sentencepiece, require_tokenizers, require_torch, slow, torch_device

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
 import torch

 from transformers import (
     MODEL_FOR_PRETRAINING_MAPPING,
     FunnelBaseModel,
     FunnelForMaskedLM,
     FunnelForMultipleChoice,
     FunnelForPreTraining,
     FunnelForQuestionAnswering,
     FunnelForSequenceClassification,
     FunnelForTokenClassification,
     FunnelModel,
 )







class 		__UpperCAmelCase:





     """simple docstring"""



     def __init__(   self			:							Optional[int]    ,					A			:							Tuple    ,					A			:							Tuple=13    ,					A			:							Optional[int]=7    ,					A			:							List[str]=True    ,					A			:							List[str]=True    ,					A			:							List[Any]=True    ,					A			:							Any=True    ,					A			:							List[Any]=99    ,					A			:							str=[1, 1, 2]    ,					A			:							Any=1    ,					A			:							Tuple=32    ,					A			:							Any=4    ,					A			:							str=8    ,					A			:							int=37    ,					A			:							Tuple="gelu_new"    ,					A			:							Any=0.1    ,					A			:							List[Any]=0.1    ,					A			:							str=0.0    ,					A			:							str=5_12    ,					A			:							int=3    ,					A			:							Dict=0.0_2    ,					A			:							Any=3    ,					A			:							Tuple=4    ,					A			:							str=None    ,					A			:							Any=False    ,					)      ->      Any:






         """simple docstring"""
         a__  			=							parent
         a__  			=							batch_size
         a__  			=							seq_length
         a__  			=							is_training
         a__  			=							use_input_mask
         a__  			=							use_token_type_ids
         a__  			=							use_labels
         a__  			=							vocab_size
         a__  			=							block_sizes
         a__  			=							num_decoder_layers
         a__  			=							d_model
         a__  			=							n_head
         a__  			=							d_head
         a__  			=							d_inner
         a__  			=							hidden_act
         a__  			=							hidden_dropout
         a__  			=							attention_dropout
         a__  			=							activation_dropout
         a__  			=							max_position_embeddings
         a__  			=							type_vocab_size
         a__  			=							2
         a__  			=							num_labels
         a__  			=							num_choices
         a__  			=							scope
         a__  			=							initializer_std

         # Used in the tests to check the size of the first attention layer
         a__  			=							n_head
         # Used in the tests to check the size of the first hidden state
         a__  			=							self.d_model
         # Used in the tests to check the number of output hidden states/attentions
         a__  			=							sum(self.block_sizes     ) + (0 if base else self.num_decoder_layers)
         # FunnelModel adds two hidden layers: input embeddings and the sum of the upsampled encoder hidden state with
         # the last hidden state of the first block (which is the first hidden state of the decoder).
         if not base:
             a__  			=							self.num_hidden_layers + 2

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Tuple     )      ->      Dict:






         """simple docstring"""
         a__  			=							ids_tensor([self.batch_size, self.seq_length]    ,					self.vocab_size     )

         a__  			=							None
         if self.use_input_mask:
             a__  			=							ids_tensor([self.batch_size, self.seq_length]    ,					vocab_size=2     )

         a__  			=							None
         if self.use_token_type_ids:
             a__  			=							ids_tensor([self.batch_size, self.seq_length]    ,					self.type_vocab_size     )

         a__  			=							None
         a__  			=							None
         a__  			=							None
         if self.use_labels:
             a__  			=							ids_tensor([self.batch_size]    ,					self.type_sequence_label_size     )
             a__  			=							ids_tensor([self.batch_size, self.seq_length]    ,					self.num_labels     )
             a__  			=							ids_tensor([self.batch_size]    ,					self.num_choices     )
             a__  			=							ids_tensor([self.batch_size, self.seq_length]    ,					1     )

         a__  			=							self.get_config()

         return (
             config,
             input_ids,
             token_type_ids,
             input_mask,
             sequence_labels,
             token_labels,
             choice_labels,
             fake_token_labels,
         )

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






         """simple docstring"""
         return FunnelConfig(
             vocab_size=self.vocab_size    ,					block_sizes=self.block_sizes    ,					num_decoder_layers=self.num_decoder_layers    ,					d_model=self.d_model    ,					n_head=self.n_head    ,					d_head=self.d_head    ,					d_inner=self.d_inner    ,					hidden_act=self.hidden_act    ,					hidden_dropout=self.hidden_dropout    ,					attention_dropout=self.attention_dropout    ,					activation_dropout=self.activation_dropout    ,					max_position_embeddings=self.max_position_embeddings    ,					type_vocab_size=self.type_vocab_size    ,					initializer_std=self.initializer_std    ,					)

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[str]    ,					A			:							Tuple    ,					A			:							List[str]    ,					A			:							str    ,					A			:							int    ,					A			:							Union[str, Any]    ,					A			:							Optional[Any]    ,					A			:							Tuple    ,					A			:							Dict    ,					)      ->      Optional[Any]:






         """simple docstring"""
         a__  			=							FunnelModel(config=_UpperCAmelCase     )
         model.to(_UpperCAmelCase     )
         model.eval()
         a__  			=							model(_UpperCAmelCase    ,					attention_mask=_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase     )
         a__  			=							model(_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase     )
         a__  			=							model(_UpperCAmelCase     )
         self.parent.assertEqual(result.last_hidden_state.shape    ,					(self.batch_size, self.seq_length, self.d_model)     )

         a__  			=							False
         a__  			=							model(_UpperCAmelCase     )
         self.parent.assertEqual(result.last_hidden_state.shape    ,					(self.batch_size, self.seq_length, self.d_model)     )

         a__  			=							False
         a__  			=							model(_UpperCAmelCase     )
         self.parent.assertEqual(result.last_hidden_state.shape    ,					(self.batch_size, self.seq_length, self.d_model)     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Optional[Any]    ,					A			:							str    ,					A			:							Dict    ,					A			:							int    ,					A			:							Union[str, Any]    ,					A			:							str    ,					A			:							Union[str, Any]    ,					A			:							List[Any]    ,					A			:							Dict    ,					)      ->      Optional[Any]:






         """simple docstring"""
         a__  			=							FunnelBaseModel(config=_UpperCAmelCase     )
         model.to(_UpperCAmelCase     )
         model.eval()
         a__  			=							model(_UpperCAmelCase    ,					attention_mask=_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase     )
         a__  			=							model(_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase     )
         a__  			=							model(_UpperCAmelCase     )
         self.parent.assertEqual(result.last_hidden_state.shape    ,					(self.batch_size, 2, self.d_model)     )

         a__  			=							False
         a__  			=							model(_UpperCAmelCase     )
         self.parent.assertEqual(result.last_hidden_state.shape    ,					(self.batch_size, 3, self.d_model)     )

         a__  			=							False
         a__  			=							model(_UpperCAmelCase     )
         self.parent.assertEqual(result.last_hidden_state.shape    ,					(self.batch_size, 2, self.d_model)     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Any    ,					A			:							str    ,					A			:							Optional[int]    ,					A			:							List[str]    ,					A			:							Tuple    ,					A			:							Union[str, Any]    ,					A			:							Optional[Any]    ,					A			:							Union[str, Any]    ,					A			:							List[Any]    ,					)      ->      Optional[int]:






         """simple docstring"""
         a__  			=							self.num_labels
         a__  			=							FunnelForPreTraining(config=_UpperCAmelCase     )
         model.to(_UpperCAmelCase     )
         model.eval()
         a__  			=							model(_UpperCAmelCase    ,					attention_mask=_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase    ,					labels=_UpperCAmelCase     )
         self.parent.assertEqual(result.logits.shape    ,					(self.batch_size, self.seq_length)     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Dict    ,					A			:							Tuple    ,					A			:							Union[str, Any]    ,					A			:							Tuple    ,					A			:							Optional[Any]    ,					A			:							Union[str, Any]    ,					A			:							Union[str, Any]    ,					A			:							Dict    ,					A			:							Optional[Any]    ,					)      ->      int:






         """simple docstring"""
         a__  			=							FunnelForMaskedLM(config=_UpperCAmelCase     )
         model.to(_UpperCAmelCase     )
         model.eval()
         a__  			=							model(_UpperCAmelCase    ,					attention_mask=_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase    ,					labels=_UpperCAmelCase     )
         self.parent.assertEqual(result.logits.shape    ,					(self.batch_size, self.seq_length, self.vocab_size)     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Dict    ,					A			:							Union[str, Any]    ,					A			:							List[Any]    ,					A			:							Tuple    ,					A			:							Optional[int]    ,					A			:							Any    ,					A			:							Optional[int]    ,					A			:							List[str]    ,					A			:							Tuple    ,					)      ->      Optional[int]:






         """simple docstring"""
         a__  			=							self.num_labels
         a__  			=							FunnelForSequenceClassification(_UpperCAmelCase     )
         model.to(_UpperCAmelCase     )
         model.eval()
         a__  			=							model(_UpperCAmelCase    ,					attention_mask=_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase    ,					labels=_UpperCAmelCase     )
         self.parent.assertEqual(result.logits.shape    ,					(self.batch_size, self.num_labels)     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Union[str, Any]    ,					A			:							Dict    ,					A			:							Union[str, Any]    ,					A			:							Union[str, Any]    ,					A			:							List[str]    ,					A			:							int    ,					A			:							Tuple    ,					A			:							Tuple    ,					A			:							List[str]    ,					)      ->      str:






         """simple docstring"""
         a__  			=							self.num_choices
         a__  			=							FunnelForMultipleChoice(config=_UpperCAmelCase     )
         model.to(_UpperCAmelCase     )
         model.eval()
         a__  			=							input_ids.unsqueeze(1     ).expand(-1    ,					self.num_choices    ,					-1     ).contiguous()
         a__  			=							token_type_ids.unsqueeze(1     ).expand(-1    ,					self.num_choices    ,					-1     ).contiguous()
         a__  			=							input_mask.unsqueeze(1     ).expand(-1    ,					self.num_choices    ,					-1     ).contiguous()
         a__  			=							model(
             _UpperCAmelCase    ,					attention_mask=_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase    ,					labels=_UpperCAmelCase    ,					)
         self.parent.assertEqual(result.logits.shape    ,					(self.batch_size, self.num_choices)     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							str    ,					A			:							int    ,					A			:							Optional[int]    ,					A			:							str    ,					A			:							Any    ,					A			:							Union[str, Any]    ,					A			:							Any    ,					A			:							str    ,					A			:							Any    ,					)      ->      Tuple:






         """simple docstring"""
         a__  			=							self.num_labels
         a__  			=							FunnelForTokenClassification(config=_UpperCAmelCase     )
         model.to(_UpperCAmelCase     )
         model.eval()
         a__  			=							model(_UpperCAmelCase    ,					attention_mask=_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase    ,					labels=_UpperCAmelCase     )
         self.parent.assertEqual(result.logits.shape    ,					(self.batch_size, self.seq_length, self.num_labels)     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Union[str, Any]    ,					A			:							Tuple    ,					A			:							List[Any]    ,					A			:							str    ,					A			:							List[Any]    ,					A			:							str    ,					A			:							str    ,					A			:							List[str]    ,					A			:							Optional[int]    ,					)      ->      str:






         """simple docstring"""
         a__  			=							FunnelForQuestionAnswering(config=_UpperCAmelCase     )
         model.to(_UpperCAmelCase     )
         model.eval()
         a__  			=							model(
             _UpperCAmelCase    ,					attention_mask=_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase    ,					start_positions=_UpperCAmelCase    ,					end_positions=_UpperCAmelCase    ,					)
         self.parent.assertEqual(result.start_logits.shape    ,					(self.batch_size, self.seq_length)     )
         self.parent.assertEqual(result.end_logits.shape    ,					(self.batch_size, self.seq_length)     )






     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[str]     )      ->      List[str]:






         """simple docstring"""
         a__  			=							self.prepare_config_and_inputs()
         (
             (
             a__		
         )			,		(
             a__		
         )			,		(
             a__		
         )			,		(
             a__		
         )			,		(
             a__		
         )			,		(
             a__		
         )			,		(
             a__		
         )			,		(
             a__		
         )			,				
         )  			=							config_and_inputs
         a__  			=							{"""input_ids""": input_ids, """token_type_ids""": token_type_ids, """attention_mask""": input_mask}
         return config, inputs_dict







@require_torch
class 		__UpperCAmelCase(		lowercase__							,						lowercase__							,						unittest.TestCase			):





     """simple docstring"""



     __UpperCAmelCase						:			Any							=     False
     __UpperCAmelCase						:			int							=     False
     __UpperCAmelCase						:			List[str]							=     (
         (
             FunnelModel,
             FunnelForMaskedLM,
             FunnelForPreTraining,
             FunnelForQuestionAnswering,
             FunnelForTokenClassification,
         )
         if is_torch_available()
         else ()
     )
     __UpperCAmelCase						:			Union[str, Any]							=     (
         {
             'feature-extraction': (FunnelBaseModel, FunnelModel),
             'fill-mask': FunnelForMaskedLM,
             'question-answering': FunnelForQuestionAnswering,
             'text-classification': FunnelForSequenceClassification,
             'token-classification': FunnelForTokenClassification,
             'zero-shot': FunnelForSequenceClassification,
         }
         if is_torch_available()
         else {}
     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Tuple    ,					A			:							Tuple    ,					A			:							Any    ,					A			:							Tuple=False     )      ->      Optional[int]:






         """simple docstring"""
         a__  			=							super()._prepare_for_class(_UpperCAmelCase    ,					_UpperCAmelCase    ,					return_labels=_UpperCAmelCase     )

         if return_labels:
             if model_class in get_values(_UpperCAmelCase     ):
                 a__  			=							torch.zeros(
                     (self.model_tester.batch_size, self.model_tester.seq_length)    ,					dtype=torch.long    ,					device=_UpperCAmelCase     )
         return inputs_dict

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[Any]     )      ->      List[Any]:






         """simple docstring"""
         a__  			=							FunnelModelTester(self     )
         a__  			=							ConfigTester(self    ,					config_class=_UpperCAmelCase     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[str]     )      ->      int:






         """simple docstring"""
         self.config_tester.run_common_tests()

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Tuple     )      ->      Tuple:






         """simple docstring"""
         a__  			=							self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_model(*_UpperCAmelCase     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Dict     )      ->      Optional[int]:






         """simple docstring"""
         a__  			=							self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_pretraining(*_UpperCAmelCase     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Dict     )      ->      Any:






         """simple docstring"""
         a__  			=							self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_masked_lm(*_UpperCAmelCase     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Tuple     )      ->      Any:






         """simple docstring"""
         a__  			=							self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_token_classification(*_UpperCAmelCase     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Optional[Any]     )      ->      Optional[Any]:






         """simple docstring"""
         a__  			=							self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_question_answering(*_UpperCAmelCase     )






     def 					__SCREAMING_SNAKE_CASE		(   self			:							Any    ,					A			:							List[Any]     )      ->      Dict:






         """simple docstring"""
         if hasattr(_UpperCAmelCase    ,					"""weight"""     ) and module.weight is not None:
             module.weight.data.fill_(3     )
         if hasattr(_UpperCAmelCase    ,					"""bias"""     ) and module.bias is not None:
             module.bias.data.fill_(3     )

         for param in ["r_w_bias", "r_r_bias", "r_kernel", "r_s_bias", "seg_embed"]:
             if hasattr(_UpperCAmelCase    ,					_UpperCAmelCase     ) and getattr(_UpperCAmelCase    ,					_UpperCAmelCase     ) is not None:
                 a__  			=							getattr(_UpperCAmelCase    ,					_UpperCAmelCase     )
                 weight.data.fill_(3     )







@require_torch
class 		__UpperCAmelCase(		lowercase__							,						unittest.TestCase			):





     """simple docstring"""



     __UpperCAmelCase						:			Optional[int]							=     False
     __UpperCAmelCase						:			Tuple							=     False
     __UpperCAmelCase						:			Any							=     (
         (FunnelBaseModel, FunnelForMultipleChoice, FunnelForSequenceClassification) if is_torch_available() else ()
     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[Any]     )      ->      Optional[Any]:






         """simple docstring"""
         a__  			=							FunnelModelTester(self    ,					base=_UpperCAmelCase     )
         a__  			=							ConfigTester(self    ,					config_class=_UpperCAmelCase     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							Any     )      ->      Tuple:






         """simple docstring"""
         self.config_tester.run_common_tests()

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[str]     )      ->      Dict:






         """simple docstring"""
         a__  			=							self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_base_model(*_UpperCAmelCase     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[str]     )      ->      Optional[Any]:






         """simple docstring"""
         a__  			=							self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_sequence_classification(*_UpperCAmelCase     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[str]     )      ->      List[str]:






         """simple docstring"""
         a__  			=							self.model_tester.prepare_config_and_inputs()
         self.model_tester.create_and_check_for_multiple_choice(*_UpperCAmelCase     )

     def 					__SCREAMING_SNAKE_CASE		(   self			:							List[Any]     )      ->      str:






         """simple docstring"""
         a__			,		a__  			=							self.model_tester.prepare_config_and_inputs_for_common()
         a__  			=							True

         for model_class in self.all_model_classes:
             if model_class.__name__ == "FunnelBaseModel":
                 continue
             a__  			=							model_class(_UpperCAmelCase     )
             model.to(_UpperCAmelCase     )
             model.train()
             a__  			=							self._prepare_for_class(_UpperCAmelCase    ,					_UpperCAmelCase    ,					return_labels=_UpperCAmelCase     )
             a__  			=							model(**_UpperCAmelCase     ).loss
             loss.backward()






     def 					__SCREAMING_SNAKE_CASE		(   self			:							Tuple    ,					A			:							List[str]     )      ->      int:






         """simple docstring"""
         if hasattr(_UpperCAmelCase    ,					"""weight"""     ) and module.weight is not None:
             module.weight.data.fill_(3     )
         if hasattr(_UpperCAmelCase    ,					"""bias"""     ) and module.bias is not None:
             module.bias.data.fill_(3     )

         for param in ["r_w_bias", "r_r_bias", "r_kernel", "r_s_bias", "seg_embed"]:
             if hasattr(_UpperCAmelCase    ,					_UpperCAmelCase     ) and getattr(_UpperCAmelCase    ,					_UpperCAmelCase     ) is not None:
                 a__  			=							getattr(_UpperCAmelCase    ,					_UpperCAmelCase     )
                 weight.data.fill_(3     )







@require_torch
@require_sentencepiece
@require_tokenizers
class 		__UpperCAmelCase(		unittest.TestCase			):





     """simple docstring"""



     def 					__SCREAMING_SNAKE_CASE		(   self			:							Union[str, Any]     )      ->      Dict:






         """simple docstring"""
         a__  			=							13
         a__  			=							7
         a__  			=							torch.arange(0    ,					batch_size * sequence_length     ).long().reshape(_UpperCAmelCase    ,					_UpperCAmelCase     )
         a__  			=							[0, 1, 2, 3, 4, 5, 6, 4, 1, 3, 5, 0, 1]
         a__  			=							torch.tensor([[2] + [0] * a + [1] * (sequence_length - a - 1) for a in lengths]     )

         a__  			=							FunnelModel.from_pretrained("""sgugger/funnel-random-tiny"""     )
         a__  			=							model(_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase     )[0].abs()

         a__  			=							torch.tensor(2_3_4_4.8_3_5_2     )
         a__  			=							torch.tensor(0.8_0_5_2     )
         self.assertTrue(torch.allclose(output.sum()    ,					_UpperCAmelCase    ,					atol=1E-4     )     )
         self.assertTrue(torch.allclose(output.mean()    ,					_UpperCAmelCase    ,					atol=1E-4     )     )

         a__  			=							torch.tensor([[1] * 7, [1] * 4 + [0] * 3] * 6 + [[0, 1, 1, 0, 0, 1, 1]]     )
         a__  			=							model(_UpperCAmelCase    ,					attention_mask=_UpperCAmelCase    ,					token_type_ids=_UpperCAmelCase     )[0].abs()

         a__  			=							torch.tensor(2_3_4_3.8_4_2_5     )
         a__  			=							torch.tensor(0.8_0_4_9     )
         self.assertTrue(torch.allclose(output.sum()    ,					_UpperCAmelCase    ,					atol=1E-4     )     )
         self.assertTrue(torch.allclose(output.mean()    ,					_UpperCAmelCase    ,					atol=1E-4     )     )






     @slow
     def 					__SCREAMING_SNAKE_CASE		(   self			:							Dict     )      ->      List[Any]:






         """simple docstring"""
         a__  			=							FunnelTokenizer.from_pretrained("""huggingface/funnel-small"""     )
         a__  			=							FunnelModel.from_pretrained("""huggingface/funnel-small"""     )
         a__  			=							tokenizer("""Hello! I am the Funnel Transformer model."""    ,					return_tensors="""pt"""     )
         a__  			=							model(**_UpperCAmelCase     )[0]

         a__  			=							torch.tensor(2_3_5.7_2_4_6     )
         a__  			=							torch.tensor(0.0_2_5_6     )
         self.assertTrue(torch.allclose(output.sum()    ,					_UpperCAmelCase    ,					atol=1E-4     )     )
         self.assertTrue(torch.allclose(output.mean()    ,					_UpperCAmelCase    ,					atol=1E-4     )     )








from __future__ import annotations
def lowerCamelCase_       (			A			:      list[int]						):




      """simple docstring"""
      if not list_of_ints:
            return []

      if min(A						) < 0:
            raise ValueError('''All numbers must be positive'''						)

      lowerCAmelCase_						=      max(len(bin(A						)[2:]						) for x in list_of_ints						)
      return _msd_radix_sort(A		,					A						)
def lowerCamelCase_       (			A			:      list[int]		,					A			:      int						):




      """simple docstring"""
      if bit_position == 0 or len(A						) in [0, 1]:
            return list_of_ints

      lowerCAmelCase_						=      []
      lowerCAmelCase_						=      []
      # 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(A						)
            else:
                  # number has a zero at bit bit_position
                  zeros.append(A						)

    # recursively split both lists further
      lowerCAmelCase_						=      _msd_radix_sort(A		,					bit_position - 1						)
      lowerCAmelCase_						=      _msd_radix_sort(A		,					bit_position - 1						)

      # recombine lists
      lowerCAmelCase_						=      zeros
      res.extend(A						)

      return res
def lowerCamelCase_       (			A			:      list[int]						):




      """simple docstring"""
      lowerCAmelCase_						=      len(A						)
      if not list_of_ints or length == 1:
            return

      if min(A						) < 0:
            raise ValueError('''All numbers must be positive'''						)

      lowerCAmelCase_						=      max(len(bin(A						)[2:]						) for x in list_of_ints						)
      _msd_radix_sort_inplace(A		,					A		,					0		,					A						)
def lowerCamelCase_       (			A			:      list[int]		,					A			:      int		,					A			:      int		,					A			:      int						):




      """simple docstring"""
      if bit_position == 0 or end_index - begin_index <= 1:
            return

      bit_position -= 1

      lowerCAmelCase_						=      begin_index
      lowerCAmelCase_						=      end_index - 1
      while i <= j:
            lowerCAmelCase_						=      False
            if not (list_of_ints[i] >> bit_position) & 1:
                  # found zero at the beginning
                  i += 1
                  lowerCAmelCase_						=      True
            if (list_of_ints[j] >> bit_position) & 1:
                  # found one at the end
                  j -= 1
                  lowerCAmelCase_						=      True

            if changed:
                  continue

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

      _msd_radix_sort_inplace(A		,					A		,					A		,					A						)
      _msd_radix_sort_inplace(A		,					A		,					A		,					A						)


if __name__ == "__main__":
 import doctest

 doctest.testmod()



