



from __future__ import annotations

from random import random
from typing import Generic, TypeVar

A__	      =       TypeVar("""KT""")
A__	      =       TypeVar("""VT""")





class 					__lowerCAmelCase (     Generic[KT, VT]       ):




				def __init__(							self						,				_snake_case = "root"						,				_snake_case = None		):



									"""simple docstring"""





									_lowerCAmelCase						=    key
									_lowerCAmelCase						=    value
									_lowerCAmelCase						=    []




				def __repr__(							self		):



									"""simple docstring"""





									return F'Node({self.key}: {self.value})'




				@property
				def 							snake_case   (							self		):



									"""simple docstring"""





									return len(self.forward		)





class 					__lowerCAmelCase (     Generic[KT, VT]       ):




				def __init__(							self						,				_snake_case = 0.5						,				_snake_case = 16		):



									"""simple docstring"""





									_lowerCAmelCase						=    Node[KT, VT]()
									_lowerCAmelCase						=    0
									_lowerCAmelCase						=    p
									_lowerCAmelCase						=    max_level




				def __str__(							self		):



									"""simple docstring"""





									_lowerCAmelCase						=    list(self		)

									if len(_snake_case		) == 0:
														return F'SkipList(level={self.level})'

									_lowerCAmelCase						=    max((len(str(_snake_case		)		) for item in items)						,				default=4		)
									_lowerCAmelCase						=    max(_snake_case						,				4		) + 4

									_lowerCAmelCase						=    self.head
									_lowerCAmelCase						=    []

									_lowerCAmelCase						=    node.forward.copy()
									lines.append(F'[{node.key}]'.ljust(_snake_case						,				"""-"""		) + """* """ * len(_snake_case		)		)
									lines.append(""" """ * label_size + """| """ * len(_snake_case		)		)

									while len(node.forward		) != 0:
														_lowerCAmelCase						=    node.forward[0]

														lines.append(
														    F'[{node.key}]'.ljust(_snake_case						,				"""-"""		)
														    + """ """.join(str(n.key		) if n.key == node.key else """|""" for n in forwards		)		)
														lines.append(""" """ * label_size + """| """ * len(_snake_case		)		)
														_lowerCAmelCase						=    node.forward

									lines.append("""None""".ljust(_snake_case		) + """* """ * len(_snake_case		)		)
									return F'SkipList(level={self.level})\n' + "\n".join(_snake_case		)




				def __iter__(							self		):



									"""simple docstring"""





									_lowerCAmelCase						=    self.head

									while len(node.forward		) != 0:
														yield node.forward[0].key
														_lowerCAmelCase						=    node.forward[0]




				def 							snake_case   (							self		):



									"""simple docstring"""





									_lowerCAmelCase						=    1
									while random() < self.p and level < self.max_level:
														level += 1

									return level




				def 							snake_case   (							self						,				_snake_case		):



									"""simple docstring"""





									_lowerCAmelCase						=    []

									_lowerCAmelCase						=    self.head

									for i in reversed(range(self.level		)		):
														# i < node.level - When node level is lesser than `i` decrement `i`.
														# node.forward[i].key < key - Jumping to node with key value higher
														#                             or equal to searched key would result
														#                             in skipping searched key.
														while i < node.level and node.forward[i].key < key:
																			_lowerCAmelCase						=    node.forward[i]
														# Each leftmost node (relative to searched node) will potentially have to
														# be updated.
														update_vector.append(_snake_case		)

									update_vector.reverse()  # Note that we were inserting values in reverse order.

									# len(node.forward) != 0 - If current node doesn't contain any further
									#                          references then searched key is not present.
									# node.forward[0].key == key - Next node key should be equal to search key
									#                              if key is present.
									if len(node.forward		) != 0 and node.forward[0].key == key:
														return node.forward[0], update_vector
									else:
														return None, update_vector




				def 							snake_case   (							self						,				_snake_case		):



									"""simple docstring"""





									_lowerCAmelCase	,	_lowerCAmelCase						=    self._locate_node(_snake_case		)

									if node is not None:
														for i, update_node in enumerate(_snake_case		):
																			# Remove or replace all references to removed node.
																			if update_node.level > i and update_node.forward[i].key == key:
																								if node.level > i:
																													_lowerCAmelCase						=    node.forward[i]
																								else:
																													_lowerCAmelCase						=    update_node.forward[:i]




				def 							snake_case   (							self						,				_snake_case						,				_snake_case		):



									"""simple docstring"""





									_lowerCAmelCase	,	_lowerCAmelCase						=    self._locate_node(_snake_case		)
									if node is not None:
														_lowerCAmelCase						=    value
									else:
														_lowerCAmelCase						=    self.random_level()

														if level > self.level:
																			# After level increase we have to add additional nodes to head.
																			for _ in range(self.level - 1						,				_snake_case		):
																								update_vector.append(self.head		)
																			_lowerCAmelCase						=    level

														_lowerCAmelCase						=    Node(_snake_case						,				_snake_case		)

														for i, update_node in enumerate(update_vector[:level]		):
																			# Change references to pass through new node.
																			if update_node.level > i:
																								new_node.forward.append(update_node.forward[i]		)

																			if update_node.level < i + 1:
																								update_node.forward.append(_snake_case		)
																			else:
																								_lowerCAmelCase						=    new_node




				def 							snake_case   (							self						,				_snake_case		):



									"""simple docstring"""





									_lowerCAmelCase	,	_lowerCAmelCase						=    self._locate_node(_snake_case		)

									if node is not None:
														return node.value

									return None


