

import argparse
import pathlib
from pathlib import Path
from tempfile import TemporaryDirectory

import esm as esm_module
import torch
from esm.esmfold.va.misc import batch_encode_sequences as esmfold_encode_sequences
from esm.esmfold.va.pretrained import esmfold_va

from transformers.models.esm.configuration_esm import EsmConfig, EsmFoldConfig
from transformers.models.esm.modeling_esm import (
    EsmForMaskedLM,
    EsmForSequenceClassification,
    EsmIntermediate,
    EsmLayer,
    EsmOutput,
    EsmSelfAttention,
    EsmSelfOutput,
)
from transformers.models.esm.modeling_esmfold import EsmForProteinFolding
from transformers.models.esm.tokenization_esm import EsmTokenizer
from transformers.utils import logging


logging.set_verbosity_info()
A_						:     Union[str, Any]			  =				logging.get_logger(__name__)

A_						:     Optional[Any]			  =				[
    (
        'protein1',
        'MNGTEGPNFYVPFSNATGVVRSPFEYPQYYLAEPWQFSMLAAYMFLLIVLGFPINFLTLYVTVQHKKLRTPLNYILLNLAVADLFMVLGGFTSTLYTSLHGYFVFGPTGCNLEGFFATLGGEIALWSLVVLAIERYVVVCKPMSNFRFGENHAIMGVAFTWVMALACAAPPLAGWSRYIPEGLQCSCGIDYYTLKPEVNNESFVIYMFVVHFTIPMIIIFFCYGQLVFTVKEAAAQQQESATTQKAEKEVTRMVIIMVIAFLICWVPYASVAFYIFTHQGSNFGPIFMTIPAFFAKSAAIYNPVIYIMMNKQFRNCMLTTICCGKNPLGDDEASATVSKTETSQVAPA',
    ),
    ('protein2', 'MKTVRQERLKSIVRILERSKEPVSGAQLAEELSVSRQVIVQDIAYLRSLGYNIVATPRGYVLA'),
    ('protein3', 'MKTVRQERLKSI<mask>RILERSKEPVSGAQLAEELS<mask>SRQVIVQDIAYLRSLGYN<mask>VATPRGYVLAGG'),
    ('protein4', 'MKTVRQERLKSI<mask>RILERSKEPVSGAQLAEELS<mask>SRQVIVQDIAYLRSLGYN<mask>VATPRGYVLA'),
]

A_						:     Union[str, Any]			  =				{
    'esm1b_t33_650M_UR50S': esm_module.pretrained.esm1b_t33_650M_UR50S,
    'esm1v_t33_650M_UR90S_1': esm_module.pretrained.esm1v_t33_650M_UR90S_1,
    'esm1v_t33_650M_UR90S_2': esm_module.pretrained.esm1v_t33_650M_UR90S_2,
    'esm1v_t33_650M_UR90S_3': esm_module.pretrained.esm1v_t33_650M_UR90S_3,
    'esm1v_t33_650M_UR90S_4': esm_module.pretrained.esm1v_t33_650M_UR90S_4,
    'esm1v_t33_650M_UR90S_5': esm_module.pretrained.esm1v_t33_650M_UR90S_5,
    'esm2_t48_15B_UR50D': esm_module.pretrained.esm2_t48_15B_UR50D,
    'esm2_t36_3B_UR50D': esm_module.pretrained.esm2_t36_3B_UR50D,
    'esm2_t33_650M_UR50D': esm_module.pretrained.esm2_t33_650M_UR50D,
    'esm2_t30_150M_UR50D': esm_module.pretrained.esm2_t30_150M_UR50D,
    'esm2_t12_35M_UR50D': esm_module.pretrained.esm2_t12_35M_UR50D,
    'esm2_t6_8M_UR50D': esm_module.pretrained.esm2_t6_8M_UR50D,
    'esmfold_v1': esmfold_va,
}

A_						:     Optional[Any]			  =				list('ARNDCQEGHILKMFPSTWYV')

A_						:     Dict			  =				restypes + ['X']
A_						:     int			  =				restypes_with_x + ['<pad>', '<mask>', '<cls>', '<sep>', '<eos>']


