





import argparse
import json
import os

import fairseq
import torch
from fairseq.data import Dictionary

from transformers import (
    UniSpeechConfig,
    UniSpeechForCTC,
    UniSpeechForPreTraining,
    WavaVecaFeatureExtractor,
    WavaVecaPhonemeCTCTokenizer,
    WavaVecaProcessor,
    logging,
)


logging.set_verbosity_info()
_lowerCAmelCase				:   Dict						       =						logging.get_logger(__name__)

_lowerCAmelCase				:   List[str]						       =						{
    '''post_extract_proj''': '''feature_projection.projection''',
    '''encoder.pos_conv.0''': '''encoder.pos_conv_embed.conv''',
    '''self_attn.k_proj''': '''encoder.layers.*.attention.k_proj''',
    '''self_attn.v_proj''': '''encoder.layers.*.attention.v_proj''',
    '''self_attn.q_proj''': '''encoder.layers.*.attention.q_proj''',
    '''self_attn.out_proj''': '''encoder.layers.*.attention.out_proj''',
    '''self_attn_layer_norm''': '''encoder.layers.*.layer_norm''',
    '''fc1''': '''encoder.layers.*.feed_forward.intermediate_dense''',
    '''fc2''': '''encoder.layers.*.feed_forward.output_dense''',
    '''final_layer_norm''': '''encoder.layers.*.final_layer_norm''',
    '''encoder.layer_norm''': '''encoder.layer_norm''',
    '''w2v_model.layer_norm''': '''feature_projection.layer_norm''',
    '''quantizer.weight_proj''': '''quantizer.weight_proj''',
    '''quantizer.vars''': '''quantizer.codevectors''',
    '''project_q''': '''project_q''',
    '''final_proj''': '''project_hid''',
    '''w2v_encoder.proj''': '''ctc_proj''',
    '''mask_emb''': '''masked_spec_embed''',
}
_lowerCAmelCase				:   Optional[Any]						       =						[
    '''ctc_proj''',
    '''quantizer.weight_proj''',
    '''quantizer.codevectors''',
    '''project_q''',
    '''project_hid''',
]

def   __snake_case    (       _lowerCAmelCase			:			str					,					_lowerCAmelCase			:			str					,					_lowerCAmelCase			:			Dict					,					_lowerCAmelCase			:			Any					,					_lowerCAmelCase			:			Union[str, Any]					,					_lowerCAmelCase			:			Any						)			->    Dict:
   for attribute in key.split("."						):
      if is_finetuned:
         if attribute in ["quantizer", "project_q", "project_hid"]:
            # those layers are only relevant for pretraining and should be dropped
            return

         if attribute == "ctc_proj":
            # we should rename `ctc_proj` to `lm_head` for fine-tuned phoneme models
            A_       :					Optional[Any]        =      "lm_head"

      A_       :					Dict        =      getattr(_lowerCAmelCase					,					_lowerCAmelCase						)

   if weight_type is not None:
      A_       :					Dict        =      getattr(_lowerCAmelCase					,					_lowerCAmelCase						).shape
   else:
      A_       :					List[Any]        =      hf_pointer.shape

   assert hf_shape == value.shape, (
       f"Shape of hf {key + '.' + weight_type if weight_type is not None else ''} is {hf_shape}, but should be"
       f" {value.shape} for {full_name}"
   )

   if weight_type == "weight":
      A_       :					int        =      value
   elif weight_type == "weight_g":
      A_       :					int        =      value
   elif weight_type == "weight_v":
      A_       :					str        =      value
   elif weight_type == "bias":
      A_       :					Union[str, Any]        =      value
   else:
      A_       :					Optional[int]        =      value

   logger.info(f"{key + '.' + weight_type if weight_type is not None else ''} was initialized from {full_name}."						)