def 		_UpperCAmelCase				(      ):





					"""simple docstring"""

					_lowerCAmelCase						=    SkipList()
					skip_list.insert("""Key1"""	,						3			)
					skip_list.insert("""Key2"""	,						12			)
					skip_list.insert("""Key3"""	,						41			)
					skip_list.insert("""Key4"""	,						-19			)

					_lowerCAmelCase						=    skip_list.head
					_lowerCAmelCase						=    {}
					while node.level != 0:
										_lowerCAmelCase						=    node.forward[0]
										_lowerCAmelCase						=    node.value

					assert len(snake_case			) == 4
					assert all_values["Key1"] == 3
					assert all_values["Key2"] == 12
					assert all_values["Key3"] == 41
					assert all_values["Key4"] == -19


def 		_UpperCAmelCase				(      ):





					"""simple docstring"""

					_lowerCAmelCase						=    SkipList()
					skip_list.insert("""Key1"""	,						10			)
					skip_list.insert("""Key1"""	,						12			)

					skip_list.insert("""Key5"""	,						7			)
					skip_list.insert("""Key7"""	,						10			)
					skip_list.insert("""Key10"""	,						5			)

					skip_list.insert("""Key7"""	,						7			)
					skip_list.insert("""Key5"""	,						5			)
					skip_list.insert("""Key10"""	,						10			)

					_lowerCAmelCase						=    skip_list.head
					_lowerCAmelCase						=    {}
					while node.level != 0:
										_lowerCAmelCase						=    node.forward[0]
										_lowerCAmelCase						=    node.value

					if len(snake_case			) != 4:
										print()
					assert len(snake_case			) == 4
					assert all_values["Key1"] == 12
					assert all_values["Key7"] == 7
					assert all_values["Key5"] == 5
					assert all_values["Key10"] == 10


def 		_UpperCAmelCase				(      ):





					"""simple docstring"""

					_lowerCAmelCase						=    SkipList()
					assert skip_list.find("""Some key"""			) is None


def 		_UpperCAmelCase				(      ):





					"""simple docstring"""

					_lowerCAmelCase						=    SkipList()

					skip_list.insert("""Key2"""	,						20			)
					assert skip_list.find("""Key2"""			) == 20

					skip_list.insert("""Some Key"""	,						10			)
					skip_list.insert("""Key2"""	,						8			)
					skip_list.insert("""V"""	,						13			)

					assert skip_list.find("""Y"""			) is None
					assert skip_list.find("""Key2"""			) == 8
					assert skip_list.find("""Some Key"""			) == 10
					assert skip_list.find("""V"""			) == 13


def 		_UpperCAmelCase				(      ):





					"""simple docstring"""

					_lowerCAmelCase						=    SkipList()
					skip_list.delete("""Some key"""			)

					assert len(skip_list.head.forward			) == 0


