


'''simple docstring'''





class     UpperCamelCase:


					def __init__(						self	:		List[str]     ,    SCREAMING_SNAKE_CASE	:		Optional[int]						)			->	Union[str, Any]:




											'''simple docstring'''

											__snake_case				=		val
											__snake_case				=		None
											__snake_case				=		None






					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[int]     ,    SCREAMING_SNAKE_CASE	:		List[Any]						)			->	Tuple:




											'''simple docstring'''

											if self.val:
																	if val < self.val:
																							if self.left is None:
																													__snake_case				=		Node(SCREAMING_SNAKE_CASE						)
																							else:
																													self.left.insert(SCREAMING_SNAKE_CASE						)
																	elif val > self.val:
																							if self.right is None:
																													__snake_case				=		Node(SCREAMING_SNAKE_CASE						)
																							else:
																													self.right.insert(SCREAMING_SNAKE_CASE						)
											else:
																	__snake_case				=		val





def 	_lowerCAmelCase       (    _lowerCAmelCase      ,	_lowerCAmelCase )						->	List[str]:


						'''simple docstring'''






						if root:
												inorder(root.left      ,	_lowerCAmelCase )
												res.append(root.val )
												inorder(root.right      ,	_lowerCAmelCase )





def 	_lowerCAmelCase       (    _lowerCAmelCase )						->	Tuple:


						'''simple docstring'''






						if len(_lowerCAmelCase ) == 0:
												return arr
						__snake_case				=		Node(arr[0] )
						for i in range(1      ,	len(_lowerCAmelCase ) ):
												root.insert(arr[i] )
						# Traverse BST in order.
						__snake_case				=		[]
						inorder(_lowerCAmelCase      ,	_lowerCAmelCase )
						return res


if __name__ == "__main__":
	print(tree_sort([10, 1, 3, 2, 9, 14, 13]))









import gc
import random
import tempfile
import unittest

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

from diffusers import AutoencoderKL, DDIMScheduler, LMSDiscreteScheduler, PNDMScheduler, UNetaDConditionModel
from diffusers.pipelines.stable_diffusion_safe import StableDiffusionPipelineSafe as StableDiffusionPipeline
from diffusers.utils import floats_tensor, nightly, torch_device
from diffusers.utils.testing_utils import require_torch_gpu