def   __snake_case    (       _lowerCAmelCase			:			List[Any]					,					_lowerCAmelCase			:			str					,					_lowerCAmelCase			:			int						)			->    Optional[int]:
   A_       :					List[Any]        =      []
   A_       :					str        =      fairseq_model.state_dict()

   A_       :					int        =      hf_model.unispeech.feature_extractor

   for name, value in fairseq_dict.items():
      A_       :					Any        =      False
      if "conv_layers" in name:
         load_conv_layer(
             _lowerCAmelCase					,					_lowerCAmelCase					,					_lowerCAmelCase					,					_lowerCAmelCase					,					hf_model.config.feat_extract_norm == "group"					,					)
         A_       :					Dict        =      True
      else:
         for key, mapped_key in MAPPING.items():
            A_       :					Optional[int]        =      "unispeech." + mapped_key if mapped_key not in TOP_LEVEL_KEYS else mapped_key
            if key in name or key.split("w2v_model."						)[-1] == name.split("."						)[0]:
               A_       :					Tuple        =      True
               if "*" in mapped_key:
                  A_       :					Any        =      name.split(_lowerCAmelCase						)[0].split("."						)[-2]
                  A_       :					Any        =      mapped_key.replace("*"					,					_lowerCAmelCase						)
               if "weight_g" in name:
                  A_       :					List[Any]        =      "weight_g"
               elif "weight_v" in name:
                  A_       :					List[str]        =      "weight_v"
               elif "bias" in name:
                  A_       :					Any        =      "bias"
               elif "weight" in name:
                  # TODO: don't match quantizer.weight_proj
                  A_       :					Optional[int]        =      "weight"
               else:
                  A_       :					Any        =      None
               set_recursively(_lowerCAmelCase					,					_lowerCAmelCase					,					_lowerCAmelCase					,					_lowerCAmelCase					,					_lowerCAmelCase					,					_lowerCAmelCase						)
            continue
      if not is_used:
         unused_weights.append(_lowerCAmelCase						)

   logger.warning(f"Unused weights: {unused_weights}"						)

def   __snake_case    (       _lowerCAmelCase			:			str					,					_lowerCAmelCase			:			Dict					,					_lowerCAmelCase			:			Optional[int]					,					_lowerCAmelCase			:			List[Any]					,					_lowerCAmelCase			:			Any						)			->    str:
   A_       :					int        =      full_name.split("conv_layers."						)[-1]
   A_       :					str        =      name.split("."						)
   A_       :					Union[str, Any]        =      int(items[0]						)
   A_       :					Optional[int]        =      int(items[1]						)

   if type_id == 0:
      if "bias" in name:
         assert value.shape == feature_extractor.conv_layers[layer_id].conv.bias.data.shape, (
             f"{full_name} has size {value.shape}, but"
             f" {feature_extractor.conv_layers[layer_id].conv.bias.data.shape} was found."
         )
         A_       :					int        =      value
         logger.info(f"Feat extract conv layer {layer_id} was initialized from {full_name}."						)
      elif "weight" in name:
         assert value.shape == feature_extractor.conv_layers[layer_id].conv.weight.data.shape, (
             f"{full_name} has size {value.shape}, but"
             f" {feature_extractor.conv_layers[layer_id].conv.weight.data.shape} was found."
         )
         A_       :					Optional[Any]        =      value
         logger.info(f"Feat extract conv layer {layer_id} was initialized from {full_name}."						)
   elif (type_id == 2 and not use_group_norm) or (type_id == 2 and layer_id == 0 and use_group_norm):
      if "bias" in name:
         assert value.shape == feature_extractor.conv_layers[layer_id].layer_norm.bias.data.shape, (
             f"{full_name} has size {value.shape}, but {feature_extractor[layer_id].layer_norm.bias.data.shape} was"
             " found."
         )
         A_       :					Any        =      value
         logger.info(f"Feat extract layer norm weight of layer {layer_id} was initialized from {full_name}."						)
      elif "weight" in name:
         assert value.shape == feature_extractor.conv_layers[layer_id].layer_norm.weight.data.shape, (
             f"{full_name} has size {value.shape}, but"
             f" {feature_extractor[layer_id].layer_norm.weight.data.shape} was found."
         )
         A_       :					Optional[Any]        =      value
         logger.info(f"Feat extract layer norm weight of layer {layer_id} was initialized from {full_name}."						)
   else:
      unused_weights.append(_lowerCAmelCase						)

