


class A__     :



  """simple docstring"""



  def __init__( self			:  Tuple				,				lowerCamelCase__			:  str = ""				,				lowerCamelCase__			:  bool = False       ):
        # Mapping from the first character of the prefix of the node
        a__	:  dict[str, RadixNode]     =   {}

        # A node will be a leaf if the tree contains its word
        a__	:  Optional[Any]     =   is_leaf

        a__	:  Optional[Any]     =   prefix

  def    _UpperCamelCase( self			:  List[Any]				,				lowerCamelCase__			:  str       ):
        a__	:  List[str]     =   0
        for q, w in zip(self.prefix				,				lowerCamelCase__       ):
              if q != w:
                    break

              x += 1

        return self.prefix[:x], self.prefix[x:], word[x:]

  def    _UpperCamelCase( self			:  str				,				lowerCamelCase__			:  list[str]       ):
        for word in words:
              self.insert(lowerCamelCase__       )

  def    _UpperCamelCase( self			:  Dict				,				lowerCamelCase__			:  str       ):
        # Case 1: If the word is the prefix of the node
        # Solution: We set the current node as leaf
        if self.prefix == word:
              a__	:  Optional[int]     =   True

        # Case 2: The node has no edges that have a prefix to the word
        # Solution: We create an edge from the current node to a new one
        # containing the word
        elif word[0] not in self.nodes:
              a__	:  Optional[int]     =   RadixNode(prefix=lowerCamelCase__				,				is_leaf=lowerCamelCase__       )

        else:
              a__	:  List[str]     =   self.nodes[word[0]]
              a__,	a__,	a__	:  Dict     =   incoming_node.match(
                  lowerCamelCase__       )

              # Case 3: The node prefix is equal to the matching
              # Solution: We insert remaining word on the next node
              if remaining_prefix == "":
                    self.nodes[matching_string[0]].insert(lowerCamelCase__       )

              # Case 4: The word is greater equal to the matching
              # Solution: Create a node in between both nodes, change
              # prefixes and add the new node for the remaining word
              else:
                    a__	:  Optional[Any]     =   remaining_prefix

                    a__	:  str     =   self.nodes[matching_string[0]]
                    a__	:  Union[str, Any]     =   RadixNode(lowerCamelCase__				,				lowerCamelCase__       )
                    a__	:  int     =   aux_node

                    if remaining_word == "":
                          a__	:  Union[str, Any]     =   True
                    else:
                          self.nodes[matching_string[0]].insert(lowerCamelCase__       )

  def    _UpperCamelCase( self			:  Optional[int]				,				lowerCamelCase__			:  str       ):
        a__	:  List[Any]     =   self.nodes.get(word[0]				,				lowerCamelCase__       )
        if not incoming_node:
              return False
        else:
              a__,	a__,	a__	:  List[Any]     =   incoming_node.match(
                  lowerCamelCase__       )
              # If there is remaining prefix, the word can't be on the tree
              if remaining_prefix != "":
                    return False
              # This applies when the word and the prefix are equal
              elif remaining_word == "":
                    return incoming_node.is_leaf
              # We have word remaining so we check the next node
              else:
                    return incoming_node.find(lowerCamelCase__       )

  def    _UpperCamelCase( self			:  int				,				lowerCamelCase__			:  str       ):
        a__	:  Any     =   self.nodes.get(word[0]				,				lowerCamelCase__       )
        if not incoming_node:
              return False
        else:
              a__,	a__,	a__	:  Tuple     =   incoming_node.match(
                  lowerCamelCase__       )
              # If there is remaining prefix, the word can't be on the tree
              if remaining_prefix != "":
                    return False
              # We have word remaining so we check the next node
              elif remaining_word != "":
                    return incoming_node.delete(lowerCamelCase__       )
              else:
                    # If it is not a leaf, we don't have to delete
                    if not incoming_node.is_leaf:
                          return False
                    else:
                          # We delete the nodes if no edges go from it
                          if len(incoming_node.nodes       ) == 0:
                                del self.nodes[word[0]]
                                # We merge the current node with its only child
                                if len(self.nodes       ) == 1 and not self.is_leaf:
                                      a__	:  Any     =   list(self.nodes.values()       )[0]
                                      a__	:  List[str]     =   merging_node.is_leaf
                                      self.prefix += merging_node.prefix
                                      a__	:  List[str]     =   merging_node.nodes
                    # If there is more than 1 edge, we just mark it as non-leaf
                          elif len(incoming_node.nodes       ) > 1:
                                a__	:  Tuple     =   False
                          # If there is 1 edge, we merge it with its child
                          else:
                                a__	:  Union[str, Any]     =   list(incoming_node.nodes.values()       )[0]
                                a__	:  Optional[Any]     =   merging_node.is_leaf
                                incoming_node.prefix += merging_node.prefix
                                a__	:  Dict     =   merging_node.nodes

                          return True

  def    _UpperCamelCase( self			:  Optional[int]				,				lowerCamelCase__			:  int = 0       ):
        if self.prefix != "":
              print("-" * height				,				self.prefix				,				"  (leaf)" if self.is_leaf else ""       )

        for value in self.nodes.values():
              value.print_tree(height + 1       )