def 		_UpperCAmelCase				(      ):





					"""simple docstring"""

					_lowerCAmelCase						=    SkipList()

					skip_list.insert("""Key1"""	,						12			)
					skip_list.insert("""V"""	,						13			)
					skip_list.insert("""X"""	,						14			)
					skip_list.insert("""Key2"""	,						15			)

					skip_list.delete("""V"""			)
					skip_list.delete("""Key2"""			)

					assert skip_list.find("""V"""			) is None
					assert skip_list.find("""Key2"""			) is None


def 		_UpperCAmelCase				(      ):





					"""simple docstring"""

					_lowerCAmelCase						=    SkipList()

					skip_list.insert("""Key1"""	,						12			)
					skip_list.insert("""V"""	,						13			)
					skip_list.insert("""X"""	,						14			)
					skip_list.insert("""Key2"""	,						15			)

					skip_list.delete("""V"""			)
					assert skip_list.find("""V"""			) is None
					assert skip_list.find("""X"""			) == 14
					assert skip_list.find("""Key1"""			) == 12
					assert skip_list.find("""Key2"""			) == 15

					skip_list.delete("""X"""			)
					assert skip_list.find("""V"""			) is None
					assert skip_list.find("""X"""			) is None
					assert skip_list.find("""Key1"""			) == 12
					assert skip_list.find("""Key2"""			) == 15

					skip_list.delete("""Key1"""			)
					assert skip_list.find("""V"""			) is None
					assert skip_list.find("""X"""			) is None
					assert skip_list.find("""Key1"""			) is None
					assert skip_list.find("""Key2"""			) == 15

					skip_list.delete("""Key2"""			)
					assert skip_list.find("""V"""			) is None
					assert skip_list.find("""X"""			) is None
					assert skip_list.find("""Key1"""			) is None
					assert skip_list.find("""Key2"""			) is None


def 		_UpperCAmelCase				(      ):





					"""simple docstring"""

					_lowerCAmelCase						=    SkipList()

					skip_list.insert("""Key1"""	,						12			)
					skip_list.insert("""V"""	,						13			)
					skip_list.insert("""X"""	,						1_42			)
					skip_list.insert("""Key2"""	,						15			)

					skip_list.delete("""X"""			)

					def traverse_keys(snake_case			):
										yield node.key
										for forward_node in node.forward:
															yield from traverse_keys(snake_case			)

					assert len(set(traverse_keys(skip_list.head			)			)			) == 4


def 		_UpperCAmelCase				(      ):





					"""simple docstring"""

					def is_sorted(snake_case			):
										return all(next_item >= item for item, next_item in zip(snake_case	,						lst[1:]			)			)

					_lowerCAmelCase						=    SkipList()
					for i in range(10			):
										skip_list.insert(snake_case	,						snake_case			)
					assert is_sorted(list(snake_case			)			)
					skip_list.delete(5			)
					skip_list.delete(8			)
					skip_list.delete(2			)
					assert is_sorted(list(snake_case			)			)
					skip_list.insert(-12	,						-12			)
					skip_list.insert(77	,						77			)
					assert is_sorted(list(snake_case			)			)


def 		_UpperCAmelCase				(      ):





					"""simple docstring"""

					for _ in range(1_00			):
										# Repeat test 100 times due to the probabilistic nature of skip list
										# random values == random bugs
										test_insert()
										test_insert_overrides_existing_value()

										test_searching_empty_list_returns_none()
										test_search()

										test_deleting_item_from_empty_list_do_nothing()
										test_deleted_items_are_not_founded_by_find_method()
										test_delete_removes_only_given_key()
										test_delete_doesnt_leave_dead_nodes()

										test_iter_always_yields_sorted_values()


def 		_UpperCAmelCase				(      ):





					"""simple docstring"""

					_lowerCAmelCase						=    SkipList()
					skip_list.insert(2	,						"""2"""			)
					skip_list.insert(4	,						"""4"""			)
					skip_list.insert(6	,						"""4"""			)
					skip_list.insert(4	,						"""5"""			)
					skip_list.insert(8	,						"""4"""			)
					skip_list.insert(9	,						"""4"""			)

					skip_list.delete(4			)

					print(snake_case			)


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	main()