@torch.no_grad()
def   __snake_case    (       _lowerCAmelCase			:			int					,					_lowerCAmelCase			:			Optional[int]					,					_lowerCAmelCase			:			List[Any]=None					,					_lowerCAmelCase			:			Optional[int]=None					,					_lowerCAmelCase			:			Dict=True						)			->    Dict:
   if config_path is not None:
      A_       :					List[Any]        =      UniSpeechConfig.from_pretrained(_lowerCAmelCase						)
   else:
      A_       :					Tuple        =      UniSpeechConfig()

   if is_finetuned:
      if dict_path:
         A_       :					str        =      Dictionary.load_from_json(_lowerCAmelCase						)

         # important change bos & pad token id since CTC symbol is <pad> and
         # not <s> as in fairseq
         A_       :					str        =      target_dict.pad_index
         A_       :					Dict        =      target_dict.bos_index
         A_       :					List[Any]        =      target_dict.eos_index
         A_       :					Dict        =      len(target_dict.symbols						)
         A_       :					Tuple        =      os.path.join(_lowerCAmelCase					,					"vocab.json"						)
         if not os.path.isdir(_lowerCAmelCase						):
            logger.error("--pytorch_dump_folder_path ({}) should be a directory".format(_lowerCAmelCase						)						)
            return
         os.makedirs(_lowerCAmelCase					,					exist_ok=_lowerCAmelCase						)
         A_       :					Any        =      target_dict.indices

         # fairseq has the <pad> and <s> switched
         A_       :					Tuple        =      42
         A_       :					Dict        =      43
         with open(_lowerCAmelCase					,					"w"					,					encoding="utf-8"						) as vocab_handle:
            json.dump(_lowerCAmelCase					,					_lowerCAmelCase						)
         A_       :					Union[str, Any]        =      WavaVecaPhonemeCTCTokenizer(
             _lowerCAmelCase					,					unk_token=target_dict.unk_word					,					pad_token=target_dict.pad_word					,					bos_token=target_dict.bos_word					,					eos_token=target_dict.eos_word					,					word_delimiter_token="|"					,					do_lower_case=_lowerCAmelCase					,					)
         A_       :					Dict        =      True if config.feat_extract_norm == "layer" else False
         A_       :					Optional[int]        =      WavaVecaFeatureExtractor(
             feature_size=1					,					sampling_rate=16000					,					padding_value=0					,					do_normalize=_lowerCAmelCase					,					return_attention_mask=_lowerCAmelCase					,					)
         A_       :					Tuple        =      WavaVecaProcessor(feature_extractor=_lowerCAmelCase					,					tokenizer=_lowerCAmelCase						)
         processor.save_pretrained(_lowerCAmelCase						)

      A_       :					int        =      UniSpeechForCTC(_lowerCAmelCase						)
   else:
      A_       :					Any        =      UniSpeechForPreTraining(_lowerCAmelCase						)

   if is_finetuned:
      A_   ,    A_   ,    A_       :					int        =      fairseq.checkpoint_utils.load_model_ensemble_and_task(
          [checkpoint_path]					,					arg_overrides={"data": "/".join(dict_path.split("/"						)[:-1]						), "w2v_path": checkpoint_path}						)
   else:
      A_   ,    A_   ,    A_       :					str        =      fairseq.checkpoint_utils.load_model_ensemble_and_task([checkpoint_path]						)

   A_       :					List[str]        =      model[0].eval()

   recursively_load_weights(_lowerCAmelCase					,					_lowerCAmelCase					,					_lowerCAmelCase						)

   hf_unispeech.save_pretrained(_lowerCAmelCase						)


if __name__ == "__main__":
 _lowerCAmelCase				:   Union[str, Any]						       =						argparse.ArgumentParser()
 parser.add_argument('''--pytorch_dump_folder_path''', default=None, type=str, help='''Path to the output PyTorch model.''')
 parser.add_argument('''--checkpoint_path''', default=None, type=str, help='''Path to fairseq checkpoint''')
 parser.add_argument('''--dict_path''', default=None, type=str, help='''Path to dict of fine-tuned model''')
 parser.add_argument('''--config_path''', default=None, type=str, help='''Path to hf config.json of model to convert''')
 parser.add_argument(
     '''--not_finetuned''', action='''store_true''', help='''Whether the model to convert is a fine-tuned model or not'''
 )
 _lowerCAmelCase				:   Optional[int]						       =						parser.parse_args()
 convert_unispeech_checkpoint(
     args.checkpoint_path, args.pytorch_dump_folder_path, args.config_path, args.dict_path, not args.not_finetuned
 )







from __future__ import annotations

import math
import random
from typing import Any


class        __magic_name__	:





     """simple docstring"""



     def __init__(				self							:Tuple	):





        '''simple docstring'''




        A_       :					list[Any]        =      []
        A_       :					int        =      0
        A_       :					int        =      0



     def     SCREAMING_SNAKE_CASE		(				self							:List[Any]	):





        '''simple docstring'''




        return self.head == self.tail



     def     SCREAMING_SNAKE_CASE		(				self							:Optional[Any]      ,   snake_case							:Any	):





        '''simple docstring'''




        self.data.append(snake_case	)
        A_       :					int        =      self.tail + 1



     def     SCREAMING_SNAKE_CASE		(				self							:str	):





        '''simple docstring'''




        A_       :					int        =      self.data[self.head]
        A_       :					Tuple        =      self.head + 1
        return ret



     def     SCREAMING_SNAKE_CASE		(				self							:Optional[int]	):





        '''simple docstring'''




        return self.tail - self.head





     def     SCREAMING_SNAKE_CASE		(				self							:Any	):





        '''simple docstring'''




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




