





'''simple docstring'''



def  lowercase__(		_UpperCamelCase  : list				)->   list:






					"""simple docstring"""

					_UpperCamelCase											=   len(_UpperCamelCase				)

					# Set the gap value to be decreased by a factor of 1.3
					# after each iteration
					_UpperCamelCase											=   1.3

					# Continue sorting until the gap is 1
					while gap > 1:
										# Decrease the gap value
										_UpperCamelCase											=   int(gap / shrink				)

										# Sort the elements using insertion sort
										for i in range(_UpperCamelCase ,   len(_UpperCamelCase				)				):
															_UpperCamelCase											=   collection[i]
															_UpperCamelCase											=   i
															while j >= gap and collection[j - gap] > temp:
																				_UpperCamelCase											=   collection[j - gap]
																				j -= gap
															_UpperCamelCase											=   temp

					return collection


if __name__ == "__main__":
			import doctest

			doctest.testmod()










'''simple docstring'''



import gc
import unittest

import numpy as np
import torch
from transformers import CLIPTextConfig, CLIPTextModel, CLIPTextModelWithProjection, CLIPTokenizer

from diffusers import (
    AutoencoderKL,
    DiffusionPipeline,
    EulerDiscreteScheduler,
    StableDiffusionXLPipeline,
    UNetaDConditionModel,
)
from diffusers.utils import slow, torch_device
from diffusers.utils.testing_utils import enable_full_determinism, require_torch_gpu

from ..pipeline_params import TEXT_TO_IMAGE_BATCH_PARAMS, TEXT_TO_IMAGE_IMAGE_PARAMS, TEXT_TO_IMAGE_PARAMS
from ..test_pipelines_common import PipelineLatentTesterMixin, PipelineTesterMixin


enable_full_determinism()

class     A_ (  lowerCAmelCase_    ,			lowerCAmelCase_    ,			unittest.TestCase  ):

			'''simple docstring'''





			_lowerCAmelCase						=    StableDiffusionXLPipeline
			_lowerCAmelCase						=    TEXT_TO_IMAGE_PARAMS
			_lowerCAmelCase						=    TEXT_TO_IMAGE_BATCH_PARAMS
			_lowerCAmelCase						=    TEXT_TO_IMAGE_IMAGE_PARAMS
			_lowerCAmelCase						=    TEXT_TO_IMAGE_IMAGE_PARAMS




			def       a	(					self   ):
								torch.manual_seed(0   )
								_UpperCamelCase											=   UNetaDConditionModel(
								    block_out_channels=(32, 64)			,     layers_per_block=2			,     sample_size=32			,     in_channels=4			,     out_channels=4			,     down_block_types=("DownBlock2D", "CrossAttnDownBlock2D")			,     up_block_types=("CrossAttnUpBlock2D", "UpBlock2D")			,     attention_head_dim=(2, 4)			,     use_linear_projection=A_			,     addition_embed_type="text_time"			,     addition_time_embed_dim=8			,     transformer_layers_per_block=(1, 2)			,     projection_class_embeddings_input_dim=80			,     cross_attention_dim=64			,     )
								_UpperCamelCase											=   EulerDiscreteScheduler(
								    beta_start=0.0_0085			,     beta_end=0.012			,     steps_offset=1			,     beta_schedule="scaled_linear"			,     timestep_spacing="leading"			,     )
								torch.manual_seed(0   )
								_UpperCamelCase											=   AutoencoderKL(
								    block_out_channels=[32, 64]			,     in_channels=3			,     out_channels=3			,     down_block_types=["DownEncoderBlock2D", "DownEncoderBlock2D"]			,     up_block_types=["UpDecoderBlock2D", "UpDecoderBlock2D"]			,     latent_channels=4			,     sample_size=1_28			,     )
								torch.manual_seed(0   )
								_UpperCamelCase											=   CLIPTextConfig(
								    bos_token_id=0			,     eos_token_id=2			,     hidden_size=32			,     intermediate_size=37			,     layer_norm_eps=1e-0_5			,     num_attention_heads=4			,     num_hidden_layers=5			,     pad_token_id=1			,     vocab_size=10_00			,     hidden_act="gelu"			,     projection_dim=32			,     )
								_UpperCamelCase											=   CLIPTextModel(A_   )
								_UpperCamelCase											=   CLIPTokenizer.from_pretrained("hf-internal-testing/tiny-random-clip"			,     local_files_only=A_   )

								_UpperCamelCase											=   CLIPTextModelWithProjection(A_   )
								_UpperCamelCase											=   CLIPTokenizer.from_pretrained("hf-internal-testing/tiny-random-clip"			,     local_files_only=A_   )

								_UpperCamelCase											=   {
								    "unet": unet,
								    "scheduler": scheduler,
								    "vae": vae,
								    "text_encoder": text_encoder,
								    "tokenizer": tokenizer,
								    "text_encoder_2": text_encoder_a,
								    "tokenizer_2": tokenizer_a,
								    # "safety_checker": None,
								    # "feature_extractor": None,
								}
								return components




			def       a	(					self			,     A_			,     A_=0   ):
								if str(A_   ).startswith("mps"   ):
													_UpperCamelCase											=   torch.manual_seed(A_   )
								else:
													_UpperCamelCase											=   torch.Generator(device=A_   ).manual_seed(A_   )
								_UpperCamelCase											=   {
								    "prompt": "A painting of a squirrel eating a burger",
								    "generator": generator,
								    "num_inference_steps": 2,
								    "guidance_scale": 5.0,
								    "output_type": "numpy",
								}
								return inputs




			def       a	(					self   ):
								_UpperCamelCase											=   "cpu"  # ensure determinism for the device-dependent torch.Generator
								_UpperCamelCase											=   self.get_dummy_components()
								_UpperCamelCase											=   StableDiffusionXLPipeline(**A_   )
								_UpperCamelCase											=   sd_pipe.to(A_   )
								sd_pipe.set_progress_bar_config(disable=A_   )

								_UpperCamelCase											=   self.get_dummy_inputs(A_   )
								_UpperCamelCase											=   sd_pipe(**A_   ).images
								_UpperCamelCase											=   image[0, -3:, -3:, -1]

								assert image.shape == (1, 64, 64, 3)
								_UpperCamelCase											=   np.array([0.5873, 0.6128, 0.4797, 0.5122, 0.5674, 0.4639, 0.5227, 0.5149, 0.4747]   )

								assert np.abs(image_slice.flatten() - expected_slice   ).max() < 1e-2




			def       a	(					self   ):
								_UpperCamelCase											=   self.get_dummy_components()
								_UpperCamelCase											=   StableDiffusionXLPipeline(**A_   )
								_UpperCamelCase											=   sd_pipe.to(A_   )
								_UpperCamelCase											=   sd_pipe.to(A_   )
								sd_pipe.set_progress_bar_config(disable=A_   )

								# forward without prompt embeds
								_UpperCamelCase											=   self.get_dummy_inputs(A_   )
								_UpperCamelCase											=   3 * ["this is a negative prompt"]
								_UpperCamelCase											=   negative_prompt
								_UpperCamelCase											=   3 * [inputs["prompt"]]

								_UpperCamelCase											=   sd_pipe(**A_   )
								_UpperCamelCase											=   output.images[0, -3:, -3:, -1]

								# forward with prompt embeds
								_UpperCamelCase											=   self.get_dummy_inputs(A_   )
								_UpperCamelCase											=   3 * ["this is a negative prompt"]
								_UpperCamelCase											=   3 * [inputs.pop("prompt"   )]

								(
								    (
								    _UpperCamelCase
								)				,	(
								    _UpperCamelCase
								)				,	(
								    _UpperCamelCase
								)				,	(
								    _UpperCamelCase
								)				,	
								)											=   sd_pipe.encode_prompt(A_			,     negative_prompt=A_   )

								_UpperCamelCase											=   sd_pipe(
								    **A_			,     prompt_embeds=A_			,     negative_prompt_embeds=A_			,     pooled_prompt_embeds=A_			,     negative_pooled_prompt_embeds=A_			,     )
								_UpperCamelCase											=   output.images[0, -3:, -3:, -1]

								# make sure that it's equal
								assert np.abs(image_slice_a.flatten() - image_slice_a.flatten()   ).max() < 1e-4




			def       a	(					self   ):
								super().test_attention_slicing_forward_pass(expected_max_diff=3e-3   )




			def       a	(					self   ):
								super().test_inference_batch_single_identical(expected_max_diff=3e-3   )