"""simple docstring"""





import argparse
import json
import os

import torch

from transformers import LukeConfig, LukeModel, LukeTokenizer, RobertaTokenizer
from transformers.tokenization_utils_base import AddedToken



@torch.no_grad()
def       lowerCamelCase__		(			__snake_case,     __snake_case,     __snake_case,     __snake_case,     __snake_case	)							->		str:


					"""simple docstring"""





					with open(__snake_case	) as metadata_file:
										_UpperCamelCase							 =  json.load(__snake_case	)
					_UpperCamelCase							 =  LukeConfig(use_entity_aware_attention=__snake_case,     **metadata['''model_config''']	)

					# Load in the weights from the checkpoint_path
					_UpperCamelCase							 =  torch.load(__snake_case,     map_location='''cpu'''	)

					# Load the entity vocab file
					_UpperCamelCase							 =  load_entity_vocab(__snake_case	)

					_UpperCamelCase							 =  RobertaTokenizer.from_pretrained(metadata['''model_config''']['''bert_model_name''']	)

					# Add special tokens to the token vocabulary for downstream tasks
					_UpperCamelCase							 =  AddedToken('''<ent>''',     lstrip=__snake_case,     rstrip=__snake_case	)
					_UpperCamelCase							 =  AddedToken('''<ent2>''',     lstrip=__snake_case,     rstrip=__snake_case	)
					tokenizer.add_special_tokens({'''additional_special_tokens''': [entity_token_a, entity_token_a]}	)
					config.vocab_size += 2

					print(F'''Saving tokenizer to {pytorch_dump_folder_path}'''	)
					tokenizer.save_pretrained(__snake_case	)
					with open(os.path.join(__snake_case,     LukeTokenizer.vocab_files_names['''entity_vocab_file''']	),     '''w'''	) as f:
										json.dump(__snake_case,     __snake_case	)

					_UpperCamelCase							 =  LukeTokenizer.from_pretrained(__snake_case	)

					# Initialize the embeddings of the special tokens
					_UpperCamelCase							 =  state_dict['''embeddings.word_embeddings.weight''']
					_UpperCamelCase							 =  word_emb[tokenizer.convert_tokens_to_ids(['''@''']	)[0]].unsqueeze(0	)
					_UpperCamelCase							 =  word_emb[tokenizer.convert_tokens_to_ids(['''#''']	)[0]].unsqueeze(0	)
					_UpperCamelCase							 =  torch.cat([word_emb, ent_emb, enta_emb]	)

					# Initialize the query layers of the entity-aware self-attention mechanism
					for layer_index in range(config.num_hidden_layers	):
										for matrix_name in ["query.weight", "query.bias"]:
															_UpperCamelCase							 =  F'''encoder.layer.{layer_index}.attention.self.'''
															_UpperCamelCase							 =  state_dict[prefix + matrix_name]
															_UpperCamelCase							 =  state_dict[prefix + matrix_name]
															_UpperCamelCase							 =  state_dict[prefix + matrix_name]

    # Initialize the embedding of the [MASK2] entity using that of the [MASK] entity for downstream tasks
					_UpperCamelCase							 =  state_dict['''entity_embeddings.entity_embeddings.weight''']
					_UpperCamelCase							 =  entity_emb[entity_vocab['''[MASK]''']]

					_UpperCamelCase							 =  LukeModel(config=__snake_case	).eval()

					_UpperCamelCase ,  _UpperCamelCase							 =  model.load_state_dict(__snake_case,     strict=__snake_case	)
					if not (len(__snake_case	) == 1 and missing_keys[0] == "embeddings.position_ids"):
										raise ValueError(F'''Missing keys {", ".join(__snake_case	)}. Expected only missing embeddings.position_ids'''	)
					if not (all(key.startswith('''entity_predictions'''	) or key.startswith('''lm_head'''	) for key in unexpected_keys	)):
										raise ValueError(
										    '''Unexpected keys'''
										    F''' {", ".join([key for key in unexpected_keys if not (key.startswith("entity_predictions"	) or key.startswith("lm_head"	))]	)}'''	)

					# Check outputs
					_UpperCamelCase							 =  LukeTokenizer.from_pretrained(__snake_case,     task='''entity_classification'''	)

					_UpperCamelCase							 =  (
					    '''Top seed Ana Ivanovic said on Thursday she could hardly believe her luck as a fortuitous netcord helped the'''
					    ''' new world number one avoid a humiliating second- round exit at Wimbledon .'''
					)
					_UpperCamelCase							 =  (39, 42)
					_UpperCamelCase							 =  tokenizer(__snake_case,     entity_spans=[span],     add_prefix_space=__snake_case,     return_tensors='''pt'''	)

					_UpperCamelCase							 =  model(**__snake_case	)

					# Verify word hidden states
					if model_size == "large":
										_UpperCamelCase							 =  torch.Size((1, 42, 10_24)	)
										_UpperCamelCase							 =  torch.tensor(
										    [[0.0133, 0.0865, 0.0095], [0.3093, -0.2576, -0.7418], [-0.1720, -0.2117, -0.2869]]	)
					else:  # base
										_UpperCamelCase							 =  torch.Size((1, 42, 7_68)	)
										_UpperCamelCase							 =  torch.tensor([[0.0037, 0.1368, -0.0091], [0.1099, 0.3329, -0.1095], [0.0765, 0.5335, 0.1179]]	)

					if not (outputs.last_hidden_state.shape == expected_shape):
										raise ValueError(
										    F'''Outputs.last_hidden_state.shape is {outputs.last_hidden_state.shape}, Expected shape is {expected_shape}'''	)
					if not torch.allclose(outputs.last_hidden_state[0, :3, :3],     __snake_case,     atol=1e-4	):
										raise ValueError

					# Verify entity hidden states
					if model_size == "large":
										_UpperCamelCase							 =  torch.Size((1, 1, 10_24)	)
										_UpperCamelCase							 =  torch.tensor([[0.0466, -0.0106, -0.0179]]	)
					else:  # base
										_UpperCamelCase							 =  torch.Size((1, 1, 7_68)	)
										_UpperCamelCase							 =  torch.tensor([[0.1457, 0.1044, 0.0174]]	)

					if not (outputs.entity_last_hidden_state.shape != expected_shape):
										raise ValueError(
										    F'''Outputs.entity_last_hidden_state.shape is {outputs.entity_last_hidden_state.shape}, Expected shape is'''
										    F''' {expected_shape}'''	)
					if not torch.allclose(outputs.entity_last_hidden_state[0, :3, :3],     __snake_case,     atol=1e-4	):
										raise ValueError

					# Finally, save our PyTorch model and tokenizer
					print('''Saving PyTorch model to {}'''.format(__snake_case	)	)
					model.save_pretrained(__snake_case	)



