






'''simple docstring'''





import itertools
import random
import unittest

import numpy as np

from transformers import BatchFeature, SpeechTaFeatureExtractor
from transformers.testing_utils import require_torch
from transformers.utils.import_utils import is_torch_available

from ...test_sequence_feature_extraction_common import SequenceFeatureExtractionTestMixin


if is_torch_available():
 import torch


__A							:							List[str]  							=		random.Random()






def    lowerCamelCase_     (    lowercase__				,     lowercase__=1.0				,     lowercase__=None				,     lowercase__=None):
 if rng is None:
  lowerCamelCase__  =     global_rng

 lowerCamelCase__  =     []
 for batch_idx in range(shape[0]):
  values.append([])
  for _ in range(shape[1]):
   values[-1].append(rng.random() * scale)

 return values
@require_torch
class 				lowercase       (							unittest.TestCase      ):


    '''simple docstring'''

    def __init__(					self     :     Optional[int]				,     __lowerCamelCase     :     Tuple				,     __lowerCamelCase     :     Dict=7				,     __lowerCamelCase     :     Optional[Any]=400				,     __lowerCamelCase     :     int=2000				,     __lowerCamelCase     :     Any=1				,     __lowerCamelCase     :     Tuple=0.0				,     __lowerCamelCase     :     int=16000				,     __lowerCamelCase     :     Optional[int]=True				,     __lowerCamelCase     :     Optional[Any]=80				,     __lowerCamelCase     :     Optional[int]=16				,     __lowerCamelCase     :     List[Any]=64				,     __lowerCamelCase     :     Any="hann_window"				,     __lowerCamelCase     :     List[str]=80				,     __lowerCamelCase     :     Dict=7600				,     __lowerCamelCase     :     Optional[int]=1E-10				,     __lowerCamelCase     :     List[str]=True				,     )							->							List[str]:

     '''simple docstring'''




     lowerCamelCase__  =     parent
     lowerCamelCase__  =     batch_size
     lowerCamelCase__  =     min_seq_length
     lowerCamelCase__  =     max_seq_length
     lowerCamelCase__  =     (self.max_seq_length - self.min_seq_length) // (self.batch_size - 1)
     lowerCamelCase__  =     feature_size
     lowerCamelCase__  =     padding_value
     lowerCamelCase__  =     sampling_rate
     lowerCamelCase__  =     do_normalize
     lowerCamelCase__  =     num_mel_bins
     lowerCamelCase__  =     hop_length
     lowerCamelCase__  =     win_length
     lowerCamelCase__  =     win_function
     lowerCamelCase__  =     fmin
     lowerCamelCase__  =     fmax
     lowerCamelCase__  =     mel_floor
     lowerCamelCase__  =     return_attention_mask

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

     '''simple docstring'''




     return {
         "feature_size": self.feature_size,
         "padding_value": self.padding_value,
         "sampling_rate": self.sampling_rate,
         "do_normalize": self.do_normalize,
         "num_mel_bins": self.num_mel_bins,
         "hop_length": self.hop_length,
         "win_length": self.win_length,
         "win_function": self.win_function,
         "fmin": self.fmin,
         "fmax": self.fmax,
         "mel_floor": self.mel_floor,
         "return_attention_mask": self.return_attention_mask,
     }

    def    a__				(					self     :     Dict				,     __lowerCamelCase     :     str=False				,     __lowerCamelCase     :     Dict=False     )							->							Tuple:

     '''simple docstring'''




     def _flatten(__lowerCamelCase     :     List[Any]     ):
      return list(itertools.chain(*__lowerCamelCase     )     )

     if equal_length:
      lowerCamelCase__  =     floats_list((self.batch_size, self.max_seq_length)     )
     else:
      # make sure that inputs increase in size
      lowerCamelCase__  =     [
          _flatten(floats_list((x, self.feature_size)     )     )
          for x in range(self.min_seq_length				,     self.max_seq_length				,     self.seq_length_diff     )
      ]

     if numpify:
      lowerCamelCase__  =     [np.asarray(__lowerCamelCase     ) for x in speech_inputs]

     return speech_inputs




    def    a__				(					self     :     Any				,     __lowerCamelCase     :     List[str]=False				,     __lowerCamelCase     :     Any=False     )							->							List[Any]:

     '''simple docstring'''




     if equal_length:
      lowerCamelCase__  =     [floats_list((self.max_seq_length, self.num_mel_bins)     ) for _ in range(self.batch_size     )]
     else:
      # make sure that inputs increase in size
      lowerCamelCase__  =     [
          floats_list((x, self.num_mel_bins)     )
          for x in range(self.min_seq_length				,     self.max_seq_length				,     self.seq_length_diff     )
      ]

     if numpify:
      lowerCamelCase__  =     [np.asarray(__lowerCamelCase     ) for x in speech_inputs]

     return speech_inputs