class     UpperCamelCase(  unittest.TestCase   ):


					def 							SCREAMING_SNAKE_CASE_  (						self	:		str						)			->	Dict:




											'''simple docstring'''

											super().tearDown()
											gc.collect()
											torch.cuda.empty_cache()


					@property
					def 							SCREAMING_SNAKE_CASE_  (						self	:		Tuple						)			->	Optional[Any]:




											'''simple docstring'''

											__snake_case				=		1
											__snake_case				=		3
											__snake_case				=		(3_2, 3_2)

											__snake_case				=		floats_tensor((batch_size, num_channels) + sizes     ,    rng=random.Random(0						)						).to(SCREAMING_SNAKE_CASE						)
											return image


					@property
					def 							SCREAMING_SNAKE_CASE_  (						self	:		int						)			->	Any:




											'''simple docstring'''

											torch.manual_seed(0						)
											__snake_case				=		UNetaDConditionModel(
											    block_out_channels=(3_2, 6_4)     ,    layers_per_block=2     ,    sample_size=3_2     ,    in_channels=4     ,    out_channels=4     ,    down_block_types=("DownBlock2D", "CrossAttnDownBlock2D")     ,    up_block_types=("CrossAttnUpBlock2D", "UpBlock2D")     ,    cross_attention_dim=3_2     ,    )
											return model


					@property
					def 							SCREAMING_SNAKE_CASE_  (						self	:		Any						)			->	str:




											'''simple docstring'''

											torch.manual_seed(0						)
											__snake_case				=		AutoencoderKL(
											    block_out_channels=[3_2, 6_4]     ,    in_channels=3     ,    out_channels=3     ,    down_block_types=["DownEncoderBlock2D", "DownEncoderBlock2D"]     ,    up_block_types=["UpDecoderBlock2D", "UpDecoderBlock2D"]     ,    latent_channels=4     ,    )
											return model


					@property
					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[str]						)			->	int:




											'''simple docstring'''

											torch.manual_seed(0						)
											__snake_case				=		CLIPTextConfig(
											    bos_token_id=0     ,    eos_token_id=2     ,    hidden_size=3_2     ,    intermediate_size=3_7     ,    layer_norm_eps=1e-0_5     ,    num_attention_heads=4     ,    num_hidden_layers=5     ,    pad_token_id=1     ,    vocab_size=1_0_0_0     ,    )
											return CLIPTextModel(SCREAMING_SNAKE_CASE						)


					@property
					def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[Any]						)			->	str:




											'''simple docstring'''

											def extract(*SCREAMING_SNAKE_CASE	:		List[str]     ,    **SCREAMING_SNAKE_CASE	:		List[Any]						):






																	class     UpperCamelCase:


																						def __init__(						self	:		Dict						)			->	Union[str, Any]:




																												'''simple docstring'''

																												__snake_case				=		torch.ones([0]						)






																						def 							SCREAMING_SNAKE_CASE_  (						self	:		Optional[Any]     ,    SCREAMING_SNAKE_CASE	:		Optional[Any]						)			->	List[Any]:




																												'''simple docstring'''

																												self.pixel_values.to(SCREAMING_SNAKE_CASE						)
																												return self




																	return Out()

											return extract


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Dict						)			->	Dict:




											'''simple docstring'''

											__snake_case				=		"cpu"  # ensure determinism for the device-dependent torch.Generator
											__snake_case				=		self.dummy_cond_unet
											__snake_case				=		DDIMScheduler(
											    beta_start=0.00085     ,    beta_end=0.012     ,    beta_schedule="scaled_linear"     ,    clip_sample=SCREAMING_SNAKE_CASE     ,    set_alpha_to_one=SCREAMING_SNAKE_CASE     ,    )

											__snake_case				=		self.dummy_vae
											__snake_case				=		self.dummy_text_encoder
											__snake_case				=		CLIPTokenizer.from_pretrained("hf-internal-testing/tiny-random-clip"						)

											# make sure here that pndm scheduler skips prk
											__snake_case				=		StableDiffusionPipeline(
											    unet=SCREAMING_SNAKE_CASE     ,    scheduler=SCREAMING_SNAKE_CASE     ,    vae=SCREAMING_SNAKE_CASE     ,    text_encoder=SCREAMING_SNAKE_CASE     ,    tokenizer=SCREAMING_SNAKE_CASE     ,    safety_checker=SCREAMING_SNAKE_CASE     ,    feature_extractor=self.dummy_extractor     ,    )
											__snake_case				=		sd_pipe.to(SCREAMING_SNAKE_CASE						)
											sd_pipe.set_progress_bar_config(disable=SCREAMING_SNAKE_CASE						)

											__snake_case				=		"A painting of a squirrel eating a burger"

											__snake_case				=		torch.Generator(device=SCREAMING_SNAKE_CASE						).manual_seed(0						)
											__snake_case				=		sd_pipe([prompt]     ,    generator=SCREAMING_SNAKE_CASE     ,    guidance_scale=6.0     ,    num_inference_steps=2     ,    output_type="np"						)
											__snake_case				=		output.images

											__snake_case				=		torch.Generator(device=SCREAMING_SNAKE_CASE						).manual_seed(0						)
											__snake_case				=		sd_pipe(
											    [prompt]     ,    generator=SCREAMING_SNAKE_CASE     ,    guidance_scale=6.0     ,    num_inference_steps=2     ,    output_type="np"     ,    return_dict=SCREAMING_SNAKE_CASE     ,    )[0]

											__snake_case				=		image[0, -3:, -3:, -1]
											__snake_case				=		image_from_tuple[0, -3:, -3:, -1]

											assert image.shape == (1, 6_4, 6_4, 3)
											__snake_case				=		np.array([0.5756, 0.6118, 0.5005, 0.5041, 0.5471, 0.4726, 0.4976, 0.4865, 0.4864]						)

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Any						)			->	Tuple:




											'''simple docstring'''

											__snake_case				=		"cpu"  # ensure determinism for the device-dependent torch.Generator
											__snake_case				=		self.dummy_cond_unet
											__snake_case				=		PNDMScheduler(skip_prk_steps=SCREAMING_SNAKE_CASE						)
											__snake_case				=		self.dummy_vae
											__snake_case				=		self.dummy_text_encoder
											__snake_case				=		CLIPTokenizer.from_pretrained("hf-internal-testing/tiny-random-clip"						)

											# make sure here that pndm scheduler skips prk
											__snake_case				=		StableDiffusionPipeline(
											    unet=SCREAMING_SNAKE_CASE     ,    scheduler=SCREAMING_SNAKE_CASE     ,    vae=SCREAMING_SNAKE_CASE     ,    text_encoder=SCREAMING_SNAKE_CASE     ,    tokenizer=SCREAMING_SNAKE_CASE     ,    safety_checker=SCREAMING_SNAKE_CASE     ,    feature_extractor=self.dummy_extractor     ,    )
											__snake_case				=		sd_pipe.to(SCREAMING_SNAKE_CASE						)
											sd_pipe.set_progress_bar_config(disable=SCREAMING_SNAKE_CASE						)

											__snake_case				=		"A painting of a squirrel eating a burger"
											__snake_case				=		torch.Generator(device=SCREAMING_SNAKE_CASE						).manual_seed(0						)
											__snake_case				=		sd_pipe([prompt]     ,    generator=SCREAMING_SNAKE_CASE     ,    guidance_scale=6.0     ,    num_inference_steps=2     ,    output_type="np"						)

											__snake_case				=		output.images

											__snake_case				=		torch.Generator(device=SCREAMING_SNAKE_CASE						).manual_seed(0						)
											__snake_case				=		sd_pipe(
											    [prompt]     ,    generator=SCREAMING_SNAKE_CASE     ,    guidance_scale=6.0     ,    num_inference_steps=2     ,    output_type="np"     ,    return_dict=SCREAMING_SNAKE_CASE     ,    )[0]

											__snake_case				=		image[0, -3:, -3:, -1]
											__snake_case				=		image_from_tuple[0, -3:, -3:, -1]

											assert image.shape == (1, 6_4, 6_4, 3)
											__snake_case				=		np.array([0.5125, 0.5716, 0.4828, 0.5060, 0.5650, 0.4768, 0.5185, 0.4895, 0.4993]						)

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[str]						)			->	List[Any]:




											'''simple docstring'''

											__snake_case				=		StableDiffusionPipeline.from_pretrained(
											    "hf-internal-testing/tiny-stable-diffusion-lms-pipe"     ,    safety_checker=SCREAMING_SNAKE_CASE						)
											assert isinstance(SCREAMING_SNAKE_CASE     ,    SCREAMING_SNAKE_CASE						)
											assert isinstance(pipe.scheduler     ,    SCREAMING_SNAKE_CASE						)
											assert pipe.safety_checker is None

											__snake_case				=		pipe("example prompt"     ,    num_inference_steps=2						).images[0]
											assert image is not None

											# check that there's no error when saving a pipeline with one of the models being None
											with tempfile.TemporaryDirectory() as tmpdirname:
																	pipe.save_pretrained(SCREAMING_SNAKE_CASE						)
																	__snake_case				=		StableDiffusionPipeline.from_pretrained(SCREAMING_SNAKE_CASE						)

											# sanity check that the pipeline still works
											assert pipe.safety_checker is None
											__snake_case				=		pipe("example prompt"     ,    num_inference_steps=2						).images[0]
											assert image is not None






					@unittest.skipIf(torch_device != "cuda"     ,    "This test requires a GPU"						)
					def 							SCREAMING_SNAKE_CASE_  (						self	:		Union[str, Any]						)			->	int:




											'''simple docstring'''

											__snake_case				=		self.dummy_cond_unet
											__snake_case				=		PNDMScheduler(skip_prk_steps=SCREAMING_SNAKE_CASE						)
											__snake_case				=		self.dummy_vae
											__snake_case				=		self.dummy_text_encoder
											__snake_case				=		CLIPTokenizer.from_pretrained("hf-internal-testing/tiny-random-clip"						)

											# put models in fp16
											__snake_case				=		unet.half()
											__snake_case				=		vae.half()
											__snake_case				=		bert.half()

											# make sure here that pndm scheduler skips prk
											__snake_case				=		StableDiffusionPipeline(
											    unet=SCREAMING_SNAKE_CASE     ,    scheduler=SCREAMING_SNAKE_CASE     ,    vae=SCREAMING_SNAKE_CASE     ,    text_encoder=SCREAMING_SNAKE_CASE     ,    tokenizer=SCREAMING_SNAKE_CASE     ,    safety_checker=SCREAMING_SNAKE_CASE     ,    feature_extractor=self.dummy_extractor     ,    )
											__snake_case				=		sd_pipe.to(SCREAMING_SNAKE_CASE						)
											sd_pipe.set_progress_bar_config(disable=SCREAMING_SNAKE_CASE						)

											__snake_case				=		"A painting of a squirrel eating a burger"
											__snake_case				=		sd_pipe([prompt]     ,    num_inference_steps=2     ,    output_type="np"						).images

											assert image.shape == (1, 6_4, 6_4, 3)