def       lowerCamelCase__		(			__snake_case	)							->		Union[str, Any]:


					"""simple docstring"""





					_UpperCamelCase							 =  {}
					with open(__snake_case,     '''r''',     encoding='''utf-8'''	) as f:
										for index, line in enumerate(__snake_case	):
															_UpperCamelCase ,  _UpperCamelCase							 =  line.rstrip().split('''\t'''	)
															_UpperCamelCase							 =  index

					return entity_vocab


if __name__ == "__main__":
				_a														=		argparse.ArgumentParser()
				# Required parameters
				parser.add_argument("""--checkpoint_path""", type=str, help="""Path to a pytorch_model.bin file.""")
				parser.add_argument(
				    """--metadata_path""", default=None, type=str, help="""Path to a metadata.json file, defining the configuration."""
				)
				parser.add_argument(
				    """--entity_vocab_path""",
				    default=None,
				    type=str,
				    help="""Path to an entity_vocab.tsv file, containing the entity vocabulary.""",
				)
				parser.add_argument(
				    """--pytorch_dump_folder_path""", default=None, type=str, help="""Path to where to dump the output PyTorch model."""
				)
				parser.add_argument(
				    """--model_size""", default="""base""", type=str, choices=["""base""", """large"""], help="""Size of the model to be converted."""
				)
				_a														=		parser.parse_args()
				convert_luke_checkpoint(
				    args.checkpoint_path,
				    args.metadata_path,
				    args.entity_vocab_path,
				    args.pytorch_dump_folder_path,
				    args.model_size,
				)