@require_torch
class 				lowercase       (							_lowerCamelCase ,       unittest.TestCase      ):


    '''simple docstring'''

    lowerCAmelCase__      				=							SpeechTaFeatureExtractor

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

     '''simple docstring'''




     lowerCamelCase__  =     SpeechTaFeatureExtractionTester(self     )

    def    a__				(					self     :     Optional[int]				,     __lowerCamelCase     :     Optional[Any]     )							->							Optional[int]:

     '''simple docstring'''




     self.assertTrue(np.all(np.mean(__lowerCamelCase				,     axis=0     ) < 1E-3     )     )
     self.assertTrue(np.all(np.abs(np.var(__lowerCamelCase				,     axis=0     ) - 1     ) < 1E-3     )     )

    def    a__				(					self     :     List[Any]     )							->							int:

     '''simple docstring'''




     lowerCamelCase__  =     self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()     )
     # create three inputs of length 800, 1000, and 1200
     lowerCamelCase__  =     [floats_list((1, x)     )[0] for x in range(800				,     1400				,     200     )]
     lowerCamelCase__  =     [np.asarray(__lowerCamelCase     ) for speech_input in speech_inputs]

     # Test not batched input
     lowerCamelCase__  =     feat_extract(speech_inputs[0]				,     return_tensors="np"     ).input_values
     lowerCamelCase__  =     feat_extract(np_speech_inputs[0]				,     return_tensors="np"     ).input_values
     self.assertTrue(np.allclose(__lowerCamelCase				,     __lowerCamelCase				,     atol=1E-3     )     )

     # Test batched
     lowerCamelCase__  =     feat_extract(__lowerCamelCase				,     return_tensors="np"     ).input_values
     lowerCamelCase__  =     feat_extract(__lowerCamelCase				,     return_tensors="np"     ).input_values
     for enc_seq_a, enc_seq_a in zip(__lowerCamelCase				,     __lowerCamelCase     ):
      self.assertTrue(np.allclose(__lowerCamelCase				,     __lowerCamelCase				,     atol=1E-3     )     )

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

     '''simple docstring'''




     lowerCamelCase__  =     self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()     )
     lowerCamelCase__  =     [floats_list((1, x)     )[0] for x in range(800				,     1400				,     200     )]

     lowerCamelCase__  =     ["longest", "max_length", "do_not_pad"]
     lowerCamelCase__  =     [None, 1600, None]
     for max_length, padding in zip(__lowerCamelCase				,     __lowerCamelCase     ):
      lowerCamelCase__  =     feat_extract(__lowerCamelCase				,     padding=__lowerCamelCase				,     max_length=__lowerCamelCase				,     return_tensors="np"     )
      lowerCamelCase__  =     processed.input_values

      self._check_zero_mean_unit_variance(input_values[0][:800]     )
      self.assertTrue(input_values[0][800:].sum() < 1E-6     )
      self._check_zero_mean_unit_variance(input_values[1][:1000]     )
      self.assertTrue(input_values[0][1000:].sum() < 1E-6     )
      self._check_zero_mean_unit_variance(input_values[2][:1200]     )

    def    a__				(					self     :     Tuple     )							->							Tuple:

     '''simple docstring'''




     lowerCamelCase__  =     self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()     )
     lowerCamelCase__  =     range(800				,     1400				,     200     )
     lowerCamelCase__  =     [floats_list((1, x)     )[0] for x in lengths]

     lowerCamelCase__  =     ["longest", "max_length", "do_not_pad"]
     lowerCamelCase__  =     [None, 1600, None]

     for max_length, padding in zip(__lowerCamelCase				,     __lowerCamelCase     ):
      lowerCamelCase__  =     feat_extract(__lowerCamelCase				,     max_length=__lowerCamelCase				,     padding=__lowerCamelCase     )
      lowerCamelCase__  =     processed.input_values

      self._check_zero_mean_unit_variance(input_values[0][:800]     )
      self._check_zero_mean_unit_variance(input_values[1][:1000]     )
      self._check_zero_mean_unit_variance(input_values[2][:1200]     )

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

     '''simple docstring'''




     lowerCamelCase__  =     self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()     )
     lowerCamelCase__  =     [floats_list((1, x)     )[0] for x in range(800				,     1400				,     200     )]
     lowerCamelCase__  =     feat_extract(
         __lowerCamelCase				,     truncation=__lowerCamelCase				,     max_length=1000				,     padding="max_length"				,     return_tensors="np"     )
     lowerCamelCase__  =     processed.input_values

     self._check_zero_mean_unit_variance(input_values[0, :800]     )
     self._check_zero_mean_unit_variance(input_values[1]     )
     self._check_zero_mean_unit_variance(input_values[2]     )

    def    a__				(					self     :     Tuple     )							->							Union[str, Any]:

     '''simple docstring'''




     lowerCamelCase__  =     self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()     )
     lowerCamelCase__  =     [floats_list((1, x)     )[0] for x in range(800				,     1400				,     200     )]
     lowerCamelCase__  =     feat_extract(
         __lowerCamelCase				,     truncation=__lowerCamelCase				,     max_length=1000				,     padding="longest"				,     return_tensors="np"     )
     lowerCamelCase__  =     processed.input_values

     self._check_zero_mean_unit_variance(input_values[0, :800]     )
     self._check_zero_mean_unit_variance(input_values[1, :1000]     )
     self._check_zero_mean_unit_variance(input_values[2]     )

     # make sure that if max_length < longest -> then pad to max_length
     self.assertTrue(input_values.shape == (3, 1000)     )

     lowerCamelCase__  =     [floats_list((1, x)     )[0] for x in range(800				,     1400				,     200     )]
     lowerCamelCase__  =     feat_extract(
         __lowerCamelCase				,     truncation=__lowerCamelCase				,     max_length=2000				,     padding="longest"				,     return_tensors="np"     )
     lowerCamelCase__  =     processed.input_values

     self._check_zero_mean_unit_variance(input_values[0, :800]     )
     self._check_zero_mean_unit_variance(input_values[1, :1000]     )
     self._check_zero_mean_unit_variance(input_values[2]     )

     # make sure that if max_length > longest -> then pad to longest
     self.assertTrue(input_values.shape == (3, 1200)     )

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

     '''simple docstring'''




     lowerCamelCase__  =     self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()     )
     lowerCamelCase__  =     np.random.rand(100     ).astype(np.floataa     )
     lowerCamelCase__  =     np_speech_inputs.tolist()

     for inputs in [py_speech_inputs, np_speech_inputs]:
      lowerCamelCase__  =     feature_extractor.pad([{"input_values": inputs}]				,     return_tensors="np"     )
      self.assertTrue(np_processed.input_values.dtype == np.floataa     )
      lowerCamelCase__  =     feature_extractor.pad([{"input_values": inputs}]				,     return_tensors="pt"     )
      self.assertTrue(pt_processed.input_values.dtype == torch.floataa     )

    def    a__				(					self     :     Union[str, Any]     )							->							int:

     '''simple docstring'''




     lowerCamelCase__  =     self.feature_extraction_class(**self.feat_extract_tester.prepare_feat_extract_dict()     )
     # create three inputs of length 800, 1000, and 1200
     lowerCamelCase__  =     [floats_list((1, x)     )[0] for x in range(800				,     1400				,     200     )]
     lowerCamelCase__  =     [np.asarray(__lowerCamelCase     ) for speech_input in speech_inputs]

     # Test feature size
     lowerCamelCase__  =     feature_extractor(audio_target=__lowerCamelCase				,     padding=__lowerCamelCase				,     return_tensors="np"     ).input_values
     self.assertTrue(input_values.ndim == 3     )
     self.assertTrue(input_values.shape[-1] == feature_extractor.num_mel_bins     )

     # Test not batched input
     lowerCamelCase__  =     feature_extractor(speech_inputs[0]				,     return_tensors="np"     ).input_values
     lowerCamelCase__  =     feature_extractor(np_speech_inputs[0]				,     return_tensors="np"     ).input_values
     self.assertTrue(np.allclose(__lowerCamelCase				,     __lowerCamelCase				,     atol=1E-3     )     )

     # Test batched
     lowerCamelCase__  =     feature_extractor(__lowerCamelCase				,     return_tensors="np"     ).input_values
     lowerCamelCase__  =     feature_extractor(__lowerCamelCase				,     return_tensors="np"     ).input_values
     for enc_seq_a, enc_seq_a in zip(__lowerCamelCase				,     __lowerCamelCase     ):
      self.assertTrue(np.allclose(__lowerCamelCase				,     __lowerCamelCase				,     atol=1E-3     )     )

     # Test 2-D numpy arrays are batched.
     lowerCamelCase__  =     [floats_list((1, x)     )[0] for x in (800, 800, 800)]
     lowerCamelCase__  =     np.asarray(__lowerCamelCase     )
     lowerCamelCase__  =     feature_extractor(__lowerCamelCase				,     return_tensors="np"     ).input_values
     lowerCamelCase__  =     feature_extractor(__lowerCamelCase				,     return_tensors="np"     ).input_values
     for enc_seq_a, enc_seq_a in zip(__lowerCamelCase				,     __lowerCamelCase     ):
      self.assertTrue(np.allclose(__lowerCamelCase				,     __lowerCamelCase				,     atol=1E-3     )     )

    def    a__				(					self     :     Union[str, Any]     )							->							Optional[int]:

     '''simple docstring'''




     lowerCamelCase__  =     self.feat_extract_tester.prepare_inputs_for_target()
     lowerCamelCase__  =     self.feature_extraction_class(**self.feat_extract_dict     )
     lowerCamelCase__  =     feat_extract.model_input_names[0]

     lowerCamelCase__  =     BatchFeature({input_name: speech_inputs}     )

     self.assertTrue(all(len(__lowerCamelCase     ) == len(__lowerCamelCase     ) for x, y in zip(__lowerCamelCase				,     processed_features[input_name]     )     )     )

     lowerCamelCase__  =     self.feat_extract_tester.prepare_inputs_for_target(equal_length=__lowerCamelCase     )
     lowerCamelCase__  =     BatchFeature({input_name: speech_inputs}				,     tensor_type="np"     )

     lowerCamelCase__  =     processed_features[input_name]

     if len(batch_features_input.shape     ) < 3:
      lowerCamelCase__  =     batch_features_input[:, :, None]

     self.assertTrue(
         batch_features_input.shape
         == (self.feat_extract_tester.batch_size, len(speech_inputs[0]     ), self.feat_extract_tester.num_mel_bins)     )

    @require_torch
    def    a__				(					self     :     Optional[int]     )							->							List[Any]:

     '''simple docstring'''




     lowerCamelCase__  =     self.feat_extract_tester.prepare_inputs_for_target(equal_length=__lowerCamelCase     )
     lowerCamelCase__  =     self.feature_extraction_class(**self.feat_extract_dict     )
     lowerCamelCase__  =     feat_extract.model_input_names[0]

     lowerCamelCase__  =     BatchFeature({input_name: speech_inputs}				,     tensor_type="pt"     )

     lowerCamelCase__  =     processed_features[input_name]

     if len(batch_features_input.shape     ) < 3:
      lowerCamelCase__  =     batch_features_input[:, :, None]

     self.assertTrue(
         batch_features_input.shape
         == (self.feat_extract_tester.batch_size, len(speech_inputs[0]     ), self.feat_extract_tester.num_mel_bins)     )

    @require_torch
    def    a__				(					self     :     List[str]     )							->							List[Any]:

     '''simple docstring'''




     lowerCamelCase__  =     self.feature_extraction_class(**self.feat_extract_dict     )
     lowerCamelCase__  =     self.feat_extract_tester.prepare_inputs_for_target()
     lowerCamelCase__  =     feat_extract.model_input_names[0]

     lowerCamelCase__  =     BatchFeature({input_name: speech_inputs}     )

     lowerCamelCase__  =     feat_extract.num_mel_bins  # hack!

     lowerCamelCase__  =     feat_extract.pad(__lowerCamelCase				,     padding="longest"				,     return_tensors="np"     )[input_name]
     lowerCamelCase__  =     feat_extract.pad(__lowerCamelCase				,     padding="longest"				,     return_tensors="pt"     )[input_name]

     self.assertTrue(abs(input_np.astype(np.floataa     ).sum() - input_pt.numpy().astype(np.floataa     ).sum()     ) < 1E-2     )

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

     '''simple docstring'''




     lowerCamelCase__  =     self.feat_extract_dict
     lowerCamelCase__  =     True
     lowerCamelCase__  =     self.feature_extraction_class(**__lowerCamelCase     )
     lowerCamelCase__  =     self.feat_extract_tester.prepare_inputs_for_target()
     lowerCamelCase__  =     [len(__lowerCamelCase     ) for x in speech_inputs]
     lowerCamelCase__  =     feat_extract.model_input_names[0]

     lowerCamelCase__  =     BatchFeature({input_name: speech_inputs}     )

     lowerCamelCase__  =     feat_extract.num_mel_bins  # hack!

     lowerCamelCase__  =     feat_extract.pad(__lowerCamelCase				,     padding="longest"				,     return_tensors="np"     )
     self.assertIn("attention_mask"				,     __lowerCamelCase     )
     self.assertListEqual(list(processed.attention_mask.shape     )				,     list(processed[input_name].shape[:2]     )     )
     self.assertListEqual(processed.attention_mask.sum(-1     ).tolist()				,     __lowerCamelCase     )

    def    a__				(					self     :     Tuple     )							->							Any:

     '''simple docstring'''




     lowerCamelCase__  =     self.feat_extract_dict
     lowerCamelCase__  =     True
     lowerCamelCase__  =     self.feature_extraction_class(**__lowerCamelCase     )
     lowerCamelCase__  =     self.feat_extract_tester.prepare_inputs_for_target()
     lowerCamelCase__  =     [len(__lowerCamelCase     ) for x in speech_inputs]
     lowerCamelCase__  =     feat_extract.model_input_names[0]

     lowerCamelCase__  =     BatchFeature({input_name: speech_inputs}     )
     lowerCamelCase__  =     min(__lowerCamelCase     )

     lowerCamelCase__  =     feat_extract.num_mel_bins  # hack!

     lowerCamelCase__  =     feat_extract.pad(
         __lowerCamelCase				,     padding="max_length"				,     max_length=__lowerCamelCase				,     truncation=__lowerCamelCase				,     return_tensors="np"     )
     self.assertIn("attention_mask"				,     __lowerCamelCase     )
     self.assertListEqual(
         list(processed_pad.attention_mask.shape     )				,     [processed_pad[input_name].shape[0], max_length]     )
     self.assertListEqual(
         processed_pad.attention_mask[:, :max_length].sum(-1     ).tolist()				,     [max_length for x in speech_inputs]     )

    def    a__				(					self     :     str				,     __lowerCamelCase     :     Tuple     )							->							List[Any]:

     '''simple docstring'''




     from datasets import load_dataset

     lowerCamelCase__  =     load_dataset("hf-internal-testing/librispeech_asr_dummy"				,     "clean"				,     split="validation"     )
     # automatic decoding with librispeech
     lowerCamelCase__  =     ds.sort("id"     ).select(range(__lowerCamelCase     )     )[:num_samples]["audio"]

     return [x["array"] for x in speech_samples]

    def    a__				(					self     :     int     )							->							List[Any]:

     '''simple docstring'''




     lowerCamelCase__  =     torch.tensor(
         [2.38_04E-03, 2.07_52E-03, 1.98_36E-03, 2.10_57E-03, 1.61_74E-03,
          3.05_18E-04, 9.15_53E-05, 3.35_69E-04, 9.76_56E-04, 1.83_11E-03,
          2.01_42E-03, 2.10_57E-03, 1.73_95E-03, 4.57_76E-04, -3.96_73E-04,
          4.57_76E-04, 1.00_71E-03, 9.15_53E-05, 4.88_28E-04, 1.15_97E-03,
          7.32_42E-04, 9.46_04E-04, 1.80_05E-03, 1.83_11E-03, 8.85_01E-04,
          4.27_25E-04, 4.88_28E-04, 7.32_42E-04, 1.09_86E-03, 2.10_57E-03]     )
     # fmt: on

     lowerCamelCase__  =     self._load_datasamples(1     )
     lowerCamelCase__  =     SpeechTaFeatureExtractor()
     lowerCamelCase__  =     feature_extractor(__lowerCamelCase				,     return_tensors="pt"     ).input_values
     self.assertEquals(input_values.shape				,     (1, 93680)     )
     self.assertTrue(torch.allclose(input_values[0, :30]				,     __lowerCamelCase				,     atol=1E-6     )     )




    def    a__				(					self     :     Any     )							->							str:

     '''simple docstring'''




     lowerCamelCase__  =     torch.tensor(
         [-2.6_8_7_0, -3.0_1_0_4, -3.1_3_5_6, -3.5_3_5_2, -3.0_0_4_4, -3.0_3_5_3, -3.4_7_1_9, -3.6_7_7_7,
          -3.1_5_2_0, -2.9_4_3_5, -2.6_5_5_3, -2.8_7_9_5, -2.9_9_4_4, -2.5_9_2_1, -3.0_2_7_9, -3.0_3_8_6,
          -3.0_8_6_4, -3.1_2_9_1, -3.2_3_5_3, -2.7_4_4_4, -2.6_8_3_1, -2.7_2_8_7, -3.1_7_6_1, -3.1_5_7_1,
          -3.2_7_2_6, -3.0_5_8_2, -3.1_0_0_7, -3.4_5_3_3, -3.4_6_9_5, -3.0_9_9_8]     )
     # fmt: on

     lowerCamelCase__  =     self._load_datasamples(1     )
     lowerCamelCase__  =     SpeechTaFeatureExtractor()
     lowerCamelCase__  =     feature_extractor(audio_target=__lowerCamelCase				,     return_tensors="pt"     ).input_values
     self.assertEquals(input_values.shape				,     (1, 366, 80)     )
     self.assertTrue(torch.allclose(input_values[0, 0, :30]				,     __lowerCamelCase				,     atol=1E-4     )     )