def  __a    (				) ->       Optional[int]:






    '''simple docstring'''
    with TemporaryDirectory() as tempdir:
        __UpperCAmelCase			   =     '''\n'''.join(SCREAMING_SNAKE_CASE )
        __UpperCAmelCase			   =     Path(SCREAMING_SNAKE_CASE ) / '''vocab.txt'''
        vocab_file.write_text(SCREAMING_SNAKE_CASE )
        __UpperCAmelCase			   =     EsmTokenizer(vocab_file=str(SCREAMING_SNAKE_CASE ) )
    __UpperCAmelCase			   =     0  # Overlaps with 'A' but that seems to be what they want
    return hf_tokenizer


def  __a    (				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE ) ->       Union[str, Any]:






    '''simple docstring'''
    __UpperCAmelCase			   =     our_module.load_state_dict(original_module.state_dict() )
    if status.missing_keys:
        raise ValueError(f'''Missing keys: {status.missing_keys}''' )
    if status.unexpected_keys:
        raise ValueError(f'''Unexpected keys: {status.unexpected_keys}''' )


def  __a    (				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE ) ->       List[str]:






    '''simple docstring'''
    if model.startswith('''esmfold''' ):
        __UpperCAmelCase			   =     MODEL_MAPPING[model]()
    else:
        __UpperCAmelCase   ,       __UpperCAmelCase			   =     MODEL_MAPPING[model]()
    esm.eval()  # disable dropout

    if model.startswith('''esmfold''' ):
        __UpperCAmelCase			   =     esm.esm.embed_dim
        __UpperCAmelCase			   =     esm.esm.num_layers
        __UpperCAmelCase			   =     esm.esm.attention_heads
        __UpperCAmelCase			   =     4 * embed_dim
        __UpperCAmelCase			   =     esm.esm.token_dropout
        __UpperCAmelCase			   =     False  # This code path does not exist in ESM-2
        __UpperCAmelCase			   =     '''rotary'''
        __UpperCAmelCase			   =     True
        __UpperCAmelCase			   =     EsmFoldConfig()
        for key, val in esm.cfg.items():
            if hasattr(SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE ) and key != "trunk":
                setattr(SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE )
        for key, val in esm.cfg.trunk.items():
            if hasattr(esmfold_config.trunk    ,				SCREAMING_SNAKE_CASE ) and key != "structure_module":
                setattr(esmfold_config.trunk    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE )
        for key, val in esm.cfg.trunk.structure_module.items():
            if hasattr(esmfold_config.trunk.structure_module    ,				SCREAMING_SNAKE_CASE ):
                setattr(esmfold_config.trunk.structure_module    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE )
    elif hasattr(SCREAMING_SNAKE_CASE    ,				'''args''' ):
        # Indicates an ESM-1b or ESM-1v model
        __UpperCAmelCase			   =     esm.args.embed_dim
        __UpperCAmelCase			   =     esm.args.layers
        __UpperCAmelCase			   =     esm.args.attention_heads
        __UpperCAmelCase			   =     esm.args.ffn_embed_dim
        __UpperCAmelCase			   =     esm.args.token_dropout
        __UpperCAmelCase			   =     True if esm.emb_layer_norm_before else False
        __UpperCAmelCase			   =     '''absolute'''
        __UpperCAmelCase			   =     False
        __UpperCAmelCase			   =     None
    else:
        # Indicates an ESM-2 model
        __UpperCAmelCase			   =     esm.embed_dim
        __UpperCAmelCase			   =     esm.num_layers
        __UpperCAmelCase			   =     esm.attention_heads
        __UpperCAmelCase			   =     4 * embed_dim  # This is hardcoded in ESM-2
        __UpperCAmelCase			   =     esm.token_dropout
        __UpperCAmelCase			   =     False  # This code path does not exist in ESM-2
        __UpperCAmelCase			   =     '''rotary'''
        __UpperCAmelCase			   =     False
        __UpperCAmelCase			   =     None

    if is_folding_model:
        __UpperCAmelCase			   =     esm.esm.alphabet
    __UpperCAmelCase			   =     tuple(alphabet.all_toks )
    __UpperCAmelCase			   =     alphabet.mask_idx
    __UpperCAmelCase			   =     alphabet.padding_idx

    if is_folding_model:
        __UpperCAmelCase			   =     esm.esm
    else:
        __UpperCAmelCase			   =     esm

    __UpperCAmelCase			   =     EsmConfig(
        vocab_size=original_esm_model.embed_tokens.num_embeddings    ,				mask_token_id=SCREAMING_SNAKE_CASE    ,				hidden_size=SCREAMING_SNAKE_CASE    ,				num_hidden_layers=SCREAMING_SNAKE_CASE    ,				num_attention_heads=SCREAMING_SNAKE_CASE    ,				intermediate_size=SCREAMING_SNAKE_CASE    ,				max_position_embeddings=1_0_2_6    ,				layer_norm_eps=1e-5    ,				attention_probs_dropout_prob=0.0    ,				hidden_dropout_prob=0.0    ,				pad_token_id=SCREAMING_SNAKE_CASE    ,				emb_layer_norm_before=SCREAMING_SNAKE_CASE    ,				token_dropout=SCREAMING_SNAKE_CASE    ,				position_embedding_type=SCREAMING_SNAKE_CASE    ,				is_folding_model=SCREAMING_SNAKE_CASE    ,				esmfold_config=SCREAMING_SNAKE_CASE    ,				vocab_list=SCREAMING_SNAKE_CASE    ,				)
    if classification_head:
        __UpperCAmelCase			   =     esm.classification_heads['''mnli'''].out_proj.weight.shape[0]
    print('''Our ESM config:'''    ,				SCREAMING_SNAKE_CASE )

    if model.startswith('''esmfold''' ):
        __UpperCAmelCase			   =     EsmForProteinFolding
    elif classification_head:
        __UpperCAmelCase			   =     EsmForSequenceClassification
    else:
        __UpperCAmelCase			   =     EsmForMaskedLM
    __UpperCAmelCase			   =     model_class(SCREAMING_SNAKE_CASE )
    model.eval()

    # Now let's copy all the weights.
    # Embeddings
    __UpperCAmelCase			   =     original_esm_model.embed_tokens.weight
    if position_embedding_type == "absolute":
        __UpperCAmelCase			   =     original_esm_model.embed_positions.weight

    if config.emb_layer_norm_before:
        __UpperCAmelCase			   =     original_esm_model.emb_layer_norm_before.weight
        __UpperCAmelCase			   =     original_esm_model.emb_layer_norm_before.bias

    __UpperCAmelCase			   =     original_esm_model.emb_layer_norm_after.weight
    __UpperCAmelCase			   =     original_esm_model.emb_layer_norm_after.bias

    for i in range(config.num_hidden_layers ):
        # Encoder: start of layer
        __UpperCAmelCase			   =     model.esm.encoder.layer[i]
        # esm_layer: TransformerSentenceEncoderLayer = original_esm_model.layers[i]
        __UpperCAmelCase			   =     original_esm_model.layers[i]

        # self attention
        __UpperCAmelCase			   =     layer.attention.self
        assert (
            esm_layer.self_attn.k_proj.weight.data.shape
            == esm_layer.self_attn.q_proj.weight.data.shape
            == esm_layer.self_attn.v_proj.weight.data.shape
            == torch.Size((config.hidden_size, config.hidden_size) )
        )

        __UpperCAmelCase			   =     esm_layer.self_attn.q_proj.weight
        __UpperCAmelCase			   =     esm_layer.self_attn.q_proj.bias
        __UpperCAmelCase			   =     esm_layer.self_attn.k_proj.weight
        __UpperCAmelCase			   =     esm_layer.self_attn.k_proj.bias
        __UpperCAmelCase			   =     esm_layer.self_attn.v_proj.weight
        __UpperCAmelCase			   =     esm_layer.self_attn.v_proj.bias

        if getattr(esm_layer.self_attn    ,				'''rot_emb'''    ,				SCREAMING_SNAKE_CASE ) is not None:
            # Matt: Although inv_freq is not a trainable weight, it is computed at model init and cached.
            # During the training of ESM-2 the model was converted to float16 precision, which also converts
            # the inv_freq tensor, and the loss of precision remains even if the model is loaded later as float32.
            # If we recompute inv_freq without this loss of precision then we will get subtly different rotary
            # embeddings, which are enough to cause significant discrepancies in model outputs. To avoid this,
            # we make sure the new model copies the data from the old inv_freq.
            __UpperCAmelCase			   =     esm_layer.self_attn.rot_emb.inv_freq

        # LayerNorm changes for pre-activation
        __UpperCAmelCase			   =     esm_layer.self_attn_layer_norm.weight
        __UpperCAmelCase			   =     esm_layer.self_attn_layer_norm.bias
        __UpperCAmelCase			   =     esm_layer.final_layer_norm.weight
        __UpperCAmelCase			   =     esm_layer.final_layer_norm.bias

        # self-attention output
        __UpperCAmelCase			   =     layer.attention.output
        assert self_output.dense.weight.shape == esm_layer.self_attn.out_proj.weight.shape
        __UpperCAmelCase			   =     esm_layer.self_attn.out_proj.weight
        __UpperCAmelCase			   =     esm_layer.self_attn.out_proj.bias

        # intermediate
        __UpperCAmelCase			   =     layer.intermediate
        assert intermediate.dense.weight.shape == esm_layer.fca.weight.shape
        __UpperCAmelCase			   =     esm_layer.fca.weight
        __UpperCAmelCase			   =     esm_layer.fca.bias

        # output
        __UpperCAmelCase			   =     layer.output
        assert bert_output.dense.weight.shape == esm_layer.fca.weight.shape
        __UpperCAmelCase			   =     esm_layer.fca.weight
        __UpperCAmelCase			   =     esm_layer.fca.bias
        # end of layer

    if is_folding_model:
        __UpperCAmelCase			   =     esm.esm_s_combine.data
        __UpperCAmelCase			   =     esm.afa_to_esm.data
        transfer_and_check_weights(esm.embedding    ,				model.embedding )
        transfer_and_check_weights(esm.esm_s_mlp    ,				model.esm_s_mlp )
        transfer_and_check_weights(esm.trunk    ,				model.trunk )
        transfer_and_check_weights(esm.distogram_head    ,				model.distogram_head )
        transfer_and_check_weights(esm.ptm_head    ,				model.ptm_head )
        transfer_and_check_weights(esm.lm_head    ,				model.lm_head )
        transfer_and_check_weights(esm.lddt_head    ,				model.lddt_head )

    elif classification_head:
        __UpperCAmelCase			   =     esm.esm.classification_heads['''mnli'''].dense.weight
        __UpperCAmelCase			   =     esm.classification_heads['''mnli'''].dense.bias
        __UpperCAmelCase			   =     esm.classification_heads['''mnli'''].out_proj.weight
        __UpperCAmelCase			   =     esm.classification_heads['''mnli'''].out_proj.bias
    else:
        # LM Head
        __UpperCAmelCase			   =     esm.lm_head.dense.weight
        __UpperCAmelCase			   =     esm.lm_head.dense.bias
        __UpperCAmelCase			   =     esm.lm_head.layer_norm.weight
        __UpperCAmelCase			   =     esm.lm_head.layer_norm.bias
        __UpperCAmelCase			   =     esm.lm_head.weight
        __UpperCAmelCase			   =     esm.lm_head.bias

    # Contact prediction head
    transfer_and_check_weights(esm.contact_head    ,				model.esm.contact_head )

    # Prepare data (first 2 sequences from ESMStructuralSplitDataset superfamily / 4)
    if is_folding_model:
        # Folding models aren't trained on masked inputs and don't like mask tokens.
        __UpperCAmelCase			   =     SAMPLE_DATA[:2]
    else:
        __UpperCAmelCase			   =     SAMPLE_DATA

    if is_folding_model:
        __UpperCAmelCase			   =     get_esmfold_tokenizer()
        __UpperCAmelCase			   =     hf_tokenizer(
            [row[1] for row in sample_data]    ,				return_tensors='''pt'''    ,				padding=SCREAMING_SNAKE_CASE    ,				add_special_tokens=SCREAMING_SNAKE_CASE )
        __UpperCAmelCase   ,       __UpperCAmelCase   ,       __UpperCAmelCase   ,       __UpperCAmelCase   ,       __UpperCAmelCase			   =     esmfold_encode_sequences([row[1] for row in sample_data] )
        __UpperCAmelCase			   =     torch.all(hf_tokens['''input_ids'''] == esmfold_aas ) and torch.all(
            hf_tokens['''attention_mask'''] == esmfold_mask )
    else:
        # Let's check that we get the same results.
        __UpperCAmelCase			   =     alphabet.get_batch_converter()
        __UpperCAmelCase   ,       __UpperCAmelCase   ,       __UpperCAmelCase			   =     batch_converter(SCREAMING_SNAKE_CASE )
        # Prepare tokenizer and make sure it matches
        with TemporaryDirectory() as tempdir:
            __UpperCAmelCase			   =     '''\n'''.join(alphabet.all_toks )
            __UpperCAmelCase			   =     Path(SCREAMING_SNAKE_CASE ) / '''vocab.txt'''
            vocab_file.write_text(SCREAMING_SNAKE_CASE )
            __UpperCAmelCase			   =     EsmTokenizer(vocab_file=str(SCREAMING_SNAKE_CASE ) )

        __UpperCAmelCase			   =     hf_tokenizer([row[1] for row in sample_data]    ,				return_tensors='''pt'''    ,				padding=SCREAMING_SNAKE_CASE )
        __UpperCAmelCase			   =     torch.all(hf_tokens['''input_ids'''] == batch_tokens )

    print('''Do both models tokenizers output the same tokens?'''    ,				'''🔥''' if success else '''💩''' )
    if not success:
        raise Exception('''Tokenization does not match!''' )

    with torch.no_grad():
        if is_folding_model:
            # Let's test the model in parts
            # ESMFold always converts the ESM stem to float16, which requires float16 ops
            # that don't exist on CPU. Therefore, to test it we need to run it on GPU. However,
            # ESMFold is what we in the community call a "big boy" and so we desperately avoid putting both the
            # original and the converted model on the GPU at the same time.
            __UpperCAmelCase			   =     esm.cuda().infer([row[1] for row in sample_data] )
            __UpperCAmelCase			   =     model.cuda()(
                input_ids=hf_tokens['''input_ids'''].cuda()    ,				attention_mask=hf_tokens['''attention_mask'''].cuda() )
        else:
            __UpperCAmelCase			   =     model(**SCREAMING_SNAKE_CASE    ,				output_hidden_states=SCREAMING_SNAKE_CASE )
            __UpperCAmelCase			   =     our_output['''logits''']
            if classification_head:
                __UpperCAmelCase			   =     esm.model.classification_heads['''mnli'''](esm.extract_features(SCREAMING_SNAKE_CASE ) )
            else:
                __UpperCAmelCase			   =     esm(hf_tokens['''input_ids''']    ,				repr_layers=list(range(9_9_9 ) ) )
                __UpperCAmelCase			   =     their_output['''logits''']

        if is_folding_model:
            __UpperCAmelCase			   =     torch.max(torch.abs(our_output['''positions'''] - their_output['''positions'''] ) ).item()
            __UpperCAmelCase			   =     torch.allclose(our_output['''positions''']    ,				their_output['''positions''']    ,				atol=1e-5 )
        else:
            __UpperCAmelCase			   =     torch.max(torch.abs(our_output - their_output ) ).item()
            __UpperCAmelCase			   =     torch.allclose(SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				atol=1e-5 )

        print(f'''max_absolute_diff = {max_absolute_diff}''' )  # ~ 1e-5
        print('''Do both models output the same tensors?'''    ,				'''🔥''' if success else '''💩''' )

        if not success:
            raise Exception('''Something went wRoNg''' )

        if not is_folding_model:
            # Let's check contact prediction too
            __UpperCAmelCase			   =     model.predict_contacts(hf_tokens['''input_ids''']    ,				hf_tokens['''attention_mask'''] )
            __UpperCAmelCase			   =     esm.predict_contacts(hf_tokens['''input_ids'''] )
            __UpperCAmelCase			   =     torch.max(torch.abs(our_output - their_output ) ).item()
            __UpperCAmelCase			   =     torch.allclose(SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				atol=1e-5 )

            print('''Contact prediction testing:''' )
            print(f'''max_absolute_diff = {max_absolute_diff}''' )  # ~ 1e-5
            print('''Do both models output the same tensors?'''    ,				'''🔥''' if success else '''💩''' )

            if not success:
                raise Exception('''Something went wRoNg''' )

        pathlib.Path(SCREAMING_SNAKE_CASE ).mkdir(parents=SCREAMING_SNAKE_CASE    ,				exist_ok=SCREAMING_SNAKE_CASE )
        print(f'''Saving model to {pytorch_dump_folder_path}''' )
        model.save_pretrained(SCREAMING_SNAKE_CASE )

        del esm  # Free up some memory before continuing

    print(f'''Saving tokenizer to {pytorch_dump_folder_path}''' )
    hf_tokenizer.save_pretrained(SCREAMING_SNAKE_CASE )

    if push_to_repo:
        model.push_to_hub(repo_id=SCREAMING_SNAKE_CASE    ,				use_auth_token=SCREAMING_SNAKE_CASE )
        hf_tokenizer.push_to_hub(repo_id=SCREAMING_SNAKE_CASE    ,				use_auth_token=SCREAMING_SNAKE_CASE )