@slow
@require_torch_gpu
class     A_ (  unittest.TestCase  ):

			'''simple docstring'''





			def       a	(					self   ):
								super().tearDown()
								gc.collect()
								torch.cuda.empty_cache()




			def       a	(					self			,     A_			,     A_="cpu"			,     A_=torch.floataa			,     A_=0   ):
								_UpperCamelCase											=   torch.Generator(device=A_   ).manual_seed(A_   )
								_UpperCamelCase											=   np.random.RandomState(A_   ).standard_normal((1, 4, 64, 64)   )
								_UpperCamelCase											=   torch.from_numpy(A_   ).to(device=A_			,     dtype=A_   )
								_UpperCamelCase											=   {
								    "prompt": "a photograph of an astronaut riding a horse",
								    "latents": latents,
								    "generator": generator,
								    "num_inference_steps": 3,
								    "guidance_scale": 7.5,
								    "output_type": "numpy",
								}
								return inputs




			def       a	(					self   ):
								_UpperCamelCase											=   DiffusionPipeline.from_pretrained("stabilityai/stable-diffusion-2-base"   )
								pipe.to(A_   )
								pipe.set_progress_bar_config(disable=A_   )

								_UpperCamelCase											=   self.get_inputs(A_   )
								_UpperCamelCase											=   pipe(**A_   ).images
								_UpperCamelCase											=   image[0, -3:, -3:, -1].flatten()

								assert image.shape == (1, 5_12, 5_12, 3)
								_UpperCamelCase											=   np.array([0.4_9493, 0.4_7896, 0.4_0798, 0.5_4214, 0.5_3212, 0.4_8202, 0.4_7656, 0.4_6329, 0.4_8506]   )
								assert np.abs(image_slice - expected_slice   ).max() < 7e-3



