




import json
import os
import pickle
import shutil
import tempfile
from unittest import TestCase
from unittest.mock import patch

import numpy as np
from datasets import Dataset

from transformers import is_faiss_available
from transformers.models.bart.configuration_bart import BartConfig
from transformers.models.bart.tokenization_bart import BartTokenizer
from transformers.models.bert.tokenization_bert import VOCAB_FILES_NAMES as DPR_VOCAB_FILES_NAMES
from transformers.models.dpr.configuration_dpr import DPRConfig
from transformers.models.dpr.tokenization_dpr import DPRContextEncoderTokenizer, DPRQuestionEncoderTokenizer
from transformers.models.rag.configuration_rag import RagConfig
from transformers.models.rag.retrieval_rag import CustomHFIndex, RagRetriever
from transformers.models.roberta.tokenization_roberta import VOCAB_FILES_NAMES as BART_VOCAB_FILES_NAMES
from transformers.testing_utils import require_faiss, require_sentencepiece, require_tokenizers, require_torch


if is_faiss_available():
			import faiss







@require_faiss
class a (     __SCREAMING_SNAKE_CASE  ):
						"""simple docstring"""

						def     UpperCAmelCase_      ( self :     Union[str, Any]				)    ->						Optional[Any]:
													"""simple docstring"""


													__lowercase      =    tempfile.mkdtemp()
													__lowercase      =    8

													# DPR tok
													__lowercase      =    [
													    '''[UNK]''',
													    '''[CLS]''',
													    '''[SEP]''',
													    '''[PAD]''',
													    '''[MASK]''',
													    '''want''',
													    '''##want''',
													    '''##ed''',
													    '''wa''',
													    '''un''',
													    '''runn''',
													    '''##ing''',
													    ''',''',
													    '''low''',
													    '''lowest''',
													]
													__lowercase      =    os.path.join(self.tmpdirname				,							'''dpr_tokenizer'''				)
													os.makedirs(lowerCamelCase__				,							exist_ok=lowerCamelCase__				)
													__lowercase      =    os.path.join(lowerCamelCase__				,							DPR_VOCAB_FILES_NAMES['''vocab_file''']				)
													with open(self.vocab_file				,							'''w'''				,							encoding='''utf-8'''				) as vocab_writer:
																				vocab_writer.write(''''''.join([x + '''\n''' for x in vocab_tokens]				)				)

													# BART tok
													__lowercase      =    [
													    '''l''',
													    '''o''',
													    '''w''',
													    '''e''',
													    '''r''',
													    '''s''',
													    '''t''',
													    '''i''',
													    '''d''',
													    '''n''',
													    '''\u0120''',
													    '''\u0120l''',
													    '''\u0120n''',
													    '''\u0120lo''',
													    '''\u0120low''',
													    '''er''',
													    '''\u0120lowest''',
													    '''\u0120newer''',
													    '''\u0120wider''',
													    '''<unk>''',
													]
													__lowercase      =    dict(zip(lowerCamelCase__				,							range(len(lowerCamelCase__				)				)				)				)
													__lowercase      =    ['''#version: 0.2''', '''\u0120 l''', '''\u0120l o''', '''\u0120lo w''', '''e r''', '''''']
													__lowercase      =    {'''unk_token''': '''<unk>'''}

													__lowercase      =    os.path.join(self.tmpdirname				,							'''bart_tokenizer'''				)
													os.makedirs(lowerCamelCase__				,							exist_ok=lowerCamelCase__				)
													__lowercase      =    os.path.join(lowerCamelCase__				,							BART_VOCAB_FILES_NAMES['''vocab_file''']				)
													__lowercase      =    os.path.join(lowerCamelCase__				,							BART_VOCAB_FILES_NAMES['''merges_file''']				)
													with open(self.vocab_file				,							'''w'''				,							encoding='''utf-8'''				) as fp:
																				fp.write(json.dumps(lowerCamelCase__				) + '''\n'''				)
													with open(self.merges_file				,							'''w'''				,							encoding='''utf-8'''				) as fp:
																				fp.write('''\n'''.join(lowerCamelCase__				)				)






						def     UpperCAmelCase_      ( self :     List[Any]				)    ->						DPRQuestionEncoderTokenizer:
													"""simple docstring"""


													return DPRQuestionEncoderTokenizer.from_pretrained(os.path.join(self.tmpdirname				,							'''dpr_tokenizer'''				)				)






						def     UpperCAmelCase_      ( self :     Dict				)    ->						DPRContextEncoderTokenizer:
													"""simple docstring"""


													return DPRContextEncoderTokenizer.from_pretrained(os.path.join(self.tmpdirname				,							'''dpr_tokenizer'''				)				)






						def     UpperCAmelCase_      ( self :     Dict				)    ->						BartTokenizer:
													"""simple docstring"""


													return BartTokenizer.from_pretrained(os.path.join(self.tmpdirname				,							'''bart_tokenizer'''				)				)






						def     UpperCAmelCase_      ( self :     List[str]				)    ->						Optional[Any]:
													"""simple docstring"""


													shutil.rmtree(self.tmpdirname				)






						def     UpperCAmelCase_      ( self :     Union[str, Any]				)    ->						Any:
													"""simple docstring"""


													__lowercase      =    Dataset.from_dict(
													    {
													        '''id''': ['''0''', '''1'''],
													        '''text''': ['''foo''', '''bar'''],
													        '''title''': ['''Foo''', '''Bar'''],
													        '''embeddings''': [np.ones(self.retrieval_vector_size				), 2 * np.ones(self.retrieval_vector_size				)],
													    }				)
													dataset.add_faiss_index('''embeddings'''				,							string_factory='''Flat'''				,							metric_type=faiss.METRIC_INNER_PRODUCT				)
													return dataset






						def     UpperCAmelCase_      ( self :     str				)    ->						Any:
													"""simple docstring"""


													__lowercase      =    self.get_dummy_dataset()
													__lowercase      =    RagConfig(
													    retrieval_vector_size=self.retrieval_vector_size				,							question_encoder=DPRConfig().to_dict()				,							generator=BartConfig().to_dict()				,							)
													with patch('''transformers.models.rag.retrieval_rag.load_dataset'''				) as mock_load_dataset:
																				__lowercase      =    dataset
																				__lowercase      =    RagRetriever(
																				    lowerCamelCase__				,							question_encoder_tokenizer=self.get_dpr_tokenizer()				,							generator_tokenizer=self.get_bart_tokenizer()				,							)
													return retriever






						def     UpperCAmelCase_      ( self :     Optional[int]				,							lowerCamelCase__ :     bool				)    ->						Optional[int]:
													"""simple docstring"""


													__lowercase      =    self.get_dummy_dataset()
													__lowercase      =    RagConfig(
													    retrieval_vector_size=self.retrieval_vector_size				,							question_encoder=DPRConfig().to_dict()				,							generator=BartConfig().to_dict()				,							index_name='''custom'''				,							)
													if from_disk:
																				__lowercase      =    os.path.join(self.tmpdirname				,							'''dataset'''				)
																				__lowercase      =    os.path.join(self.tmpdirname				,							'''index.faiss'''				)
																				dataset.get_index('''embeddings'''				).save(os.path.join(self.tmpdirname				,							'''index.faiss'''				)				)
																				dataset.drop_index('''embeddings'''				)
																				dataset.save_to_disk(os.path.join(self.tmpdirname				,							'''dataset'''				)				)
																				del dataset
																				__lowercase      =    RagRetriever(
																				    lowerCamelCase__				,							question_encoder_tokenizer=self.get_dpr_tokenizer()				,							generator_tokenizer=self.get_bart_tokenizer()				,							)
													else:
																				__lowercase      =    RagRetriever(
																				    lowerCamelCase__				,							question_encoder_tokenizer=self.get_dpr_tokenizer()				,							generator_tokenizer=self.get_bart_tokenizer()				,							index=CustomHFIndex(config.retrieval_vector_size				,							lowerCamelCase__				)				,							)
													return retriever






						def     UpperCAmelCase_      ( self :     Tuple				)    ->						List[Any]:
													"""simple docstring"""


													__lowercase      =    Dataset.from_dict(
													    {
													        '''id''': ['''0''', '''1'''],
													        '''text''': ['''foo''', '''bar'''],
													        '''title''': ['''Foo''', '''Bar'''],
													        '''embeddings''': [np.ones(self.retrieval_vector_size + 1				), 2 * np.ones(self.retrieval_vector_size + 1				)],
													    }				)
													dataset.add_faiss_index('''embeddings'''				,							string_factory='''Flat'''				,							metric_type=faiss.METRIC_INNER_PRODUCT				)

													__lowercase      =    os.path.join(self.tmpdirname				,							'''hf_bert_base.hnswSQ8_correct_phi_128.c_index'''				)
													dataset.save_faiss_index('''embeddings'''				,							index_file_name + '''.index.dpr'''				)
													pickle.dump(dataset['''id''']				,							open(index_file_name + '''.index_meta.dpr'''				,							'''wb'''				)				)

													__lowercase      =    os.path.join(self.tmpdirname				,							'''psgs_w100.tsv.pkl'''				)
													__lowercase      =    {sample['''id''']: [sample['''text'''], sample['''title''']] for sample in dataset}
													pickle.dump(lowerCamelCase__				,							open(lowerCamelCase__				,							'''wb'''				)				)

													__lowercase      =    RagConfig(
													    retrieval_vector_size=self.retrieval_vector_size				,							question_encoder=DPRConfig().to_dict()				,							generator=BartConfig().to_dict()				,							index_name='''legacy'''				,							index_path=self.tmpdirname				,							)
													__lowercase      =    RagRetriever(
													    lowerCamelCase__				,							question_encoder_tokenizer=self.get_dpr_tokenizer()				,							generator_tokenizer=self.get_bart_tokenizer()				)
													return retriever






						def     UpperCAmelCase_      ( self :     List[Any]				)    ->						Optional[Any]:
													"""simple docstring"""


													__lowercase      =    1
													__lowercase      =    self.get_dummy_canonical_hf_index_retriever()
													__lowercase      =    np.array(
													    [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,							dtype=np.floataa				)
													__lowercase     ,     __lowercase     ,     __lowercase      =    retriever.retrieve(lowerCamelCase__				,							n_docs=lowerCamelCase__				)
													self.assertEqual(retrieved_doc_embeds.shape				,							(2, n_docs, self.retrieval_vector_size)				)
													self.assertEqual(len(lowerCamelCase__				)				,							2				)
													self.assertEqual(sorted(doc_dicts[0]				)				,							['''embeddings''', '''id''', '''text''', '''title''']				)
													self.assertEqual(len(doc_dicts[0]['''id''']				)				,							lowerCamelCase__				)
													self.assertEqual(doc_dicts[0]['''id'''][0]				,							'''1'''				)  # max inner product is reached with second doc
													self.assertEqual(doc_dicts[1]['''id'''][0]				,							'''0'''				)  # max inner product is reached with first doc
													self.assertListEqual(doc_ids.tolist()				,							[[1], [0]]				)






						def     UpperCAmelCase_      ( self :     List[str]				)    ->						List[str]:
													"""simple docstring"""


													__lowercase      =    self.get_dummy_canonical_hf_index_retriever()
													with tempfile.TemporaryDirectory() as tmp_dirname:
																				with patch('''transformers.models.rag.retrieval_rag.load_dataset'''				) as mock_load_dataset:
																											__lowercase      =    self.get_dummy_dataset()
																											retriever.save_pretrained(lowerCamelCase__				)
																											__lowercase      =    RagRetriever.from_pretrained(lowerCamelCase__				)
																											self.assertIsInstance(lowerCamelCase__				,							lowerCamelCase__				)
																											__lowercase      =    np.array(
																											    [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,							dtype=np.floataa				)
																											__lowercase      =    retriever.retrieve(lowerCamelCase__				,							n_docs=1				)
																											self.assertTrue(out is not None				)






						def     UpperCAmelCase_      ( self :     Optional[int]				)    ->						List[Any]:
													"""simple docstring"""


													__lowercase      =    1
													__lowercase      =    self.get_dummy_custom_hf_index_retriever(from_disk=lowerCamelCase__				)
													__lowercase      =    np.array(
													    [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,							dtype=np.floataa				)
													__lowercase     ,     __lowercase     ,     __lowercase      =    retriever.retrieve(lowerCamelCase__				,							n_docs=lowerCamelCase__				)
													self.assertEqual(retrieved_doc_embeds.shape				,							(2, n_docs, self.retrieval_vector_size)				)
													self.assertEqual(len(lowerCamelCase__				)				,							2				)
													self.assertEqual(sorted(doc_dicts[0]				)				,							['''embeddings''', '''id''', '''text''', '''title''']				)
													self.assertEqual(len(doc_dicts[0]['''id''']				)				,							lowerCamelCase__				)
													self.assertEqual(doc_dicts[0]['''id'''][0]				,							'''1'''				)  # max inner product is reached with second doc
													self.assertEqual(doc_dicts[1]['''id'''][0]				,							'''0'''				)  # max inner product is reached with first doc
													self.assertListEqual(doc_ids.tolist()				,							[[1], [0]]				)






						def     UpperCAmelCase_      ( self :     Union[str, Any]				)    ->						str:
													"""simple docstring"""


													__lowercase      =    self.get_dummy_custom_hf_index_retriever(from_disk=lowerCamelCase__				)
													with tempfile.TemporaryDirectory() as tmp_dirname:
																				retriever.save_pretrained(lowerCamelCase__				)
																				__lowercase      =    RagRetriever.from_pretrained(lowerCamelCase__				)
																				self.assertIsInstance(lowerCamelCase__				,							lowerCamelCase__				)
																				__lowercase      =    np.array(
																				    [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,							dtype=np.floataa				)
																				__lowercase      =    retriever.retrieve(lowerCamelCase__				,							n_docs=1				)
																				self.assertTrue(out is not None				)






						def     UpperCAmelCase_      ( self :     int				)    ->						int:
													"""simple docstring"""


													__lowercase      =    1
													__lowercase      =    self.get_dummy_custom_hf_index_retriever(from_disk=lowerCamelCase__				)
													__lowercase      =    np.array(
													    [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,							dtype=np.floataa				)
													__lowercase     ,     __lowercase     ,     __lowercase      =    retriever.retrieve(lowerCamelCase__				,							n_docs=lowerCamelCase__				)
													self.assertEqual(retrieved_doc_embeds.shape				,							(2, n_docs, self.retrieval_vector_size)				)
													self.assertEqual(len(lowerCamelCase__				)				,							2				)
													self.assertEqual(sorted(doc_dicts[0]				)				,							['''embeddings''', '''id''', '''text''', '''title''']				)
													self.assertEqual(len(doc_dicts[0]['''id''']				)				,							lowerCamelCase__				)
													self.assertEqual(doc_dicts[0]['''id'''][0]				,							'''1'''				)  # max inner product is reached with second doc
													self.assertEqual(doc_dicts[1]['''id'''][0]				,							'''0'''				)  # max inner product is reached with first doc
													self.assertListEqual(doc_ids.tolist()				,							[[1], [0]]				)






						def     UpperCAmelCase_      ( self :     List[str]				)    ->						Tuple:
													"""simple docstring"""


													__lowercase      =    self.get_dummy_custom_hf_index_retriever(from_disk=lowerCamelCase__				)
													with tempfile.TemporaryDirectory() as tmp_dirname:
																				retriever.save_pretrained(lowerCamelCase__				)
																				__lowercase      =    RagRetriever.from_pretrained(lowerCamelCase__				)
																				self.assertIsInstance(lowerCamelCase__				,							lowerCamelCase__				)
																				__lowercase      =    np.array(
																				    [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,							dtype=np.floataa				)
																				__lowercase      =    retriever.retrieve(lowerCamelCase__				,							n_docs=1				)
																				self.assertTrue(out is not None				)






						def     UpperCAmelCase_      ( self :     Union[str, Any]				)    ->						Optional[Any]:
													"""simple docstring"""


													__lowercase      =    1
													__lowercase      =    self.get_dummy_legacy_index_retriever()
													__lowercase      =    np.array(
													    [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,							dtype=np.floataa				)
													__lowercase     ,     __lowercase     ,     __lowercase      =    retriever.retrieve(lowerCamelCase__				,							n_docs=lowerCamelCase__				)
													self.assertEqual(retrieved_doc_embeds.shape				,							(2, n_docs, self.retrieval_vector_size)				)
													self.assertEqual(len(lowerCamelCase__				)				,							2				)
													self.assertEqual(sorted(doc_dicts[0]				)				,							['''text''', '''title''']				)
													self.assertEqual(len(doc_dicts[0]['''text''']				)				,							lowerCamelCase__				)
													self.assertEqual(doc_dicts[0]['''text'''][0]				,							'''bar'''				)  # max inner product is reached with second doc
													self.assertEqual(doc_dicts[1]['''text'''][0]				,							'''foo'''				)  # max inner product is reached with first doc
													self.assertListEqual(doc_ids.tolist()				,							[[1], [0]]				)






						def     UpperCAmelCase_      ( self :     Dict				)    ->						Any:
													"""simple docstring"""


													__lowercase      =    self.get_dummy_legacy_index_retriever()
													with tempfile.TemporaryDirectory() as tmp_dirname:
																				retriever.save_pretrained(lowerCamelCase__				)
																				__lowercase      =    RagRetriever.from_pretrained(lowerCamelCase__				)
																				self.assertIsInstance(lowerCamelCase__				,							lowerCamelCase__				)
																				__lowercase      =    np.array(
																				    [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,							dtype=np.floataa				)
																				__lowercase      =    retriever.retrieve(lowerCamelCase__				,							n_docs=1				)
																				self.assertTrue(out is not None				)






						@require_torch
						@require_tokenizers
						@require_sentencepiece
						def     UpperCAmelCase_      ( self :     Optional[int]				)    ->						int:
													"""simple docstring"""


													import torch

													__lowercase      =    1
													__lowercase      =    self.get_dummy_canonical_hf_index_retriever()
													__lowercase      =    [[5, 7], [10, 11]]
													__lowercase      =    np.array(
													    [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,							dtype=np.floataa				)
													__lowercase      =    retriever(lowerCamelCase__				,							lowerCamelCase__				,							prefix=retriever.config.generator.prefix				,							n_docs=lowerCamelCase__				)
													__lowercase     ,     __lowercase     ,     __lowercase      =    (
													    out['''context_input_ids'''],
													    out['''context_attention_mask'''],
													    out['''retrieved_doc_embeds'''],
													)
													self.assertEqual(retrieved_doc_embeds.shape				,							(2, n_docs, self.retrieval_vector_size)				)
													self.assertIsInstance(lowerCamelCase__				,							lowerCamelCase__				)
													self.assertIsInstance(lowerCamelCase__				,							lowerCamelCase__				)
													self.assertIsInstance(lowerCamelCase__				,							np.ndarray				)

													__lowercase      =    retriever(
													    lowerCamelCase__				,							lowerCamelCase__				,							prefix=retriever.config.generator.prefix				,							n_docs=lowerCamelCase__				,							return_tensors='''pt'''				,							)
													__lowercase     ,     __lowercase     ,     __lowercase     ,     __lowercase      =    (  # noqa: F841
													    out['''context_input_ids'''],
													    out['''context_attention_mask'''],
													    out['''retrieved_doc_embeds'''],
													    out['''doc_ids'''],
													)
													self.assertEqual(retrieved_doc_embeds.shape				,							(2, n_docs, self.retrieval_vector_size)				)
													self.assertIsInstance(lowerCamelCase__				,							torch.Tensor				)
													self.assertIsInstance(lowerCamelCase__				,							torch.Tensor				)
													self.assertIsInstance(lowerCamelCase__				,							torch.Tensor				)






						@require_torch
						@require_tokenizers
						@require_sentencepiece
						def     UpperCAmelCase_      ( self :     Any				)    ->						Tuple:
													"""simple docstring"""


													__lowercase      =    self.get_dpr_ctx_encoder_tokenizer()
													__lowercase      =    1
													__lowercase      =    self.get_dummy_custom_hf_index_retriever(from_disk=lowerCamelCase__				)
													retriever.set_ctx_encoder_tokenizer(lowerCamelCase__				)

													__lowercase      =    [[5, 7], [10, 11]]
													__lowercase      =    np.array(
													    [np.ones(self.retrieval_vector_size				), -np.ones(self.retrieval_vector_size				)]				,							dtype=np.floataa				)
													__lowercase      =    retriever(lowerCamelCase__				,							lowerCamelCase__				,							prefix=retriever.config.generator.prefix				,							n_docs=lowerCamelCase__				)

													self.assertEqual(
													    len(lowerCamelCase__				)				,							6				)  # check whether the retriever output consist of 6 attributes including tokenized docs
													self.assertEqual(
													    all(k in out for k in ('''tokenized_doc_ids''', '''tokenized_doc_attention_mask''')				)				,							lowerCamelCase__				)  # check for doc token related keys in dictionary.












import argparse
import copy







def 		_A(       UpperCamelCase__							:			Union[str, Any]				)    -> Tuple:
							'''simple docstring'''


							__lowercase      =    {}

							with open(UpperCamelCase__				) as f:
														for line in f:
																					if line.split()[0] not in dict_of_neighbours:
																												__lowercase      =    []
																												_list.append([line.split()[1], line.split()[2]]				)
																												__lowercase      =    _list
																					else:
																												dict_of_neighbours[line.split()[0]].append(
																												    [line.split()[1], line.split()[2]]				)
																					if line.split()[1] not in dict_of_neighbours:
																												__lowercase      =    []
																												_list.append([line.split()[0], line.split()[2]]				)
																												__lowercase      =    _list
																					else:
																												dict_of_neighbours[line.split()[1]].append(
																												    [line.split()[0], line.split()[2]]				)

							return dict_of_neighbours







def 		_A(       UpperCamelCase__							:			Optional[int]				,       UpperCamelCase__							:			Optional[Any]				)    -> Dict:
							'''simple docstring'''


							with open(UpperCamelCase__				) as f:
														__lowercase      =    f.read(1				)
							__lowercase      =    start_node

							__lowercase      =    []

							__lowercase      =    start_node

							__lowercase      =    0
							while visiting not in first_solution:
														__lowercase      =    1_0000
														for k in dict_of_neighbours[visiting]:
																					if int(k[1]				) < int(UpperCamelCase__				) and k[0] not in first_solution:
																												__lowercase      =    k[1]
																												__lowercase      =    k[0]

														first_solution.append(UpperCamelCase__				)
														__lowercase      =    distance_of_first_solution + int(UpperCamelCase__				)
														__lowercase      =    best_node

							first_solution.append(UpperCamelCase__				)

							__lowercase      =    0
							for k in dict_of_neighbours[first_solution[-2]]:
														if k[0] == start_node:
																					break
														position += 1

							__lowercase      =    (
							    distance_of_first_solution
							    + int(dict_of_neighbours[first_solution[-2]][position][1]				)
							    - 1_0000
							)
							return first_solution, distance_of_first_solution







def 		_A(       UpperCamelCase__							:			int				,       UpperCamelCase__							:			Optional[Any]				)    -> Optional[int]:
							'''simple docstring'''


							__lowercase      =    []

							for n in solution[1:-1]:
														__lowercase      =    solution.index(UpperCamelCase__				)
														for kn in solution[1:-1]:
																					__lowercase      =    solution.index(UpperCamelCase__				)
																					if n == kn:
																												continue

																					__lowercase      =    copy.deepcopy(UpperCamelCase__				)
																					__lowercase      =    kn
																					__lowercase      =    n

																					__lowercase      =    0

																					for k in _tmp[:-1]:
																												__lowercase      =    _tmp[_tmp.index(UpperCamelCase__				) + 1]
																												for i in dict_of_neighbours[k]:
																																			if i[0] == next_node:
																																										__lowercase      =    distance + int(i[1]				)
																					_tmp.append(UpperCamelCase__				)

																					if _tmp not in neighborhood_of_solution:
																												neighborhood_of_solution.append(_tmp				)

							__lowercase      =    len(neighborhood_of_solution[0]				) - 1

							neighborhood_of_solution.sort(key=lambda UpperCamelCase__				: x[index_of_last_item_in_the_list]				)
							return neighborhood_of_solution







def 		_A(       UpperCamelCase__							:			List[Any]				,       UpperCamelCase__							:			List[str]				,       UpperCamelCase__							:			Optional[int]				,       UpperCamelCase__							:			Optional[int]				,       UpperCamelCase__							:			Optional[int]				)    -> List[str]:
							'''simple docstring'''


							__lowercase      =    1
							__lowercase      =    first_solution
							__lowercase      =    []
							__lowercase      =    distance_of_first_solution
							__lowercase      =    solution

							while count <= iters:
														__lowercase      =    find_neighborhood(UpperCamelCase__				,       UpperCamelCase__				)
														__lowercase      =    0
														__lowercase      =    neighborhood[index_of_best_solution]
														__lowercase      =    len(UpperCamelCase__				) - 1

														__lowercase      =    False
														while not found:
																					__lowercase      =    0
																					while i < len(UpperCamelCase__				):
																												if best_solution[i] != solution[i]:
																																			__lowercase      =    best_solution[i]
																																			__lowercase      =    solution[i]
																																			break
																												__lowercase      =    i + 1

																					if [first_exchange_node, second_exchange_node] not in tabu_list and [
																					    second_exchange_node,
																					    first_exchange_node,
																					] not in tabu_list:
																												tabu_list.append([first_exchange_node, second_exchange_node]				)
																												__lowercase      =    True
																												__lowercase      =    best_solution[:-1]
																												__lowercase      =    neighborhood[index_of_best_solution][best_cost_index]
																												if cost < best_cost:
																																			__lowercase      =    cost
																																			__lowercase      =    solution
																					else:
																												__lowercase      =    index_of_best_solution + 1
																												__lowercase      =    neighborhood[index_of_best_solution]

														if len(UpperCamelCase__				) >= size:
																					tabu_list.pop(0				)

														__lowercase      =    count + 1

							return best_solution_ever, best_cost







def 		_A(       UpperCamelCase__							:			List[Any]=None				)    -> int:
							'''simple docstring'''


							__lowercase      =    generate_neighbours(args.File				)

							__lowercase     ,     __lowercase      =    generate_first_solution(
							    args.File				,       UpperCamelCase__				)

							__lowercase     ,     __lowercase      =    tabu_search(
							    UpperCamelCase__				,       UpperCamelCase__				,       UpperCamelCase__				,       args.Iterations				,       args.Size				,       )

							print(F'Best solution: {best_sol}, with total distance: {best_cost}.'				)


if __name__ == "__main__":
			UpperCAmelCase__				     = argparse.ArgumentParser(description="Tabu Search")
			parser.add_argument(
			    "-f",
			    "--File",
			    type=str,
			    help="Path to the file containing the data",
			    required=True,
			)
			parser.add_argument(
			    "-i",
			    "--Iterations",
			    type=int,
			    help="How many iterations the algorithm should perform",
			    required=True,
			)
			parser.add_argument(
			    "-s", "--Size", type=int, help="Size of the tabu list", required=True
			)

			# Pass the arguments to main method
			main(parser.parse_args())