def UpperCamelCase_				(				)	->   bool:
      a__	:  Tuple     =   "banana bananas bandana band apple all beast".split()
      a__	:  Union[str, Any]     =   RadixNode()
      root.insert_many(__a      )

      assert all(root.find(__a      ) for word in words      )
      assert not root.find("bandanas"      )
      assert not root.find("apps"      )
      root.delete("all"      )
      assert not root.find("all"      )
      root.delete("banana"      )
      assert not root.find("banana"      )
      assert root.find("bananas"      )

      return True



def UpperCamelCase_				(				)	->   None:
      assert test_trie()



def UpperCamelCase_				(				)	->   None:
      a__	:  Tuple     =   RadixNode()
      a__	:  int     =   "banana bananas bandanas bandana band apple all beast".split()
      root.insert_many(__a      )

      print("Words:"			,				__a      )
      print("Tree:"      )
      root.print_tree()


if __name__ == "__main__":
    main()





'''simple docstring'''

from collections import OrderedDict
from typing import TYPE_CHECKING, Any, Mapping, Optional, Union

from ...configuration_utils import PretrainedConfig
from ...onnx import OnnxConfig, OnnxSeqaSeqConfigWithPast
from ...utils import logging


if TYPE_CHECKING:
 from ...feature_extraction_utils import FeatureExtractionMixin
 from ...tokenization_utils_base import PreTrainedTokenizerBase
 from ...utils import TensorType

lowerCamelCase				:  Dict    		=      logging.get_logger(__name__)

lowerCamelCase				:  List[Any]    		=      {
    'openai/whisper-base': 'https://huggingface.co/openai/whisper-base/resolve/main/config.json',
}