@nightly
@require_torch_gpu
class     UpperCamelCase(  unittest.TestCase   ):


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[str]						)			->	Tuple:




											'''simple docstring'''

											super().tearDown()
											gc.collect()
											torch.cuda.empty_cache()


					def 							SCREAMING_SNAKE_CASE_  (						self	:		List[Any]						)			->	Optional[Any]:




											'''simple docstring'''

											__snake_case				=		StableDiffusionPipeline.from_pretrained("runwayml/stable-diffusion-v1-5"     ,    safety_checker=SCREAMING_SNAKE_CASE						)
											__snake_case				=		LMSDiscreteScheduler.from_config(sd_pipe.scheduler.config						)
											__snake_case				=		sd_pipe.to(SCREAMING_SNAKE_CASE						)
											sd_pipe.set_progress_bar_config(disable=SCREAMING_SNAKE_CASE						)

											__snake_case				=		(
											    "portrait of girl with smokey eyes makeup in abandoned hotel, grange clothes, redshift, wide high angle"
											    " coloured polaroid photograph with flash, kodak film, hyper real, stunning moody cinematography, with"
											    " anamorphic lenses, by maripol, fallen angels by wong kar - wai, style of suspiria and neon demon and"
											    " children from bahnhof zoo, detailed "
											)
											__snake_case				=		4_0_0_3_6_6_0_3_4_6
											__snake_case				=		7

											# without safety guidance (sld_guidance_scale = 0)
											__snake_case				=		torch.manual_seed(SCREAMING_SNAKE_CASE						)
											__snake_case				=		sd_pipe(
											    [prompt]     ,    generator=SCREAMING_SNAKE_CASE     ,    guidance_scale=SCREAMING_SNAKE_CASE     ,    num_inference_steps=5_0     ,    output_type="np"     ,    width=5_1_2     ,    height=5_1_2     ,    sld_guidance_scale=0     ,    )

											__snake_case				=		output.images
											__snake_case				=		image[0, -3:, -3:, -1]
											__snake_case				=		[0.2278, 0.2231, 0.2249, 0.2333, 0.2303, 0.1885, 0.2273, 0.2144, 0.2176]

											assert image.shape == (1, 5_1_2, 5_1_2, 3)

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

											# without safety guidance (strong configuration)
											__snake_case				=		torch.manual_seed(SCREAMING_SNAKE_CASE						)
											__snake_case				=		sd_pipe(
											    [prompt]     ,    generator=SCREAMING_SNAKE_CASE     ,    guidance_scale=SCREAMING_SNAKE_CASE     ,    num_inference_steps=5_0     ,    output_type="np"     ,    width=5_1_2     ,    height=5_1_2     ,    sld_guidance_scale=2_0_0_0     ,    sld_warmup_steps=7     ,    sld_threshold=0.025     ,    sld_momentum_scale=0.5     ,    sld_mom_beta=0.7     ,    )

											__snake_case				=		output.images
											__snake_case				=		image[0, -3:, -3:, -1]
											__snake_case				=		[0.2383, 0.2276, 0.236, 0.2192, 0.2186, 0.2053, 0.1971, 0.1901, 0.1719]

											assert image.shape == (1, 5_1_2, 5_1_2, 3)

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


					def 							SCREAMING_SNAKE_CASE_  (						self	:		Tuple						)			->	List[str]:




											'''simple docstring'''

											__snake_case				=		StableDiffusionPipeline.from_pretrained("runwayml/stable-diffusion-v1-5"     ,    safety_checker=SCREAMING_SNAKE_CASE						)
											__snake_case				=		LMSDiscreteScheduler.from_config(sd_pipe.scheduler.config						)
											__snake_case				=		sd_pipe.to(SCREAMING_SNAKE_CASE						)
											sd_pipe.set_progress_bar_config(disable=SCREAMING_SNAKE_CASE						)

											__snake_case				=		"padme amidala taking a bath artwork, safe for work, no nudity"
											__snake_case				=		2_7_3_4_9_7_1_7_5_5
											__snake_case				=		7

											__snake_case				=		torch.manual_seed(SCREAMING_SNAKE_CASE						)
											__snake_case				=		sd_pipe(
											    [prompt]     ,    generator=SCREAMING_SNAKE_CASE     ,    guidance_scale=SCREAMING_SNAKE_CASE     ,    num_inference_steps=5_0     ,    output_type="np"     ,    width=5_1_2     ,    height=5_1_2     ,    sld_guidance_scale=0     ,    )

											__snake_case				=		output.images
											__snake_case				=		image[0, -3:, -3:, -1]
											__snake_case				=		[0.3502, 0.3622, 0.3396, 0.3642, 0.3478, 0.3318, 0.35, 0.3348, 0.3297]

											assert image.shape == (1, 5_1_2, 5_1_2, 3)

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

											__snake_case				=		torch.manual_seed(SCREAMING_SNAKE_CASE						)
											__snake_case				=		sd_pipe(
											    [prompt]     ,    generator=SCREAMING_SNAKE_CASE     ,    guidance_scale=SCREAMING_SNAKE_CASE     ,    num_inference_steps=5_0     ,    output_type="np"     ,    width=5_1_2     ,    height=5_1_2     ,    sld_guidance_scale=2_0_0_0     ,    sld_warmup_steps=7     ,    sld_threshold=0.025     ,    sld_momentum_scale=0.5     ,    sld_mom_beta=0.7     ,    )

											__snake_case				=		output.images
											__snake_case				=		image[0, -3:, -3:, -1]
											__snake_case				=		[0.5531, 0.5206, 0.4895, 0.5156, 0.5182, 0.4751, 0.4802, 0.4803, 0.4443]

											assert image.shape == (1, 5_1_2, 5_1_2, 3)

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






					def 							SCREAMING_SNAKE_CASE_  (						self	:		Dict						)			->	int:




											'''simple docstring'''

											__snake_case				=		StableDiffusionPipeline.from_pretrained("runwayml/stable-diffusion-v1-5"						)
											__snake_case				=		sd_pipe.to(SCREAMING_SNAKE_CASE						)
											sd_pipe.set_progress_bar_config(disable=SCREAMING_SNAKE_CASE						)

											__snake_case				=		(
											    "the four horsewomen of the apocalypse, painting by tom of finland, gaston bussiere, craig mullins, j. c."
											    " leyendecker"
											)
											__snake_case				=		1_0_4_4_3_5_5_2_3_4
											__snake_case				=		1_2

											__snake_case				=		torch.manual_seed(SCREAMING_SNAKE_CASE						)
											__snake_case				=		sd_pipe(
											    [prompt]     ,    generator=SCREAMING_SNAKE_CASE     ,    guidance_scale=SCREAMING_SNAKE_CASE     ,    num_inference_steps=5_0     ,    output_type="np"     ,    width=5_1_2     ,    height=5_1_2     ,    sld_guidance_scale=0     ,    )

											__snake_case				=		output.images
											__snake_case				=		image[0, -3:, -3:, -1]
											__snake_case				=		np.array([0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]						)

											assert image.shape == (1, 5_1_2, 5_1_2, 3)

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

											__snake_case				=		torch.manual_seed(SCREAMING_SNAKE_CASE						)
											__snake_case				=		sd_pipe(
											    [prompt]     ,    generator=SCREAMING_SNAKE_CASE     ,    guidance_scale=SCREAMING_SNAKE_CASE     ,    num_inference_steps=5_0     ,    output_type="np"     ,    width=5_1_2     ,    height=5_1_2     ,    sld_guidance_scale=2_0_0_0     ,    sld_warmup_steps=7     ,    sld_threshold=0.025     ,    sld_momentum_scale=0.5     ,    sld_mom_beta=0.7     ,    )

											__snake_case				=		output.images
											__snake_case				=		image[0, -3:, -3:, -1]
											__snake_case				=		np.array([0.5818, 0.6285, 0.6835, 0.6019, 0.625, 0.6754, 0.6096, 0.6334, 0.6561]						)
											assert image.shape == (1, 5_1_2, 5_1_2, 3)

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





