





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

import faiss
import numpy as np
from datasets import Dataset

from transformers import BartConfig, BartTokenizer, DPRConfig, DPRQuestionEncoderTokenizer, RagConfig
from transformers.file_utils import is_datasets_available, is_faiss_available, is_psutil_available, is_torch_available
from transformers.integrations import is_ray_available
from transformers.models.bert.tokenization_bert import VOCAB_FILES_NAMES as DPR_VOCAB_FILES_NAMES
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_ray


sys.path.append(os.path.join(os.getcwd()))  # noqa: E402 # noqa: E402 # isort:skip

if is_torch_available():
				from distributed_pytorch_retriever import RagPyTorchDistributedRetriever  # noqa: E402 # isort:skip
else:
				__lowerCAmelCase     =			None

if is_ray_available():
				import ray  # noqa: E402 # isort:skip
				from distributed_ray_retriever import RagRayDistributedRetriever, RayRetriever  # noqa: E402 # isort:skip
else:
				__lowerCAmelCase     =			None
				__lowerCAmelCase     =			None
				__lowerCAmelCase     =			None

def     a						(      _lowercase   :     Optional[int]       )     ->Any:
		if not (is_datasets_available() and is_faiss_available() and is_psutil_available()):
				UpperCamelCase__         =	unittest.skip("""test requires Datasets, Faiss, psutil"""       )(_lowercase       )
		return test_case