# fmt: off
lowerCamelCase				:  Dict    		=      [
    1, 2, 7, 8, 9, 10, 14, 25,
    26, 27, 28, 29, 31, 58, 59, 60, 61, 62,
    63, 90, 91, 92, 93, 357, 366, 438, 532, 685,
    705, 796, 930, 1_058, 1_220, 1_267, 1_279, 1_303, 1_343, 1_377,
    1_391, 1_635, 1_782, 1_875, 2_162, 2_361, 2_488, 3_467, 4_008, 4_211,
    4_600, 4_808, 5_299, 5_855, 6_329, 7_203, 9_609, 9_959, 10_563, 10_786,
    11_420, 11_709, 11_907, 13_163, 13_697, 13_700, 14_808, 15_306, 16_410, 16_791,
    17_992, 19_203, 19_510, 20_724, 22_305, 22_935, 27_007, 30_109, 30_420, 33_409,
    34_949, 40_283, 40_493, 40_549, 47_282, 49_146, 50_257, 50_359, 50_360, 50_361
]
lowerCamelCase				:  str    		=      [
    1, 2, 7, 8, 9, 10, 14, 25,
    26, 27, 28, 29, 31, 58, 59, 60, 61, 62,
    63, 90, 91, 92, 93, 359, 503, 522, 542, 873,
    893, 902, 918, 922, 931, 1_350, 1_853, 1_982, 2_460, 2_627,
    3_246, 3_253, 3_268, 3_536, 3_846, 3_961, 4_183, 4_667, 6_585, 6_647,
    7_273, 9_061, 9_383, 10_428, 10_929, 11_938, 12_033, 12_331, 12_562, 13_793,
    14_157, 14_635, 15_265, 15_618, 16_553, 16_604, 18_362, 18_956, 20_075, 21_675,
    22_520, 26_130, 26_161, 26_435, 28_279, 29_464, 31_650, 32_302, 32_470, 36_865,
    42_863, 47_425, 49_870, 50_254, 50_258, 50_360, 50_361, 50_362
]
class     __lowerCAmelCase		(lowercase_	):





      '''simple docstring'''






      lowerCAmelCase__   :	List[str]       =				"""whisper"""
      lowerCAmelCase__   :	Dict       =				["""past_key_values"""]
      lowerCAmelCase__   :	Optional[int]       =				{"""num_attention_heads""": """encoder_attention_heads""", """hidden_size""": """d_model"""}



      def __init__(self       :       int  ,		UpperCamelCase       :       Optional[int]=51865  ,		UpperCamelCase       :       Any=80  ,		UpperCamelCase       :       Dict=6  ,		UpperCamelCase       :       str=4  ,		UpperCamelCase       :       Optional[Any]=6  ,		UpperCamelCase       :       List[Any]=4  ,		UpperCamelCase       :       Tuple=1536  ,		UpperCamelCase       :       Dict=1536  ,		UpperCamelCase       :       Any=0.0  ,		UpperCamelCase       :       Any=0.0  ,		UpperCamelCase       :       int=50257  ,		UpperCamelCase       :       List[str]=True  ,		UpperCamelCase       :       List[Any]=True  ,		UpperCamelCase       :       List[str]="gelu"  ,		UpperCamelCase       :       Dict=256  ,		UpperCamelCase       :       Optional[int]=0.0  ,		UpperCamelCase       :       str=0.0  ,		UpperCamelCase       :       str=0.0  ,		UpperCamelCase       :       Dict=0.02  ,		UpperCamelCase       :       List[Any]=False  ,		UpperCamelCase       :       int=1500  ,		UpperCamelCase       :       List[str]=448  ,		UpperCamelCase       :       int=50256  ,		UpperCamelCase       :       Optional[int]=50256  ,		UpperCamelCase       :       Optional[Any]=50256  ,		UpperCamelCase       :       Any=None  ,		UpperCamelCase       :       Tuple=[220, 50256]  ,		UpperCamelCase       :       Optional[Any]=False  ,		UpperCamelCase       :       int=256  ,		UpperCamelCase       :       Optional[int]=False  ,		UpperCamelCase       :       int=0.05  ,		UpperCamelCase       :       List[Any]=10  ,		UpperCamelCase       :       Optional[int]=2  ,		UpperCamelCase       :       Optional[int]=0.0  ,		UpperCamelCase       :       Dict=10  ,		UpperCamelCase       :       Union[str, Any]=0  ,		UpperCamelCase       :       Union[str, Any]=7  ,		**UpperCamelCase       :       Union[str, Any]  ,		):

             '''simple docstring'''







             lowercase__      =					vocab_size
             lowercase__      =					num_mel_bins
             lowercase__      =					d_model
             lowercase__      =					encoder_layers
             lowercase__      =					encoder_attention_heads
             lowercase__      =					decoder_layers
             lowercase__      =					decoder_attention_heads
             lowercase__      =					decoder_ffn_dim
             lowercase__      =					encoder_ffn_dim
             lowercase__      =					dropout
             lowercase__      =					attention_dropout
             lowercase__      =					activation_dropout
             lowercase__      =					activation_function
             lowercase__      =					init_std
             lowercase__      =					encoder_layerdrop
             lowercase__      =					decoder_layerdrop
             lowercase__      =					use_cache
             lowercase__      =					encoder_layers
             lowercase__      =					scale_embedding  # scale factor will be sqrt(d_model) if True
             lowercase__      =					max_source_positions
             lowercase__      =					max_target_positions

             # Audio Classification-specific parameters. Feel free to ignore for other classes.
             lowercase__      =					classifier_proj_size
             lowercase__      =					use_weighted_layer_sum

             # fine-tuning config parameters for SpecAugment: https://arxiv.org/abs/1904.08779
             lowercase__      =					apply_spec_augment
             lowercase__      =					mask_time_prob
             lowercase__      =					mask_time_length
             lowercase__      =					mask_time_min_masks
             lowercase__      =					mask_feature_prob
             lowercase__      =					mask_feature_length
             lowercase__      =					mask_feature_min_masks

             lowercase__      =					median_filter_width

             super().__init__(
                 pad_token_id=UpperCamelCase  ,		bos_token_id=UpperCamelCase  ,		eos_token_id=UpperCamelCase  ,		is_encoder_decoder=UpperCamelCase  ,		decoder_start_token_id=UpperCamelCase  ,		suppress_tokens=UpperCamelCase  ,		begin_suppress_tokens=UpperCamelCase  ,		**UpperCamelCase  ,		)