class        __magic_name__	:





     """simple docstring"""



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





        '''simple docstring'''




        A_       :					Any        =      data
        A_       :					MyNode | None        =      None
        A_       :					MyNode | None        =      None
        A_       :					int        =      1



     def     SCREAMING_SNAKE_CASE		(				self							:List[str]	):





        '''simple docstring'''




        return self.data



     def     SCREAMING_SNAKE_CASE		(				self							:Dict	):





        '''simple docstring'''




        return self.left



     def     SCREAMING_SNAKE_CASE		(				self							:Any	):





        '''simple docstring'''




        return self.right



     def     SCREAMING_SNAKE_CASE		(				self							:List[Any]	):





        '''simple docstring'''




        return self.height



     def     SCREAMING_SNAKE_CASE		(				self							:List[str]      ,   snake_case							:Any	):





        '''simple docstring'''




        A_       :					Optional[int]        =      data



     def     SCREAMING_SNAKE_CASE		(				self							:Optional[int]      ,   snake_case							:MyNode | None	):





        '''simple docstring'''




        A_       :					Tuple        =      node



     def     SCREAMING_SNAKE_CASE		(				self							:str      ,   snake_case							:MyNode | None	):





        '''simple docstring'''




        A_       :					str        =      node





     def     SCREAMING_SNAKE_CASE		(				self							:Tuple      ,   snake_case							:int	):





        '''simple docstring'''




        A_       :					Optional[int]        =      height




def   __snake_case    (       _lowerCAmelCase			:			MyNode | None						)			->    int:
   if node is None:
      return 0
   return node.get_height()

def   __snake_case    (       _lowerCAmelCase			:			int					,					_lowerCAmelCase			:			int						)			->    int:
   if a > b:
      return a
   return b

def   __snake_case    (       _lowerCAmelCase			:			MyNode						)			->    MyNode:
   print("left rotation node:"					,					node.get_data()						)
   A_       :					Optional[int]        =      node.get_left()
   assert ret is not None
   node.set_left(ret.get_right()						)
   ret.set_right(_lowerCAmelCase						)
   A_       :					Any        =      my_max(get_height(node.get_right()						)					,					get_height(node.get_left()						)						) + 1
   node.set_height(_lowerCAmelCase						)
   A_       :					List[str]        =      my_max(get_height(ret.get_right()						)					,					get_height(ret.get_left()						)						) + 1
   ret.set_height(_lowerCAmelCase						)
   return ret

def   __snake_case    (       _lowerCAmelCase			:			MyNode						)			->    MyNode:
   print("right rotation node:"					,					node.get_data()						)
   A_       :					Union[str, Any]        =      node.get_right()
   assert ret is not None
   node.set_right(ret.get_left()						)
   ret.set_left(_lowerCAmelCase						)
   A_       :					int        =      my_max(get_height(node.get_right()						)					,					get_height(node.get_left()						)						) + 1
   node.set_height(_lowerCAmelCase						)
   A_       :					Dict        =      my_max(get_height(ret.get_right()						)					,					get_height(ret.get_left()						)						) + 1
   ret.set_height(_lowerCAmelCase						)
   return ret

def   __snake_case    (       _lowerCAmelCase			:			MyNode						)			->    MyNode:
   A_       :					List[Any]        =      node.get_left()
   assert left_child is not None
   node.set_left(left_rotation(_lowerCAmelCase						)						)
   return right_rotation(_lowerCAmelCase						)

def   __snake_case    (       _lowerCAmelCase			:			MyNode						)			->    MyNode:
   A_       :					List[Any]        =      node.get_right()
   assert right_child is not None
   node.set_right(right_rotation(_lowerCAmelCase						)						)
   return left_rotation(_lowerCAmelCase						)

def   __snake_case    (       _lowerCAmelCase			:			MyNode | None					,					_lowerCAmelCase			:			Any						)			->    MyNode | None:
   if node is None:
      return MyNode(_lowerCAmelCase						)
   if data < node.get_data():
      node.set_left(insert_node(node.get_left()					,					_lowerCAmelCase						)						)
      if (
          get_height(node.get_left()						) - get_height(node.get_right()						) == 2
      ):  # an unbalance detected
         A_       :					Any        =      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
            A_       :					Optional[int]        =      right_rotation(_lowerCAmelCase						)
         else:
            A_       :					int        =      lr_rotation(_lowerCAmelCase						)
   else:
      node.set_right(insert_node(node.get_right()					,					_lowerCAmelCase						)						)
      if get_height(node.get_right()						) - get_height(node.get_left()						) == 2:
         A_       :					Dict        =      node.get_right()
         assert right_child is not None
         if data < right_child.get_data():
            A_       :					Optional[Any]        =      rl_rotation(_lowerCAmelCase						)
         else:
            A_       :					Dict        =      left_rotation(_lowerCAmelCase						)
   A_       :					Optional[int]        =      my_max(get_height(node.get_right()						)					,					get_height(node.get_left()						)						) + 1
   node.set_height(_lowerCAmelCase						)
   return node