if __name__ == "__main__":
       A_						:     Optional[int]			  =				argparse.ArgumentParser()
       # Required parameters
       parser.add_argument(
           '--pytorch_dump_folder_path', type=str, required=True, help='Path to the output PyTorch model.'
       )
       parser.add_argument(
           '--classification_head', action='store_true', help='Whether to convert a final classification head.'
       )
       parser.add_argument('--model', default=None, type=str, required=True, help='Name of model to convert.')
       parser.add_argument('--push_to_repo', type=str, help='Repo to upload to (including username!).')
       parser.add_argument('--auth_token', type=str, help='HuggingFace auth token.')
       A_						:     Tuple			  =				parser.parse_args()
       convert_esm_checkpoint_to_pytorch(
           args.model, args.pytorch_dump_folder_path, args.classification_head, args.push_to_repo, args.auth_token
       )







from __future__ import annotations


def  __a    (				SCREAMING_SNAKE_CASE ) ->       list[int]:






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

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

    __UpperCAmelCase			   =     max(len(bin(SCREAMING_SNAKE_CASE )[2:] ) for x in list_of_ints )
    return _msd_radix_sort(SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE )


def  __a    (				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE ) ->       list[int]:






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

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

    # recursively split both lists further
    __UpperCAmelCase			   =     _msd_radix_sort(SCREAMING_SNAKE_CASE    ,				bit_position - 1 )
    __UpperCAmelCase			   =     _msd_radix_sort(SCREAMING_SNAKE_CASE    ,				bit_position - 1 )

    # recombine lists
    __UpperCAmelCase			   =     zeros
    res.extend(SCREAMING_SNAKE_CASE )

    return res


def  __a    (				SCREAMING_SNAKE_CASE ) ->       Optional[int]:






    '''simple docstring'''
    __UpperCAmelCase			   =     len(SCREAMING_SNAKE_CASE )
    if not list_of_ints or length == 1:
        return

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

    __UpperCAmelCase			   =     max(len(bin(SCREAMING_SNAKE_CASE )[2:] ) for x in list_of_ints )
    _msd_radix_sort_inplace(SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				0    ,				SCREAMING_SNAKE_CASE )


def  __a    (				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE ) ->       int:






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

    bit_position -= 1

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

        if changed:
            continue

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

    _msd_radix_sort_inplace(SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE )
    _msd_radix_sort_inplace(SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE    ,				SCREAMING_SNAKE_CASE )


if __name__ == "__main__":
       import doctest

       doctest.testmod()