class     __lowerCAmelCase		(lowercase_	):





      '''simple docstring'''






      @property
      def  UpperCamelCase__						(self       :       str					):

             '''simple docstring'''







             lowercase__      =					OrderedDict(
                 [
                     ('''input_features''', {0: '''batch''', 1: '''feature_size''', 2: '''encoder_sequence'''}),
                 ]					)
             if self.use_past:
                    lowercase__      =					{0: '''batch'''}
             else:
                    lowercase__      =					{0: '''batch''', 1: '''decoder_sequence'''}

             if self.use_past:
                    self.fill_with_past_key_values_(UpperCamelCase  ,		direction='''inputs'''					)

             return common_inputs



      def  UpperCamelCase__						(self       :       Union[str, Any]  ,		UpperCamelCase       :       Union["PreTrainedTokenizerBase", "FeatureExtractionMixin"]  ,		UpperCamelCase       :       int = -1  ,		UpperCamelCase       :       int = -1  ,		UpperCamelCase       :       bool = False  ,		UpperCamelCase       :       Optional["TensorType"] = None  ,		UpperCamelCase       :       int = 22050  ,		UpperCamelCase       :       float = 5.0  ,		UpperCamelCase       :       int = 220  ,		):

             '''simple docstring'''







             lowercase__      =					OrderedDict()
             lowercase__      =					OnnxConfig.generate_dummy_inputs(
                 self  ,		preprocessor=preprocessor.feature_extractor  ,		batch_size=UpperCamelCase  ,		framework=UpperCamelCase  ,		sampling_rate=UpperCamelCase  ,		time_duration=UpperCamelCase  ,		frequency=UpperCamelCase  ,		)
             lowercase__      =					encoder_inputs['''input_features'''].shape[2]
             lowercase__      =					encoder_sequence_length // 2 if self.use_past else seq_length

             lowercase__      =					super().generate_dummy_inputs(
                 preprocessor.tokenizer  ,		UpperCamelCase  ,		UpperCamelCase  ,		UpperCamelCase  ,		UpperCamelCase					)

             lowercase__      =					encoder_inputs.pop('''input_features'''					)
             lowercase__      =					decoder_inputs.pop('''decoder_input_ids'''					)

             if "past_key_values" in decoder_inputs:
                    lowercase__      =					decoder_inputs.pop('''past_key_values'''					)

             return dummy_inputs






      @property
      def  UpperCamelCase__						(self       :       Union[str, Any]					):

             '''simple docstring'''







             return 1E-3