def   __snake_case    (       _lowerCAmelCase			:			MyNode						)			->    Any:
   while True:
      A_       :					Any        =      root.get_right()
      if right_child is None:
         break
      A_       :					Optional[Any]        =      right_child
   return root.get_data()

def   __snake_case    (       _lowerCAmelCase			:			MyNode						)			->    Any:
   while True:
      A_       :					Optional[Any]        =      root.get_left()
      if left_child is None:
         break
      A_       :					int        =      left_child
   return root.get_data()

def   __snake_case    (       _lowerCAmelCase			:			MyNode					,					_lowerCAmelCase			:			Any						)			->    MyNode | None:
   A_       :					Optional[int]        =      root.get_left()
   A_       :					Dict        =      root.get_right()
   if root.get_data() == data:
      if left_child is not None and right_child is not None:
         A_       :					int        =      get_left_most(_lowerCAmelCase						)
         root.set_data(_lowerCAmelCase						)
         root.set_right(del_node(_lowerCAmelCase					,					_lowerCAmelCase						)						)
      elif left_child is not None:
         A_       :					Tuple        =      left_child
      elif right_child is not None:
         A_       :					Any        =      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(_lowerCAmelCase					,					_lowerCAmelCase						)						)
   else:  # root.get_data() < data
      if right_child is None:
         return root
      else:
         root.set_right(del_node(_lowerCAmelCase					,					_lowerCAmelCase						)						)

   if get_height(_lowerCAmelCase						) - get_height(_lowerCAmelCase						) == 2:
      assert right_child is not None
      if get_height(right_child.get_right()						) > get_height(right_child.get_left()						):
         A_       :					Dict        =      left_rotation(_lowerCAmelCase						)
      else:
         A_       :					List[Any]        =      rl_rotation(_lowerCAmelCase						)
   elif get_height(_lowerCAmelCase						) - get_height(_lowerCAmelCase						) == -2:
      assert left_child is not None
      if get_height(left_child.get_left()						) > get_height(left_child.get_right()						):
         A_       :					Optional[Any]        =      right_rotation(_lowerCAmelCase						)
      else:
         A_       :					Tuple        =      lr_rotation(_lowerCAmelCase						)
   A_       :					List[str]        =      my_max(get_height(root.get_right()						)					,					get_height(root.get_left()						)						) + 1
   root.set_height(_lowerCAmelCase						)
   return root


class        __magic_name__	:





     """simple docstring"""



     def __init__(				self							:List[str]	):





        '''simple docstring'''




        A_       :					MyNode | None        =      None



     def     SCREAMING_SNAKE_CASE		(				self							:List[Any]	):





        '''simple docstring'''




        return get_height(self.root	)



     def     SCREAMING_SNAKE_CASE		(				self							:str      ,   snake_case							:Any	):





        '''simple docstring'''




        print("insert:" + str(snake_case	)	)
        A_       :					List[Any]        =      insert_node(self.root      ,   snake_case	)



     def     SCREAMING_SNAKE_CASE		(				self							:Optional[Any]      ,   snake_case							:Any	):





        '''simple docstring'''




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





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





        '''simple docstring'''




        A_       :					Optional[Any]        =      ""
        A_       :					Optional[int]        =      MyQueue()
        q.push(self.root	)
        A_       :					Optional[int]        =      self.get_height()
        if layer == 0:
           return output
        A_       :					Dict        =      0
        while not q.is_empty():
           A_       :					Optional[int]        =      q.pop()
           A_       :					Union[str, Any]        =      " " * 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
           A_       :					str        =      cnt + 1
           for i in range(100	):
              if cnt == math.pow(2      ,   snake_case	) - 1:
                 A_       :					int        =      layer - 1
                 if layer == 0:
                    output += "\n*************************************"
                    return output
                 output += "\n"
                 break
        output += "\n*************************************"
        return output




def   __snake_case    (       )			->    None:
   import doctest

   doctest.testmod()


if __name__ == "__main__":
 _test()
 _lowerCAmelCase				:   int						       =						AVLtree()
 _lowerCAmelCase				:   Optional[int]						       =						list(range(10))
 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))