@require_distributed_retrieval
class   _UpperCAmelCase	(   _lowercase					):




					def 	snake_case_		(						self       )						->  List[str]:
							UpperCamelCase__         =	tempfile.mkdtemp()
							UpperCamelCase__         =	8

							# DPR tok
							UpperCamelCase__         =	[
							    """[UNK]""",
							    """[CLS]""",
							    """[SEP]""",
							    """[PAD]""",
							    """[MASK]""",
							    """want""",
							    """##want""",
							    """##ed""",
							    """wa""",
							    """un""",
							    """runn""",
							    """##ing""",
							    """,""",
							    """low""",
							    """lowest""",
							]
							UpperCamelCase__         =	os.path.join(self.tmpdirname    ,      """dpr_tokenizer"""       )
							os.makedirs(__lowerCAmelCase    ,      exist_ok=__lowerCAmelCase       )
							UpperCamelCase__         =	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
							UpperCamelCase__         =	[
							    """l""",
							    """o""",
							    """w""",
							    """e""",
							    """r""",
							    """s""",
							    """t""",
							    """i""",
							    """d""",
							    """n""",
							    """\u0120""",
							    """\u0120l""",
							    """\u0120n""",
							    """\u0120lo""",
							    """\u0120low""",
							    """er""",
							    """\u0120lowest""",
							    """\u0120newer""",
							    """\u0120wider""",
							    """<unk>""",
							]
							UpperCamelCase__         =	dict(zip(__lowerCAmelCase    ,      range(len(__lowerCAmelCase       )       )       )       )
							UpperCamelCase__         =	["""#version: 0.2""", """\u0120 l""", """\u0120l o""", """\u0120lo w""", """e r""", """"""]
							UpperCamelCase__         =	{"""unk_token""": """<unk>"""}

							UpperCamelCase__         =	os.path.join(self.tmpdirname    ,      """bart_tokenizer"""       )
							os.makedirs(__lowerCAmelCase    ,      exist_ok=__lowerCAmelCase       )
							UpperCamelCase__         =	os.path.join(__lowerCAmelCase    ,      BART_VOCAB_FILES_NAMES["""vocab_file"""]       )
							UpperCamelCase__         =	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 	snake_case_		(						self       )						->  DPRQuestionEncoderTokenizer:
							return DPRQuestionEncoderTokenizer.from_pretrained(os.path.join(self.tmpdirname    ,      """dpr_tokenizer"""       )       )




					def 	snake_case_		(						self       )						->  BartTokenizer:
							return BartTokenizer.from_pretrained(os.path.join(self.tmpdirname    ,      """bart_tokenizer"""       )       )




					def 	snake_case_		(						self       )						->  Optional[Any]:
							shutil.rmtree(self.tmpdirname       )




					def 	snake_case_		(						self       )						->  List[str]:
							UpperCamelCase__         =	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 	snake_case_		(						self    ,      __lowerCAmelCase    ,      __lowerCAmelCase=12_345       )						->  RagPyTorchDistributedRetriever:
							UpperCamelCase__         =	self.get_dummy_dataset()
							UpperCamelCase__         =	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:
									UpperCamelCase__         =	dataset
									UpperCamelCase__         =	RagPyTorchDistributedRetriever(
									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      )
									if init_retrieval:
											retriever.init_retrieval(__lowerCAmelCase       )
							return retriever




					def 	snake_case_		(						self    ,      __lowerCAmelCase       )						->  RagRayDistributedRetriever:
							# Have to run in local mode because sys.path modifications at top of
							# file are not propogated to remote workers.
							# https://stackoverflow.com/questions/54338013/parallel-import-a-python-file-from-sibling-folder
							ray.init(local_mode=__lowerCAmelCase       )
							UpperCamelCase__         =	RagConfig(
							    retrieval_vector_size=self.retrieval_vector_size    ,      question_encoder=DPRConfig().to_dict()    ,      generator=BartConfig().to_dict()    ,      )
							UpperCamelCase__         =	ray.remote(__lowerCAmelCase       )
							UpperCamelCase__         =	[remote_cls.remote() for _ in range(1       )]
							with patch("""transformers.models.rag.retrieval_rag.load_dataset"""       ) as mock_load_dataset:
									UpperCamelCase__         =	self.get_dummy_dataset()
									UpperCamelCase__         =	RagRayDistributedRetriever(
									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      retrieval_workers=__lowerCAmelCase    ,      )
									if init_retrieval:
											retriever.init_retrieval()
							return retriever




					def 	snake_case_		(						self    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      __lowerCAmelCase=12_345       )						->  List[Any]:
							UpperCamelCase__         =	self.get_dummy_dataset()
							UpperCamelCase__         =	RagConfig(
							    retrieval_vector_size=self.retrieval_vector_size    ,      question_encoder=DPRConfig().to_dict()    ,      generator=BartConfig().to_dict()    ,      index_name="""custom"""    ,      )
							if from_disk:
									UpperCamelCase__         =	os.path.join(self.tmpdirname    ,      """dataset"""       )
									UpperCamelCase__         =	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
									UpperCamelCase__         =	RagPyTorchDistributedRetriever(
									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      )
							else:
									UpperCamelCase__         =	RagPyTorchDistributedRetriever(
									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      index=CustomHFIndex(config.retrieval_vector_size    ,      __lowerCAmelCase       )    ,      )
							if init_retrieval:
									retriever.init_retrieval(__lowerCAmelCase       )
							return retriever




					def 	snake_case_		(						self    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )						->  List[Any]:
							# Have to run in local mode because sys.path modifications at top of
							# file are not propogated to remote workers.
							# https://stackoverflow.com/questions/54338013/parallel-import-a-python-file-from-sibling-folder
							ray.init(local_mode=__lowerCAmelCase       )
							UpperCamelCase__         =	self.get_dummy_dataset()
							UpperCamelCase__         =	RagConfig(
							    retrieval_vector_size=self.retrieval_vector_size    ,      question_encoder=DPRConfig().to_dict()    ,      generator=BartConfig().to_dict()    ,      index_name="""custom"""    ,      )
							UpperCamelCase__         =	ray.remote(__lowerCAmelCase       )
							UpperCamelCase__         =	[remote_cls.remote() for _ in range(1       )]
							if from_disk:
									UpperCamelCase__         =	os.path.join(self.tmpdirname    ,      """dataset"""       )
									UpperCamelCase__         =	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
									UpperCamelCase__         =	RagRayDistributedRetriever(
									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      retrieval_workers=__lowerCAmelCase    ,      index=CustomHFIndex.load_from_disk(
									        vector_size=config.retrieval_vector_size    ,      dataset_path=config.passages_path    ,      index_path=config.index_path    ,      )    ,      )
							else:
									UpperCamelCase__         =	RagRayDistributedRetriever(
									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      retrieval_workers=__lowerCAmelCase    ,      index=CustomHFIndex(config.retrieval_vector_size    ,      __lowerCAmelCase       )    ,      )
							if init_retrieval:
									retriever.init_retrieval()
							return retriever




					def 	snake_case_		(						self    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )						->  None:
							UpperCamelCase__  ,			UpperCamelCase__  ,			UpperCamelCase__         =	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 	snake_case_		(						self       )						->  str:
							UpperCamelCase__         =	1
							UpperCamelCase__         =	np.array(
							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )

							self.distributed_retriever_check(
							    self.get_dummy_pytorch_distributed_retriever(init_retrieval=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )




					def 	snake_case_		(						self       )						->  int:
							UpperCamelCase__         =	1
							UpperCamelCase__         =	np.array(
							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )

							self.distributed_retriever_check(
							    self.get_dummy_custom_hf_index_pytorch_retriever(init_retrieval=__lowerCAmelCase    ,      from_disk=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      )




					def 	snake_case_		(						self       )						->  Union[str, Any]:
							UpperCamelCase__         =	1
							UpperCamelCase__         =	np.array(
							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )

							self.distributed_retriever_check(
							    self.get_dummy_custom_hf_index_pytorch_retriever(init_retrieval=__lowerCAmelCase    ,      from_disk=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      )




					@require_ray
					def 	snake_case_		(						self       )						->  str:
							UpperCamelCase__         =	1
							UpperCamelCase__         =	np.array(
							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )

							self.distributed_retriever_check(
							    self.get_dummy_ray_distributed_retriever(init_retrieval=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )
							ray.shutdown()




					@require_ray
					def 	snake_case_		(						self       )						->  List[Any]:
							UpperCamelCase__         =	1
							UpperCamelCase__         =	np.array(
							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )
							with self.assertRaises(__lowerCAmelCase       ):
									self.distributed_retriever_check(
									    self.get_dummy_custom_hf_index_ray_retriever(init_retrieval=__lowerCAmelCase    ,      from_disk=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      )
							ray.shutdown()




					@require_ray
					def 	snake_case_		(						self       )						->  Union[str, Any]:
							UpperCamelCase__         =	1
							UpperCamelCase__         =	np.array(
							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )

							self.distributed_retriever_check(
							    self.get_dummy_custom_hf_index_ray_retriever(init_retrieval=__lowerCAmelCase    ,      from_disk=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )
							ray.shutdown()












def     a						(      _lowercase   :     List[str]       )     ->List[str]:
		UpperCamelCase__         =	[7_0_1, 3_0_1, 1_3_2, 5_7, 2_3, 1_0, 4, 1]
		for gap in gaps:
				for i in range(_lowercase ,						len(_lowercase       )       ):
						UpperCamelCase__         =	collection[i]
						UpperCamelCase__         =	i
						while j >= gap and collection[j - gap] > insert_value:
								UpperCamelCase__         =	collection[j - gap]
								j -= gap
						if j != i:
								UpperCamelCase__         =	insert_value
		return collection


if __name__ == "__main__":
				from doctest import testmod

				testmod()
				__lowerCAmelCase     =			input("Enter numbers separated by a comma:\n").strip()
				__lowerCAmelCase     =			[int(item) for item in user_input.split(",")]
				print(shell_sort(unsorted))