'''simple docstring'''





class 				lowercase       :


    '''simple docstring'''

    def __init__(					self     :     Any				,     __lowerCamelCase     :     Union[str, Any]				,     __lowerCamelCase     :     Optional[int]     )							->							Optional[int]:

     '''simple docstring'''




     lowerCamelCase__  =     name
     lowerCamelCase__  =     val

    def __str__(					self     :     Tuple     )							->							Union[str, Any]:

     '''simple docstring'''




     return f'''{self.__class__.__name__}({self.name}, {self.val})'''




    def __lt__(					self     :     List[str]				,     __lowerCamelCase     :     List[str]     )							->							str:

     '''simple docstring'''




     return self.val < other.val
class 				lowercase       :


    '''simple docstring'''

    def __init__(					self     :     int				,     __lowerCamelCase     :     Optional[Any]     )							->							List[Any]:

     '''simple docstring'''




     lowerCamelCase__  =     {}
     lowerCamelCase__  =     {}
     lowerCamelCase__  =     self.build_heap(__lowerCamelCase     )

    def __getitem__(					self     :     Tuple				,     __lowerCamelCase     :     Optional[int]     )							->							Tuple:

     '''simple docstring'''




     return self.get_value(__lowerCamelCase     )

    def    a__				(					self     :     str				,     __lowerCamelCase     :     int     )							->							Optional[Any]:

     '''simple docstring'''




     return (idx - 1) // 2

    def    a__				(					self     :     List[str]				,     __lowerCamelCase     :     List[Any]     )							->							Optional[int]:

     '''simple docstring'''




     return idx * 2 + 1

    def    a__				(					self     :     Any				,     __lowerCamelCase     :     str     )							->							Tuple:

     '''simple docstring'''




     return idx * 2 + 2

    def    a__				(					self     :     Any				,     __lowerCamelCase     :     int     )							->							Dict:

     '''simple docstring'''




     return self.heap_dict[key]

    def    a__				(					self     :     str				,     __lowerCamelCase     :     List[str]     )							->							str:

     '''simple docstring'''




     lowerCamelCase__  =     len(__lowerCamelCase     ) - 1
     lowerCamelCase__  =     self.get_parent_idx(__lowerCamelCase     )

     for idx, i in enumerate(__lowerCamelCase     ):
      lowerCamelCase__  =     idx
      lowerCamelCase__  =     i.val

     for i in range(__lowerCamelCase				,     -1				,     -1     ):
      self.sift_down(__lowerCamelCase				,     __lowerCamelCase     )
     return array

    def    a__				(					self     :     List[Any]				,     __lowerCamelCase     :     Tuple				,     __lowerCamelCase     :     Optional[int]     )							->							int:

     '''simple docstring'''




     while True:
      lowerCamelCase__  =     self.get_left_child_idx(__lowerCamelCase     )  # noqa: E741
      lowerCamelCase__  =     self.get_right_child_idx(__lowerCamelCase     )

      lowerCamelCase__  =     idx
      if l < len(__lowerCamelCase     ) and array[l] < array[idx]:
       lowerCamelCase__  =     l
      if r < len(__lowerCamelCase     ) and array[r] < array[smallest]:
       lowerCamelCase__  =     r

      if smallest != idx:
       lowerCamelCase__  ,	lowerCamelCase__  =     array[smallest], array[idx]
       (
           (
           lowerCamelCase__
       )  ,	(
           lowerCamelCase__
       )  ,	
       )  =     (
           self.idx_of_element[array[smallest]],
           self.idx_of_element[array[idx]],
       )
       lowerCamelCase__  =     smallest
      else:
       break

    def    a__				(					self     :     str				,     __lowerCamelCase     :     Optional[int]     )							->							Union[str, Any]:

     '''simple docstring'''




     lowerCamelCase__  =     self.get_parent_idx(__lowerCamelCase     )
     while p >= 0 and self.heap[p] > self.heap[idx]:
      lowerCamelCase__  ,	lowerCamelCase__  =     self.heap[idx], self.heap[p]
      lowerCamelCase__  ,	lowerCamelCase__  =     (
          self.idx_of_element[self.heap[idx]],
          self.idx_of_element[self.heap[p]],
      )
      lowerCamelCase__  =     p
      lowerCamelCase__  =     self.get_parent_idx(__lowerCamelCase     )

    def    a__				(					self     :     Union[str, Any]     )							->							List[Any]:

     '''simple docstring'''




     return self.heap[0]

    def    a__				(					self     :     Tuple     )							->							int:

     '''simple docstring'''




     lowerCamelCase__  ,	lowerCamelCase__  =     self.heap[-1], self.heap[0]
     lowerCamelCase__  ,	lowerCamelCase__  =     (
         self.idx_of_element[self.heap[-1]],
         self.idx_of_element[self.heap[0]],
     )

     lowerCamelCase__  =     self.heap.pop()
     del self.idx_of_element[x]
     self.sift_down(0				,     self.heap     )
     return x

    def    a__				(					self     :     List[str]				,     __lowerCamelCase     :     Tuple     )							->							List[Any]:

     '''simple docstring'''




     self.heap.append(__lowerCamelCase     )
     lowerCamelCase__  =     len(self.heap     ) - 1
     lowerCamelCase__  =     node.val
     self.sift_up(len(self.heap     ) - 1     )

    def    a__				(					self     :     Dict     )							->							Any:

     '''simple docstring'''




     return len(self.heap     ) == 0




    def    a__				(					self     :     Dict				,     __lowerCamelCase     :     str				,     __lowerCamelCase     :     Union[str, Any]     )							->							Tuple:

     '''simple docstring'''




     assert (
         self.heap[self.idx_of_element[node]].val > new_value
     ), "newValue must be less that current value"
     lowerCamelCase__  =     new_value
     lowerCamelCase__  =     new_value
     self.sift_up(self.idx_of_element[node]     )
__A							:							str  							=		Node("""R""", -1)
__A							:							Dict  							=		Node("""B""", 6)
__A							:							Tuple  							=		Node("""A""", 3)
__A							:							str  							=		Node("""X""", 1)
__A							:							Optional[Any]  							=		Node("""E""", 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
__A							:							Tuple  							=		MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print("""Min Heap - before decrease key""")
for i in my_min_heap.heap:
 print(i)

print("""Min Heap - After decrease key of node [B -> -17]""")
my_min_heap.decrease_key(b, -17)

# After
for i in my_min_heap.heap:
 print(i)

if __name__ == "__main__":
 import doctest

 doctest.testmod()

