






import unittest
from unittest.util import safe_repr

from transformers import AutoTokenizer, RwkvConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
		import torch

		from transformers import (
		    RWKV_PRETRAINED_MODEL_ARCHIVE_LIST,
		    RwkvForCausalLM,
		    RwkvModel,
		)
		from transformers.pytorch_utils import is_torch_greater_or_equal_than_2_0
else:
		UpperCamelCase												=      False



class  __UpperCAmelCase						:







			def __init__(      self:    Tuple ,      UpperCAmelCase_:    Optional[int] ,      UpperCAmelCase_:    Tuple=14 ,      UpperCAmelCase_:    str=7 ,      UpperCAmelCase_:    Any=True ,      UpperCAmelCase_:    List[Any]=False ,      UpperCAmelCase_:    Dict=True ,      UpperCAmelCase_:    List[Any]=True ,      UpperCAmelCase_:    Any=True ,      UpperCAmelCase_:    List[Any]=99 ,      UpperCAmelCase_:    Union[str, Any]=32 ,      UpperCAmelCase_:    Any=5 ,      UpperCAmelCase_:    List[str]=37 ,      UpperCAmelCase_:    List[str]="gelu" ,      UpperCAmelCase_:    List[str]=0.1 ,      UpperCAmelCase_:    Dict=0.1 ,      UpperCAmelCase_:    str=512 ,      UpperCAmelCase_:    Tuple=16 ,      UpperCAmelCase_:    Tuple=2 ,      UpperCAmelCase_:    Dict=3 ,      UpperCAmelCase_:    Tuple=4 ,      UpperCAmelCase_:    Optional[int]=None ,      ):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    parent
									_SCREAMING_SNAKE_CASE       =    batch_size
									_SCREAMING_SNAKE_CASE       =    seq_length
									_SCREAMING_SNAKE_CASE       =    is_training
									_SCREAMING_SNAKE_CASE       =    use_token_type_ids
									_SCREAMING_SNAKE_CASE       =    use_input_mask
									_SCREAMING_SNAKE_CASE       =    use_labels
									_SCREAMING_SNAKE_CASE       =    use_mc_token_ids
									_SCREAMING_SNAKE_CASE       =    vocab_size
									_SCREAMING_SNAKE_CASE       =    hidden_size
									_SCREAMING_SNAKE_CASE       =    num_hidden_layers
									_SCREAMING_SNAKE_CASE       =    intermediate_size
									_SCREAMING_SNAKE_CASE       =    hidden_act
									_SCREAMING_SNAKE_CASE       =    hidden_dropout_prob
									_SCREAMING_SNAKE_CASE       =    attention_probs_dropout_prob
									_SCREAMING_SNAKE_CASE       =    max_position_embeddings
									_SCREAMING_SNAKE_CASE       =    type_vocab_size
									_SCREAMING_SNAKE_CASE       =    type_sequence_label_size
									_SCREAMING_SNAKE_CASE       =    num_labels
									_SCREAMING_SNAKE_CASE       =    num_choices
									_SCREAMING_SNAKE_CASE       =    scope
									_SCREAMING_SNAKE_CASE       =    vocab_size - 1
									_SCREAMING_SNAKE_CASE       =    vocab_size - 1
									_SCREAMING_SNAKE_CASE       =    vocab_size - 1







			def 				UpperCamelCase (      self:    Dict	):







									'''simple docstring'''




									return RwkvConfig.from_pretrained("""sgugger/rwkv-4-pile-7b"""	)







			def 				UpperCamelCase (      self:    List[str] ,      UpperCAmelCase_:    List[Any]=False ,      UpperCAmelCase_:    Optional[Any]=False ,      UpperCAmelCase_:    Union[str, Any]=False	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    ids_tensor([self.batch_size, self.seq_length] ,      self.vocab_size	)

									_SCREAMING_SNAKE_CASE       =    None
									if self.use_input_mask:
															_SCREAMING_SNAKE_CASE       =    random_attention_mask([self.batch_size, self.seq_length]	)

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

									_SCREAMING_SNAKE_CASE       =    None
									if self.use_mc_token_ids:
															_SCREAMING_SNAKE_CASE       =    ids_tensor([self.batch_size, self.num_choices] ,      self.seq_length	)

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

									_SCREAMING_SNAKE_CASE       =    self.get_config(
									    gradient_checkpointing=UpperCAmelCase_ ,      scale_attn_by_inverse_layer_idx=UpperCAmelCase_ ,      reorder_and_upcast_attn=UpperCAmelCase_ ,      )

									return (
									    config,
									    input_ids,
									    input_mask,
									    None,
									    token_type_ids,
									    mc_token_ids,
									    sequence_labels,
									    token_labels,
									    choice_labels,
									)







			def 				UpperCamelCase (      self:    Optional[Any] ,      UpperCAmelCase_:    Union[str, Any]=False ,      UpperCAmelCase_:    Union[str, Any]=False ,      UpperCAmelCase_:    Union[str, Any]=False	):







									'''simple docstring'''




									return RwkvConfig(
									    vocab_size=self.vocab_size ,      hidden_size=self.hidden_size ,      num_hidden_layers=self.num_hidden_layers ,      intermediate_size=self.intermediate_size ,      activation_function=self.hidden_act ,      resid_pdrop=self.hidden_dropout_prob ,      attn_pdrop=self.attention_probs_dropout_prob ,      n_positions=self.max_position_embeddings ,      type_vocab_size=self.type_vocab_size ,      use_cache=UpperCAmelCase_ ,      bos_token_id=self.bos_token_id ,      eos_token_id=self.eos_token_id ,      pad_token_id=self.pad_token_id ,      gradient_checkpointing=UpperCAmelCase_ ,      scale_attn_by_inverse_layer_idx=UpperCAmelCase_ ,      reorder_and_upcast_attn=UpperCAmelCase_ ,      )







			def 				UpperCamelCase (      self:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.get_config()
									_SCREAMING_SNAKE_CASE       =    300
									return config







			def 				UpperCamelCase (      self:    str	):







									'''simple docstring'''




									(
									    (
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	
									)       =    self.prepare_config_and_inputs()

									_SCREAMING_SNAKE_CASE       =    floats_tensor([self.batch_size, self.seq_length, self.hidden_size]	)
									_SCREAMING_SNAKE_CASE       =    ids_tensor([self.batch_size, self.seq_length] ,      vocab_size=2	)

									return (
									    config,
									    input_ids,
									    input_mask,
									    head_mask,
									    token_type_ids,
									    sequence_labels,
									    token_labels,
									    choice_labels,
									    encoder_hidden_states,
									    encoder_attention_mask,
									)







			def 				UpperCamelCase (      self:    str ,      UpperCAmelCase_:    Optional[Any] ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    Optional[Any] ,      *UpperCAmelCase_:    Optional[Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    True
									_SCREAMING_SNAKE_CASE       =    RwkvModel(config=UpperCAmelCase_	)
									model.to(UpperCAmelCase_	)
									model.eval()

									_SCREAMING_SNAKE_CASE       =    model(UpperCAmelCase_	)

									self.parent.assertEqual(result.last_hidden_state.shape ,      (self.batch_size, self.seq_length, self.hidden_size)	)
									self.parent.assertEqual(len(result.hidden_states	) ,      config.num_hidden_layers + 1	)







			def 				UpperCamelCase (      self:    Union[str, Any] ,      UpperCAmelCase_:    Optional[int] ,      UpperCAmelCase_:    Optional[Any] ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    Optional[Any] ,      UpperCAmelCase_:    Tuple ,      *UpperCAmelCase_:    Tuple	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    RwkvForCausalLM(UpperCAmelCase_	)
									model.to(UpperCAmelCase_	)
									model.eval()

									_SCREAMING_SNAKE_CASE       =    model(UpperCAmelCase_ ,      labels=UpperCAmelCase_	)
									self.parent.assertEqual(result.loss.shape ,      ()	)
									self.parent.assertEqual(result.logits.shape ,      (self.batch_size, self.seq_length, self.vocab_size)	)







			def 				UpperCamelCase (      self:    Optional[Any] ,      UpperCAmelCase_:    List[Any] ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    List[str] ,      UpperCAmelCase_:    Optional[Any] ,      UpperCAmelCase_:    Optional[int] ,      *UpperCAmelCase_:    int	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    RwkvModel(config=UpperCAmelCase_	)
									model.to(UpperCAmelCase_	)
									model.eval()

									_SCREAMING_SNAKE_CASE       =    model(UpperCAmelCase_	)
									_SCREAMING_SNAKE_CASE       =    outputs.last_hidden_state

									_SCREAMING_SNAKE_CASE       =    model(input_ids[:, :2]	)
									_SCREAMING_SNAKE_CASE       =    outputs.last_hidden_state

									# Using the state computed on the first inputs, we will get the same output
									_SCREAMING_SNAKE_CASE       =    model(input_ids[:, 2:] ,      state=outputs.state	)
									_SCREAMING_SNAKE_CASE       =    outputs.last_hidden_state

									self.parent.assertTrue(torch.allclose(torch.cat([output_one, output_two] ,      dim=1	) ,      UpperCAmelCase_ ,      atol=1E-5	)	)







			def 				UpperCamelCase (      self:    List[Any] ,      UpperCAmelCase_:    Tuple ,      UpperCAmelCase_:    Optional[int] ,      UpperCAmelCase_:    Tuple ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    Optional[int] ,      *UpperCAmelCase_:    int ,      UpperCAmelCase_:    Any=False	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    RwkvForCausalLM(UpperCAmelCase_	)
									model.to(UpperCAmelCase_	)
									if gradient_checkpointing:
															model.gradient_checkpointing_enable()

									_SCREAMING_SNAKE_CASE       =    model(UpperCAmelCase_ ,      labels=UpperCAmelCase_	)
									self.parent.assertEqual(result.loss.shape ,      ()	)
									self.parent.assertEqual(result.logits.shape ,      (self.batch_size, self.seq_length, self.vocab_size)	)
									result.loss.backward()







			def 				UpperCamelCase (      self:    Tuple	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.prepare_config_and_inputs()

									(
									    (
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	(
									    _SCREAMING_SNAKE_CASE
									) ,	
									)       =    config_and_inputs

									_SCREAMING_SNAKE_CASE       =    {"""input_ids""": input_ids}

									return config, inputs_dict



@unittest.skipIf(
    not is_torch_greater_or_equal_than_2_0			,reason="See https://github.com/huggingface/transformers/pull/24204"       )
@require_torch
class  __UpperCAmelCase						(_UpperCAmelCase			,_UpperCAmelCase			,_UpperCAmelCase			,unittest.TestCase       ):
			__snake_case							: List[str]							=				(RwkvModel, RwkvForCausalLM) if is_torch_available() else ()
			__snake_case							: Optional[Any]							=				(
			    {"feature-extraction": RwkvModel, "text-generation": RwkvForCausalLM} if is_torch_available() else {}
			)
			# all_generative_model_classes = (RwkvForCausalLM,) if is_torch_available() else ()
			__snake_case							: Any							=				False
			__snake_case							: Optional[int]							=				False
			__snake_case							: int							=				False
			__snake_case							: List[str]							=				False
			__snake_case							: Optional[Any]							=				False  # Rwkv does not support head masking







			def 				UpperCamelCase (      self:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    RwkvModelTester(self	)
									_SCREAMING_SNAKE_CASE       =    ConfigTester(
									    self ,      config_class=UpperCAmelCase_ ,      n_embd=37 ,      common_properties=["""hidden_size""", """num_hidden_layers"""]	)







			def 				UpperCamelCase (      self:    Tuple ,      UpperCAmelCase_:    int ,      UpperCAmelCase_:    Tuple ,      UpperCAmelCase_:    Tuple=None	):







									'''simple docstring'''




									if isinstance(UpperCAmelCase_ ,      torch.Tensor	):
															_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE       =    member.max().item(), member.min().item()
									elif isinstance(UpperCAmelCase_ ,      UpperCAmelCase_	) or isinstance(UpperCAmelCase_ ,      UpperCAmelCase_	):
															_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE       =    max(UpperCAmelCase_	), min(UpperCAmelCase_	)

									if not isinstance(UpperCAmelCase_ ,      UpperCAmelCase_	):
															raise TypeError("""container should be a list or tuple"""	)
									elif len(UpperCAmelCase_	) != 2:
															raise ValueError("""container should have 2 elements"""	)

									_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE       =    container

									_SCREAMING_SNAKE_CASE       =    (min_value >= expected_min) and (max_value <= expected_max)

									if not is_inside_interval:
															_SCREAMING_SNAKE_CASE       =    """%s not found in %s""" % (safe_repr(UpperCAmelCase_	), safe_repr(UpperCAmelCase_	))
															self.fail(self._formatMessage(UpperCAmelCase_ ,      UpperCAmelCase_	)	)







			def 				UpperCamelCase (      self:    List[str]	):







									'''simple docstring'''




									self.config_tester.run_common_tests()







			def 				UpperCamelCase (      self:    Optional[int]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_rwkv_model(*UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    Optional[int]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_causl_lm(*UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs()
									self.model_tester.create_and_check_state_equivalency(*UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs_for_common()

									for model_class in self.all_model_classes:
															_SCREAMING_SNAKE_CASE       =    model_class(config=UpperCAmelCase_	)
															for name, param in model.named_parameters():
																					if "time_decay" in name:
																											if param.requires_grad:
																																	self.assertTrue(param.data.max().item() == 3.0	)
																																	self.assertTrue(param.data.min().item() == -5.0	)
																					elif "time_first" in name:
																											if param.requires_grad:
																																	# check if it's a ones like
																																	self.assertTrue(torch.allclose(param.data ,      torch.ones_like(param.data	) ,      atol=1E-5 ,      rtol=1E-5	)	)
																					elif any(x in name for x in ["""time_mix_key""", """time_mix_receptance"""]	):
																											if param.requires_grad:
																																	self.assertInterval(
																																	    param.data ,      [0.0, 1.0] ,      msg=F'Parameter {name} of model {model_class} seems not properly initialized' ,      )
																					elif "time_mix_value" in name:
																											if param.requires_grad:
																																	self.assertInterval(
																																	    param.data ,      [0.0, 1.3] ,      msg=F'Parameter {name} of model {model_class} seems not properly initialized' ,      )







			def 				UpperCamelCase (      self:    Optional[int]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE ,	_SCREAMING_SNAKE_CASE       =    self.model_tester.prepare_config_and_inputs_for_common()
									_SCREAMING_SNAKE_CASE       =    True

									_SCREAMING_SNAKE_CASE       =    getattr(self.model_tester ,      """seq_length""" ,      UpperCAmelCase_	)

									for model_class in self.all_model_classes:
															_SCREAMING_SNAKE_CASE       =    True
															_SCREAMING_SNAKE_CASE       =    False
															_SCREAMING_SNAKE_CASE       =    True
															_SCREAMING_SNAKE_CASE       =    model_class(UpperCAmelCase_	)
															model.to(UpperCAmelCase_	)
															model.eval()

															_SCREAMING_SNAKE_CASE       =    self._prepare_for_class(UpperCAmelCase_ ,      UpperCAmelCase_	)
															_SCREAMING_SNAKE_CASE       =    inputs["""input_ids"""].shape[0]
															with torch.no_grad():
																					_SCREAMING_SNAKE_CASE       =    model(**UpperCAmelCase_	)
															_SCREAMING_SNAKE_CASE       =    outputs.attentions
															self.assertEqual(len(UpperCAmelCase_	) ,      self.model_tester.num_hidden_layers	)

															# check that output_attentions also work using config
															del inputs_dict["output_attentions"]
															_SCREAMING_SNAKE_CASE       =    True
															_SCREAMING_SNAKE_CASE       =    model_class(UpperCAmelCase_	)
															model.to(UpperCAmelCase_	)
															model.eval()

															_SCREAMING_SNAKE_CASE       =    self._prepare_for_class(UpperCAmelCase_ ,      UpperCAmelCase_	)
															_SCREAMING_SNAKE_CASE       =    inputs["""input_ids"""].shape[0]
															with torch.no_grad():
																					_SCREAMING_SNAKE_CASE       =    model(**UpperCAmelCase_	)
															_SCREAMING_SNAKE_CASE       =    outputs.attentions
															self.assertEqual(len(UpperCAmelCase_	) ,      self.model_tester.num_hidden_layers	)

															self.assertListEqual(
															    list(attentions[0].shape[-3:]	) ,      [batch_size, seq_len, config.hidden_size] ,      )
															_SCREAMING_SNAKE_CASE       =    len(UpperCAmelCase_	)

															# Check attention is always last and order is fine
															_SCREAMING_SNAKE_CASE       =    True
															_SCREAMING_SNAKE_CASE       =    True
															_SCREAMING_SNAKE_CASE       =    model_class(UpperCAmelCase_	)
															model.to(UpperCAmelCase_	)
															model.eval()

															_SCREAMING_SNAKE_CASE       =    self._prepare_for_class(UpperCAmelCase_ ,      UpperCAmelCase_	)
															_SCREAMING_SNAKE_CASE       =    inputs["""input_ids"""].shape[0]
															with torch.no_grad():
																					_SCREAMING_SNAKE_CASE       =    model(**UpperCAmelCase_	)

															_SCREAMING_SNAKE_CASE       =    1
															self.assertEqual(out_len + added_hidden_states ,      len(UpperCAmelCase_	)	)

															_SCREAMING_SNAKE_CASE       =    outputs.attentions

															self.assertEqual(len(UpperCAmelCase_	) ,      self.model_tester.num_hidden_layers	)
															self.assertListEqual(
															    list(self_attentions[0].shape[-3:]	) ,      [batch_size, seq_len, config.hidden_size] ,      )







			@slow
			def 				UpperCamelCase (      self:    List[Any]	):







									'''simple docstring'''




									for model_name in RWKV_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
															_SCREAMING_SNAKE_CASE       =    RwkvModel.from_pretrained(UpperCAmelCase_	)
															self.assertIsNotNone(UpperCAmelCase_	)



@unittest.skipIf(
    not is_torch_greater_or_equal_than_2_0			,reason="See https://github.com/huggingface/transformers/pull/24204"       )
@slow
class  __UpperCAmelCase						(unittest.TestCase       ):







			def 				UpperCamelCase (      self:    Optional[Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    """RWKV/rwkv-4-169m-pile"""
									_SCREAMING_SNAKE_CASE       =    AutoTokenizer.from_pretrained(self.model_id	)







			def 				UpperCamelCase (      self:    Any	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    """Hello my name is Jasmine and I am a newbie to the"""
									_SCREAMING_SNAKE_CASE       =    RwkvForCausalLM.from_pretrained(self.model_id	).to(UpperCAmelCase_	)

									_SCREAMING_SNAKE_CASE       =    self.tokenizer("""Hello my name is""" ,      return_tensors="""pt"""	).input_ids.to(UpperCAmelCase_	)
									_SCREAMING_SNAKE_CASE       =    model.generate(UpperCAmelCase_ ,      max_new_tokens=10	)
									_SCREAMING_SNAKE_CASE       =    self.tokenizer.decode(output[0].tolist()	)

									self.assertEqual(UpperCAmelCase_ ,      UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    Optional[Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    """Hello my name is Jasmine and I am a newbie to the"""

									_SCREAMING_SNAKE_CASE       =    self.tokenizer("""Hello my name is""" ,      return_tensors="""pt"""	).input_ids.to(UpperCAmelCase_	)
									_SCREAMING_SNAKE_CASE       =    RwkvForCausalLM.from_pretrained(self.model_id ,      torch_dtype=torch.bfloataa	).to(UpperCAmelCase_	)

									_SCREAMING_SNAKE_CASE       =    model.generate(UpperCAmelCase_ ,      max_new_tokens=10	)
									_SCREAMING_SNAKE_CASE       =    self.tokenizer.decode(output[0].tolist()	)

									self.assertEqual(UpperCAmelCase_ ,      UpperCAmelCase_	)









import math
import sys



class  __UpperCAmelCase						:







			def __init__(      self:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    0
									_SCREAMING_SNAKE_CASE       =    []
									_SCREAMING_SNAKE_CASE       =    {}  # To store the pos of node in array







			def 				UpperCamelCase (      self:    List[str]	):







									'''simple docstring'''




									return self.cur_size == 0







			def 				UpperCamelCase (      self:    int ,      UpperCAmelCase_:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.left(UpperCAmelCase_	)
									_SCREAMING_SNAKE_CASE       =    self.right(UpperCAmelCase_	)
									if lc < self.cur_size and self.array(UpperCAmelCase_	)[0] < self.array(UpperCAmelCase_	)[0]:
															_SCREAMING_SNAKE_CASE       =    lc
									else:
															_SCREAMING_SNAKE_CASE       =    idx
									if rc < self.cur_size and self.array(UpperCAmelCase_	)[0] < self.array(UpperCAmelCase_	)[0]:
															_SCREAMING_SNAKE_CASE       =    rc
									if smallest != idx:
															self.swap(UpperCAmelCase_ ,      UpperCAmelCase_	)
															self.min_heapify(UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    int ,      UpperCAmelCase_:    Tuple	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.cur_size
									self.cur_size += 1
									self.array.append((sys.maxsize, tup[1])	)
									self.decrease_key((sys.maxsize, tup[1]) ,      tup[0]	)







			def 				UpperCamelCase (      self:    Union[str, Any]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.array[0][1]
									_SCREAMING_SNAKE_CASE       =    self.array[self.cur_size - 1]
									self.cur_size -= 1
									self.min_heapify(1	)
									del self.pos[min_node]
									return min_node







			def 				UpperCamelCase (      self:    Dict ,      UpperCAmelCase_:    List[Any]	):







									'''simple docstring'''




									return 2 * i + 1







			def 				UpperCamelCase (      self:    Optional[Any] ,      UpperCAmelCase_:    List[Any]	):







									'''simple docstring'''




									return 2 * i + 2







			def 				UpperCamelCase (      self:    Union[str, Any] ,      UpperCAmelCase_:    int	):







									'''simple docstring'''




									return math.floor(i / 2	)







			def 				UpperCamelCase (      self:    str ,      UpperCAmelCase_:    Optional[Any] ,      UpperCAmelCase_:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    j
									_SCREAMING_SNAKE_CASE       =    i
									_SCREAMING_SNAKE_CASE       =    self.array[i]
									_SCREAMING_SNAKE_CASE       =    self.array[j]
									_SCREAMING_SNAKE_CASE       =    temp







			def 				UpperCamelCase (      self:    int ,      UpperCAmelCase_:    Dict ,      UpperCAmelCase_:    Dict	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    self.pos[tup[1]]
									# assuming the new_d is atmost old_d
									_SCREAMING_SNAKE_CASE       =    (new_d, tup[1])
									while idx > 0 and self.array[self.par(UpperCAmelCase_	)][0] > self.array[idx][0]:
															self.swap(UpperCAmelCase_ ,      self.par(UpperCAmelCase_	)	)
															_SCREAMING_SNAKE_CASE       =    self.par(UpperCAmelCase_	)



class  __UpperCAmelCase						:







			def __init__(      self:    Tuple ,      UpperCAmelCase_:    Any	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    {}  # To store graph: u -> (v,w)
									_SCREAMING_SNAKE_CASE       =    num  # Number of nodes in graph
									# To store the distance from source vertex
									_SCREAMING_SNAKE_CASE       =    [0] * self.num_nodes
									_SCREAMING_SNAKE_CASE       =    [-1] * self.num_nodes  # To store the path







			def 				UpperCamelCase (      self:    Tuple ,      UpperCAmelCase_:    int ,      UpperCAmelCase_:    List[Any] ,      UpperCAmelCase_:    Any	):







									'''simple docstring'''




									if u in self.adjList:
															self.adjList[u].append((v, w)	)
									else:
															_SCREAMING_SNAKE_CASE       =    [(v, w)]

									# Assuming undirected graph
									if v in self.adjList:
															self.adjList[v].append((u, w)	)
									else:
															_SCREAMING_SNAKE_CASE       =    [(u, w)]







			def 				UpperCamelCase (      self:    Dict	):







									'''simple docstring'''




									for u in self.adjList:
															print(UpperCAmelCase_ ,      """->""" ,      """ -> """.join(str(F'{v}({w})'	) for v, w in self.adjList[u]	)	)







			def 				UpperCamelCase (      self:    Optional[int] ,      UpperCAmelCase_:    str	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    [-1] * self.num_nodes
									# src is the source node
									_SCREAMING_SNAKE_CASE       =    0
									_SCREAMING_SNAKE_CASE       =    PriorityQueue()
									q.insert((0, src)	)  # (dist from src, node)
									for u in self.adjList:
															if u != src:
																					_SCREAMING_SNAKE_CASE       =    sys.maxsize  # Infinity
																					_SCREAMING_SNAKE_CASE       =    -1

									while not q.is_empty():
															_SCREAMING_SNAKE_CASE       =    q.extract_min()  # Returns node with the min dist from source
															# Update the distance of all the neighbours of u and
															# if their prev dist was INFINITY then push them in Q
															for v, w in self.adjList[u]:
																					_SCREAMING_SNAKE_CASE       =    self.dist[u] + w
																					if self.dist[v] > new_dist:
																											if self.dist[v] == sys.maxsize:
																																	q.insert((new_dist, v)	)
																											else:
																																	q.decrease_key((self.dist[v], v) ,      UpperCAmelCase_	)
																											_SCREAMING_SNAKE_CASE       =    new_dist
																											_SCREAMING_SNAKE_CASE       =    u

        # Show the shortest distances from src
									self.show_distances(UpperCAmelCase_	)







			def 				UpperCamelCase (      self:    Optional[int] ,      UpperCAmelCase_:    int	):







									'''simple docstring'''




									print(F'Distance from node: {src}'	)
									for u in range(self.num_nodes	):
															print(F'Node {u} has distance: {self.dist[u]}'	)







			def 				UpperCamelCase (      self:    str ,      UpperCAmelCase_:    str ,      UpperCAmelCase_:    List[str]	):







									'''simple docstring'''




									_SCREAMING_SNAKE_CASE       =    []
									_SCREAMING_SNAKE_CASE       =    0
									_SCREAMING_SNAKE_CASE       =    dest
									# Backtracking from dest to src
									while self.par[temp] != -1:
															path.append(UpperCAmelCase_	)
															if temp != src:
																					for v, w in self.adjList[temp]:
																											if v == self.par[temp]:
																																	cost += w
																																	break
															_SCREAMING_SNAKE_CASE       =    self.par[temp]
									path.append(UpperCAmelCase_	)
									path.reverse()

									print(F'----Path to reach {dest} from {src}----'	)
									for u in path:
															print(F'{u}' ,      end=""" """	)
															if u != dest:
																					print("""-> """ ,      end=""""""	)

									print("""\nTotal cost of path: """ ,      UpperCAmelCase_	)


if __name__ == "__main__":
		UpperCamelCase												=      Graph(9)
		graph.add_edge(0, 1, 4)
		graph.add_edge(0, 7, 8)
		graph.add_edge(1, 2, 8)
		graph.add_edge(1, 7, 11)
		graph.add_edge(2, 3, 7)
		graph.add_edge(2, 8, 2)
		graph.add_edge(2, 5, 4)
		graph.add_edge(3, 4, 9)
		graph.add_edge(3, 5, 14)
		graph.add_edge(4, 5, 10)
		graph.add_edge(5, 6, 2)
		graph.add_edge(6, 7, 1)
		graph.add_edge(6, 8, 6)
		graph.add_edge(7, 8, 7)
		graph.show_graph()
		graph.dijkstra(0)
		graph.show_path(0, 4)

# OUTPUT
# 0 -> 1(4) -> 7(8)
# 1 -> 0(4) -> 2(8) -> 7(11)
# 7 -> 0(8) -> 1(11) -> 6(1) -> 8(7)
# 2 -> 1(8) -> 3(7) -> 8(2) -> 5(4)
# 3 -> 2(7) -> 4(9) -> 5(14)
# 8 -> 2(2) -> 6(6) -> 7(7)
# 5 -> 2(4) -> 3(14) -> 4(10) -> 6(2)
# 4 -> 3(9) -> 5(10)
# 6 -> 5(2) -> 7(1) -> 8(6)
# Distance from node: 0
# Node 0 has distance: 0
# Node 1 has distance: 4
# Node 2 has distance: 12
# Node 3 has distance: 19
# Node 4 has distance: 21
# Node 5 has distance: 11
# Node 6 has distance: 9
# Node 7 has distance: 8
# Node 8 has distance: 14
# ----Path to reach 4 from 0----
# 0 -> 7 -> 6 -> 5 -> 4
# Total cost of path:  21

